CSE 341 -- Final

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.

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

  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

  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

  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;

  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;

  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.

  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.

  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. Suppose that Smalltalk used dynamic scoping for nonlocal variables in blocks, rather than static scoping. What would be printed to the transcript then? Explain.

  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.

  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.

  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.

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

  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]).
      
    2. ?- remove([1,2,3,4],L).
      
    3. ?- remove(A,[1,2,3]).
      
    4. ?- remove(A,B).
      

  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?