CHAPTER 10

Nama : Aditya Isnugraha
Class   : LM01
NIM    : 1801419606

Assignment from Tri Djoko Wahjono
CHAPTER10

- REVIEW QUESTIONS

11. What is an EP, and what is its purpose? 
Answer :


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

 
13. Name three widely used programming languages that do not allow nested subprograms. 
Answer :


14. What are the two potential problems with the static-chain method
Answer :
1. It is difficult for a programmer working on a time-critical program to estimate the costs of nonlocal references, because the cost of each reference depends on the depth of nesting between the reference and the scope of declaration.
 2. Subsequent code modifications may change nesting depths, thereby changing the timing of some references, both in the changed code and possibly in code far from the changes.


15. Explain the two methods of implementing blocks.
Answer :
- Blocks can be implemented by using the static-chain process for implementing nested subprograms. Blocks are treated as parameterless subprograms that are always called from the same place in the program. Therefore, every block has an activation record. An instance of its activation record is created every time the block is executed.

- Blocks 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 execution of a program can be statically determined, because blocks are entered and exited in strictly textual order. This amount of space can be allocated after the local variables in the activation record. Offsets for all block variables can be statically computed, so block variables can addressed exactly as if they were local variables.


- PROBLEM SET

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 par- ent of a newly enacted procedure is found (see Section 10.4.2).
Answer : 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? 
Answer : 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.





10. Design a skeletal program and a calling sequence that results in an acti- vation record instance in which the static and dynamic links point to dif- ferent activation-recorded instances in the run-time stack.
Answer :
 >\verb+ + X : Integer;\\
\verb+ +procedure Bigsub is\\
\verb+ +\verb+ + A, B, C : Integer;\\
\verb+ +\verb+ + procedure Sub1 is\\
\verb+ +\verb+ +\verb+ + A, D : Integer;\\
\verb+ +\verb+ +\verb+ + begin — of Sub1\\
\verb+ +\verb+ +\verb+ + A := B + C; $\longleftarrow$ 1\\
\verb+ +\verb+ +\verb+ + …\\
\verb+ + end; — of Sub1\\
\verb+ + procedure Sub2(X : Integer) is\\
\verb+ +\verb+ + B, E : Integer;\\
\verb+ +\verb+ + procedure Sub3 is\\
\verb+ +\verb+ +\verb+ + C, E : Integer;\\
\verb+ +\verb+ +\verb+ + begin — of Sub3\\
\verb+ +\verb+ +\verb+ + …\\
\verb+ +\verb+ +\verb+ + Sub1;\\
\verb+ +\verb+ +\verb+ + …\\
\verb+ +\verb+ +\verb+ + E := B + A; $\longleftarrow$ 2\\
\verb+ +\verb+ + end; — of Sub3\\
\verb+ +\verb+ + begin — of Sub2\\
\verb+ +\verb+ + …\\
\verb+ +\verb+ + Sub3;\\
\verb+ +\verb+ + …\\
\verb+ +\verb+ + A := D + E; $\longleftarrow$ 3\\
\verb+ + end; — of Sub2\\
\verb+ + begin — of Bigsub\\
\verb+ +\verb+ + …\\
\verb+ +\verb+ + Sub2(7);\\
\verb+ +\verb+ + …\\
\verb+ + end; — of Bigsub\\
begin — of Main\_2\\
\verb+ + …\\
\verb+ + Bigsub;\\
\verb+ + …\\
end; — of Main\_2\\
\\
The sequence of procedure calls is:\\
Main\_2 calls Bigsub\\
Bigsub calls Sub2\\
Sub2 calls Sub3\\
Sub3 calls Sub1\\
\\
The activation records with static and dynamic links is as follows:\\
\begin{figure}
\centering
\includegraphics[scale=0.5]{ari}
\end{figure}


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



12. Examine the subprogram call instructions of three different architec- tures, including at least one CISC machine and one RISC machine, and write a short comparison of their capabilities. (The design of these instructions usually determines at least part of the compiler writer’s design of subprogram linkage.) 
Answer :