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

CS 61A		Solutions to sample final exam #3

1.  Domain and range

The domain of a procedure is the TYPE of thing(s) it accepts as argument(s).
The range is the TYPE of thing it returns.  So we wanted types as the answers
to this question.  That's generally what you gave for the domain, but for the
range, several people instead gave explanations of the purpose of the
procedure, e.g., "Range: the children of the tree node."

(a) CHILDREN

CHILDREN takes one argument, a Tree (which is the same as a node).
It returns a forest, which is a list of Trees.  So:

	Domain: TREE or NODE
	Range:  FOREST or LIST OF TREES or just LIST

Most people got this one.

(b) OWNER

OWNER takes one argument, a THING object.  It returns the *name of* the
person who owns the thing (not the person, not the name of the thing).
A name is a word, not an object!  So:

	Domain: OBJECT or THING OBJECT or THING INSTANCE
	Range:  WORD

We also accepted NAME for the range, although that isn't really a type.
The most common wrong answer for the range was PERSON; that's a kind of
object, not a word.  A fairly common wrong answer for the domain was CLASS;
the procedure takes a particular thing as its argument, not the class of all
things.  Another common wrong answer was PROCEDURE; it's true that we use
procedures to represent objects, but not every procedure is an object, and
not every procedure can be used as the argument to OWNER.

(c) SET-CDR!

SET-CDR! takes two arguments; the first must be a pair, and the second can be
of any type.  Its return value is unspecified, since it is used for its effect
rather than for its return value, so we accepted anything for the range in
this part.

	Domain: PAIR and ANYTHING (you had to say both).
	Range:  UNSPECIFIED (but we accepted anything).

We didn't accept LIST for the domain; there is no requirement that the first
argument to SET-CDR! be a pair whose cdr is a list (which is what it means for
a pair to be a list).  Also, the LIST domain would include the empty list,
which can't be used as the first argument to SET-CDR!.

Scoring: One point each, all or nothing.


2.  Data abstraction

The argument is a LIST of RATIONALs.  For the list itself, the appropriate
selectors are CAR and CDR.  (Constructors for lists include CONS, LIST, and
APPEND, but in this problem we are not constructing a list!)  For a rational
number, the constructor is MAKE-RAT and the selectors are NUMER and DENOM.
So the corrected version is

(define (ratprod lst)
  (define (helper lst n d)
    (if (null? lst)
	(MAKE-RAT n d)
	(helper (CDR lst) (* n (NUMER (CAR lst)) (* d (DENOM (CAR lst)))))))
  (helper lst 1 1))

The call to CDR doesn't change because it is selecting part of a list, not
part of a single rational number.  The calls to CAAR and CDAR do change,
as shown above; they both select the first element of the list (CAR), and
each then selects one piece of a rational number (NUMER or DENOM).

Scoring: -1 point per error, either a required change not made or something
changed that shouldn't have been.  But 0 points if no correct change was
made at all (e.g., if the question was left blank).


3.  Order of growth

(a)

(define (two-to-the n)
  (if (zero? n)
      1
      (let ((prev (two-to-the (- n 1))))
	(* prev 2) )))

Each call to this procedure does three constant-time operations (ZERO?, -,
and *) in addition to making one recursive call.  So there are N recursive
calls, each of which takes constant time.  Therefore, this procedure takes
time Theta(N).

(b)

(define (two-to-the n)
  (if (zero? n)
      1
      (let ((prev (two-to-the (- n 1))))
	(+ prev prev) )))

The only difference here is (+ PREV PREV) instead of (* PREV 2).  This
is still a single, constant-time arithmetic operation, although both operands
are the variable PREV rather than including the explicit number 2.  But
finding the value of a variable is also constant time, so this doesn't affect
the program's running time, which is still Theta(N).

(c)

(define (two-to-the n)
  (if (zero? n)
      1
      (+ (two-to-the (- n 1))
	 (two-to-the (- n 1)) )))

In this version, each call to TWO-TO-THE gives rise to *two* recursive
calls.  So, for example, (two-to-the 5) calls (two-to-the 4) twice; each
of those makes two calls, for a total of four calls of (two-to-the 3).
Similarly, there are eight (two-to-the 2) calls and 16 of (two-to-the 1).
Increasing N by 1 doubles the total number of recursive calls, so the
running time for this procedure is exponential, Theta(2^N).

The most common error was to think that the last version was Theta(N^2).

Scoring: One point each.


4.  Functions of functions.

The point of this question is to illustrate some of the ways in which
functions can be manipulated on their own, without explicit reference to
the arguments of the functions.  You've seen COMPOSE before, in lecture;
the other two tools given here are similar in spirit.

One way to think about these questions would be to try writing the
desired procedure without using COMPOSE, SPECIALIZE, or SWAP-ARGS, and
then think about how you did it.

[a] INITIALS

