Chap 10 - Review Question and Problem Set - Concepts of Programming Languages, Sebesta

CONCEPTS OF

PROGRAMMING LANGUAGES

TENTH EDITION

Robert W. Sebesta

Chapter 10-Implementing Subprogram

Review Question


1. What is the definition used in this chapter for “simple” subprograms ?
Answer: Simple subprograms are not nasted and all variables in it are static

2. Which of the caller of callee saves execution status information ?
Answer: Either can save the execution status

4. What is the task of a linker?
Answer: 
-find the files that contain the translated subprograms referenced in that program 
-load the files that contains translated subprograminto memory.
-set the target addresses of all calls to those subprograms in the main program to the entry addresses of those subprograms.

8. What kind of machines often use registers to pass parameters ?
Answer: RISC Machines

10. Define static chain, static_depth, nesting_depth,and chain_offset.
Answer: 
static chain : a chain of static links that connect certain activation record instances in the stack.
static_depth : integer associated with a static scope that indicates how deeply it is nested in the outermost scope.
nesting_depth : difference between static_depth of a subprogram containing reference to x and the static_depth of a subprogram containing the declaration of x.
chain_offset : number of links to the correct activation record instance

12. How are references to variables represented in the static-chain method ?
Answer: It is represented by static_depth.


17. Describe the shallow-access method of implementing dynamic scoping.
Answer: 
Shallow access is an alternative implementation method. The semantic of shallow and deep access are indentical.
In the shallow-access method, variables declared in subprograms are not stored in the activation records of those subprograms.


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.
Answer: 
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?
Answer: 
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?
Answer: 
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?
Answer: 
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.



Special thanks to Mr. Tri Djoko Wahjono, Ir., M.Sc.