Book : Concept of Programming Languages(tenth edition)

By : Robert W. Sebesta

Review Question

1. What are the three primary uses of symbolic logic in formal logic?
– Express propositions
– Express relationships between propositions
– Describe how new propositions can be inferred from other propositions

2. What are the two parts of a compound term?
– Functor: function symbol that names the relationship
– Ordered list of parameters (tuple)

3. What are the two modes in which a proposition can be stated?
Fact and query.

4. What is the general form of a proposition in clausal form?
B1 u B2 u … u Bn c A1 n A2 n … n Am
means if all the As are true, then at least one B is true

5. What are antecedents? Consequents?
Antecedents are right side of a clausal form proposition. Consequent is left side of a clausal form propositions

6. Give general definitions of resolution and unification
– Resolution : inference rule that allows inferred propositions to be computed from given propositions, thus providing a method with potential application to automatic theorem proving.
– Unification : Process of determining useful values for variables.

7. What are the forms of Horn clauses?
Headed and headless.

9. What does it mean for a language to be nonprocedural?
Programs do not state now a result is to be computed, but rather the form of the result.


Problem Set

2. Describe how a multiple-processor machine could be used to implement resolution. Could Prolog, as currently defined, use this method?
On a single processor machine, the resolution process takes place on the rule base, one rule at a time, starting with the first rule, and progressing toward the last until a match is found.  Because the process on each rule is independent of the process on the other rules, separate processors could concurrently operate on separate rules.  When any of the processors finds a match, all resolution processing could terminate.

9. From a book on Prolog, learn and write a description of a monkey-banana prolem. Why does Prolog allow this problem to exist in its implementation ?
The problem is defined as this : a monkey is in a room. Suspended from the ceiling is a bunch of bananas, beyond the monkey’s reach. However, in the room there are also a chair and a stick. The ceiling is just the right height so that a monkey standing on a chair could knock the bananas down with the stick. The monkey knows how to move around, carry other things around, reach for the bananas, and wave a stick in the air. What is the best sequence of actions for the monkey?
It exists to create a variation in output of Prolog. As Prolog is an AI programming language, a variation might be needed in AI output to make them respond relevant to the situation.

10.  Using the internet for reference, find some of the applications of expert systems.

• Expert system in healthcare: The Electronic health record (EHR) is designed to replace the traditional medical and bring together a more versatile, expansive and robust expert system to provide greater quality care.

• Expert systems in the financial field: Loan departments are interested in expert systems for morgages because of the growing cost of labour, which makes the handling and acceptance of relatively small loans less profitable.

• A new application for expert systems is automated computer program generation. Funded by a US Air Force grant, an expert system-based application (hprcARCHITECT) that generates computer programs for mixed processor technology (FPGA/GPU/Multicore) systems without a need for technical specialists has recently been commercially introduced.


Book : Concept of Programming Languages(tenth edition)

By : Robert W. Sebesta

Review Question

2. What does a lambda expression specify?
The predicate function is often given as a lambda expression, which in ML is defined exactly like a function, except with the fn reserved word, instead of fun, and of course the lambda expression is nameless.

5. Explain why QUOTE is needed for a parameter that is a data list.
To avoid evaluating a parameter, it is first given as a parameter to the primitive function QUOTE, which simply returns it without change.

6. What is a simple list?
A list which membership of a given atom in a given list that does not include sublists.

7. What does the abbreviation REPL stand for?
REPL stand for read-evaluate-print loop.

