CS 61A Spring 1992 Midterm 3 solutions
1. Box & pointer
(let ((x (list 1 2 3)))
(set-car! x (cdr x))
x)
Diagram:
[Here is the new arrow:] The dotted ... arrow is no longer in the picture.
|
|
V
+-----------+
| |
| V
+-|-+---+ +---+---+ +---+---+
| | | | | | | | | /|
x -------> | | ----->| | | ----->| | | / |
| . | | | | | | | | |/ |
+-.-+---+ +-|-+---+ +-|-+---+
. | |
. | |
V V V
1 2 3
Prints: ((2 3) 2 3)
[This is still a list of three elements; if you ignore all the CARs
what you have is three CDR-linked pairs. The first element is a
list. The second and third elements are numbers.]
(let ((x (list 1 2 3)))
(set-cdr! (cdr x) (car x))
x)
Diagram:
+---+---+ +---+---+ +---+---+
| | | | | | | | /|
x -------> | | | ----->| | | ....>| | | / |
| | | | | | | | | | | |/ |
+-|-+---+ +-|-+-|-+ +-|-+---+
| | | |
| | | |
V V V V
1 2 1 3
^
n
e
w
[It's fine if you drew the diagram so that the number "1" only
appears once, with two arrows pointing to it. Either form is
acceptable because the eq?/equal? distinction doesn't apply to
atoms, so we don't have to distinguish between "one 1" and
"two 1s." There is only one 1 no matter how the picture looks.]
Prints: (1 2 . 1)
[The resulting structure has two pairs. The second pair has a
non-nil atom as its cdr, so the structure is an improper list.]
Scoring: One point for each diagram, one for each printed answer.
Things that went wrong:
Error 1.1. Thinking that a pointer can point to half of a pair. That is,
people drew diagrams like this for the first problem:
+---+
| | (WRONG! Trying to point to the cdr of x.)
| V
+-|-+---+ +---+---+ +---+---+
| | | | | | | | | /|
x -------> | | ----->| | | ----->| | | / |
| . | | | | | | | | |/ |
+-.-+---+ +-|-+---+ +-|-+---+
. | |
. | |
V V V
1 2 3
Remember that set-car! is NOT a special form. Its arguments are evaluated
before any mutation is done. So (set-car! x (cdr x)) means to set the car
of the first pair to *THE VALUE OF* (cdr x), i.e., the second pair. The
car of the first pair is changed so that it points to the second pair.
Some people who made this mistake went on to show the correct printed
result, but most people who made this mistake then interpreted their own
diagram as meaning that the car of the first pair points to the first pair
itself, so that a circular list would be created: (1 (1 (1 (1 ...)))).
Some people made a similar mistake in the second problem, as if it had been
(set-cdr! (cdr x) x).
Error 1.2. Thinking that set-car! constructs new pairs. These people drew
diagrams like this:
+---+---+ +---+---+ +---+---+
| | | | | | | | /|
x -------> | | ----->| | | ----->| | | / |
| | | | | | | | | | |/ |
+-|-+---+ +-|-+---+ +-|-+---+
| | |
| | |
| V V
|
| 2 3
|
|
| +---+---+ +---+---+
| | | | | | /|
+-------->| | | ----->| | | / |
| | | | | | |/ |
[WRONG! new pairs +-|-+---+ +-|-+---+
can't be created | |
as they are here.] | |
V V
2 3
People who made this mistake generally got the right printed representation.
Why does it matter about the diagram? Because what if we later mutate the
second or third pair of the original list? In the correct diagram you see
that the effect of the mutation appears twice in the result, whereas in this
incorrect diagram the change wouldn't affect the new pairs.
Error 1.3. Thinking, in the first problem, that set-car! means set!
These people changed the diagram not by mutating any pairs, but by making
the symbol X point to the second pair instead of the first. They then
printed (2 3) as the result. This is a pretty fundamental confusion.
2. Stream set-difference.
The mathematical set-difference function is defined even if the second
argument is not a subset of the first. We intended that your programs
work in those cases. Here is the solution we were hoping for:
(define (set-difference big small)
(cond ((empty-stream? big) the-empty-stream)
((empty-stream? small) big)
((= (head big) (head small))
(set-difference (tail big) (tail small)))
((< (head big) (head small))
(cons-stream (head big) (set-difference (tail big) small)))
(else (set-difference big (tail small))) ))
There are five clauses in that cond:
Clause 1. If the universe set has run out, there are no more
candidates for inclusion in the result.
Clause 2. If the set to be excluded has run out, then everything
left in the universe should be in the result.
Clause 3. If the same number is found in both sets, don't
include it in the result, and see what's left after we remove
it from the two arguments.
Clause 4. If the smallest number in the universe set is smaller
than the smallest number to be excluded, then we want to keep
the universe-set number in the result. Note that we do NOT say
(tail small) in this case, because the next number in the universe
may still be smaller than the first excluded number! For example:
universe is {4, 5, 6, 7}
excluded is {6}
Clause 5. If the smallest number in the universe set is bigger
than the smallest number to be excluded, then we don't know yet
whether or not to allow it. Here is an example where we'll want
to keep it:
universe is {4, 5, 6, 7}
excluded is {2, 5, 8}
And here's an example where we'll want to exclude it:
universe is {4, 5, 6, 7}
excluded is {2, 4, 6, 8}
So we have to postpone the decision on this number, but we can
forget about (head small), which is smaller than everything in
the universe.
Nevertheless, we decided that the problem statement might have led you to
believe that the second argument would always be a subset of the first, so
we allowed solutions such as this:
(define (set-difference big small)
(cond ((empty-stream? small) big)
((= (head big) (head small))
(set-difference (tail big) (tail small)))
(else
(cons-stream (head big) (set-difference (tail big) small)) )))
However, many people who had this idea messed up in other ways, such as
saying (tail small) in the last line. (See the comments under clause 4
above.)
Problems 2-4 were graded on the standard 60A scale of
5 correct and elegant
3-4 has the idea
1-2 has an idea
0 has no idea
Things that went wrong:
Error 2.1: No base case. This produces a program that works *ONLY* for
infinite streams. You were told that the streams were "possibly infinite"
but they might be finite too.
A related problem was an incorrect base case, such as
((empty-stream? small) the-empty-stream)
My guess is that a lot of people just habitually assume that the answer
in the base case must be empty, without thinking about the specific problem
at hand.
Error 2.2: List/stream confusion. CAR instead of HEAD, using MAPCAR,
returning '() instead of the-empty-stream, and so on.
Error 2.3: Using MEMQ or something similar. If you used MEMQ itself,
this is also a case of list/stream confusion. But let's suppose you write:
(define (stream-memq element stream)
(cond ((empty-stream? stream) #f)
((eq? element (head stream)) #t)
(else (stream-memq element stream)) ))
You might then try to use this procedure to filter the universe set, either by
(define (set-difference big small) ;WRONG
(filter (lambda (num) (not (stream-memq num small))) big) )
or by the equivalent without filter:
(define (set-difference big small) ;WRONG
(cond ((empty-stream? big) the-empty-stream)
((stream-memq (head big) small)
(set-difference (tail big) small))
(else (cons-stream (head big) (set-difference (tail big) small))) ))
A few people during the exam asked if we'd object to this solution on the
grounds of inefficiency -- it's O(n^2) instead of O(n) -- but the real
problem is that for infinite streams this program doesn't work at all!
The function stream-memq takes infinitely long to decide that a number is
not a member of a stream. So, to take the particular example given in
the problem, if INTEGERS is {1, 2, 3, 4 ...} and PRIMES is {2, 3, 5, 7, ...}
then this program has to compute (stream-memq 1 primes) in order to decide
whether to keep 1 in the result. This process will never terminate, and
we'll never get to think about the second number.
You may think, "yeah, but if we're talking about infinite streams, the
program can never finish anyway, so how come that's okay but this isn't?"
The point is that for any infinite-stream problem we can never reach the
end of the stream, but we must be able to get to any finite point in the
stream. For example, we have a program to generate the stream of prime
numbers. Of course we can never actually see all of them, but we can ask
for the 147th prime and we should be able to carry out that computation in
finite time. This erroneous version of set-difference can't even get to the
first element of its result in finite time!
This point about making sure we can get partial results from a stream in
finite time is central to the whole idea of using streams, and if you
didn't get it, that counts as not having the idea.
On the other hand, there is a way to use a memq-like solution that takes
advantage of the ordering of the numbers in the streams:
(define (ordered-memq element stream)
(cond ((empty-stream? stream) #f)
((= element (head stream)) #t)
((< element (head stream)) #f) ; THIS IS THE CRUCIAL PART
(else (ordered-memq element (tail stream))) ))
This procedure always computes a result in finite time. It can be used
instead of stream-memq in the two incorrect versions above and they'll be
correct.
Error 2.4: Putting things in your program that are specifically about
integers or prime numbers. As I keep saying, when we give an example of
how your program might be used, it's just an example! You were asked to
write a general procedure that works for any two ordered streams. If you
don't understand that, it counts as not having any idea. Zero points.
3. Magic wand objects.
(define-class (wand metal destination)
(parent (thing (word metal '-wand)))
(method (magic)
(ask (ask self 'possessor) 'go-directly-to destination) ))
The most crucial point was to understand that a wand is a kind of thing,
and what that implies about its parenthood.
Error 3.1: Not having a parent at all, or having the wrong parent,
or having a parent but not using inheritance. Some people duplicated
all the methods of things in the class definition for wands.
Error 3.2: Not instantiating the parent properly with the right name
and nothing else. Some people said (parent (thing metal destination))
which I take to be pattern-matching without understanding. Even if you
thought that things required an initial place as an instantiation argument,
it wouldn't be *that* place -- it's silly to put the wand in the place that
it takes you to. What good does that do? You're already there when you
pick it up!
Error 3.3: Not knowing how to find out the wand's possessor. Some people
went to lots of extra trouble to have a local state variable in the wand
class. That's silly; you're just asking for trouble if your object has
two different variables that are supposed to have the same value but might
drift apart as one is changed but not the other.
4. Environments and scope
(a) We are evaluating ((upper 'next) 3). First let's do the (upper 'next)
part. This is a procedure invocation, so it creates a new frame. In that
frame we bind the procedure's formal parameter to its actual argument:
message ==> next
The frame extends the environment in which the procedure (upper) was
created, i.e., the frame that has bindings for my-counter and self.
Within this new frame we evaluate the body of upper. That body is
(cond ((eq? message 'next) (lambda (amount) ...)) ...)
Since message is, in fact, the word NEXT, we evaluate the lambda expression.
This creates a procedure object (two bubbles). The left bubble has
param: amount
body: (set! count (+ count amount))
count
The right bubble points to the environment in which we saw the lambda,
i.e., the new frame you just drew.
That's the end of evaluating (upper 'next). Now we have to evaluate
( 3)
That is, we have to invoke the procedure that you just created. To do
that we create a new frame, extending the frame you drew earlier, with
the binding
amount ==> 3
In this new frame we're going to try to evaluate the body of the method,
and that gets us into part (b) of the question. Stop here in drawing
the environment diagram.
(b) What goes wrong? The body of the method wants to do
(set! count (+ count amount))
That expression has five symbols in it (counting "count" twice). Each of
them must be looked up in the current environment. What is the current
environment? It contains four frames: the two you drew, the one that has
a binding for my-counter, and the global frame.
The only frame that has a binding for COUNT is not part of this environment.
Therefore we get a "variable COUNT not bound" error message.
The worst thing people did in this problem, from the point of view of the
graders at least, was to write enormous essays! It would have been plenty
just to say:
The only frame that has a binding for COUNT is not part of the current
environment when the SET! is evaluated. Therefore we get a "variable
COUNT not bound" error message.
For that matter, it's possible to explain the problem without explicit
reference to the environment diagram, by saying:
There is no instance variable COUNT in the lexical scope of the
INCREMENTER class definition.
But we did ask you to explain with reference to the diagram. (We'd like you
to understand, by the way, why these two explanations mean exactly the same
thing, even though they are expressed very differently.)
Go back to the questions
Back to the Midterm/Final page