CS 61A		Fall 2000		Midterm 3 solutions

1.  Pi-approximation stream

(a) numerators {2 4 4 6 6 8 ...} implicitly

"Implicit definition" really means not only that no procedures are
defined, but also that the stream itself is used in the definition,
so the answer we expected was

	(define numerator
	  (cons-stream 2
	    (cons-stream 4
	      (stream-map (lambda (x) (+ x 2)) numerator))))

This is slightly different from most of the examples in the book
because it needs two pump-priming cons-streams in order to get the
special case of only one 2 at the beginning right.

But since we didn't explicitly require using the stream itself in
the definition, we also accepted

	(define numerator
	  (cons-stream 2 (interleave (stream-cdr evens)
				     (stream-cdr evens))))

where EVENS is the stream {2 4 6 8 10 ...} that can be generated in
various ways, such as (scale-stream integers 2).

A truly implicit (self-referential) definition with only one cons-stream
can be made by generating the helper stream {2 0 2 0 2 0 ...} in one of
several possible ways and adding it to the numerator stream:

	(define numerator
	  (cons-stream 2
	    (add-streams numerator
			 (interleave (scale-stream ones 2)
				     (scale-stream ones 0)))))

Scoring:  Two points for any of the above (and correct variants).
One point for a correct computation that didn't follow the pattern
(starting with cons-stream).  No points for solutions using recursive
procedures or ones that generate incorrect streams.

The most common incorrect solution was

	(define numerator	;; WRONG!
	  (cons-stream 2
	    (interleave (stream-map (lambda (x) (+ x 2)) numerator)
			(stream-map (lambda (x) (+ x 2)) numerator))))

This was really well-motivated, and it's too bad it doesn't work, but
you really want to add 2 only to half the elements of the stream!  In
fact this generates {2 4 4 6 6 6 6 8 8 8 8 8 8 8 8 10 10 10 10 10 ...}
with twice as many copies of each larger number.


(b) Denominator from numerator

The solution we expected was

	(define denominator (stream-map (lambda (x) (- x 1))
					(stream-cdr numerator)))

The stream-cdr is needed because numerator has that single 2 at the
beginning, whereas denominator is all pairs of equal values.  An
equivalent solution was

	(define denominator (stream-map -
					(stream-cdr numerator)
					ones))

A minor variation was to account for that beginning 2 not by removing
it but by turning it into a pair of equal values:

	(define denominator (stream-map (lambda (x) (+ x 1))
					(cons-stream 2 numerator)))

Note that we now have to add one instead of subtracting one.

Another elegant solution adds the stream {1 -1 1 -1 1 -1 ...} to
numerator, avoiding the need to add or remove an element:

	(define denominator (stream-map +
					numerator
					(stream-map
					 (lambda (x) (if (even? x) -1 1))
					 integers)))

Scoring:  Two points for any of the above (and correct variants).
One point for a correct solution that violated the given pattern by
leaving out stream-map, or for a solution that was correct except for
adding 1 instead of subtracting or vice versa.  No points for a
solution that doesn't use numerator.


(c)  Combining the two.

The only really good solution was

	(define pi/4-stream
	  (series-stream *
			 (stream-map / numerator denominator)))

Since each term in the approximation stream is the product of the previous
term and a new value, the combiner really must be *.  And the new value is
formed by dividing an element of numerator by the corresponding element
of denominator.

An okay but silly variation was to use
	(lambda (a b) (/ a b))
instead of just /.  Did you think the word LAMBDA has to appear in the
first argument to stream-map?  The argument has to be a procedure, but
any expression whose value is a procedure can be used.


Scoring:  This was basically right or wrong.  There were a few correct
but overly complicated variations on the above solution, which got two
points; incorrect solutions got no points.

A typical wrong solution was one that tried to do the job of series-stream
in the argument to series-stream (multiplying elements of numerator and
denominator).


2.  Parallelism in real life.

For this question we got several essays trying to justify solutions other
than the obvious ones.  For the most part we didn't accept these -- the
problem did say "the answer which BEST describes..." -- with one exception
noted in part (b) below.