11. What are the two forms of DEFINE?
The simplest form of DEFINE is one used to bind a name to the value of an expression. This form is
(DEFINE symbol expression)
The general form of such a DEFINE is
(DEFINE (function_name parameters)

13. Why are CAR and CDR so named?
The names of the CAR and CDR functions are peculiar at best. The origin of these names lies in the first implementation of LISP, which was on an IBM 704 computer. The 704’s memory words had two fields, named decrement and address, that were used in various operand addressing strategies. Each of
these fields could store a machine memory address. The 704 also included two machine instructions, also named CAR (contents of the address part of a register) and CDR (contents of the decrement part of a register), that extracted the associated fields. It was natural to use the two fields to store the two pointers
of a list node so that a memory word could neatly store a node. Using these conventions, the CAR and CDR instructions of the 704 provided efficient list selectors. The names carried over into the primitives of all dialects of LISP.

18. What is tail recursion? Why is it important to define functions that use recursion to specify repetition to be tail recursive?
A function is tail recursive if its recursive call is the last operation in the function. This means that the return value of the recursive call is the return value of the nonrecursive call to the function. It is important to specify repetition to be tail recursive because it is more efficient(increase the efficiency).

19. Why were imperative features added to most dialects of LISP?
LISP began as a pure functional language but soon acquired some important imperative features to increased its execution efficiency.

26. What is type inferencing, as used in ML?
Type inference refers to the automatic deduction of the type of an expression in a programming language. If some, but not all, type annotations are already present it is referred to as type reconstruction.

29. What is a curried function?
Curried functions a function which a new functions can be constructed from them by partial evaluation.

30. What does partial evaluation mean?
Partial evaluation means that the function is evaluated with actual parameters for one or more of the leftmost formal parameters.

32. What is the use of the evaluation environment table?
A table called the evaluation environment stores the names of all implicitly and explicitly declared identifiers in a program, along with their types. This is like a run-time symbol table.

33. Explain the process of currying.
The process of currying replaces a function with more than one parameter with a function with one parameter that returns a function that takes the other parameters of the initial function.


Problem Set

2.  Give the general form of function declaration in ML.

Function declarations in ML appear in the general form
fun function_name( formal parameters ) = expression;

8. How is the functional operator pipeline ( |> ) used in F#?
The pipeline operator is a binary operator that sends the value of its left operand, which is an expression, to the last parameter of the function call, which is the right operand. It is used to chain together function calls while flowing the data being processed to each call.

9. What does  the following Scheme function do?
(define ( y s lis)
(( null? lis) ‘ () )
((equal? s (car lis)) lis)
(else (y s (cdr lis)))
y returns the given list with leading elements removed up to but not including the first occurrence of the first given parameter.

10.What does  the following Scheme function do?
(define ( x lis)
(( null? lis) 0 )
(( not(list? (car lis)))
((eq? (car lis) #f) (x (cdr lis)))
(else (+1 (x (cdr lis))))))
(else (+ (x (car lis))  (x (cdr lis))))
x returns the number of non-#f atoms in the given list.


Book : Concept of Programming Languages(tenth edition)

By : Robert W. Sebesta

Review Question

2. When is an exception thrown or raised?

An exception is raised when its associated event occurs.

6 . What is exception propagation in Ada?

Exception propagation allows an exception raised in one program unit to be handled in some other unit in its dynamic or static ancestry. This allows a single exception handler to be used for any number of different program units. This reuse can result in significant savings in development cost, program size, and program complexity.

9. What is the scope of exception handlers in Ada?

Exception handlers can be included in blocks or in the bodies of subprograms, packages, or tasks.

10. What are the four exceptions defined in the Standard package of Ada?

There are four exceptions that are defined in the default package, Standard:

Constraint_aError, Program_Error, Storage_Error, Tasking_Error.

11. are they any predefined exceptions in Ada?

Yes, they are.

12. What is the use of Suppress pragma in Ada?

The suppress pragma is used to disable certain run-time checks that

are parts of the built-in exceptions in Ada.

14. What is the name of all C++ exception handlers?

Try clause.

30. In which version were assertions added to Java?

Assertions were added to Java in version 1.4.

31. What is the use of the assert statement?

The assert statement is used for defensive programming. A program may be written with many assert statements, which ensure that the program’s computation is on track to produce correct results.

32. What is event-driven programming?

Event-driven programming is a programming where parts of the program are executed at completely unpredictable times, often triggered by user interactions with the executing program.

33. What is the purpose of a Java JFrame?

The JFrame class defines the data and methods that are needed for frames. So, a class that uses a frame can be a subclass of JFrame. A JFrame has several layers, called panes.

34. What are the different forms of assert statement?

There are two possible forms of the assert statement:

assert condition;

assert condition : expression;


Problem Set

1. What mechanism did early programming languages provide to detect or attempt to deal with errors?

Early programming languages were designed and implemented in such a way that the user program could neither detect nor attempt to deal with such errors. In these languages, the occurrence of such an error simply causes the program to be terminated and control to be transferred to the operating system.

2. Describe the approach for the detection of subscript range errors used in C and Java.

In C subscript ranges are not checked. Java compilers usually generate code to check the correctness of every subscript expression. If any exception generates, then an unchecked exception is thrown.

6. In languages without exception-handling facilities, it is common to have most subprograms include an “error” parameter, which can be set to some values representing “OK” or some other value representing “error in procedure”. What advantage does a linguistic exception-handling facility like that of Ada have over this method?

There are several advantages of a linguistic mechanism for handling exceptions, such as that found in Ada, over simply using a flag error parameter in all subprograms. One advantage is that the code to test the flag after every call is eliminated. Such testing makes programs longer and harder to read. Another advantage is that exceptions can be propagated farther than one level of control in a uniform and implicit way. Finally, there is the advantage that all programs use a uniform method for dealing with unusual circumstances, leading to enhanced readability.

7. In languages without exception-handling facilities, we could send an error-handling procedure as parameter to each procedure that can detect errors than must be handled. What disadvantage are there to this method?

There are several disadvantages of sending error handling subprograms to other subprograms. One is that it may be necessary to send several error handlers to some subprograms, greatly complicating both the writing and execution of calls. Another is that there is no method of propagating exceptions, meaning that they must all be handled locally. This complicates exception handling, because it requires more attention to handling in more places.

14. Summarize the arguments in favor of the termination and resumption models of continuation.

The resumption model is useful when the exception is only an unusual condition, rather than an error. The termination model is useful when the exception is an error and it is highly unlikely that the error can be corrected so that execution could continue in some useful way.


Book : Concept of Programming Languages(tenth edition)

By : Robert W. Sebesta

Review Question

1. What are the three possible levels of concurrency in programs?

– Instruction level (executing two or more machine instructions simultaneously)

– Statement level (executing two or more high-level language statements simultaneously)

– Unit level (executing two or more subprogram units simultaneously).

7. What is the difference between physical and logical concurrency?

Physical concurrency is several program units from the same program that literally execute simultaneously.

Logical concurrency is multiple processors providing actual concurrency, when in fact the actual execution of programs is taking place in interleaved fashion on a single processor.

8. What is the work of a scheduler?

Scheduler manages the sharing of processors among the tasks.

12. What is a heavyweight task? What is a lightweight task?

Heavyweight task executes in its own address space. Lightweight task all run in the same address space.

16. What is a task descriptor?

Task descriptor is a data structure that stores all of the relevant information about the execution state of a task.

18. What is the purpose of a task-ready queue?

The purpose of a task-ready queue is to be storage of tasks that are ready to run.

21. What is a binary semaphore? What is a counting semaphore?

Binary semaphore is a semaphore that requires only a binary-valued counter, like the one used to provide competition synchronization. A counting semaphore is a synchronization object that can have an arbitrarily large number of states.

30. What is purpose of an Ada terminate clause?

The purpose of an Ada terminate clause is to mark that the task is finished with its job but is not yet terminated.

34. What does the Java sleep method do?

Sleep method blocks the the thread.

35. What does the Java yield method do?

Yield method surrenders the processor voluntarily as a request from the running thread.

36. What does the Java join method do?

Java forces a method to delay its execution until the run method of another thread has completed its execution.

37. What does the Java interrupt method do?

Interrupt becomes one way to communicate to a thread that it should stop.

55. What is Concurrent ML?

Concurrent ML is an extension to ML that includes a fform of threads and a form of synchronous message passing to support concurrency.

56. What is the use of the spawn primitive of CML?

The use of Spawn primitive of CML is to create a thread.

57. What is the use of subprograms BeginInvoke and EndInvoke in F#?

The use of subprograms BeginInvoke and Endinvoke in F# is to call threads asynchronously.

58. What is the use of the DISTRIBUTE and ALIGN specification of HPC?

The use of DISTRIBUTE and ALIGN specification of HPC is to provide information to the compiler on machines that do not share memory, that is, each processor has its own memory.


Problem Set

1. Explain clearly why a race condition can create problems for a system.

Because two or more tasks are racing to use the shared resource and the behavior of the program depends on which task arrives first (and wins the race). The importance of competition synchronization should now be clear.

2. What are the different ways to handle deadlock?

– Ignoring deadlock

– Detection

– Prevention

– Avoidance

3. Busy waiting is a method whereby a task waits for a given event by continuously checking for that event to occur. What is the main problem with this approach?

Busy-waiting or spinning is a technique in which a process repeatedly checks to see if a condition is true, such as whether keyboard input or a lock is available. Spinning can also be used to generate an arbitrary time delay, a technique that was necessary on systems that lacked a method of waiting a specific length of time. Processor speeds vary greatly from computer to computer, especially as some processors are designed to dynamically adjust speed based on external factors, such as the load on the operating system. Busy waiting may loop forever and it may cause a computer freezing.


Book : Concept of Programming Languages(tenth edition)

By : Robert W. Sebesta

Review Question

1. Name two functional languages that support object-oriented programming.

C++ and Python.

2. What are the problems associated with programming using abstract data types?

-In nearly all cases, the features and capabilities of the existing type are not quite right for the new use.

-The type definitions are all independent and are at the same level.

4. What is message protocol?
The entire collection of methods of an object is called the message protocol, or message interface, of the object.

5. What is an overriding method?
An overriding method is a method that provide an operation in the subclass that is similar to one in the parent class, but is customized for objects of the subclass. For example, a parent class, Bird, might have a draw method that draws a generic bird. A subclass of Bird named Waterfowl could override the draw method inherited from Bird to draw a generic waterfowl, perhaps a duck.

7. What is dynamic dispatch?
Dynamic dispatch is the third characteristic (after abstract data types and inheritance) of object-oriented programming language which is a kind of polymorhphism provided by the dynamic binding of messages to method definitions.

8. What is an abstract method? What is an abstract class?
For example, suppose a program defined a Building class and a collection of subclasses for specific types of buildings, for instance, French_Gothic. It probably would not make sense to have an implemented draw method in Building. But because all of its descendant classes should have such an implemented method, the protocol (but not the body) of that method is included in Building. Such a method is often called an abstract method ( pure virtual method in C++). A class that includes at least one abstract method is called an abstract class (abstract base class in C++).

10. What is an inner class?
Inner classes are non-static classes that are nested directly in another class.

12. From where are Smalltalk objects allocated?
Smalltalk objects are allocated from the heap and are referenced through reference variables, which are implicitly dereferenced.

15. What kind of inheritance, single or multiple, does Smalltalk support?
Smalltalk supports single inheritance; it does not allow multiple inheritance.

19. How are C++ heap-allocated objects deallocated?
C++ heap-allocated objects are deallocated using destructor.

29. Does Objective-C support multiple inheritance?
No Objective-C doesn’t support it. (It supports only single inheritance).

33. What is the purpose of an Objective-C category?
The purpose of an Objective-C category is to add certain functionalities to different classes and also to provide some of the benefits of multiple inheritance, without the naming collisions that could occur if modules did not require module names on their functions.

38. What is boxing?
Boxing is primitive values in Java 5.0+ which is implicitly coerced when they are put in object context. This coercion converts the primitive value to an object of the wrapper class of the primitive value’s type.

39. How are Java objects deallocated?
By implicitly calling a finalizemethod when the garbage collector is about to reclaim the storage occupied by the object.


Problem Set

1 . What important part of support for inheritance is missing in Java?
Java does not support the private and protected derivations of C++. One can surmise that the Java designers believed that subclasses should be subtypes, which they are not when private and protected derivations are supported. Thus, they did not include them.

3. Compare the inheritance of C++ and Java.

-In Java, all classes inherit from the Object class directly or indirectly. Therefore, there is always a single inheritance tree of classes in Java, and Object class is root of the tree. In Java, if we create a class that doesn’t inherit from any class then it automatically inherits from Object Class. In C++, there is forest of classes; when we create a class that doesn’t inherit from anything, we create a new tree in forest.

-In Java, members of the grandparent class are not directly accessible.The meaning of protected member access specifier is somewhat different in Java. In Java, protected members of a class “A” are accessible in other class “B” of same package, even if B doesn’t inherit from A (they both have to be in the same package)

-Java uses extends keyword for inheritence. Unlike C++, Java doesn’t provide an inheritance specifier like public, protected or private. Therefore, we cannot change the protection level of members of base class in Java, if some data member is public or protected in base class then it remains public or protected in derived class. Like C++, private members of base class are not accessible in derived class.

-Unlike C++, in Java, we don’t have to remember those rules of inheritance which are combination of base class access specifier and inheritance specifier.

-In Java, methods are virtual by default. In C++, we explicitly use virtual keyword.

-Java uses a separate keyword interface for interfaces, and abstract keyword for abstract classes and abstract functions.

-Unlike C++, Java doesn’t support multiple inheritance. A class cannot inherit from more than one class. A class can implement multiple interfaces though.

-In C++, default constructor of parent class is automatically called, but if we want to call parametrized constructor of a parent class, we must use Initalizer list. Like C++, default constructor of the parent class is automatically called in Java, but if we want to call parametrized constructor then we must use super to call the parent constructor

5. Compare abstract class and interface in Java.

  • First and major difference between abstract class and interface is that, abstract class is a class while interface is a interface, means by extending abstract class you can not extend another class becauseJava does not support multiple inheritance but you can implement multiple inheritance in Java.
  • Second difference between interface and abstract class in Java is that you can not create non abstract method in interface, every method in interface is by default abstract, but you can create non abstract method in abstract class. Even a class which doesn’t contain any abstract method can be abstract by using abstract keyword.
  • Third difference between abstract class and interface in Java is that abstract class are slightly faster than interface because interface involves a search before calling any overridden method in Java. This is not a significant difference in most of cases but if you are writing a time critical application than you may not want to leave any stone unturned.
  • Fourth difference between abstract class vs interface in Java is that, interface are better suited for Type declaration and abstract class is more suited for code reuse and evolution perspective.
  • Another notable difference between interface and abstract class is that when you add a new method in existing interface it breaks all its implementation and you need to provide an implementation in all clients which is not good. By using abstract class you can provide default implementation in super class.
  • 10. Explain one advantage of inheritance.
    Inheritance offers a solution to both the modification problem posed by abstract data type reuse and the program organization problem. If a new abstract data type can inherit the data and functionality of some existing type, and is also allowed to modify some of those entities and add new entities, reuse is greatly facilitated without requiring changes to the reused abstract data type. Programmers can begin with an existing abstract data type and design a modified descendant of it to fit a new problem requirement. Furthermore, inheritance provides a framework for the definition of hierarchies of related classes that can reflect the descendant relationships in the problem space.

    12. Compare inheritance and nested classes in C++. Which of these supports an is-a relationship?
    Inheritance is where one class (child class) inherits the members of another class (parent class).Nested class is a class declared entirely within the body of another class or interface.

    Inheritance does.

    17. What are the different options for object destruction in Java?
    Finalize is related to C++ destructor. A finalize method is implicitly called when the garbage collector is about to reclaim the storage occupied by the object. The problem with finalize is that the time it will run cannot be forced or even predicted. The alternative to using finalize to reclaim resources held by an object about to be garbage collected is to include a method that does the reclamation. The only problem with this is that all clients of the objects must be aware of this method and remember to call it.

    20. Compare the way Smalltalk provides dynamic binding with that of C++.
    In C++, the programmer can specify whether static binding or dynamic binding is to be used. Because static binding is faster, this is an advantage for those situations where dynamic binding is not necessary. Furthermore, even the dynamic binding in C++ is fast when compared with that of Smalltalk. Binding a virtual member function call in C++ to a function definition has a fixed cost, regardless of how distant in the inheritance hierarchy the definition appears. Calls to virtual functions require only five more memory references than statically bound calls (Stroustrup, 1988). In Smalltalk, however, messages are always dynamically bound to methods, and the farther away in the inheritance hierarchy the correct method is, the longer it takes. The disadvantage of allowing the user to decide which bindings are static and which are dynamic is that the original design must include these decisions, which may have to be changed later.

    21. Compare the support for polymorphism in C# with that of in Objective-C.
    In Objective-C, polymorphism is implemented in a way that differs from the way it is done in most other common programming languages. A polymorphic variable is created by declaring it to be of type id. Such a variable can reference any object. The run-time system keeps track of the class of the object to which
    an id type variable refers. If a call to a method is made through such a variable, the call is dynamically bound to the correct method, assuming one exists.
    To allow dynamic binding of method calls to methods in C#, both the base method and its corresponding methods in derived classes must be specially marked. The base class method must be marked with virtual, as in C++. To make clear the intent of a method in a subclass that has the same name and protocol as a virtual method in an ancestor class, C# requires that such methods be marked override if they are to override the parent class virtual method.

    25. Study and explain private and public modifiers in C++. How do those modifiers differ in C#?
    C++ includes both classes and structs, which are nearly identical constructs. The only difference is that the default access modifier for class is private, whereas for structs it is public. C# also has structs, but they are very different from those of C++. In C#, structs are, in a sense, lightweight classes. They can have constructors, properties, methods, and data fields and can implement interfaces but do not support inheritance.



1. What are the two kinds of abstractions in programming languages?

Two kinds of abstractions in programming languages are process abstraction and data abstraction.

5. What are the language design issues for abstract data types?

-The first design issue for abstract data types is the form of the container for the interface to the type.

-The second design issue is whether abstract data types can be parameterized.

-The third design issue is what access controls are provided and how such controls are specified.

6. Explain how information hiding is provided in an Ada package.
There are two approaches to hiding the representation from clients in the package specification. One is to include two sections in the package specification—one in which entities are visible to clients and one that hides its contents.

9. What is in an Ada package specification? What about a body package?

Package specification : is an Ada package which provides the interface of the encapsulation (and perhaps more).
Body package : is an Ada package which provides the implementation of most, if not all, of the entities named in the associated package specification.

10. What is the use of Ada ‘with’ clause?

The ‘with’ clause in Ada makes the names defined in external packages visible.

11. What i sthe use of Ada ‘use’ clause?

The ‘use’ clause in Ada can be accessed simply as ‘put’. Ada’s ‘use’ is similar to Java’s ‘import’.

12. What is the fundamental difference between a C++ class and an Ada package?

C++ provides two different kinds of encapsulation-header and implementation files can be defined as in C, or class headers and definition an be defined.

Ada package specifications can include any number of data and subprogram declarations in their public and private section.

15. What is the purpose of a C++ destructor?

The purpose of a C++ destructor is to deallocate heap space (memory) that the object or class used.

16. What are the legal return types of a destructor?

A destructor has no return types.

20. What is the use of limited private types?

Limited private types are useful when the usual predefined operations of assignment and comparison are not meaningful or useful.

21. What are initializers in Objective-C?

Intializers in Objective-C are constructors.

26. Why does Java not have destructors?

The purpose of a Destructor is usually to clear off unused variables and clean up the memory. Java has in built memory handling mechanisms (Garbage collection) that clear off unused memory automatically. Hence there is no requirement for destructor methods. So that Java doesn’t need any destructor.

27. Where are all Java methods defined?

Methods in Java must be defined completely in a class.

28. Where are Java classes allocated?

Java classes are allocated from the heap and accessed through reference variables.

48. What elements can appear in a Ruby module?

Modules typically define collections of methods and constants.


Problem Set

2. Suppose someone designed a stack abstract data type in which the function top returned an access path (or pointer ) rather than returning a copy of the top element. This is not a true data abstraction. Why ? Give an example that illustrates the problem.

– The problem with this is that the user is given access to the stack through the returned value of the “top” function. For example, if p is a pointer to objects of the type stored in the stack, we could have:

p = top(stack1);

*p = 42;

These statements access the stack directly, which violates the principle of a data abstraction.

4. The advantages of the nonpointer concept in Java?

• There is no memory leak such as dangling pointers or unnamed variables.

• Memory access via pointer arithmetic – this is fundamentally unsafe. Java has a robust security model and disallows pointer arithmetic for this reason.

• Array access via pointer offsets – Java does this via indexed array access so you don’t need pointers. A big advantage of Java’s indexed array access is that it detects and disallows out of bounds array access, which can be a major source of bugs.

• References to objects – Java has this, it just doesn’t call them pointers. Any normal object reference works as one of these.

8. Some drawbacks of user-defined generic classes in Java 5.0 are: for one thing, they cannot store primitives. Second, the elements cannot be indexed. Elements must be added to user-defined generic collections with the add method.

9. If the constuctor is absent in Java and C++, it will be automatically made by the compiler.

11. Destructors in C# are rarely used because it uses garbage collection for most of its heap objects.

12. Classes in Ruby are dynamic in the sense that members can be added at any time. This is done by simply including additional class definitions that specify the new members.



Book : Concept of Programming Languages(tenth edition)

By : Robert W. Sebesta

Review Question

1. What is the definition used in this chapter for “simple” subprograms?

By “simple” it means that subprograms cannot be nested and all local variables are static.

2. Which of the caller or calle saves execution status information?

Either can save the execution status.

3. What must be stored for the linkage to a subprogram?

Execution status information be stored for the linkage to a subprogram.

4. What is the task of a linker?

Its first task is to find the files that contain the translated subprograms referenced in that program and load them into memory. Then, the linker must set the target addresses of all calls to those subprograms in the main program to the entry addresses of those subprograms.

6. What is the difference between an activation record and an activation record instance?
An activation record is the format, or layout, of the moncode part of a subprogram, whereas an activation record instance is a concrete example of an activation record, a collection of data in the form of an activation record.

8. What kind of machines often use registers to pass parameters?
RISC machines, parameters are passed in registers.

10. Define static chain, static depth, nesting depth, and chain offset.

static chain : is a chain of static links that connect certain activation record instance in the stack.

static depth : an integer associated with a static scope that indicates how deeply it is nested in the outermost scope.

nesting depth/chain offset : the difference between the static depth of the subprogram containing the reference to X and the static depth of the subprogram contining the declaration for X.


Problem Set

6. Although local variables in Java methods are dynamically allocated at the beginning of each activation, under what circumstances could the value of a local variable in a particular activation retain the value of previous activation?
If the variable is declared as static. Static modifier is a modifier that makes a variable history – sensitive.

7. It is stated in this chapter that when nonlocal variables are accessed in a dynamic-scoped language using the dynamic chain, variable names must be stored in the activation records with the values. If this were actually done, every nonlocal access would require a sequence of costly string comparisons on names. Design an alternative to these string comparisons that would be faster.

Using approach that uses an auxiliary data structure called a display. Or, to write variable names as integers. These integers act like an array. So when the activation happens, the comparisons will be faster.

8. Pascal allows gotos with nonlocal targets. How could such statements be handled if static chains were used for nonlocal variable access? Hint:Consider the way the correct activation record instance of the static parent of a newly enacted procedure is found(see Section 10.4.2).

Based on the hint statement, the target of every goto in a program could be represented as an address and a nesting_depth, where the nesting_depth is the difference between the nesting level of the procedure that contains the goto and that of the procedure containing the target. Then, when a goto is executed, the static chain is followed by the number of links indicated in the nesting_depth of the goto target. The stack top pointer is reset to the top of the activation record at the end of the chain.

9. The static-chain method could be expanded slightly by using two static links in each activation record instance where the second points to the static grandparent activation record instance. How would this approach affect the time required for subprogram linkage and nonlocal references?

Including two static links would reduce the access time to nonlocals that are defined in scopes two steps away to be equal to that for nonlocals that are one step away. Overall, because most nonlocal references are relatively close, this could significantly increase the execution efficiency of many programs.

11. If a compiler uses the static chain approach to implementing blocks, which of the entries in the activation records for subprograms are needed in the activation records for blocks?

There are two options for implementing blocks as parameterless subprograms: One way is to use the same activation record as a subprogram that has no parameters. This is the most simple way, because accesses to block variables will be exactly like accesses to local variables. Of course, the space for the static and dynamic links and the return address will be wasted. The alternative is to leave out the static and dynamic links and the return address, which saves space but makes accesses to block variables different from subprogram locals


Book : Concept of Programming Languages(tenth edition)

By : Robert W. Sebesta

Review Question

1. What are the three general characteristic of subprograms?

• Each subprogram has a single entry point.
• The calling program unit is suspended during the execution of the called subprogram, which implies that there is only one subprogram in execution at any given time.
• Control always returns to the caller when the subprogram execution terminates.

2. What does it mean for a subprogram to be active?

A subprogram is said to be active , if after having been called, it has begun execution but has not yet completed that execution.

3. What is given in the header of a subprogram?

• First, it specifies that the following syntactic unit is a subprogram definition of some particular kind.1 In languages that have more than one kind of subprogram, the kind of the subprogram is usually specified with a special word.
• Second, if the subprogram is not anonymous, the header provides a name for the subprogram.
• Third, it may optionally specify a list of parameters.

4. What characteristic of Python subprograms sets them apart from those of other languages?

Function def statements are executable.

5. What languages allow a variable number of parameters?

C,C++,Perl JavaScript, and Lua.

6. What is a Ruby array formal parameter?

The initial parameters are expressions, whose value objects are passed to the corresponding formal parameters. The initial parameters can be following by a list of key => value pairs, which are plced in an anonymous hash and a reference to that hash is passed to the next formal parameters. The hash item can be followed by a single parameters preceded by an asterisk.

7. What is a parameter profil? What is a subprogram protocol?

The parameter profile of a subprogram contains the number, order, and types of its formal parameters. The protocol of a subprogram is its parameter profile plus, if it is a function, its return type.

8. What are formal parameters? What are actual parameters?

Formal parameters are The parameters in the subprogram header. They are sometimes thought of as dummy variables because they are not variables in the usual sense. Actual parameters are a list of parameters to be bound to the formal parameters of the subprogram.

11. What are the design issues for subprogram?

-Are local variables statically or dynamically allocated?

-Can subprogram definitions appear in other subprogram definitions?

-What parameter-passing method or methods are used?

-Can subprograms be overloaded?

-Can subprogram be generic?


15. What are the three semantic models of parameter passing?

• They can receive data from the corresponding actual parameter;

• They can transmit data to the actual parameter; or

• They can do both.

These models are called in mode, out mode, and inout mode, respectively.

30. What are the design issues for functions?

• Are side effects allowed?
• What types of values can be returned?
• How many values can be returned?

34. What is a closure?

Function or reference to a function together with a referencing environment or a table storing a reference to each of the non-local  variables of that function.


Problem Set

1. What are arguments for and against a user program building additional definitions for existing operators, as can be done in Python and C++? Do you think such user-defined operator overloading is good or bad? Support your answer.

Arguments for:

It allows the developer to program using notation “closer to the target domain” and allows user-defined types a similar level of syntactic support as types built into the language. It can easily be emulated using function calls.

Arguments against:

It can be implemented according to user’s want, eventhough it is not logically true.

I think such user-defined operator overloading is good as long as user use it according to its logical rules. User must use for example, + operator to be overloaded to implement “add” not “substraction”. And sometimes, in C++ there is condition when user need to add many data in class, so user-defined operator like this is needed to make it easier.

3. Argue in support of the templated functions of C++. How is it different from the templated functions of other languages?

It is different as C++ differentiates function based on overloading. It is not practical to make multiple function overloading in regard to writability and readability. Instead, creating a template allows a function to receive any datatype as long as the variation is based on the formal parameter definition.

5. Consider the following program written in C syntax:
void swap(int a, int b) {
int temp;
temp = a;
a = b;
b = temp;

void main() {
int value =1, list[5]= {2,4,6,8,10};
swap (value,list[0]);
for each of the following parameter-passing methods, what are all of the values of the variables value, and list after each of the three calls to swap?

a. Passed by value
b. Passed by reference
c. Passed by value-result


a. Passed by value : value = 1, list[5] = { 2 , 4 , 6 , 8 , 10 }

b. Passed by reference: value = 6, list[5] = { 4 , 1 , 2 , 8 , 10 }

c. Passed by value-Result: value = 6, list[5] = { 4 , 1 , 2 , 8 , 10 }

6. Compare and contrast PHP’s parameter passing with that of C#

PHP’s parameter passing is similiar to that of C#, excfept that either the actual parameter or formal parameter can specify pass-by-reference. Pass by reference is specified by preceding one or both of the parameters with an ampersand.

7. Consider the following program written in C syntax:
void fun(int first, int second){

void main(){
int list[2] = { 3 , 5 };
fun(list[0], list[1]);
for each of the following parameter-passing methods, what are the values of the list array after execution?
a. Passed by value
b. Passed by reference
c. Passed by value-result


a. Passed by value: list[2] = { 3 , 5 }

b. Passed by reference: list[2] = { 6 , 10 }

c. Passed by value-result: list[2] = { 6 , 10 }

15. How is the problem of passing multidimensional arrays handled by Ada?

Ada compilers are able to determine the defined size of the dimensions of all arrays that are used as parameters at the time subprograms are compiled.