Solutions: Programming language principles, part 2, CS 288, May 16, 2005

a) call-by-reference
b) when objects (i.e., object references) are passed as parameters. Parameters of primitive (i.e., non-object) types are passed by value.
c) Call-by-reference would be used if modifications by the callee are supposed to be visible in the caller, and might be used if the parameter being passed is very large.
d) To simulate passing of an entity by reference, the referencing operator & could be invoked to pass a pointer to the entity. The formal parameter would be of a pointer type. The callee would have to use the explicit dereferencing operator * to access the entity.
e) Single dimensional arrays in C are "largely interchangeable with pointers" in the words of Scott. That is, an array variable is effectively a pointer even outside the context of parameter passing.
a) The stacks are given below, with static links in parentheses:
```
                     B (A)
        D (B)        D (lower frame for B)
        C (B)        C (lower frame for B)
        B (A)        B (A)
        A            A
```
b) Using the notational conventions of Scott, in the first case there are three array locations, pointing respectively to A's frame, B's frame, and D's frame. In the second case, there are two locations, pointing respectively to A's frame and to the upper frame for B.
c) Resolving a nonlocal reference using a static chain requires accessing each frame in the chain, while a display gives immediate access to the desired frame. However static chains are usually quite short, since programs rarely have deeply nested routines (or other blocks). Other reasons why displays don't represent a major advantage over static chains are given beginning on page 430 of Scott.
d) In the first case, the caller simply provides its own frame pointer as the new static link. In the second case, k+1 static links are followed from the callee. For example, when D calls B in (a), B is 1 level outward from D, so 2 static links are followed to get from D to B, and from B to A. The link to A is the new static link.

a) Processing an instruction requires several tasks, which need to be done sequentially -- the instruction needs to be fetched from memory, decoded, have its operands fetched, executed, and have its resuls stored into the appropriate place. In a pipelined architecture, a processor may execute a later task for an earlier instruction in parallel with an earlier task for a later instruction, since different tasks can be accomplished by different functional units of the processor.
b) In the code of Figure 1, there will be a delay while the product that is to be assigned to register f4 is computed. Since the very next instruction in sequence uses f4, this will delay the entire computation, even in the pipelined case. In the code of Figure 2, the instruction that uses f4 has been separated from the computation of the product. In the pipelined case, this allows some processing of the intervening instructions while the product is being computed, thus reducing the total delay.
c) Here the bookkeeping instructions that update the values in registers r1, r2, and r3 need to be executed only n/2 times rather than n times. A similar observation applies to the testing and branching instructions.
d) There are many possible answers. In general, any two registers with disjoint live ranges can map to the same physical register. For example, registers f2 and f5 can be combined. This is a case where the two registers come from the same register of the code of Figure 1.