CSE 341 -- Final -- Answer Key

December 11, 1995


110 minutes and points, open book and notes

Your name:


  1. [5 points] Write a recursive Lisp function abs-sqrts that takes a list of numbers, and returns a list of the square roots of the absolute values of those numbers. Don't write any auxiliary functions. For example, (abs-sqrts '(1.0 -4.0 25.0)) should evaluate to (1.0 2.0 5.0). Hints: use the built-in absolute value function abs and the built-in square root function sqrt.

    (defun abs-sqrts (s) (if (null s) nil (cons (sqrt (abs (first s))) (abs-sqrts (rest s)))))

  2. [5 points] Write a non-recursive version of abs-sqrts using applicative programming. Don't write any named auxiliary functions (use lambda instead).

    (defun abs-sqrts (s) (mapcar #'(lambda (x) (sqrt (abs x))) s))

  3. [10 points] Consider the following program in an Algol-like language. begin integer n; procedure p(j,k: integer); begin j := j+2; print(j,k,n); k := k+5; print(j,k,n); end; n := 0; p(n,n); print(n); end; Suppose that this language does not specify in which order the actual parameters are evaluated, or in which order the formal parameter values are copied back for call by result or value-result. The answer that you get may depend on this order; if so, give all the possible answers, and explain how they might arise.

    What is the output if both j and k are passed by:

    1. value
    2. value-result
    3. reference

    By value:

    2 0 0 2 5 0 0 Explanation: n is assigned 0 in the outer block. We pass it as a parameter to both j and k, copying the value of 0 into both local variables in the procedure. Then we increment j to 2. Since j, k, and n are all separate variables, k and n are unaffected. So we print out 2 0 0. Then we increment k by 5, and print out 2 5 0. Then we return. Since this is call by value, nothing is copied back, and n is still 0 -- so the final print statement prints 0. (You don't need to include this explanation in your answer, though.)

    By value-result:

    2 0 0 2 5 0 5 or 2 Explanation: n is assigned 0 in the outer block. We pass it as a parameter to both j and k, copying the value of 0 into both local variables in the procedure. Then we increment j to 2. Since j, k, and n are all separate variables, we print out 2 0 0. Then we increment k by 5, and print out 2 5 0. Then we return. Since this is call by value result, we copy the values in the formal parameters back to the actuals. If we copy j first, then we copy 2 and then overwrite it with the 5 from k -- so that the final print statement prints 5. If we copy k first, then the final print statement prints 2. (You only need to include the explanation of the different results depending on whether j or k is copied back first, however.)

    By reference:

    2 2 2 7 7 7 7 Explanation: n is assigned 0 in the outer block. We pass it as a reference parameter to both j and k. There is no local storage for j and k -- both of these parameters indirect to n. We increment j to 2, which actually increments n, so that its value is now 2. We print out 2 2 2 (since j, k, and n all refer to the same variable). Then we increment k by 5, which actually increments n, so that its value is 7. We then print out 7 7 7. Then we return. Nothing need be copied back. The final print statement prints 7, the current value of n.

  4. [10 points] Consider the following program in an Algol-like language. begin integer n; integer array a[1..3]; procedure p(j,k: integer); begin print(j,k,n); j := j+1; print(j,k,n); end; a[1]:=10; a[2]:=20; a[3]:=30; n := 1; p(n,a[n]); end; Again suppose that this language does not specify in which order the actual parameters are evaluated, or in which order the formal parameter values are copied back for call by result or value-result. The answer that you get may depend on this order; if so, give all the possible answers, and explain how they might arise.

    What is the output if both j and k are passed by:

    1. value
    2. name
    3. reference

    By value:

    1 10 1 2 10 1 Explanation: n is assigned 1 in the outer block, and the array a holds 10, 20, 30 in elements 1, 2, and 3. We pass n as a parameter to j (copying the value 1 into j), and a[n] to k, copying the value 10 into k. (It doesn't matter here which is done first.) So we print out 1 10 1. Then we increment j by 1, so that its value is 2. (n is not affected, since we are using call by value.) So we print out 2 10 1.

    By name:

    1 10 1 2 20 2 Explanation: n is assigned 1 in the outer block, and the array a holds 10, 20, 30 in elements 1, 2, and 3. We pass n by name as a parameter to j, and a[n] by name to k -- so that every reference to j and k re-evaluates n or a[n] respectively. We then print out the current values of j, k, and n (re-evaluating n and a[n] to produce the values for j and k respectively), printing 1 10 1. Then we increment j by 1, which actually increments n, so that the value of n is now 2. When we get the value of j, k, and n for the next print statement, j is 2, of course. To get the value for k, we re-evaluate a[n], which gives 20 (the value in a[2]). n is still 2. So we print out 2 20 2.

    By reference:

    1 10 1 2 10 2 Explanation: n is assigned 1 in the outer block, and the array a holds 10, 20, 30 in elements 1, 2, and 3. We pass n by reference as a parameter to j, so that references to j actually indirect to n. We pass a[n] by reference to k -- so that every reference to k actually references a[1]. (Note that we just use the current value of n in deciding which element is referenced.) It doesn't matter in which order these correspondences are set up. We then print out the values of j, k, and n -- for j we indirect to n, and for k we indirect to a[1] -- so that we print 1 10 1. Then we increment j by 1, which actually increments n, so that the value of n is now 2. The next print statement prints out 2 10 2.

    Note: since there is no order dependence, your answer need only include the output, not the above explanations.

  5. [5 points] What is printed by the following program in an Algol-like language? Explain your reasoning. (Lexical scoping is used.) begin integer j,k; procedure whale(j: integer); begin function jonah(k: integer); begin return j+k; end; print(jonah(j)); end; j := 10; k := 20; whale(5); end;

    The program prints 10. Explanation: j and k are assigned 10 and 20 in the outer scope. Then we call whale, binding j to 5 (in the whale scope). We evaluate jonah(j), i.e. jonah(5). jonah binds 5 to k, and jonah returns j+k. Since j is non-local, we use the value from the enclosing scope, namely 5. Thus jonah returns 10, which is printed.

  6. [5 points] What is printed by the following program in an Algol-like language? This is similar to the previous program, except that jonah isn't inside whale. Explain your reasoning. (Again lexical scoping is used.) begin integer j,k; function jonah(k: integer); begin return j+k; end; procedure whale(j: integer); begin print(jonah(j)); end; j := 10; k := 20; whale(5); end;

    The program prints 15. Explanation: j and k are assigned 10 and 20 in the outer scope. Then we call whale, binding j to 5 (in the whale scope). We evaluate jonah(j), i.e. jonah(5). jonah binds 5 to k, and jonah returns j+k. Since j is non-local, we use the value from the enclosing scope -- which in this case is the outermost scope, in which j is 10. Thus jonah returns 15, which is printed.

  7. [5 points] Suppose the following Lisp definitions have been filed in. (setf x 50) (setf y 100) (defun clam (x) (+ x y)) (defun squid (y) (clam 10)) What is the result of evaluating (squid 2) Explain how you computed your answer.

    The result is 110. We evaluate (squid 2). This binds y to 2, and calls clam with an argument of 10. clam evaluates (+ x y), with x bound to 10. y is nonlocal, and since it is lexically scoped, we use the global value of 100. So 110 is returned.

  8. [5 points] This is a continuation of Question 7. Now suppose instead that x and y are dynamically scoped variables, in other words that we filed in the following code instead: (defvar x 50) (defvar y 100) (defun clam (x) (+ x y)) (defun squid (y) (clam 10)) Then what is the result of evaluating (squid 2) Explain how you computed your answer.

    The result is 12. We evaluate (squid 2). This binds y to 2, and calls clam with an argument of 10. clam evaluates (+ x y), with x bound to 10. y is nonlocal, and since it is dynamically scoped, we use the value in the calling context, which is squid, in which y is 2. So 12 is returned.

  9. [6 points] Suppose that in Smalltalk the do: method in the class Array is defined as follows: do: block 1 to: self size do: [:n | block value: (self at: n)] (Note: this is the corrected version of the question -- the original printed version had an error.)

    Now suppose that we evaluate the following code. What is printed to the transcript? Explain.

    | a n sum | a := Array new: 1. a at: 1 put: 10. n := 100. a do: [:k | sum := n+k]. Transcript show: sum printString. 110 is printed. We bind a to an array, and set the first element to 10. n is 100. Then we evaluate the a do: [:k | sum := n+k] statement. This evaluates the block for k bound to each element of the array -- there is only one element. So we assign n+k to sum, which is 100+10=110. Note that the block is lexically scoped and captures its environment of definition, so that n is the variable that holds 100.

    Suppose that Smalltalk used dynamic scoping for nonlocal variables in blocks, rather than static scoping. What would be printed to the transcript then? Explain.

    11 is printed. We bind a to an array, and set the first element to 10. n is 100. Then we evaluate the a do: [:k | sum := n+k] statement. This evaluates the block for k bound to each element of the array -- there is only one element. Since we are using dynamic scoping now, when we evaluate n+k, n is captured by the local variable in the do: method, so its value is 1. k is looked up dynamically, but we still find the value of 10. So we assign n+k to sum, which is 1+10=11, and print 11.

  10. [10 points] Suppose we have classes A, B, and C in Smalltalk. B is a subclass of A, and C is a subclass of B. Each contains a method m1, and A has another method m2, as follows: class A m1 ^ 100 m2 ^self m1 class B m1 ^ super m1 + 5 class C m1 ^ 200 What is returned when you send the m2 message to an instance of A? To an instance of B? To an instance of C? Explain your answers.

    Suppose a, b, and c are instances of A, B, and C respectively.

    a m2 evaluates to 100, since the method for m2 just returns self m1, which returns 100.

    b m2 evaluates to 105. When we send the m2 message to b, Smalltalk doesn't find a method for m2 in the class B, so it looks in A. It finds the method there, and evaluates self m1. The lookup for m1 starts in B again, where we find super m1 + 5. super m1 looks for m1 starting in the superclass of B, namely A, so this returns 100. We then add 5 to 100 and return.

    c m2 evaluates to 200. When we send the m2 message to c, Smalltalk doesn't find a method for m2 in the class C, so it looks first in B, and then in A. It finds the method in A, and evaluates self m1. The lookup for m1 starts in C again, where we find 200, which is returned.

  11. [10 points] Why is a memory leak undesirable? Can you have a memory leak in a language that uses garbage collection for storage management? In a language that uses reference counting? In a language with explicit programmer-controlled deallocation? In each case explain your answer.

    A memory leak is a situation in which memory continues to be used even though it is no longer needed by the program. It is undesirable since one might run out of memory, or, if virtual memory is used, encounter excessive paging. One can't have a memory leak in a system with garbage collection, since the storage for an object is automatically reclaimed when there are no accessible references to the object. (An alternative acceptable answer is that one can have a memory leak in this case, if one accidentally keeps unnecessary pointers to the object.) One can have a memory leak in a system with reference counting, since reference counting can't reclaim circular structures. One can have a memory leak in a system with programmer-controlled deallocation, since the programmer might forget to deallocate the storage after it is no longer needed.

  12. [10 points] Why is a dangling pointer undesirable? Can you have a dangling pointer in a language that uses garbage collection for storage management? In a language that uses reference counting? In a language with explicit programmer-controlled deallocation? In each case explain your answer.

    A dangling pointer is a reference to storage that has been reclaimed and perhaps reallocated for another purpose. A dangling pointer is undesirable since referring to it can produce unexpected results -- the programmer may inadvertently reference or modify an unrelated piece of data, perhaps of a different type (thus resulting in a system that isn't type safe). Dangling pointers can't occur in systems using garbage collection or reference counting, since there is no explicit deallocation -- rather, the system deallocates storage when there are no longer references to it. They can occur in systems with explicit programmer-controlled deallocation, since the programmer might deallocate some storage even though there are still accessible pointers to it.

  13. [0 points] What are the advantages and disadvantages of using cut-and-paste editors in making up exams?

    Since this is a 0 point question, you can say whatever you want ... (and there were definitely some weird answers). Actually this question was supposed to refer to the fact that Question 12 was produced from Question 11 by substituting "dangling pointer" for "memory leak" but nobody noticed ...

  14. [12 points] Consider the following remove rule in Prolog, which removes an element from a list.
    remove([_|Xs],Xs).
    remove([X|Xs],[X|Ys]) :- remove(Xs,Ys).
    
    What answers are produced for the following goals? If there is more than one, give all of the answers. If at some point Prolog gets into an infinite search, say so.
    1. ?- remove([1,2,3,4],[1,3,4]).
      
      yes
      

    2. ?- remove([1,2,3,4],L).
      
      L = [2,3,4] ;
      L = [1,3,4] ;
      L = [1,2,4] ;
      L = [1,2,3] ;
      no
      

    3. ?- remove(A,[1,2,3]).
      
      A = [_9273,1,2,3] ;
      A = [1,_9275,2,3] ;
      A = [1,2,_9277,3] ;
      A = [1,2,3,_9279] ;
      no
      

    4. ?- remove(A,B).
      
      A = [_9260|B],
      B = _9157 ;
      
      A = [_9260,_9264|_9263],
      B = [_9260|_9263] ;
      
      A = [_9260,_9264,_9268|_9267],
      B = [_9260,_9264|_9267] ;
      
      A = [_9260,_9264,_9268,_9272|_9271],
      B = [_9260,_9264,_9268|_9271] ;
       
      etc ...
      

  15. [12 points] Now suppose that the remove rule has been altered by inserting a cut:
    remove([_|Xs],Xs) :- !.
    remove([X|Xs],[X|Ys]) :- remove(Xs,Ys).
    
    What answers are produced for each of the goals in Question 14?
    | ?- remove([1,2,3,4],[1,3,4]).
    
    yes
    | ?- remove([1,2,3,4],L).
    
    L = [2,3,4] ;
    
    no
    | ?- remove(A,[1,2,3]).
    
    A = [_9483,1,2,3] ;
    
    no
    | ?- remove(A,B).
    
    A = [_9470|B],
    B = _9367 ;
    
    no
    | ?-