Source:
Concepts of Programming Languages, Robert W. Sebesta.
Chapter 10: Implementing Subprograms, page 467-470Concepts of Programming Languages, Robert W. Sebesta.
By:
Name : Helena Natanael
NIM : 1801380333
Review Question:
6. What is the difference between an activation record and an activation record instance?
The format, or layout, of the noncode part of a subprogram is called an activation record, because the data it describes are relevant only during the activation, or execution of the subprogram. The form of an activation record is static. An activation record instance is a concrete example of an activation record, a collection of data in the form of an activation record.
7. Why are the return address, dynamic link, and parameters placed in the bottom of the activation record?
Because the return address, dynamic link, and parameters are placed in the activation record instance by the caller, these entries must appear first. The return address usually consists of a pointer to the instruction following the call in the code segment of the calling program unit. The dynamic link is a pointer to the base of the activation record instance of the caller. In static- scoped languages, this link is used to provide traceback information when a run-time error occurs. In dynamic-scoped languages, the dynamic link is used to access nonlocal variables. The actual parameters in the activation record are the values or addresses provided by the caller.
8. What kind of machines often use registers to pass parameters?
In many compilers for RISC machines, parameters are passed in registers. This is because RISC machines normally have many more registers than CISC machines. In the remainder of this chapter, however, we assume that parameters are passed in the stack. It is straightforward to modify this approach for parameters being passed in registers.
9. What are the two steps in locating a nonlocal variable in a static-scoped language with stack-dynamic local variables and nested subprograms?
The first step of the access process is to find the instance of the activation record in the stack in which the variable was allocated. The second part is to use the local_offset of the variable (within the activation record instance) to access it.
10. Define static chain, static_depth, nesting_depth, and chain_offset.
- 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.
- A static_depth is a static scope that indicates how deeply it is nested in the outermost scope. A program unit that is not nested inside any other unit has a static_depth of 0. If subprogram A is defined in a nonnested program unit, its static_depth is 1. If subprogram A contains the definition of a nested subprogram B, then B’s static_depth is 2.
- A nesting_depth or chain_offset is the difference between the static_depth of the subprogram containing the reference to X and the static_depth of the subprogram containing the declaration for X.
Problem Sets:
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 the previous activation?
Each activation allocates variables in exactly the same order. Variables are not initialized to any value unless the program contains an initialization statement for the variable – they simply have whatever value is stored in the location they are allocated. If a procedure finishes executing, returns, and is immediately reinvoked, a variable would be assigned the same stack location it had on the previous invocation, and would have the last value from that previous invocation.
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.
10. Design a skeletal program and a calling sequence that results in an activation record instance in which the static and dynamic links point to different activation-recorded instances in the run-time stack.
| \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} |
No comments:
Post a Comment