Question

Question 2 (5 marks) In class, we discussed how to implement static scoping using a static chain. We discussed how to use the static chain to access a variable we want to update at runtime. What we did not discuss is how to maintain this static chain when we make recursive calls. Your task in this question is to provide the details of computing the static link for a function that is being called, that is, how to find the stack frame the static link of the newly created stack frame needs to point to. (The compiler should be able to determine at compile time how many jumps up the caller's static chain are necessary to reach the stack frame that is the target of the static link in the callee's stack frame.)

Answer 1

Static Chain Maintenance

• The static chain must be modified for each subroutine call and return

• The return part is trivial – When a subroutine terminates, its activation record is simply removed

• The call part is more complex – When a subroutine is called, its activation record needs to be built – Two methods to construct static links

Static Link Construction 1

• When a subroutine is called, search the dynamic chain until the first one of the parent scope is found

• However, this search can be avoided by treating subroutine declarations and calls as variable definitions and references

Static Link Construction 2

• At compile time, – When the compiler encounters a subroutine call A() in subroutine C, it determines the subroutine B which declares A – It then computes the nesting_depth between C and B – The information is stored and can be accessed by subroutine call during execution – When A is called, the static link to B is determined by moving down the static chain of C() nesting_depth hops