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

  1. This question deals with parameter passing and aliasing. According to Scott, aliasing occurs when "two or more names refer to a single object in a given scope".

    a) Of the parameter passing methods call-by-reference and call-by-value, which one can result in aliasing?

    b) In Java, under what circumstances does parameter passing result in aliasing?

    c) For languages that support both call-by-reference and call-by-value, give two reasons why a programmer might choose call-by-reference over call-by-value.

    d) In C, call-by-reference is not available. How can its effect be simulated? Make sure you describe what happens in both the caller and the callee.

    e) In C, if an array is passed as a parameter, modification of the array contents by the callee is visible in the caller. How is this possible, given that call-by-reference is not available in C?

  2.  
    a) Recall that to implement static scoping, a static link may be provided for each frame on the subroutine call stack. This link points from the frame to the frame of the lexically surrounding subroutine. Assuming static scoping and nesting corresponding to indentation in the pseudocode at right, show the contents of the subroutine call stack, including the static links, after each of the following sequences of calls:
      1. A calls B, B calls C, C calls D
      2. A calls B, B calls C, C calls D, D calls B

    b) Recall that a display is an embedding of the static chain into an array. Give the display corresponding to each of your answers to part (a).

    c) What is the potential advantage of a display over a static chain? Give one reason why this advantage is not as important as it might appear.

    d) Describe how the static link of a newly created frame is found
      1. if the callee is nested immediately inside the caller
      2. if the callee appears k levels outward from the caller, where k is a nonnegative integer
    Make sure that your solution works for the examples in (a) (you needn't demonstrate this). You may assume that the code is being compiled. You may ignore the issue of closures. 

       define A
     define B
       define C
         body of C
       end C
       define D
         body of D
       end D
       body of B
     end B
     define E
       body of E
     end E
     body of A
   end A

     

  3. a) What is pipelining? Why is it useful?

    b) The code in Figure 1 is intended to compute the dot product of two vectors A and B -- that is, the sum from 1 to n of A[i]*B[i]. It uses registers whose names begin with r or f; the registers f1, f2, f3, and f4 are floating point registers. The result of the dot product computation is available in register f1 after the computation. The loop of Figure 2 is intended to do the same thing as the loop of Figure 1. What is the advantage of the code in Figure 2 over the code in Figure 1?

    c) The loop of Figure 3 is intended as another improvement over that of Figure 1. In Figure 3, each iteration of the loop handles two consecutive subscripts. What is the advantage of the code in Figure 3 over the code in Figure 1, assuming that n is a multiple of 2?

    d) In the code of Figure 3, the registers represent virtual registers rather than physical registers. Give an example of two virtual registers that may be mapped to the same physical register. 

        r1 := &A            - pointer to A[1]
    r2 := &B            - pointer to B[1)
    r3 := n             - count of elements yet to go
    f1 := 0             - accumulated dot product (floating-point)
    goto L2
L1: f2 := *r1           - A[i] (floating-point)
    f3 := *r2           - B[i] (floating-point)
    f4 := f2 * f3
    f1 := f1 + f4
    r1 := r1 + 8        - 8 bytes per double-word
    r2 := r2 + 8
    r3 := r3 - 1
L2: if r3 <> 0 goto L1


    Figure 1
    

L1: f2 := *r1           - A[i] (floating-point)
    f3 := *r2           - B[i] (floating-point)
    r1 := r1 + 8
    f4 := f2 * f3
    r2 := r2 + 8
    r3 := r3 - 1
    f1 := f1 + f4
L2: if r3 <> 0 goto L1


    Figure 2
    

L1: f2 := *r1            - A[i]
    f3 := *r2            - B[i]
    f4 := f2 * f3
    f1 := f1 + f4
    f5 := *(r1+8)        - A[i+1]
    f6 := *(r2+8)        - B[i+1]
    f7 := f5 * f6
    f1 := f1 + f7
    r1 := r1 + 16        - 8 bytes per double-word,
    r2 := r2 + 16        - 2 double-words per iteration
    r3 := r3-2
L2: if r3 <> 0 goto L1


    Figure 3