Programming Language Concept (10)

Book : Concept of Programming Language

Page 466
Review Question
1. What is the definition used in this chapter for “simple” subprograms ?
-Subprograms cannot be nested and all local variables are static.

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

3. What must be stored for the linkage to a subprogram ?
- Execution status information

4. What is the task of a linker ?
- find files that contain the translated subprograms referenced in that program and load them into memory, set 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 ?
- RISC Machines

10. Define static chain, static_depth, nesting_depth,and chain_offset.
-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 ?
-It is represented by static_depth.


Page 467
Problem Set  
1. Show the stack with all activation record instances, including static and dynamic chains, when execution reaches position 1 in the following skeletal program. Assume Bigsub is at level 1.
(page 487)

      -      +--------------------------------------------+ <------ top
     /       !       Dynamic link                     ! --+>----\
    /        !----------------------------------------+---!     !
   B         !       Static link                      ! -----\  !
    \        !----------------------------------------+---!  !  !
     \       !       Return (to C)                    !   !  !  !
      -      !----------------------------------------+---!<-+--/
     /       !       Dynamic link                     ! --+>-!
    /        !----------------------------------------+---!  !
   C         !       Static link                      ! --+>-!
    \        !----------------------------------------+---!  !
     \       !       Return (to A)                    !   !  !
      -      !----------------------------------------+---!<-/
     /       !       Dynamic link                     ! --+>------\
    /        !----------------------------------------+---!       !
   A         !       Static link                      ! --+>------!
    \        !----------------------------------------+---!       !
     \       !       Return (to BIGSUB)               !   !       !
      -      !----------------------------------------+---!<------/
BIGSUB       !       Local variables                  !   !
             +----------------------------------------+---+

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 previous activation ?
- If the variable is declared as static. Static modifier is a modifier that makes a variable history – sensitive.

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.

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.