- [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)))))
- [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))
- [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:
- value
- value-result
- 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.
- [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:
- value
- name
- 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 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.
- [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.
- [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.
- [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.
- [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 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.
- [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.
- [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.
- [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 ...
- [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.
-
?- remove([1,2,3,4],[1,3,4]).
yes
-
?- remove([1,2,3,4],L).
L = [2,3,4] ;
L = [1,3,4] ;
L = [1,2,4] ;
L = [1,2,3] ;
no
-
?- 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
-
?- 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 ...
- [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
| ?-