Saturday, June 15, 2013

Concepts of Programming Languages - Chapter 10


Review Questions

1. What are the two reasons why implementing subprograms with stack-dynamic local variables is more difficult than implementing simple sub-programs?
A stack-dynamic local variable is more complex activation records. The compiler must generate code to cause implicit allocation and de-allocation of local variables.
Recursion must be supported (adds the possibility of multiple simultaneous activations of a subprogram).

2. What is the difference between an activation record and activation record instance?
The Format, or layout, of the non-code part of a subprogram is called an activation record.
An activation record stores all the information about subprogram calls, activation records stores the following data (in the following order).
Return address
Static link – to the static parent (where the subprogram is declared).
Dynamic link – to the caller of this subprogram.
Parameters
Local variables.

4. What are the two steps in locating a nonlocal variable in a static-scoped language with stack-dynamic local variables and nested subprograms?
Find the correct activation record instance.
Determine the correct offset within that activation record instance.

5. Define static chain, static depth, nesting_depth, and chain offset.
A static chain is a chain of static links that connects certain activation record instances.
Static_depth is an integer associated with a static scope representing the scope’s nesting depth.
The chain_offset or nesting_depth of a non-local reference is the difference between the static_depth of the reference and that of the scope where it is declared.

6. What are the two potential problems with the static chain methods?
A nonlocal reference is slow if the number of scopes between the reference and the declaration of the referenced variable is large.
Time-critical code is difficult, because the costs of nonlocal references are not equal, and can change with code upgrades and fixes.

7. What is display?
One alternative to static chain is to use a display, for this approach, the static links are collected in a single array called a display. Display uses a pointer array to store the activation records along the static chain.

10. Explain the two methods of implementing block?
Blocks are treated as parameter less subprograms that are always called from the same place in the program.
Block can also be implemented in a different and somewhat simpler and more efficient way. The maximum amount of storage required for block variables at any time during the exaction of program can be statically determined, because block are entered and exited in strictly textual order.

11. Describe the deep access method of implementing dynamic scoping?
Deep Access – nonlocal references are found by searching the activation record instances on the dynamic chain. Length of chain cannot be statically determined every activation record instance must have variable names.

12. Describe the shallow access method of implementing dynamic scoping?
In case of shallow access names and values are stored in a global table. Using this method, space is allocated for every variable name that is in the program (one space for variable temp though there might be several declarations of temp in the different methods). When a sub-routine is called it saves the current value of the variable and replaces it with the value in its current scope and restores the value of the variable while exiting.

14. Compare the efficiency of the deep access method to that of the shallow access method, in term of both call and nonlocal access?
The deep access methods provides fast subprogram linkage, but references to nonlocal, especially references to distant nonlocals (in term of the call chain), are costly. The shallow access methods provide much faster references to nonlocals, especially distant nonlocals, but are more costly in term of subprogram linkage.


Problem Set

7. It 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?
Following the hint stated with the question, 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.

No comments:

Post a Comment