Explanation of the assignments

There are two points that still need to be explained regarding the implementation of static scoping used in the assignments:

1) Where the first component of the pair of offsets comes from, and

2) Where the value of the static link for a new activation record comes from

Recall that both of these values were treated as given in the test program.

The key observation is that during compilation under static scoping, the compiler processes the program text from top down, so that the order in which it enters and leaves blocks is LIFO. In other words, the compiler maintains a stack of all of the blocks that it is currently inside of. This stack necessarily reflects the nesting of blocks in the program. Another way of thinking of this is that the compiler is essentially using dynamic scoping to keep track of the blocks.

So for example, if a main block contains a block for a function f, which contains a block for a function g, which contains a block for a function h, then the stack has an entry for h at the top, an entry for g below that, an entry for f below that, and an entry for main below that. If h calls g, then the compiler has to look for the symbol g, using essentially the dynamic scoping algorithm. In this case it will find it 2 entries down, since g is defined in the block f. If h calls f, then since f is defined in main, the symbol f will be found 3 blocks down.

Thus the answer to (1) is that the first component of the offset for a function block is computed from the number of stack entries that the compiler has to search to find the name of the function.

Now if h calls g, the static link for g's activation record should point to the proper activation record for f, and not for h. But the number of static links to follow to get from the top activation record on the stack (corresponding to h) to an activation record for f is given by the offset above. In this case it will follow 2 static links from the top of the stack -- the first going to an activation record for g, and the second to an activation record for f. If g in turn calls itself, then the symbol g will be found 1 block down, so that one static link will be followed from the new activation record for g. This is the static link just constructed, and it points to an activation record for f, as desired.

So the answer to (2) is as follows: the destination of the new static link is obtained by starting with the current activation record (at the top of the stack), and following a number of activation records given by the offset computed for (1).