CS 61A Midterm 3 solutions Fall 2008
1. Box and pointer.
(let ((x (list 'a 'b 'c)))
(SET! (CAR X) (CADDR X))
x)
Result: ERROR
Of course the SET! expression should be (setcar! x (caddr x)).
SET! is a special form whose first argument must be a symbol,
not an arbitrary expression.
Scoring: 2 points, all or nothing.
(define a (list (list 3) 5))
(define b (APPEND A A))
(setcar! (cdr b) (caddr b))
(setcar! a (cons 3 4))
b
Result: ((3) (3) (3 . 4) 5)
box and pointer diagram key:
XX X/ original pairs
** pair made by (CONS 3 4)

  original pointers

:
: original pointers eliminated by mutation
:
!
=== ! new pointers added by mutation
!
a

V
b >XX>XX>XX>X/
 :\ :\ 
 : ! : ! 
 V ! : V V
 5 ! : **>4 5
 ! : 
 ! : 
 ! : V
 ! : 3
 ! :
+++>X/


V
3
The key to understanding this diagram is knowing how APPEND works:
it makes a copy of /all but the last/ argument, but shares memory
with the last one. This is why the last two pairs of B are the
same as the two pairs of A, and this is why there is only one pair
representing all instances of (3) in the diagram. And this is why
changing the car of A changes the third element, but not the first
element, of B.
Scoring: One point for the printed result, one point for the diagram.
2. Mutation.
The two parts of this question start with the same diagram before the
mutation you have to provide:
foo >XX>XX>X/
  
V V V
1 2 XX>X/
 
V V
3 4
bar >XX>XX>X/
  
 V V
 c d
V
XX>X/
 
V V
a b
The value of BAR in this initial diagram is ((a b) c d).
In the first problem, you are asked to change the value of BAR to
((a b (3 4)) c d). That is, you are supposed to add one new element, the
list (3 4), at the end of the list (a b) which is the first element of BAR.
To add an element at the end of a list, you SETCDR! the last pair of the
list's spine to point, /not to the element itself/, but to a spine pair whose
car is the element and whose cdr is the empty list. So this is the change:
+==========+
! !
V !
foo >XX>XX>X/ !
   !
V V V !
1 2 XX>X/ !
  !
V V !
3 4 !
!
bar >XX>XX>X/ !
   !
 V V !
 c d !
V !
XX>XX================+
 
V V
a b
The pair we're changing is the CDR of the list (A B), which is the CAR of
BAR, so we want to (SETCDR! (CDAR BAR) ...). The pair we want to point to
is the third spine pair of FOO, so the desired solution is
(SETCDR! (CDAR BAR) (CDDR FOO))
Scoring: One point for SETCDR!, one point for (CDAR BAR), one point
for (CDDR FOO). No points if the expression starts with SET!.
Since we are changing the cdr of the last spine pair of a list, it turns
out that the following expressions are equivalent to the given solution:
(APPEND! (CAR BAR) (CDDR FOO))
(APPEND! (CDAR BAR) (CDDR FOO))
We accepted either of those, scored as above except APPEND! instead of
SETCDR!. (No points for APPEND instead of APPEND!.)
In the second problem, you are asked to change ((a b) c d) to
(((2 (3 4)) b) c d). In other words, you are asked to replace the first
element of (a b) with something different. That means you SETCAR! the
first pair of the spine of (a b):
+===================+
! !
! V
! foo >XX>XX>X/
!   
! V V V
! 1 2 XX>X/
!  
! V V
! 3 4
!
! bar >XX>XX>X/
!   
!  V V
!  c d
! V
+============XX>X/
: 
V V
a b
So the solution is (SETCAR! (CAR BAR) (CDR FOO)).
Scoring: Same as the first part, except that in this problem there's no
equivalent solution using APPEND!.
3. OOP below the line.
(a) A class variable is a /local state variable/ of /the class constructor
procedure/. We make local state variables by putting a LET /outside/ the
lambda that creates the procedure. So we want
(define makeperson
(let ((people '()))
(lambda (name)
...
so the answer is Point A.
(b) SELF in the OOP language is a name for the dispatch procedure that
represents an object. In the ordinaryScheme code we're writing as an
equivalent to the defineclass code, there is nothing called SELF! There
is something called MAKEPERSON, but that's the /class/ constructor, not
the instance. So the answer is DISPATCH.
(c) It can't be Point B because DISPATCH isn't defined at that point.
It can't be Point C because that would cause the initialization to be done
every time a message is sent to the object! It has to be during the
creation of the object, but somewhere where DISPATCH exists. So the answer
is Point E.
(d) Point D corresponds to the expression (ASK OTHER 'NAME) in the
defineclass code. In the plainScheme version, there's no ASK; we just
invoke the object's dispatch procedure: (OTHER 'NAME). But the result of
calling the dispatch procedure with a message argument is that it returns
/a method/, i.e., a procedure; we have to invoke that procedure to get the
result we want, the other person's name. So the answer is ((OTHER 'NAME)).
Scoring: 1.5 points each. In part (d), 0.5 points for (OTHER 'NAME).
The total is rounded down to an integer value.
4. Vectors.
During the exam, many students asked questions that were answered in the
introductory text on page 6 of the exam booklet. This was definitely a
question for which you should have spent much more time reading than writing.
As you'll see below, the actual solution is not that much code, provided that
you understand what you're doing.
We chose insertion sort rather than some other sorting algorithm because
you'd already seen the list version, when we talked about orders of growth
of time in algorithms.
(a) INSERT! works by shifting some elements of the vector one slot leftward.
So the nonbase case of INSERT! will do one such shift, plus a recursive
call. There are two base cases: running off the right end of the vector,
or finding an element larger than the one we want to insert.
It's important to understand that an invariant of this procedure is that
the slot to the left of FROM always exists (FROM is never zero), and is
always free (either the new value or some shiftedleft value used to be in
it).
(define (insert! vect value from to)
(cond ((> from to) ; fall off right edge
(vectorset! vect to value))
((< value (vectorref vect from))
(vectorset! vect ( from 1) value))
(else (vectorset! vect ( from 1) (vectorref vect from))
(insert! vect value (+ from 1) to))))
That's it! Some students worried about how to handle two equal values in
the vector, but if they're equal, it doesn't matter which goes first, so we
were happy with either < or <= as the comparison operator.
Scoring:
We checked whether your procedure could insert at the beginning of the region,
in the middle, and at the end.
4 correct
3 trivial error (off by 1, sort backwards)
2 two out of three of beginning, middle, end
1 an idea
0 other
(b) SORT! needs a helper procedure, because it doesn't take an index as an
argument, so we need one to keep track of where we're up to in the vector.
As page 6 makes clear, we are inserting elements from right to left. We
start with one alreadysorted element, so from = to = length1. There are
various ways to write this, depending on what index you want to use as the
argument to the helper. The candidates are FROM (the index of the first
alreadysorted element) and the position of VALUE (the value to be inserted).
(TO never changes from length1, so it doesn't have to be an argument,
although it could be.) In the following solution, I use FROM as the index:
(define (sort! vect)
(define (help index)
(cond ((= index 0) ; when from=0 there's nothing left to insert
vect)
(else (insert! vect (vectorref vec ( index 1))
index ( (vectorlength vect) 1))
(help ( index 1)))))
(help ( (vectorlength vect) 1)))
Scoring:
4 correct
3 trivial error
2 has the idea
1 has an idea
0 other
5. Streams.
The quickest way to solve this problem is to observe that addition is
associative, so the given code is equivalent to
(define mystery
(consstream 1
(streammap + (STREAMMAP + ONES INTS) mystery)))
The capitalized part obviously generates the stream of integers starting
from 2. So we draw this picture:
mystery 1 ____ ____ ____ ____
intsfrom2 2 3 4 5 6
     
sum 3 ____ ____ ____ ____
As we compute numbers in the SUM line, we copy them up to the MYSTERY line
one space over:
mystery 1 3 ____ ____ ____
intsfrom2 2 3 4 5 6
     
sum 3 6 ____ ____ ____
mystery 1 3 6 ____ ____
intsfrom2 2 3 4 5 6
     
sum 3 6 10 ____ ____
mystery 1 3 6 10 ____
intsfrom2 2 3 4 5 6
     
sum 3 6 10 15 ____
mystery 1 3 6 10 15
intsfrom2 2 3 4 5 6
     
sum 3 6 10 15 21
So the answer is 1, 3, 6, 10, 15. (These are the "triangle numbers.")
Scoring:
5 correct
4 one arithmetic error (which then propagates to later numbers), e.g.,
1, 4, 7, 11, 16; 1, 2, 5, 9, 14.
3 ints instead of intsfrom2: 1, 2, 4, 7, 11.
3 add 1 only to first int, not all ints: 1, 3, 5, 8, 12.
0 Anything with a constant increment between elements, e.g.:
1, 2, 3, 4, 5
1, 3, 5, 7, 9
4, 6, 8, 10, 12
1, 3, 4, 5, 6
6. Concurrency.
We /did/ give the hint "Read the code carefully! We didn't make a mistake;
this is what we intended to write." In other words, you were warned that
something in this problem is a little peculiar.
The thing you had to notice was that the first thunk in the parallelexecute
just computes a value, but doesn't change X. So we can ignore it; the
problem is equivalent to
(define x 16)
(parallelexecute (lambda () (set! x (* x 2)))
(lambda () (set! x (+ x 1))))
There are two possible correct answers and two possible incorrect answers.
The correct ones are consistent with a sequential ordering of the tasks,
either
(define x 16)
(set! x (* x 2)) ==> 32
(set! x (+ x 1)) ==> 33
or
(define x 16)
(set! x (+ x 1)) ==> 17
(set! x (* x 2)) ==> 34
Since each of the relevant tasks just loads X once, the only possible wrong
answers are from sequences of LOAD, LOAD, STORE, STORE, so that one of the
two threads is overruled by the other. So in effect we do
(define x 16)
(set! x (* x 2)) ==> 32
or
(define x 16)
(set! x (+ x 1)) ==> 17
So the answers are
(a) 33, 34, 32, 17
(b) 33, 34
Scoring: (a) was worth 4 points. We subtracted 1 for each missing or wrong
value, and we subtracted 1 for each extra answer, except that the penalty for
extra answers was limited to 2. (In other words, 1 for one extra answer,
2 for more than one extra answer.)
(b) was worth 2 points, computed with the same formula.
Of course the most common mistake was to work as if the first thunk were
(lambda () (set! x (if (even? x) (+ x 5) ( x 5))))
This gave rise to many extra answers for both (a) and (b); people who did
include the correct answers therefore got 2 points for (a) and 0 for (b).
Group problem (environment diagram):
(define y 6)
adds binding Y=6 to global frame (G).
(define (foo y)
(lambda (x) (+ x y)))
creates procedure P1 with parameter Y and body (LAMBDA ...),
right bubble points to G.
adds binding FOO=P1 to G.
The LAMBDA expression is not evaluated at this time.
(define (baz x)
(let ((+ *)
(y 10)
(garply (foo (+ x y))))
(garply y)))
creates procedure P2 with parameter X and body (LET ...),
right bubble points to G.
adds binding BAZ=P2 to G.
The LET expression is not evaluated at this time.
(baz 10)
This is a procedure call, so we first evaluate subexpressions.
The value of BAZ is P2; the value of 10 is 10.
Now we invoke P2 with argument 10. This creates a frame E1,
pointing to G (because P2's right bubble points to G), with the
binding X=10.
With E1 as current environment, we evaluate the body of P2, which is
the LET expression. It's worth expanding this to what it abbreviates,
a LAMBDA expression which is surrounded by its invocation:
((lambda (+ y garply)
(garply y))
*
10
(foo (+ x y)))
This is a procedure call, so we start by evaluating its four
subexpressions:
The LAMBDA creates procedure P3, parameters +, Y, GARPLY,
body (GARPLY Y), right bubble points to E1.
* is the multiplication primitive, 10 is 10.
(FOO (+ X Y)) is a procedure call, so we evaluate its subexpressions:
FOO is procedure P1.
(+ X Y) is a procedure call, so we evaluate its
subexpressions: + is the /addition/ primitive, X=10, /Y=6/.
Then we call the addition primitive, which returns 16.
Now we invoke P1 (i.e., FOO). To do this we create a new frame E2,
which extends /G/ (because P1's right bubble points to G), with the
binding Y=16. P1's body is a LAMBDA expression, so it creates
procedure P4, with parameter X and body (+ X Y), whose right bubble
points to E2. P4 is the return value from P1.
/Now/ we can call P3. This creates a new frame, E3, extending E1
(because P3's right bubble points to E1), with three bindings:
+ is the multiplication primitive (but this binding will never be
used for anything!), Y=10, GARPLY=P4.
The body of P3 is (GARPLY Y). We evaluate this in the current
environment, which is E3. So we evaluate the subexpressions in
E3, where we find GARPLY=P4, Y=/10/ (not 16, which isn't in the
current environment). So we call P4 with argument 10.
This creates frame E4, extending E2 (because that's where P4's right
bubble points), containing the binding X=10. With E4 as current
environment, we evaluate the body of P4, which is (+ X Y). This
is a procedure call, so we evaluate its subexpressions, which are
all symbols. For the + symbol, the only binding in our environment
is the addition primitive, in G. (E3, which binds + to the
multiplication primitive, is not in the current environment.)
We find X=10 in frame E4, and Y=16 in E2.
So the return value from GARPLY, which is also the return value
from the LET, and therefore the return value from BAZ, is 26
(10+16).
Scoring: We allowed the omission of the LET procedure, P3. Since FOO and
BAZ are plain old toplevel procedures, I figured (incorrectly, as it turns
out) that everyone would get those correct in the diagram. This leaves
four frames, one procedure (P4), and six arrows: the ones from the four
frames to the environments they extend, the one from P4's right bubble,
and the one for the binding of GARPLY. So my first thought was to score
1 for a missing frame, 0.5 for an incorrect arrow. But students found
other ways to make mistakes. One was to use the substitution model, e.g.,
showing the body of P4 as (+ X 16) by substituting argument value 16 for
parameter Y in the call to FOO. This was a halfpoint error. Another
was normal order; for example, in E4, binding X to Y rather than to 10.
That was a onepoint error.
But these errors were combined in complicated ways; sometimes the consistent
working out of an early error led to more halfpoint losses than it really
seemed to deserve, and sometimes a late error seemed so wrongheaded that
it deserved a lower score than the formula gave. I tried to keep to the
usual correct/trivial error/the idea/an idea/other scale. The papers with
grades of 4, 3, and 0 were easy to grade, but the difference between 1 and 2
was harder to decide.
One common mistake was to use dynamic scope, which would make E2 extend E1.
Another was to think that E2 should extend E3, although this is actually
backwards in time!
Another common error was to treat the definition of BAZ as though the LET
established local state variables for the procedure, i.e., as if the code
were
(define baz
(let (...)
(lambda (x) (garply y))))
Another pretty common error, surprising to me, was to merge frames, e.g.,
adding the LET variables as additional bindings in E1 rather than creating
a new frame E3.
A few groups bound GARPLY to either FOO or BAZ, rather than to a newly
created procedure.
I didn't take points off for the /very/ common error of labelling E2 as E3
and vice versa, as long as the arrows pointed to the right places.
Please be careful about putting arrowheads at one end of your arrows! This
is especially important if you're also careless about whether each end of
the arrow is inside or outside the box.
Many groups who had pretty bizarre diagrams nevertheless got the answer 26.
I consider this a weakness, not a strength, of those papers; the ultimate
result of the computation should be consistent with the diagram! But I didn't
adjust the score either way based on the final answer.