Solutions -- programming language principles, part 2, CS 288, April 25, 2007

1. A static chain is a linked list of frames that represents the sequence of blocks that enclose a given block, from most closely to least closely, beginning with the frame representing the given block. A static link is a link in this linked list. A display is an array that represents the same sequence of frames as the static chain.
2. If the callee is nested directly inside the caller, then the caller is the successor of the callee in the sequence of enclosing blocks. After the caller in this sequence comes the rest of the static chain of the caller. In other words, the correct static chain of the callee consists of the callee itself, followed by the caller's static chain. So the callee's static chain may be obtained from the caller's by simply adding a frame for the callee to the beginning of the caller's chain. This may be accomplished by having the callee's static link point to the caller. That is, the caller's static link should be the caller's frame pointer.
  In the second case, to say that the callee is k scopes outward is to say that the name of the callee is resolved in a block whose representing frame is k frames down the static chain for the caller (and is thus accessible by dereferencing the caller's static link k times). This block is also the immediately enclosing block for the callee, and thus should appear immediately after the callee's frame on the callee's static chain. So the callee's static link should link to the frame corresponding to this block, and this is precisely what the algorithm does.
3. The caller can only access the callee by referring to its name. For the name of the callee to be available to the caller, it has to be declared immediately inside the caller, or to appear in a block enclosing the caller. These two cases correspond to the two cases of the algorithm.
1. The attribute is inherited. In the given macro, its value is assigned from operator to operand. The operator argument corresponds to a parent node and the operand arguments to child nodes, as can be seen in the grammar rule for +.
2. To restore the contents of saved registers. These registers are the ones that the current computation will (or at least may) need to write to, and they are saved by the spill code.
3. The value of expr₁.register is "r1". The value of spill_code is nil (since the value of expr₃.next_free_register is 1). The value of expr₁.code is a string corresponding to the target code below.
```
    r1 := a
    r2 := b
    r1 := r1 + r2
```
4. Virtual registers are hypothetical registers that may exceed in number the registers that are available on the target machine. The use of virtual registers allows a clean separation of code generation into a machine-independent phase (in which virtual registers are used) and a machine-dependent phase (in which virtual registers are mapped onto actual registers).
1. The compiler assumes that the type of the loop control variable is the same as that of a member of the range given by the bounds of the loop.
2. Conventional iteration requires assignment, which is not available in the pure functional programming paradigm. Recursion is used instead.
3. No, to simulate iteration Prolog also uses recursion. The general control mechanism in Prolog is depth-first search with backtracking, with some special purpose control constructs such as "cut" available for the programmer.
4. To give the programmer control, in the case of nested loops, over which loops to escape from and which not to escape from.
5. The proposed translation would need a second branch statement of the form goto L1 at the bottom of the loop. Thus every loop iteration would require two branches instead of one.