CS 61A Fall 1994 Midterm 3 solutions
1. Box & pointer diagrams
In the diagrams below, the arrows drawn with dots (......>) are
replaced by mutation with the ones drawn in bangs (!!!!!!>).
You didn't have to show the old ones to get credit.
> (let ((x (list 1 2 3 4)))
(setcar! (cdr x) (cddr x))
x)
(1 (3 4) 3 4)
!!!!!!!!!!!!!
! V
+++ +!++ +++ +++
    !        /
>    > !  >   >   / 
     .         / 
+++ +.++ +++ +++
 .  
 .  
V V V V
1 2 3 4
[Notice that there are only four pairs in this diagram. It would
be an error to draw two extra pairs whose cars are 3 and 4.]
> (let ((x (list 1 2 3 4)))
(setcdr! (cdr x) (caddr x))
x)
(1 2 . 3)
[Note the dot!! Also, it's not (1 (2 . 3)), which would be a proper
(nullterminated) list of two elements.]
+++ +++ +++ +++
           /
>    >   +....>   >   / 
       !        / 
+++ ++!+ +++ +++
  !  
  !  
V V ! V V
!
1 2 !!!!!!> 3 4
> (let ((x (list 1 '(2 3) 4)))
(setcar! x (caddr x))
x)
(4 (2 3) 4)
+++ +++ +++
        /
>    >   >   / 
          / 
+++ +++ +++
  
  V
.\ 
. \!!!!!!!!!!!!!!!!!> 4
. 
. 
V 

1 
V
+++ +++
     /
   >   / 
      / 
+++ +++
 
V V
2 3
[Note that the new arrow points to the 4, not to the pair above it.
It's okay if you wrote another 4 near the 1 instead of drawing an
arrow across to the right. (It's *not* okay to duplicate pairs,
because that obscures the fact that modifying the one pair would
change two parts of the printed representation. But numbers aren't
mutable, so it doesn't really matter whether there's one four or
two fours.)]
Scoring: One point each. Both the printed form and the diagram
had to be right.
2. makealist!
The easiest way to do a problem like this is to use a LET in which
you give names to every relevant piece of the list structure. Then,
inside the LET, you can mutate the pairs in any old order without
risk of error:
(define (makealist! lst)
(if (null? lst)
'done
(let ((car1 (car lst))
(cdr1 (cdr lst))
(car2 (cadr lst))
(cdr2 (cddr lst)))
(setcar! lst cdr1)
(setcdr! lst cdr2)
(setcar! cdr1 car1)
(setcdr! cdr1 car2)
(makealist! cdr2))))
But that's more work than is really needed. If you're clever about
the order in which you do the mutation, you can get by with only one
temporary variable. There are several such solutions; here's one:
(define (makealist! lst)
(if (null? lst)
'done
(let ((tmp (cddr lst)))
(setcdr! (cdr lst) (cadr lst))
(setcar! (cdr lst) (car lst))
(setcar! lst (cdr lst))
(setcdr! lst tmp)
(makealist! tmp))))
Both of these solutions use the original first pair as the topleft pair
of the resulting association list; the original second pair becomes the
bottomleft pair. Several people noticed that you can rearrange the
pairs with no temporary variables at all if you reverse those roles,
so that what used to be the second pair becomes the head of the new
association list. Unfortunately, this isn't quite a correct solution,
because the caller of MAKEALIST! probably has some variable that still
has the original first pair as its value, so the caller will think that
that first pair is the new alist.
Note that you must check (NULL? LST) *before* you try to take its
CAR or CDR.
Scoring of typical solutions:
4 OK
3 Bad/missing base case;
rearranges by mutation but the order isn't quite right;
leaves second pair on top;
uses return value from recursive call but doesn't return a value.
2 No temporary variable (via LET or helper procedure).
1 Uses CONS (or LIST or APPEND, etc).
0 (set! (car lst) ...) or similar confusions.
Solutions using CONS scored lower than other errors because the problem
explicitly said not to allocate new pairs. It's important that you
understand the difference between allocating a pair and making a new
pointer to an alreadyexisting pair. Although it's true that the old
pairs would be reclaimed, so the total storage requirement of the program
wouldn't increase with solutions using CONS, sometimes it's important not
to allow a delay for garbage collection. For example, if your program is
creating video animation in real time, a garbage collection would bring
the animation to a halt for a substantial time, perhaps half a second.
3. Allintegers.
The answer we expected was
(define allintegers
(consstream 0 (interleave integers
(scalestream 1 integers))))
The stream generated by this expression looks like this:
0, 1, 1, 2, 2, 3, 3, 4, 4, ...
You had to understand two key points to get this solution:
1. You can't have all the integers in size order. A stream must have
a definite first element! There's no smallest negative integer. Some
people tried to REVERSE the stream of integers; that's meaningless.
2. You can't APPENDSTREAMS two infinite streams. This is explained
in the handout you got in lecture. Since the first stream will never
finish, it's as if the second stream isn't there at all! (A few people
used MERGE, which works for two sorted, increasing streams, but not
in a case like this where one stream is growing up and one growing down.)
There were many other correct solutions, most of which essentially
reinvented INTERLEAVE. Special mention for the following beautiful
solution (which the student unfortunately didn't get quite right):
(define zerosones (consstream 0 (consstream 1 zerosones)))
(define allintegers (subtractstreams zerosones
(consstream 0 allintegers)))
where subtractstreams is like addstreams with the obvious difference.
Work this out to convince yourself that it really works!
Scoring:
4 correct
3 small mistakes, like leaving out zero
2 appendstream etc.
1 stream of streams, like (consstream negatives positives)
0 not a stream at all
I've heard from several students who think that the streamofstreams
solution was graded too harshly. Here's the reasoning behind this
grading policy: Most errors come from uncertainty about how to
implement an infinite stream successfully. But this error indicates
a misunderstanding about what the stream abstraction is for! Think
about the example of testing whether a number is prime. We create
a stream containing a range of numbers (range 2 14) and then we use
that as an argument to FILTER:
(filter (lambda (number) (= (remainder 15 number) 0))
(range 2 14))
If RANGE returned a stream of streams, then this FILTER wouldn't
work, because the elements of the stream wouldn't be numbers! So,
even though the problem said "a stream containing all the integers"
instead of "a stream containing all the integers, in which each
element is a single integer," it's unreasonable to think that a
stream whose elements aren't numbers would be acceptable.
4. Hyperspace
(defineclass (hyperspace name)
(parent (place name))
(classvars (allhyperspaces '()))
(initialize (set! allhyperspaces (cons self allhyperspaces)))
(method (enter who)
(usual 'enter who)
(if (coinheads?)
(ask who 'godirectlyto (chooserandomly allhyperspaces)))))
It's important that we specialize the ENTER method rather than the
APPEAR method. When APPEAR is invoked, the person hasn't entirely
entered the place yet; in particular, the person's PLACE variable
doesn't reflect where the person actually is.
The overall grading scheme was this:
4 OK
3 You don't understand the specific classes in the project.
2 You don't understand message passing in general.
1 You don't even inherit from the PLACE class.
0 Even worse.
Typical examples:
3 Copied code from PLACE class's ENTER instead of using USUAL.
Didn't SET! the class variable.
Used a global variable instead of a class variable.
Tried to use APPEAR instead of ENTER and didn't quite manage.
2 No initialization at all.
Tried to use messages with wrong number of arguments.
Tried to set variables in other objects directly instead of
sending the object a message.
Made a list of *names* of hyperspace objects instead of a
list of the actual objects.
Group problem:
____________________
G: 

<+
 
everynth > OO
 p: num, lst
____________________ b: (define ...) (help ...)
^



_____________________
E1: 

num = 2 
lst = (she loves you) 
<+
 
help > OO
 p: lst, pos
______________________ b: (cond ...)
^



_____________________
E2: 

lst = (she loves you) 
pos = 1 
______________________
______________________
E3: 

lst = (loves you) > E1
pos = 2 
______________________
______________________
E4: 

lst = (you) > E1
pos = 3 
______________________
______________________
E5: 

lst = () > E1
pos = 4 
______________________
The crucial point is that all of the frames E2 through E5 point back
to E1, not to each other. (Not, for example, E4 to E3.) That's the
meaning of lexical scope.
Scoring:
4 OK.
3 Lexically scoped but with some errors.
2 Correctly dynamically scoped.
1 Dynamically scoped with additional errors (or no E3E5).
0 Even worse.