(define (initials sent)
  (every first sent))

So INITIALS is a specialized version of EVERY, in which the first
(procedure) argument is FIRST.  Thus we have the answer:

(define initials (specialize every first))


[b] POSITIVE?

(define (positive num)
  (> num 0))

This is a specialization of >, in which the *second* argument is held
constant (zero), not the first argument as in INITIALS.  So SPECIALIZE
won't quite do the job by itself.  One solution would be to use <
instead of >:

(define (positive num)
  (< 0 num))

(define positive (specialize < 0))

but that wasn't one of the choices.  Instead we use SWAP-ARGS to get
the arguments in the right order:

(define positive (specialize (swap-args >) 0))


[c] LEAF?

(define (leaf? node)
  (null? (children node))

This is a composition of functions:

(define leaf? (compose null? children))


Scoring: One point each.


5.  Mystery function on Trees

(define (mystery tree)
  (if (null? (children tree))
      (make-tree (datum tree) '())
      (make-tree (+ (datum tree) 100)
		 (map mystery (cdr (children tree))))))

This function says:  If the node is a leaf, return a leaf node with the
same datum.  (This is actually unnecessarily complicated; it could have
just returned the argument TREE itself, since the node it constructs has
the same datum and the same (empty) children.)  If the node isn't a leaf,
add 100 to its datum, and recursively apply the same function to its
children, but omit the first child (because of the CDR call).

In the given tree, the root node (datum 1) has three children, so we add
100 to its datum (giving 101), we omit the subtree headed by the node with
datum 2, and we recursively process nodes 3 and 4.

Node 3 (I'm using this as an abbreviation for "the node with datum 3" and
similarly for the other nodes) has two children, so we add 100 to its
datum, omit the first child (6), and recursively process the other child
(node 7).

Node 7 has no children, so we just return a leaf with datum 7.

Node 4 has one child.  So we add 100 to its datum, omit its first (only)
child 8, and recursively process its other children -- but there aren't
any, so the node with datum 104 will be a leaf node in the resulting tree.

Omitting a node doesn't just mean omitting the datum of that node; we
never look at its children either.  So we don't have to think about nodes
5, 9, and 10.

Don't forget that this function builds a new tree!  It doesn't mutate the
argument tree.  In particular, one common wrong answer was to return a
tree with 10 nodes, just like the argument tree, but with 100 added to
some of the data.  The correct answer is a tree with only the four nodes
mentioned earlier as part of the result:

			       101
			      /   \
			    103   104
			     |
			     7

Another too-common mistake was to draw a tree in which some nodes have
lists as the datum.  For example, the child of the 103 node was shown as
having (7) as its datum, or the 104 node had a child with the empty list
as its datum.  These errors, I think, come from not respecting the data
abstraction, but instead trying to translate the tree selectors and
constructor into operations on pairs.  As you can see from the explanation
above, there is no need to think about how tree nodes are represented!  The
only pair operation used is the CDR in the procedure, and that's because
(CHILDREN TREE) returns a forest -- a list of trees -- rather than a single
tree node.

Several people thought that a Scheme error would result from the expression

	(map mystery (cdr (children tree)))

when it is applied to the 4 node, which has only one child, because in this
case the expression is equivalent to

	(map mystery '())

But there's nothing wrong with this -- MAP is happy to take the empty list
as its second argument, in which case it returns the empty list without
ever calling MYSTERY.  Empty lists are legitimate lists!


Scoring:

5  Correct.

4  Correct except that instead of 101, 103, and 104, the values in those
   nodes are computed by some different arithmetic; most commonly these
   nodes have the data 101, 301, and 401.  Node 7 must be correct.

3  Right shape, but one incorrect datum (most often 107 instead of 7).

2  The four correct nodes plus one or two extras, including the case of
   "error" as a child of node 104.

2  The solution obtained by ignoring the CDR in the procedure: 10 nodes
   in the same shape as the original, but with 1, 2, 3, 4, and 8 changed
   to 101, 102, 103, 104, and 108.

0  "Error" as the complete answer without an explanation.

0  Any list structure in the tree data.

0  Anything else, including the "mutation" solution mentioned earlier with
   10 nodes like the original but with 1, 3, and 4 changed to 101, 103, 104.



6.  Scheme to OOP

We are given

(define foo
  (let ((a 3))
    (LAMBDA (B)			;; This is the class FOO
      (let ((c 4))
	(LAMBDA (MESSAGE)	;; This is the instance's dispatch procedure
	  (cond ((eq? message 'hi)
		 (+ a b))
		(else
		 (+ c message))))))))

The scope of the LET variable A encloses the procedure representing the class,
so it's a class variable.  B is an argument to the class, so it's an
instantiation variable.  And C is inside the scope of the class, but outside
the scope of the instance, so it's an instance variable -- each instance has
its own C.  Therefore:

(define-class (foo b)
  (class-vars (a 3))
  (instance-vars (c 4))
  (method (hi)
    (+ a b))
  (default-method
    (+ c message)))

The dispatch procedure looks explicitly for the message HI and provides
a method for it; the ELSE clause in the dispatch procedure handles any
other message, so it's a default method.

Most people got the translation of the LET expressions for A and C right,
although a few people reversed them and a few people thought A and C were
the same kind of variable.  B was trickier; some people didn't realize
that that LAMBDA represents the class, and instead thought that B was a
formal parameter of a method.

Similarly, some people thought the inner LAMBDA expression represents a
method rather than a dispatch procedure, so they wrote methods with
MESSAGE as a parameter.

As in any object class definition, it's possible to have only a default
method that checks for particular messages explicitly:

  (default-method
    (if (eq? message 'hi)
	(+ a b)
	(+ c message)))

and we accepted that, although it's contrary to the spirit of OOP.  But
most people who were confused about the meaning of the inner LAMBDA came
up with incorrect solutions, such as

  (method (hi message b) ...)
  (default-method (message) ...)
  (method (hi) (if ...))

Scoring:  The correct solution has five components: the use of B as an
instantiation variable, and the four clauses within the define-class (A, C,
HI, and DEFAULT-METHOD).  We subtracted one point for each missing or
incorrect component.  Incorrect solutions that tried to combine the HI
method with the default method lost both points, except for the
  (method (hi) (if ...))
version (no parameter to HI!), which lost only one point for the methods.


7.  Environment diagrams

The diagrams have many features in common:  They all have a global frame
and an additional frame E1; they all have a symbol F bound to a procedure.
But there are two things that differ among diagrams:

	* The symbol F is in frame G (diagrams A and B) or in frame
	  E1 (diagrams C and D).

	* The procedure's right bubble points to frame G (diagrams
	  A and C) or to frame E1 (diagrams B and D).

So, to figure out this question, for each of the four Scheme programs we
have to ask "where is the procedure created?" and "where is F bound?"

(let ((f (lambda (x) x)))
 'okay) 

	Here the LAMBDA expression is evaluated in the global environment,
	because LET value expressions are evaluated *before* the implicit
	procedure created by the LET is invoked.  But the binding for F is
	made locally, in the frame E1 that's created by the LET.  So this
	is diagram C: procedure points to G, F bound in E1.

(define f
 (let ()
   (lambda (x) x)))

	This time the LAMBDA expression is evaluated in the body of the LET,
	so its current environment is E1, and so that's what the right bubble
	remembers.  But the DEFINE is in the global environment, so that's
	where F is bound.  This is diagram B: procedure points to E1, F
	bound in G.

(let ()
 (define f (lambda (x) x)))

	This time both the LAMBDA and the DEFINE are in the body of the LET,
	so both of them have E1 as the current environment.  This is diagram
	D: procedure points to E1, F bound in E1.

(define (f) f)
(f)

	Here we have a straightforward global definition of a procedure F,
	so both the (implicit) LAMBDA and the DEFINE happen in G.  So this
	is diagram A: procedure points to G, F bound in G.  (Frame E1 is
	created by the second, separate expression, which invokes F.)

Most students got this correct.  The most common wrong answer was DBCA.
Choosing D for the first expression comes from the frequent misunderstanding
in which students think that the expressions that provide the values for the
LET variables are evaluated inside the scope of the LET.  I'm not sure how
anyone would choose C for the third expression, but probably it's because you
assumed (correctly) that each diagram was used once.

Scoring: one point each.


8.  CADR for message-passing pairs

A pair made by MAKE-PAIR can handle CAR and CDR messages directly because
its local state variables X and Y contain the desired values.  But in order
to handle the CADR message, it has to find its own CDR (which is Y) and
send a CAR message to that other pair:

(define (make-pair x y)
  (lambda (msg)
    (cond ((eq? msg 'car) x)
	  ((eq? msg 'cdr) y)
	  ((EQ? MSG 'CADR) (Y 'CAR))	;; <<=== This line added!
	  (else (error "I have no idea what you're talking about.")) )))

One common mistake was (ASK Y 'CAR); this has the idea, but we're using
plain Scheme message passing, not the OOP language.

Many students used roundabout means to find the pair's CDR, such as

	   ((eq? msg 'cadr) (((make-pair x y) 'cdr) 'car))

presumably because you mistrusted a simple Y as something you can invoke.
This works, but it really violates the spirit of the problem -- it creates a
new pair every time you look at the pair -- and didn't get full credit.

Another common error was (CAR Y).  Unless you explicitly redefine CAR to
use the message-passing pairs, this will invoke the ordinary CAR that
expects a built-in Scheme pair as its argument, not a procedure.  We
named the pair constructor MAKE-PAIR rather than CONS to make it clear
that we didn't mean to eliminate the regular pairs, and our example says
(ABC 'CAR) rather than (CAR ABC).

Of course the worst mistake was to build the specific example ABC into
the solution!

Scoring:

3  Correct.

2  (ASK Y 'CAR)

2  (X 'CDR)		; this would give the CDAR, not the CADR.

2  Working solutions that call MAKE-PAIR.

1  (X 'CAR) or (Y 'CDR)	; CAAR and CDDR.

0  Anything else, including (CAR Y).



9.  List mutation.

Here is the box-and-pointer diagram *before* doing any mutation:

---> XX------------> XX------------> X/
     |               |               |
     V               V               V

     XX---> X/       XX---> X/       E
     |      |        |      |
     V      V        V      V

     A      B        C      D

The expression (SET-CAR! (CADR LST) (CDDR LST)) modifies the pair that is
the CADR of the original list -- the CAR of the CDR.  (CDR LST) is the
second pair of the spine, in the top row.  CAR of that pair is the first
pair in the spine of the sublist (C D).  So we are going to change the CAR
of that pair, replacing C with something.  With what?  With the value of
(CDDR LST), the second argument to SET-CAR!.  (CDDR LST) is the third
pair of the spine of the entire list, the one whose CAR is E.  So after
this first mutation we have

---> XX------------> XX---------->-> X/
     |               |          /    |
     V               V          *    V
                                *
     XX---> X/       XX---> X/  *    E
     |      |        *      |   *
     V      V        *      V   *
                     *          *
     A      B        *      D   *
                     *          *
                     ************

The second mutation, (SET-CAR! (CAR LST) (CADDR LST)), modifies (CAR LST),
which is the first element of the big list -- the first pair of the spine
of the sublist (A B).  We change the CAR of this pair, so that instead of
pointing to A, it points to the CADDR of the big list, which is the third
element, the symbol E:

---> XX------------> XX---------->-> X/
     |               |          /    |
     V               V          *    V
                                *
     XX---> X/       XX---> X/  *    E
     *      |        *      |   *
     *      V        *      V   *    ^
     *               *          *    *
     *      B        *      D   *    *
     *               *          *    *
     *               ************    *
     *                               *
     *********************************

Notice that the first mutation points to a pair, not to E, but the second
one points to E.  This is the difference between (CDDR LST) and (CADDR LST).

It's okay if you draw another E underneath the relevant pair, instead of
drawing an arrow over to the original E.  Since two equal symbols are always
EQ, it's not important to distinguish two equal symbols in the diagram.

The third mutation is (SET-CDR! (CAR LST) (CDAR LST)).  This says, "change
the CDR of (CAR LST) to the CDR of (CAR LST)"!  In other words, it doesn't
really change anything:

---> XX------------> XX---------->-> X/
     |               |          /    |
     V               V          *    V
                                *
     XX***> X/       XX---> X/  *    E
     *      |        *      |   *
     *      V        *      V   *    ^
     *               *          *    *
     *      B        *      D   *    *
     *               *          *    *
     *               ************    *
     *                               *
     *********************************

Finally we have (SET-CAR! (CDDR LST) 'X).  This modifies (CDDR LST), which
is the last pair of the spine.  Its CAR used to point to E, but now points
to X instead:

---> XX------------> XX---------->-> X/
     |               |          /    *
     V               V          *    *
                                *    V
     XX***> X/       XX---> X/  *    
     *      |        *      |   *    X
     *      V        *      V   *    
     *               *          *    
     *      B        *      D   *    E
     *               *          *    
     *               ************    ^
     *                               *
     *********************************

So the printed representation of the final result is:

	((E B) ((X) D) X)

The most common wrong answer was ((X B) ((X) D) X).  This comes from thinking
that the last mutation changes *everything* that points to E so that it points
to X instead.  But that would be true only if the pair (CAR LST) pointed to
the *pair* (CDDR LST), whose CAR is changed from E to X, rather than pointing
directly to E.

Another common wrong answer was ((E B) (X D) X), ignoring the fact that the
first mutation replaces the letter C with the *pair* (CDDR LST), which is a
list, not a symbol; its printed representation is (X).

A common error in the diagram itself was to create new pairs, most often
making a *copy of* (CDDR LST) to be the CAR of (CADR LST).

Another misunderstanding, which led to huge errors in the diagram, was to
think that (CAR LST) means the first *pair in the spine* of LST, rather
than the first *element* of LST.  Similarly, students misinterpreted
(CADR LST) to mean the second pair of the spine, and so on.

Scoring:  We subtracted one point per wrong change in the diagram (out of
the four possible changes), and one point if the printed representation
didn't match your diagram.


10.  Scheme vs Logo evaluators

In Scheme, evaluating the expression (+ A 3) requires the evaluator to look up
two variables: + and A.  Since we are giving MC-EVAL an environment that only
has a binding for A, this first expression gives the result

	ERROR: Unbound variable +

In Logo, procedure names aren't part of the environment, but are found in a
separate, global table that's used automatically by LOGO-EVAL.  So in order to
evaluate the Logo expression (SUM 2 :A), we have to look up A in the
environment, but we don't need SUM in the environment.  Therefore the result
of this evaluation is

	5


One too-common error was to say (+ A 3) as the value returned in the first
case.  Presumably students who said this were reacting to the fact that the
expression (+ A 3) is quoted when used as an argument to MC-EVAL.  But this
just means that the argument is (+ A 3) rather than being the result of
evaluating (+ A 3) in the underlying STk evaluator!

Scoring:  Two points each.  We accepted any ERROR message for the first part.

For the second part, we accepted 6 instead of 5 (because it's not important
if you didn't notice that the second expression used 2 rather than 3) for
full credit.

We gave half credit (one point) to either of two particular wrong answers
to the second part:

	You don't say what to do with 5

(which would be correct if we were calling DRIVER-LOOP instead of LOGO-EVAL),
and

	5  =no-value=

(which can't be correct, since it's two values instead of one, but presumably
is meant to show the values computed by EVAL-LINE, although that isn't right
either because EVAL-LINE returns a value as soon as it gets anything other
than =no-value= from evaluating an expression).


11.  Streams

The first two elements are explicitly given as A and B.  The remaining
elements are the result of interleaving two streams, so we can draw a
picture like this:


	A  B  ___       ___       ___       ___

                   ___       ___       ___       ___


The second argument to INTERLEAVE is a stream containing only elements
that are the symbol B, so we can start to fill this in:


	A  B  ___       ___       ___       ___

                   _B_       _B_       _B_       _B_


To fill in the top row, we just copy the entire stream FOO.  We already
know FOO's first two elements, so we can fill those in, and that tells us
FOO's third and fifth elements.  (Its fourth element is the first B on the
bottom row.)


	A  B  _A_       _B_       _A_       _B_

                   _B_       _B_       _B_       _B_


Putting this back into a single row gives the solution:

	A  B  A  B  B  B  A  B  B  B


Scoring:  We subtracted one point per wrong letter.  This means that the
common error in which only the first letter is A [A B B B B B B B B B B]
got one point.

Exception:  Some people apparently think that STREAM-FILTER keeps only
the elements that *don't* satisfy the predicate, so they put a stream of
As in the bottom row rather than a stream of Bs.  This gives the incorrect
solution A B A A B A A A A A, to which we gave one point.


12.  Logic programming

As a reminder, here's ASSOC written in Scheme:

(define (assoc key alist)
  (cond ((null? alist) #f)
	((equal? key (caar alist)) (car alist))
	(else (assoc key (cdr alist)))))

The first COND clause does not have any analog in the logic program!  In
logic programming, if nothing satisfies the question we're asking, we just
don't match any rule.  We don't want a rule that shows a value of #F.

Here's the rule corresponding to the second COND clause:

(assert! (rule (assoc ?key ((?key . ?value) . ?rest) (?key . ?value))))

No condition is necessary for this rule; the pattern says it all.  But
it would be okay to show this rule in a form closer to that of the Scheme
program:

(assert! (rule (assoc ?key (?car . ?cdr) ?car)
	       (and (same ?car (?caar . ?cdar))
		    (same ?key ?caar))))

The second COND clause is a little tricky, because we only want to allow
the recursion if the key doesn't match the first entry.  In Scheme, COND
automatically handles this, because COND can only return one value, so it
doesn't look at any clauses after the first successful one.  But logic
programming allows multiple results, so we have to explicitly disable the
recursion in case of a match:

(assert! (rule (assoc ?key ((?caar . ?cdar) . ?rest) ?result)
	       (and (assoc ?key ?rest ?result)
		    (not (same ?key ?caar)))))

To make this work we also have to define the SAME relation:

(assert! (rule (same ?x ?x)))

but we didn't require this to be explicitly included in your solution.


Some people tried to use a single rule that matches any association list
that has the desired key anywhere in it, like this:

(rule (assoc ?key (?left . (?key . ?value) . ?right) (?key . ?value))) ;WRONG!

This isn't such a bad idea, except that there is no (x . y . z) notation for
a list that has element Y in the middle.  But the desired result can be
obtained using the APPEND rules:

(assert! (rule (assoc ?key ?alist (?key . ?value))
	       (and (append ?left ((?key . ?value) . ?right) ?alist)
		    (not (assoc ?key ?left ?something)))))

The NOT clause is required to eliminate duplicate matching keys.  Alas,
most people who tried this didn't quite use APPEND correctly.  The worst
problem was to try to use it as a function rather than a relation:

	(rule (assoc ?key (append ?left ((?key . ?value) . ?right))
		          (?key . ?value)))	; WRONG!!!

This is an attempt to use the "return value" from APPEND as part of the
pattern for the ASSOC rule, but APPEND doesn't return a value.  It's a
relation that succeeds or fails, and the appended list is one of the
components of the relation, as in the correct version above.


The most common error was to include spurious base cases, such as

	(rule (assoc ?key () #f))	; WRONG!

A more subtle error was to try to eliminate duplicate keys in the
association list in the wrong rule:

(assert! (rule (assoc ?key ((?key . ?value) . ?rest) (?key . ?value))
	       (not (assoc ?key ?rest ?something))))	; WRONG!

This rule would find the last matching key, not the first matching key,
in the association list.


Scoring:

5  Correct.

4  Extracts just the key, or just the value, rather than the entire pair.

4  Finds the last matching key rather than the first one.

3  Finds all matching keys (no NOT clause).

3  Spurious base case for empty list.

2  No recursive rule at all.

2  Other "has the idea" but non-working solutions with a rule that tries
   to match the car of the association list.

0  No rule matching the car of the association list (recursive rule only).

0  Has the example built in (e.g., only works for lists of length four).

0  Composition of functions (like the incorrect APPEND version above).

0  Anything not mentioned above.


13.  Concurrency

All of the examples try to call the procedures F and G, which both modify
the variable X, and must therefore be protected against each other.
Therefore, we must use the same serializer for both of them.

(parallel-execute (s f) (t g))

	This uses two different serializers for the two thunks, so they
	are not protected against each other.  This can give rise to
	INCORRECT RESULTS.

(parallel-execute (s f) (s g))

	This is the correct way to do it -- a single serializer protects
	the variable X, and every process that depends on X is protected
	using S.  So it produces NEITHER incorrect results nor deadlock.

(parallel-execute (s (t f)) (t g))

	This has an unnecessary invocation of serializer S.  Both processes
	are protected by T, so no incorrect results are possible, and nothing
	is added by calling S also.  But since S is used for only one process,
	there will be NEITHER incorrect results nor deadlock.

(parallel-execute (s (t f)) (s g))

	This is just like the previous case: S does the needed protection,
	and T is unhelpful but not harmful either, since only one process
	uses it.  So NEITHER problem can arise.

(parallel-execute (s (t f)) (t (s g)))

	There won't be incorrect results, since both processes use the same
	serializer (either S or T can be considered as the useful one).  The
	second serializer is unnecessary.  But this time, since two processes
	use the same two serializers, in different orders, DEADLOCK is
	possible.

Scoring: One point each.


14.  Tree to binary tree.

The crucial point here is that two different abstract data types (Tree and
Binary Tree) are involved.  A binary tree isn't just a Tree!  It's different
because if a node has exactly one child, a Binary Tree can distinguish whether
this is the left child or the right child; the Tree type doesn't allow for
this distinction.  So, for example, you couldn't use the Tree type to
represent a binary search tree.

We are given a Tree as argument, and asked to return a Binary Tree.
Therefore, our program should use the *selectors* for the Tree type (namely
DATUM and CHILDREN), but should use the *constructor* for the Binary Tree
type (MAKE-BT).

We didn't say explicitly in the problem what the arguments to MAKE-BT should
be, but we did say it's based on the Binary Tree type in the text (see page
157), except changing the name from MAKE-TREE to MAKE-BT.  It takes three
arguments, the three components of a Binary Tree node: entry, left, and right.

(define (tree->bt tree)
  (if (> (length (children tree)) 2)
      #f
      (let ((kids (map tree->bt (children tree))))
	(cond ((member #f kids) #f)	; propagate failure upward
	      ((null? kids) (make-bt (datum tree) '() '()))
	      ((null? (cdr kids)) (make-bt (datum tree) (car kids) '()))
	      (else (make-bt (datum tree) (car kids) (cadr kids)))))))

The most common error was to forget the first COND clause.  It's not good
enough to return #F if *this* node has three or more children; we also have to
return #F if any *child* (or grandchild, etc.) of this node has too many
children.  So we see if the value returned by any recursive call to TREE->BT
is false, and if so we return false too.

Since MAKE-BT has separate arguments for the left and right branches,
we need three COND clauses for each of the possible number of children
in order to put the child(ren) in the right place(s).

We accepted solutions in which MAKE-BT takes a list of length exactly two,
every time, to specify the two branches of the new node.  But we didn't accept
solutions in which MAKE-BT takes a list of any number of children, because
that interface wouldn't allow the user to distinguish the case of a node with
only a left child from the case of a node with only a right child.  (In this
problem we say that we aren't going to create any nodes with only a right
child, but you can't specify a constructor for Binary Trees that doesn't allow
for that possibility.)

Another common error was data abstraction violations.  These come in two
forms:  (1) mixing the selectors and constructors for Trees with those for
Binary Trees, and (2) using list/pair selectors and constructors (CONS, CAR,
etc.) for either Trees or Binary Trees.  We considered the first category less
severe than the second, although either kind of DAV really shows a failure to
understand the point of data abstraction!  (This is true despite the fact that
a few students wrote essays to try to justify their violations.)

Another severe error was to try to mutate the tree instead of constructing a
new data structure.  This was rarely explicit (e.g., using SET-CAR!); the
usual thing was for students to call MAP, ignore its return value, and think
(apparently) that something has changed in the argument tree.  We referred to
this in the grading as the "MAP!" error -- using MAP as if it were a mutator.

Scoring:

6  Correct.

4  Correct except that #F from a child isn't propagated to the parent.

2  Case analysis errors, e.g., two-child nodes handled correctly but
   one-child nodes handled incorrectly.

2  Tree vs. Binary Tree DAV.

0  Tree vs. Pair DAV [e.g., (CAR TREE)].

0  No deep recursion (grandchildren not examined).

0  Pseudo-mutation (using MAP as if it were MAP! mutator).

0  Anything worse.



15.  SWAP!

This was a relatively easy mutation problem, since there was no need to
examine inside any lists found as elements of the argument list.  We only
care about elements of the top-level list.

The first decision to be made is whether this is a job for SET-CAR! or
for SET-CDR!.  The best choice is SET-CAR!, because we don't want to change
which pair comes first in the list's spine, in case some variable used in the
calling procedure is bound to this list.

We want to mutate the pairs of the spine, not any pairs that might be elements
of the list.  And we need a temporary variable to remember one of the elements
while we're doing the swapping.

(define (swap! lst)
  (cond ((null? lst) lst)
	((null? (cdr lst)) lst)
	(else (let ((temp (car lst)))
		(set-car! lst (cadr lst))
		(set-car! (cdr lst) temp)
		(swap! (cddr lst))
		lst))))

Scoring:

6  Correct.

5  Swaps correctly but doesn't return a value.

5  Correct except for base cases.

4  Has the idea:
    * Uses a temporary variable; and
    * SET-CAR! of two pairs, with at least one in the spine; and
    * Recursive;
   but...
     - recurs on (CDR LST) instead of (CDDR LST); or
     - uses SET-CDR! and reorders correctly but loses the head pair; or
     - has the wrong value in TEMP (a spine pair instead of an element).

3  (set-car! (CAR lst) (cadr lst)) and (set-car! (CADR lst) temp).

2  Has an idea:
    - only one SET-CxR!; or
    - no temporary variable; or
    - mutates two wrong pairs; or
    - thinks SET! will change a pair, but also uses SET-CxR!.

0  Other, including:
    - allocates pairs (CONS, LIST, APPEND, etc.); or
    - no recursion; or
    - no SET-CxR!; or
    - SET! of a non-symbol [e.g., (SET! (CAR LST) (CADR LST))].


16.  Partial application in MCE

The feature we want to add, which in the programming language literature is
generally called "partial application," is used when a procedure is called.
Procedure calling is the job of MC-APPLY, so that's where we have to make the
change.  (It's possible to do it elsewhere, but less straightforward.)

We are asked to construct a new procedure.  How do we do that?  The best
answer is to call MAKE-PROCEDURE.  There's no need to construct and then
evaluate a LAMBDA expression!

What should the procedure look like?  One solution is to do exactly what's
shown in the question: a procedure whose body is an invocation of the
underlying procedure.  But this is actually a little tricky, because when we
get to APPLY we no longer know what *expression* has that procedure as its
value!  We only have the procedure itself.  So the easiest thing will be if we
can create a procedure with the same body as the original procedure.  For
example, if the original procedure is

	(lambda (base exp)
	  (cond ((= exp 0) 1)
		((even? exp) (fast-exp (* base base) (/ exp 2)))
		(else (* base (fast-exp base (- exp 1))))))

then we'll create a procedure

	(lambda (EXP)		;; only this line is different
	  (cond ((= exp 0) 1)
		((even? exp) (fast-exp (* base base) (/ exp 2)))
		(else (* base (fast-exp base (- exp 1))))))

but we'll create it in an environment with BASE bound to 2, as if the
user had typed

	(let ((base 2))
	  (lambda (exp)
	    (cond ((= exp 0) 1)
		  ((even? exp) (fast-exp (* base base) (/ exp 2)))
		  (else (* base (fast-exp base (- exp 1)))))))

But of course we can't build this particular example into the solution;
it has to work for any procedure, with any number of parameters, and with
any smaller number of arguments given in the invocation.

(define (mc-apply procedure arguments)
  (cond ((primitive-procedure? procedure)
	 (apply-primitive-procedure procedure arguments))
	((compound-procedure? procedure)
	 (IF (< (LENGTH ARGUMENTS) (LENGTH (PROCEDURE-PARAMETERS PROCEDURE)))
	     (MAKE-PROCEDURE
	      (BUTFIRST-N (LENGTH ARGUMENTS)
			  (PROCEDURE-PARAMETERS PROCEDURE))	; parameters
	      (PROCEDURE-BODY PROCEDURE)			; body
	      (EXTEND-ENVIRONMENT				; environment
	       (FIRST-N (LENGTH ARGUMENTS)
			(PROCEDURE-PARAMETERS PROCEDURE))
	       ARGUMENTS
	       (PROCEDURE-ENVIRONMENT PROCEDURE))) 	; lexical scope!
	     (eval-sequence
	      (procedure-body procedure)
	      (extend-environment
	       (procedure-parameters procedure)
	       arguments
	       (procedure-environment procedure)))))
	(else
	 (error
	  "Unknown procedure type -- APPLY" procedure))))

This solution uses helper procedures to extract the first N parameters,
and all but the first N parameters, from the original procedure's list of
parameters:

(define (first-n n lst)
  (if (= n 0)
      '()
      (cons (car lst) (first-n (- n 1) (cdr lst)))))

(define (butfirst-n n lst)
  ((repeated cdr n) lst))

This is the most elegant solution, because it deals only with values,
not with expressions -- there's no need to call MC-EVAL anywhere in it.
It's also possible to solve the problem by manipulating the text of the
procedure in various ways.  For example, we could try to substitute the
argument values for the first N parameters in the body, so we'd get the
procedure

	(lambda (exp)
	  (cond ((= exp 0) 1)
		((even? exp) (fast-exp (* 2 2) (/ exp 2)))
		(else (* 2 (fast-exp 2 (- exp 1))))))

for our example.  This is trickier than it looks to get correct, though.
In this example the actual argument is a number, which is self-evaluating.
But suppose the actual argument value is a non-numeric word or a list.
It won't work to substitute the argument *value* into the body; we have
to find the argument *expression* (which means we'd have to do the job in
MC-EVAL rather than in MC-APPLY), or else we have to quote the value each
time we substitute it.

The key point is to be clear on the difference between an expression and a
value -- for example, a LAMBDA expression versus a procedure.  We want to
return a procedure, so either we call MAKE-PROCEDURE or we call

	(mc-eval (make-lambda ...) some-environment)

Which environment should we extend?  The one in the original procedure,
of course -- we don't want to break Scheme's lexical scope rule.  Some
solutions passed the current environment from MC-EVAL to MC-APPLY, thereby
switching to dynamic scope.

Many students came up with solutions modifying EXTEND-ENVIRONMENT instead of
modifying MC-APPLY.  This is a reasonable first idea, since the problem is
about matching formal parameters with actual arguments, and that's the job of
EXTEND-ENVIRONMENT.  But it's really tricky to get this right, because the
context in which EXTEND-ENVIRONMENT is called is that MC-APPLY is going to use
the resulting environment to evaluate the body of the procedure, and we don't
want to evaluate the body in the case of partial application.  Some of you
actually managed to work around this problem by modifying EVAL-SEQUENCE as
well as EXTEND-ENVIRONMENT, something along these lines:

	(define (extend-environment vars vals base-env)
	  (if (= (length vars) (length vals))
	      (cons (make-frame vars vals) base-env)
	      (if (< (length vars) (length vals))
		  (error "Too many arguments supplied" vars vals)
		  (MAKE-PROCEDURE ...))))

	(define (eval-sequence exps ENV-OR-PROC)
	  (cond ((COMPOUND-PROCEDURE? ENV-OR-PROC) ENV-OR-PROC)
		((last-exp? exps) (mc-eval (first-exp exps) env))
		(else (mc-eval (first-exp exps) env)
		      (eval-sequence (rest-exps exps) env))))

but this is an ugly solution.  For one thing, EVAL-SEQUENCE might be used
someplace other than in MC-APPLY, so we shouldn't change its behavior without
thinking about those other callers.  But even if the call to EVAL-SEQUENCE in
MC-APPLY is the only one in the program, it's ugly to have a procedure named
EVAL-SEQUENCE that sometimes doesn't actually evaluate a sequence!  We
accepted working solutions on this model, but you shouldn't get in the habit
of designing this way.


Scoring:  There are too many variants to list them all.  We decided to group
them according to one central issue: do they actually return a procedure?

6  Correct.

5  Correct except for some trivial error.

4  Has the idea: Checks for length mismatch between parameters and arguments,
   and returns a procedure if there are fewer parameters, but something is
   wrong with the new procedure's parameters, body, or environment.

2  Has an idea:  Checks for length mismatch, but then returns a lambda
   expression, an environment, or something else that isn't an MCE procedure
   (including an STk procedure formed by an underlying-Scheme LAMBDA
   expression!).

0  Anything else, including modifying only EVAL-SEQUENCE.