1. (5 points) What is a static chain? What is a static link? What is a display?

2. (10 points) The following algorithm will initialize the static link when a subroutine is called. Explain why this algorithm works correctly. Note that the algorithm assumes that static links are to point to the same location within a frame as frame pointers do.

   1. The callee is nested (directly) inside the caller. In this case, the callee's static link should refer to the caller's frame. The caller therefore passes its own frame pointer as the callee's static link.

   2. The callee is k>-1 scopes "outward" -- closer to the outer level of lexical nesting. In this case, all scopes that surround the callee also surround the caller. The caller dereferences its own static link k times and passes the result as the callee's static link.

3. (5 points) Why are the two cases of the algorithm the only two cases that need to be considered in the case of a subroutine call?

In the grammar,

1. (4 points) is next_free_register an inherited attribute, or a synthetic attribute? Justify your answer.

2. (4 points) what is the purpose of the restore code?

3. (8 points) for a syntax tree node expr₁ that corresponds to an addition operation, find the value of expr1.register, spill_code, and expr1.code, assuming that
   1. expr2.reg is "r1",
   2. expr3.reg is "r2",
   3. expr1.next_free_reg is 0
   4. expr2.code is "r1 := a"
   5. expr3.code is "r2 := b"
   6. k (the number of registers available) is 8,

4. (4 points) virtual registers are not used. What are virtual registers, and what is the advantage of using them?

reg_names : array [0..k-1] of register_name := ["r1", "r2", "r3", "r4", "r5", "r6", "r7", "r8"]
   -- ordered set of temporaries
'+' : expr1 → expr2 expr3
    ⊲ handle_op(expr1, expr2, expr3, "+")
macro handle_op(ref result, L_operand, R_operand, op: syntax_tree_node)
    result.reg := L_operand.reg
    L_operand.next_free_reg := result.next_free_reg
    R_operand.next_free_reg := result.next_free_reg + 1
    if R_operand.next_free_reg < k
      spill_code := restore_code := nil
    else
      spill_code := ["*sp :=" reg_names[R_operand.next_free_reg mod k]] +
                      ["sp := sp - 4"]
      restore_code := ["sp := sp + 4"] +
                        [reg_names[R_operand.next_free_reg mod k] ":= *sp"]
    result.code := L_operand.code + spill_code + R_operand.code +
              [result.reg ":=" L_operand.reg op R_operand.reg + restore_code

1. In Ada, loop control variables needn't be declared. How does the compiler know what the type of the loop control variable is (for example, the type of i in the code below)?

            for i in 1..10 do 
                   ... 

2. Why is iteration not used in pure functional programming languages? What control mechanism is used instead?

3. Is iteration used in Prolog? If not, what control mechanism is used instead? (Hint: consider the member predicate.)

4. Many languages provide a break or exit statement, as an alternative to goto, to allow control to leave a loop. Why might a language allow this statement to take a label as parameter?

5. The code below is intended to translate the loop

       FOR i:= first TO last BY step DO

   in the case where step is positive. What is the advantage of this over a translation in which a loop beginning with

       L1: if r1 > r3 goto L2

   follows the assignments to r1, r2, and r3, assuming that L2 again labels the statement after the loop?

               r1 := first               
               r2 := step               
               r3 := last
               goto L2
           L1: ...
               r1 := r1 + r2
           L2: if r1 <= r3 goto L1