path: root/js/games/nluqo.github.io/~bh/61a-pages/Volume2/Midterm3/mt3-3.soln.txt

CS 61A		Solutions to sample midterm 3 #3

1.  Box and pointer.

(let ((x (list 1 2 3)))
  (set-cdr! (cdr x) (cddr x))
  x)

(1 2 3) is printed.

X-->[o|o]-->[o|o]==>[o|/]
     |       |       |      
     V       V       V      
     1       2       3

In this example the SET-CDR! call effectively does nothing, since it
replaces the cdr of (cdr x) with the cddr -- the cdr of the cdr -- of X.
The arrow drawn with = instead of - above is the one that's replaced with
itself.


(let ((x (list 1 2 3)))
  (set-car! x (cddr x))
  x)

((3) 2 3) is printed.

     +----------------+
     |                |
     |                V
X-->[o|o]-->[o|o]-->[o|/]
             |       |      
             V       V      
             2       3

The set-car! invocation changes (car x), i.e., the first element of X.
It's changed to (cddr x), which is a *sublist*, not just an element, of X.
Thus the new first element is not 3, but (3).



(let ((x (list 1 2 3)))
  (set-car! (cdr x) (cdr x))
  x)
(1 ((((((((( ...  is printed.

             +-+
             | |
             | V
X-->[o|o]-->[o|o]-->[o|/]
     |               |      
     V               V      
     1               3 

Note that the arrow at the top of the diagram points *from the car* of the
second pair, but points *to the entire pair* (because that's how pointers
always work), not just to the cdr, even though that's where the arrowhead
happens to be.

There's still a 3 in this list, but it'll never be printed.



(let ((x (list 1 2 3 4)))
  (set-cdr! (cddr x) (cadr x))
  x)

(1 2 3 . 2) is printed.

X-->[o|o]-->[o|o]-->[o|o]--> 2      
     |       |       |      
     V       V       V      
     1       2       3

In this example we change the cdr of a pair (because we're doing SET-CDR!) to
point to a non-pair, (CADR X), the second element of X, which is 2.  Thus the
result is an improper list, so there's a dot in the printed version.

It doesn't matter, in the diagram, whether you have two 2s, as above, or have
two arrows pointing to the same 2.  It *does* matter when the thing being
pointed to is a pair; then there's a big difference between two pointer to the
same pair, and two pairs that have the same values in them.


Scoring: One point per printed representation; one point per diagram.


2.  Local state.

Does Louis's MEMOIZE give wrong answers?  YES.

Explanation:  It has one table shared among all memoized functions,
instead of a separate table per function.

Example:

[Louis has defined MEMO-FIB, as shown in the question.]

> (memo-fib 4)
3
> (define memo-square (memoize (lambda (x) (* x x))))
> (memo-square 4)
3

Since MEMO-FIB and MEMO-SQUARE share the same table, (memo-square 4)
returns the value previously remembered from (memo-fib 4).

Some students who checked NO explained why the answer is really YES, so
we figured people misread the question, and went by your explanantion
rather than by which choice you checked.

Pretty much any explanation with a phrase like "a single table" or
"universal table" or "global table" was accepted.  (It's not quite right
to say "a table in the global environment"; the table is actually a local
state variable of MEMOIZE.)

Explanations that merely restate the form of Louis's change to the program
were not accepted:  "The program gives wrong answers because Louis has moved
the LET to outside of the LAMBDA."  You had to explain what *effect* that
would have on the program's *behavior*.

The example didn't necessarily have to take the form of a specific Scheme
interaction as above, but did have to assert that two different functions are
memoized.

Scoring:

4  correct
2  correct explanation, no/bad example;
   iffy explanation (like "global environment" discussed above)
0  bad explanation (including saying that it doesn't give wrong answers)

No odd scores were assigned.


3.  Environment diagram.

Bindings A=8 and B=9 go in the global environment.

Then comes the LET, which is equivalent to an invocation of the procedure
generated by an implicit LAMBDA:

	((lambda (a f) (f 5))
	 3
	 (lambda (b) (+ a b)))

As with any procedure invocation, **first all the subexpressions are
evaluated!**  This evaluation takes place in the global environment -- we
haven't invoked any procedures yet.

Thus, two procedures are created whose right bubbles point to the global
environment.  Only then do we invoke the (lambda (a f) ...) procedure, which
creates a frame in which A is bound to 3, and F is bound to the
(lambda (b) ...) procedure.  That new frame, of course, extends the global
environment.

With that frame as (the first frame of) the current environment, we can
evaluate the body of the LET, which is (F 5).  We find a binding for F in
the current environment; it's the (lambda (b) ...) procedure.  So we can
invoke that with the argument 5.

Since F's right bubble points to the global environment, that's what we
extend with the new frame that binds B=5.  So when we evaluate F's body,
which is (+ A B), we find the bindings A=8 and B=5.

Thus, the final answer is 13.


The overwhelmingly most common mistake was to think that the (lambda (b) ...)
procedure's right bubble points to the A=3 frame, so the B=5 frame points
there also, and the final value is 8.  You should know, though, that a LET
binding can't depend on another binding in the same LET; for example, if the
problem had been

	(let ((a 3)
	      (c (+ a b)))
	  (+ a c))

I hope most people would have known that C would be 8+9, using the global
bindings for both A and B.  The fact that the computation using A happens
inside a lambda body doesn't change the fact that the LET's binding for A
isn't available to it.

A few people drew the environment diagram that would give an answer of 8,
but instead wrote 13 as their final answer, which means either that they
copied someone else's final answer or that they *do* know how Scheme
evaluates expressions, but don't make any connection between that and
the environment model.  We graded this as if they'd said 8.

A couple of people had procedure F's right bubble correctly pointing to the
global environment, but nevertheless had the B=5 frame extending the A=3
frame, using dynamic scope instead of lexical scope.  This gave the same
wrong final answer of 8.

Scoring:

6  correct.
3  answer was (or should have been) 8, as discussed above.
0  even worse (too many frames, no arrows at all -- there weren't many).


4.  List mutation

(define a (list 'x))
(define b (list 'x))
(define c (cons a b))
(define d (cons a b)) 

(eq? a b)                    => #F

	Each call to LIST generates new pairs (one new pair, in this case,
	because each list has only one element).

(eq? (car a) (car b))        => #T

	Both CARs are the symbol X, and equal symbols are always EQ.

(eq? (cdr a) (cdr b))        => #T

	Both CDRs are the empty list, and there's only one empty list.

(eq? c d)                    => #F

	Each call to CONS generates a new pair.

(eq? (cdr c) (cdr d))        => #T

	Both CDRs are the pair named B -- the same pair.

(define p a)
(set-car! p 'squeegee)
(eq? p a)                    => #T

	P and A are two names for the same pair.  Mutating the pair
	doesn't change the variable bindings.

(define q a)
(set-cdr! a q)
(eq? q a)                    => #T

	This one looks trickier because the pair now points to itself,
	but it's really the same as the previous question: Q and A are
	two names for the same pair.

(define r a)
(set! r 'squeegee)
(eq? r a)                    => #F

	This time we didn't mutate a pair; we changed the binding of
	one of the variables.  So R and A now name two different things;
	A is still a pair, but R is now a symbol.

Score: 1/2 point each, rounded down to the nearest whole point.


5.  Vector programming

(define (ssort! vec)
  (define (help start)
    (if (= start (vector-length vec))
	vec
	(let ((smallest (subvec-min-start vec start)))
	  (let ((temp (vector-ref vec smallest)))
	    (vector-set! vec smallest (vector-ref vec start))
	    (vector-set! vec start temp)
	    (help (+ start 1))))))
  (help 0))

The key point to understand is that you need to walk through the vector,
bringing the smallest element out to position 0, then the next-smallest to
position 1, and so on, until you run out of elements.  Thus we have a helper
procedure with an argument, START, whose value is the position that we're
up to in the vector; it starts at 0 and is increased by 1 on each recursive
invocation.

The next important point is that you can't exchange two elements without
using a temporary variable to remember one of them, hence the LET that
creates the variable TEMP.  There are two nested LETs because the value of
SMALLEST is needed to find the value of TEMP in this solution; I could have
simplified things a little by remembering the other value in the swap instead:

(define (ssort! vec)
  (define (help start)
    (if (= start (vector-length vec))
	vec
	(let ((smallest (subvec-min-start vec start))
	      (temp (vector-ref vec start)))
	  (vector-set! vec start (vector-ref vec smallest))
	  (vector-set! vec smallest temp)
	  (help (+ start 1))))))
  (help 0))

Scoring:

6  correct
5  trivial error (e.g. base case off by one)
3  right structure, gets swap wrong
2  serious algorithm confusion
0  allocates new vector, uses lists, or incoherent


6.  Concurrency

(define (make-mutex)
  (let ((in-use #f)
	(s (make-serializer)))
    (define (the-mutex m)
      (cond ((eq? m 'acquire)
	     (if ((s (lambda ()
		       (if in-use
			   #t
			   (begin (set! in-use #t)
				  #f)))))
		 (the-mutex 'acquire)))     ; retry
	    ((eq? m 'release)
	     (set! in-use #f))))
    the-mutex))

The structure of the above is just like that of the MAKE-MUTEX in the book,
except that when an atomic test-and-set operation is needed, it's done by
including the (IF IN-USE ...) and the (SET! IN-USE #T) within the same
serialized procedure, rather than by relying on a TEST-AND-SET! primitive.

Many people found the problem deeply confusing.  You learned that
serialization has three levels of abstraction: the hardware support,
the critical section mechanism (mutex) based on the hardware, and
the more abstract level in which procedures are protected rather than
sequences of instructions.  So what does it mean to define a mutex
in terms of a serializer?  But actually this could happen.  Suppose
you are using a language such as Java, with high-level serialization
built in (and presumably implemented using hardware support), to write
an operating system that is supposed to provide a mutex capability to
its users.  You would then write something equivalent to what this
problem asks for.  What defines an abstraction is its behavior, not
how it's implemented -- this is the whole idea behind abstraction.

The SICP version uses (LET ((CELL (LIST FALSE))) ...) because their
TEST-AND-SET! tests and modifies a pair, not a variable, mainly so that
it can be an ordinary procedure rather than a special form.  In this
version there's no need to use a pair, although it wouldn't be wrong.

The ugly (IF ((S (LAMBDA () ...))) ...) is necessary because of the way
serializers work: they take a procedure as argument and return a protected
version of that procedure, which must then actually be invoked.
We didn't take off for minor failures in the notation, accepting even
solutions in which the argument to the serializer was an expression to
be evaluated atomically: (IF (S (IF IN-USE ...)) ...)  But we didn't
accept solutions in which the serializer was given data, rather than
activity, as its argument.  (More on that below.)

The reason for the nested IFs is a little subtle; the recursive call
to THE-MUTEX to retry the operation if it fails can't be inside the
serialized procedure, because then it'll block waiting for S, which is
held by this process itself -- in effect, setting up a deadlock within a
single process.  But we didn't take off points for missing this subtlety.

Some people used a single global serializer instead of a separate one
for each mutex.  At first we considered this a serious error, because
it means that two mutexes can't be acquired at the same time.  But then
we realized that the serializer just protects the acquiring of the mutex,
not the critical section that the mutex itself protects, so any mutex
holds the serializer only for a very short time.  So we allowed a global
serializer, except in papers that also missed the point in the previous
paragraph.  If a mutex can get into a deadlock with itself, while holding
a serializer needed by all the other mutexes, that's serious enough to
lose a point.

Some solutions never actually tested whether the mutex was in use before
acquiring it.  Presumably those people thought that the serializer would
protect the entire critical section, not just the acquiring, so that if
an acquire operation could get into the serializer the mutex must be free.
But that's not the case; the mutex returns to its caller once it has
set its in-use flag, so the caller's critical section is *not* keeping the
serializer busy.  Such solutions got at most one point.

There were a few common zero-point solutions.  The strangest were the
ones that called parallel-execute.  The job of a mutex is to protect
critical sections against other processes, not to create other processes.

Another zero-point solution had expressions such as (S CELL) that showed
a lack of understanding of the key fact that a serializer protects
activities, not data.  Similarly, no points for anything that included

        (something . args)       ;; pfui

which indicated mindless copying from the MAKE-SERIALIZER in the book
without understanding.  Serializers accept as arguments procedures with
any number of arguments, but any particular use of a serializer isn't
going to be that complicated -- and none of these solutions found any
use for the ARGS variable anyway.

Scoring:
3  OK
2  at least an atomic test-and-set implementation
1  no test-and-set, but some idea
0  way off


7.  Streams.

The answer we expected was

(define all-integers
  (cons-stream 0 (interleave integers
                             (scale-stream -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 APPEND-STREAMS 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 zeros-ones (cons-stream 0 (cons-stream 1 zeros-ones)))

(define all-integers (subtract-streams zeros-ones
                                       (cons-stream 0 all-integers)))

where subtract-streams is like add-streams 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  append-stream etc.
1  stream of streams, like (cons-stream negatives positives)
0  not a stream at all

We heard from several students who thought that the stream-of-streams
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.