Chapter 10 of Concept of Programming Languages

Review Question

1. What is the definition used in this chapter for “simple” subprograms?
By “simple” they mean that subprograms cannot be nested and all local variables are static.

2. Which of the caller or callee saves execution status information?
The last three actions of a call clearly must be done by the caller. Saving the execution status of the caller could be done by either.

4. What is the task of a linker?
Task of a linker 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.

5. What are the two reasons why implementing subprograms with stack-dynamic local variables is more difficult than implementing simple subprograms?

• The compiler must generate code to cause the implicit allocation and deallocation of local variables.
• Recursion adds the possibility of multiple simultaneous activations of a subprogram, which means that there can be more than one instance (incomplete execution) of a subprogram at a given time, with at least one call from outside the subprogram and one or more recursive calls. The number of activations is limited only by the memory size of the machine. Each activation requires its activation record instance.

11 . What is an EP, and what is it’s purpose?
EP is required to control the execution of a subprogram. Initially, the EP points at the base, or first address of the activation record instance of the main program. Therefore, the run-time system must
ensure that it always points at the base of the activation record instance of the currently executing program unit. When a subprogram is called, the current EP is saved in the new activation record instance as the dynamic link. The EP is then set to point at the base of the new activation record instance. Upon return from the subprogram, the stack top is set to the value of the current EP minus one and the EP is set to the dynamic link from the activation record instance of the subprogram that has completed its execution. Resetting the stack top effectively removes the top activation record instance.


16 . Describe the deep-access method of implementing dynamic scoping.
If local variables are stack dynamic and are part of the activation records in a
dynamic-scoped language, references to nonlocal variables can be resolved by searching through the activation record instances of the other subprograms that are currently active, beginning with the one most recently activated. This concept is similar to that of accessing nonlocal variables in a static-scoped language with nested subprograms, except that the dynamic—rather than the static—chain is followed. The dynamic chain links together all subprogram activation record instances in the reverse of the order in which they were activated. Therefore, the dynamic chain is exactly what is needed to reference nonlocal variables in a dynamic-scoped language. This method is called deep access, because access may require searches deep into the stack.

---

Problem Set


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.
One very simple alternative is to assign integer values to all variable names used in the program. Then the integer values could be used in the activation records, and the comparisons would be between integer values, which are much faster than string comparisons.


8. Pascal allows gotos with nonlocal targets. How could such statements be handled if static chains were used for nonlocal variable access?
Finding the correct activation record instance of a nonlocal variable using static links is relatively straightforward. When a reference is made to nonlocal variable, the activation record instance containing the variable can be found by searching the static chain until a static ancestor activation record instance is found that contains the variable.


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?
The nesting of scopes is known at compile time, the compiler can determine not only that a reference is nonlocal but also the length of the static chain that must be followed to reach the activation records instance that contains the nonlocal object.


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?
A static chain is a chain of static links that connect certain activation record instances in the stack. During the execution of a subprogram P, the static link of its activation record instance points to an activation record instance of P’s static parent program unit. That instance’s static link points in turn to P’s static grandparent program unit’s activation record instance, if there is one. So, the static chain connects all the static ancestors of an executing subprogram, in order of static parent first. This chain can obviously be used to implement the accesses to nonlocal variables in static-scoped languages.