(a) People at tables can't get food; people waiting for food can't get
tables.  This is a potential deadlock, and that was the answer we wanted.
It's true that the deadlock might not happen, because some people at
tables may actually have food and might eventually leave, letting the line
continue moving.  It depends partly on whether the restaurant servers
believe you when you say "it's okay to serve me because my friend is already
sitting at a table and saving me a seat."  Even if they do, a deadlock can
happen if someone comes in alone (so doesn't have a friend to grab a table)
and when that person gets to the front of the line, all the tables are filled
with friends of people behind him/her in line.

You may think "it's UNFAIR for people who don't have food yet to hog the
tables" or "it's INEFFICIENT for people to sit at tables when they don't
have food yet."  But these are technical terms about parallellism errors,
and the particular situation described in the problem is technically a
deadlock.

(b) There are several inspectors serving several lines in parallel, but
there's only one metal detector, which acts as a single serializer for
all the inspectors.  This is inefficiency (too much serialization).

Some people argued that the metal detector is best viewed as an actual
resource, not as a serializer, and so this is correct, if unfortunate,
serialization of a shared resource.  We accepted that reasoning, so we
also accepted "none of the above" as a correct answer.

(c) You write while your friend researches.  This is correct parallelism,
with two processors carrying out parallelizable tasks.

Some people argued that the tasks *aren't* correctly parallellizable
because the research has to come before the writing.  That idea has some
merit for a short paper, but you wouldn't be writing a short paper as a
team anyway; it'd be an individual assignment.  We meant that you were
writing one part of the paper while your friend was researching a different
part of the paper.

Some people said "unfairness" because you have to do the boring writing
while your friend is off doing the interesting research.  One of the
nice things about working in groups is that sometimes you're lucky and
your interests complement those of your friend!  But even if you would
feel an unfairness in this arrangement, it's not unfair in the technical
sense -- a parallelism unfairness would be if the librarians always get
books for your friend before they get books for you.

Scoring: One point each.


3.  Marbles with a class variable

The key point here is that the list of colors is shared by all the
marbles; it isn't a list per marble.  Therefore, the LET that creates
the variable must come outside the LAMBDA that creates the class.
Choices 1 and 3 have the LET inside that LAMBDA, but outside the
LAMBDA that represents an instance, so it would be creating an instance
variable; each marble would list only its own color.

What distinguishes answers 2 and 4 is the position of the SET! that adds
a particular marble's color to the list of colors.  Should that happen
when the marble (instance) is created, or when it's invoked?  Clearly
when it's created.  So the SET! has to be inside the class LAMBDA, but
not inside the instance LAMBDA.  This is the case in answer 4 (and also
in answer 3, but that was ruled out in the previous paragraph).

Scoring: One point for choosing (only) the fourth definition.


4.  Parallel marriages.

We apologize for two errors in the procedures we gave you.  In part (a) we
got the order of arguments to insert-queue wrong; it should have been

	(define (vegas-goers man woman)
	  (insert-queue! man-queue man)
	  (insert-queue! woman-queue woman))

In part (b) we put the local variables GROOM and BRIDE inside an internal
procedure and then used them outside of that procedure.  We should have said

	(define (justice name)
	  (let ((groom #F) (bride #F))
	    ((s (lambda ()
		  (set! groom (front-queue man-queue))
		  (set! bride (front-queue woman-queue))
		  (delete-queue! man-queue)
		  (delete-queue! woman-queue))))
	    (marry groom bride)
	    (display "Congratulations!")))

(a) This is indeed dangerous, because we could get incorrect results.
INSERT-QUEUE! needs to be serialized.  For example, if the queue is
empty, and two couples try to insert themselves at the same time, they
might both get #T from (empty-queue? queue) and therefore both try to
make themsevles the first element.  One of them would end up not queued
at all.  Even if the queue isn't empty, the SET-CDR! and SET-REAR-PTR!
calls near the end of INSERT-QUEUE! must be done atomically, or else a
queue entry will be lost.

By the way, the danger is that someone will be dropped from the queue
completely, not that people will be added out of order.  So Paul might
end up marrying Yoko, but then Linda won't have anyone to marry; she
can't marry John if Paul marries Yoko.

There can't be a deadlock if there is no serialization!  That answer
couldn't be right.

(b) Although there was an error in our code, it wasn't an error in
parallelism.  The sentence "Because queues, not justices..." makes
the "This is incorrect" choice wrong despite our bug.  If the queues
did the serialization, nothing would prevent justice A getting groom #1,
then justice B getting groom #2 and bride #1, and then justice A getting
bride #2.  The processing of both queues must be a single atomic
transaction, as in Alyssa's program, which is correct in its handling
of serialization.

Scoring: one point each.


5.  Implementing sorted lists.

The fact that the lists are sorted really doesn't affect the heart of the
problem, which is about our ability to modify a data structure.  In effect
this question is asking why SICP's tables are represented using a header
of *TABLE* as a first element even when the table is empty.

(a) Can we represent an empty data structure using the empty list?
No, we can't; there is nothing for INSERT! to mutate when inserting the
first element.  (This is the second of the answers given.)

Why can't we say

	(define (insert! element slist)		;; WRONG!
	  (if (null? slist)
	      (set! slist (cons element '()))
	      ...))

The SET! inside INSERT! changes INSERT!'s local variable SLIST, but
doesn't affect the global variables SLIST1 or SLIST2 in the examples.
So the result of (insert! 1 slist1) would indeed be to create a list
containing 1 as its only element, but that list would *not* be pointed
to by the variable SLIST1, which still points to the empty list.

This is a way in which SET! and SET-CAR!/SET-CDR! are different.  SET! can
only change the specific variable used as its first argument -- in this
example, the variable SLIST that's local to INSERT!.  But if a global and
a local variable point to the same pair, then the procedure can use
SET-CAR! or SET-CDR! on (the pair pointed to by) its local variable, and
the mutation will affect the value as seen by the global variable.

(b) Okay, so we need a header pair to represent an empty sorted list, so
that the first insertion will be possible.  So let's make one:

	(define the-empty-sorted-list		;; WRONG!
	  (cons 'sorted-list '()))

Why is this wrong?  With this implementation, SLIST1 and SLIST2 are the
same pair, the one made when we defined the-empty-sorted-list.  So any
insertions made to either one will affect the other -- they share the
same memory, as the third answer points out.

The correct solution is to construct a new pair for each new sorted list:

	(define (make-sorted-list)
	  (cons 'sorted-list '()))

	(define slist1 (make-sorted-list))
	(define slist2 (make-sorted-list))

Here we call a constructor procedure for each of the sorted lists; the
procedure makes a new pair to serve as the header for each list.

It's because of the need for a header pair that the display procedure
SORTED->REGULAR is needed; this procedure just removes the header for
display purposes:

	(define (sorted->regular slist)
	  (cdr slist))

Scoring:  Two points each, all or nothing.


Group question: environment diagram

The first DEFINE is an abbreviation for

	(define bar (lambda (x) (let ...)))

So the implicit LAMBDA expression creates a procedure

	P1: param=x, body=(let ...), env=Global

It's in the global environment because that's always the current
environment for expressions typed at the Scheme prompt, as opposed to
expressions inside a procedure body.  Then in the global environment
we bind BAR to this:

	G: BAR -> P1

That's all that happens when Scheme evaluates the first expression; the
stuff in the procedure body is not evaluated at this time.

The second expression is (define foo (bar 4)).  First we have to
evaluate the procedure call (bar 4).  We do this by creating a new
environment in which BAR's parameter (x) is bound to the argument
value (4), extending the procedure's defining environment:

	E1: X -> 4, extends G

Using E1 as the current environment, we evaluate the procedure body,
which is the expression

	(let ((z (lambda (b) ...)) (c x))
	  (lambda (x) ...))

LET abbreviates a lambda and a procedure call, as follows:

	( (lambda (z c) (lambda (x) ...))  (lambda (b) ...) x )
	  -------------------------------  ---------------- -
	      implicit procedure               arg for z    c

To evaluate a procedure call, we first evaluate all the subexpressions.
Two of them are LAMBDA expressions, which create procedures:

	P2: params=z,c,  body=(lambda (x) ...),  env=E1
	P3: param=b,     body=(* x b),           env=E1

These procedures have E1 as their defining environment because that's
the current environment right now.

The third expression, X, is evaluated by looking for the symbol X in E1.
We find it; its value is 4.

Now that we've evaluated the subexpressions, we call procedure P2 with
arguments P3 and 4.  We do this by creating a new environment binding
P2's parameters to these arguments and extending P2's defining environment:

	E2: Z -> P3,  C -> 4,  extends E1

Note that the value of C is 4, not X!  Parameters are bound to the actual
argument *values*, not to the expressions that give rise to the values.
Similarly, the value of Z is P3, not (* X B) or (LAMBDA (B) (* X B)).

With E2 as the current environment, we now evaluate the body of P2.  That
body is a lambda expression, so it creates a procedure:

	P4: param=x,  body=(set! ...)...,  env=E2

P4 is the value of the lambda expression, so it's the value returned by
the call to P2, so it's the value returned by the LET, so it's the value
returned by (bar 4), and so back in the global environment we bind FOO
to this value:

	G:  BAR -> P1,  FOO -> P4

That's it for the second expression.  We invoked P2 because it was
created by a LET, which both creates and invokes a procedure, but nothing
says to invoke P3 or P4 so far.

Now for the third expression, (FOO 3).  This is a procedure call; we
evaluate the subexpressions (looking up FOO in the global environment and
noticing that 3 is self-evaluating).  Then we invoke P4, which is the value
of FOO, with 3 as its argument.  This creates a new environment:

	E3: X -> 3,  extends E2

With E3 as the current environment, we evaluate the body of P4.  This
body contains two expressions.  The first is

	(set! c (z (* c x)))

To evaluate this, we must first evaluate (z (* c x)), which is a procedure
call.  We evaluate the subexpression Z by looking it up in E3, the current
environment.  We don't find it directly in E3, but E3 extends E2, where Z
is bound to P3.  The subexpression (* c x) is a procedure call.  We evaluate
the subexpressions, finding * in G (it's bound to the primitive multiply
procedure), C in E2 (where it's bound to 4), and X in E3 (bound to 3).
Since the multiply procedure is primitive, we apply it by magic, getting
the answer 12 without creating a new environment.  This value 12 is the
argument to Z (which is actually P3).  So we create a new environment for
the call to P3:

	E4: B -> 12,  extends E1

The body of P3 is (* x b).  We look up these three symbols and find
* in the global environment (bound to the primitive multiplication
procedure), X in E1 (not in E3, which isn't part of the current
environment!) (bound in E1 to 4), and B in E4, bound to 12.  By magic
we multiply 4 by 12 and get the answer 48.

We did that to evaluate the second argument to (set! c ...).  Now that
we know the argument value, we can find a binding for C in what's now
the current environment, the one in which we saw the SET! expression,
namely E3.  There's no binding for C in E3's first frame, but we find
one in E2, which E3 extends.  There we change C's binding from 4 to 48.

The second and last expression in the body of P4 is just C, so we
return the value 48 that we just put there.

To summarize, the diagram has five frames (including G) and four procedures:

	G:  BAR -> P1,  FOO -> P4
	E1: X -> 4,                extends G
	E2: Z -> P3,  C -> 4,      extends E1
	E3: X -> 3,                extends E2
	E4: B -> 12,               extends E1

	P1: param=x,     body=(let ...),         env=Global
	P2: params=z,c,  body=(lambda (x) ...),  env=E1
	P3: param=b,     body=(* x b),           env=E1
	P4: param=x,     body=(set! ...)...,     env=E2

Common errors:

The most common was having P3's right bubble point to E2 instead of E1,
probably from thinking that the lambda expression was within the scope
of the LET.  But the expressions that provide values for the LET variables
must be computed before the LET variables are bound!  This generally led to
having E4 extend E2 instead of E1.

Several people left out E4 altogether.

One mistake I couldn't understand was that a lot of people had FOO bound
to E2 instead of P4.  An environment can't be the value of a variable!
(Environments are not first class in Scheme.)

As mentioned above, too many people bound the E2 variables to expressions
[C -> X, Z -> (lambda (b) (* x b))] rather than to the values of those
expressions.  (In effect you are inventing normal order evaluation, which
isn't what Scheme does.)

Some people bound B to 16 instead of 12, thinking that X was 4 (from E1)
instead of the correct 3 (from E3).  This mistake wasn't necessarily
accompanied by any error in the arrangement of E1 and E3 themselves.
These people generally got 64 as the answer to (foo 3).

Some people had E1 and E2 backwards (that is, E1 extending E2 which
extends G).  I can't imagine a mental model that would produce such a
diagram, since the value of C in E2 is based on the value of X in E1.
Perhaps these groups wanted to evaluate the LET as part of the process of
defining BAR (rather than when BAR is invoked), but in that case it's not
clear to me where the value of C came from.

A few people had E4 extending E3 (dynamic scope), but not as many as I
would have predicted -- it was more common to omit E4 altogether.

Some people added empty frames to the diagram.  An empty frame is
created by invoking a procedure of no arguments [(lambda () ...)], but
there aren't any of those in this problem.

Some people added bindings for Z and C to E1 instead of creating a
separate E2.  That would be appropriate for internal definitions:
	(define (bar x)
	  (define (z b) (* x b))
	  (define c x)
	  (lambda (x) ...))
But LET creates a new frame because it abbreviates a LAMBDA and an
invocation of the resulting procedure.


Scoring:  3 if correct.  2 for a single error (which could involve two
pointers if a procedure pointing to the wrong environment led to another
environment extending that wrong environment.  1 for multiple errors in
an otherwise reasonable environment diagram.  0 for multiple missing
frames or seriously incoherent results such as variables whose value is
an environment.


-----------------------------------

If you don't like your grade, first check these solutions.  If we
graded your paper according to the standards shown here, and you
think the standards were wrong, too bad -- we're not going to grade
you differently from everyone else.  If you think your paper was
not graded according to these standards, bring it to Brian or your TA.
We will regrade the entire exam carefully; we may find errors that
we missed the first time around.  :-)

If you believe our solutions are incorrect, we'll be happy to discuss
it, but you're probably wrong!