CS 61A		Spring 1995		Midterm 2 solutions

1.  Box & pointer diagrams

> (cddaar '(((a b c d e) (f g h i j))
	    ((l m n o p) (q r s t u))))
(C D E)

(car '(((a b c d e) (f g h i j))
       ((l m n o p) (q r s t u))))
   ===> ((a b c d e) (f g h i j))

(car '((a b c d e) (f g h i j)))
   ===> (a b c d e)

(cdr '(a b c d e)) ===> (b c d e)

(cdr '(b c d e))   ===> (c d e)

The box and pointer diagram for this is just

           +---+---+   +---+---+   +---+---+
           |   |   |   |   |   |   |   |  /|
---------> | | | ----->| | | ----->| | | / |
           | | |   |   | | |   |   | | |/  |
           +-|-+---+   +-|-+---+   +-|-+---+
             |           |           |
             V           V           V

             C           D           E


> (cons '(a b) (append '(c d) '(e f)))
((A B) C D E F)

Some people said ((a b) . (c d e f)) but Scheme never prints the
sequence ". (" in representing a list structure.

In the picture below, the starred pair is the one created by
the CONS invocation.

          ***********
          *+---+---+*        +---+---+   +---+---+   +---+---+   +---+---+
          *|   |   |*        |   |   |   |   |   |   |   |   |   |   |  /|
--------->*| | | ----------->| | | ----->| | | ----->| | | ----->| | | / |
          *| | |   |*        | | |   |   | | |   |   | | |   |   | | |/  |
          *+-|-+---+*        +-|-+---+   +-|-+---+   +-|-+---+   +-|-+---+
          ***|*******          |           |           |           |
             |                 V           V           V           V
             |                                 
             |                 C           D           E           F
             |                                  
             V                                  
	   +---+---+   +---+---+
	   |   |   |   |   |  /|
	   | | | ----->| | | / |
	   | | |   |   | | |/  |
	   +-|-+---+   +-|-+---+
	     |           |
	     V           V

	     A           B


Scoring: one-half point for each printed result, one-half point for
each box & pointer diagram, rounded down.


2.  Type of last element of each result.

> '(list (count 'hello))
(LIST (COUNT 'HELLO))

	So the last element is the (sub)list (COUNT 'HELLO).
	--> LIST

> '(list count)
(LIST COUNT)

	So the last element is the word COUNT.
	--> NON-NUMERIC WORD

> (list 'count count)
(COUNT #<PROCEDURE COUNT>)

	So the last element is the procedure named count.
	--> PROCEDURE

> (list 'hello (count 'hello))
(HELLO 5)

	So the last element is the number 5.
	--> NUMBER

Scoring: One half point each, rounded down.


3.  Tree-accumulate.

Here is the solution we were expecting:

(define (tree-accumulate fn tree)
  (if (null? (children tree))
      (datum tree)
      (fn (datum tree) (forest-accumulate fn (children tree)))))

(define (forest-accumulate fn forest)
  (if (null? (cdr forest))
      (tree-accumulate fn (car forest))
      (fn (tree-accumulate fn (car forest))
	  (forest-accumulate fn (cdr forest)))))

Alternatively, it can be done using other higher-order functions, especially
if you learned about REDUCE in CS 3:

(define (tree-accumulate fn tree)
  (if (null? (children tree))
      (datum tree)
      (fn (datum tree)
	  (reduce fn (map (lambda (t) (tree-accumulate fn t))
			  (children tree))))))

REDUCE takes a function and a list (a sequence, not a tree!) and
accumulates (fn element-1 (fn element-2 (... (fn element-n-1 element-n)...)))


Forest-accumulate has a slightly messier than usual base case, because
there must be at least one tree in the forest in order to get an answer.
(You can't assume that the identity element for FN is zero; that's true
for +, and you might think it's true for MAX if you forget about negative
numbers, but zero isn't the identity for * (1), SENTENCE ('()), WORD (""),
or lots of other possible functions.  But we only took off one point for
any base-case confusion.


*** RESPECTING THE DATA ABSTRACTION DOES **NOT** MEAN SAYING "DATUM" WHENEVER
*** YOU MEAN CAR, AND "CHILDREN" WHENEVER YOU MEAN CDR!!  That is precisely
DISrespecting the data abstraction!  Respecting it means to distinguish
between a tree, whose component parts are called datum and children, and other
data types that have other component parts, such as forests (car and cdr, since
a forest is just a particular kind of sequence), rational numbers (numer and
denom), and so on.

The most common mistake was to ignore the tree abstraction and do a car/cdr
recursion, assuming that the leaves of the tree must be words:

(define (tree-accumulate fn tree)          ;; wrong!
  (cond ((null? tree) --something--)
	((atom? tree) tree)
	(else (fn (tree-accumulate fn (car tree))
		  (tree-accumulate fn (cdr tree))))))

It makes it **WORSE**, not better, if you say "datum" instead of car and
"children" instead of cdr in this procedure.  All such solutions got at
most two points.  Notice that the second argument to tree-accumulate is
supposed to be a tree.  Neither (datum tree) nor (children tree) is a tree!
Therefore neither can be a valid argument to tree-accumulate.

Scoring:  Broadly speaking the scale is the usual
5    correct
3-4  has the idea
1-2  has an idea
0    other

In this problem, "has the idea" means doing a tree recursion respecting
the tree abstraction.  Solutions with only a base case problem, or some
small notation problem, got 4 points; more serious errors that still
showed an understanding of what an abstraction means got 3.

2-point solutions came in two main categories: car/cdr recursions, as
described above, and sequential (non-tree) recursions that respected the
abstraction.  For example:
     (fn (datum (car (children tree)))
	 (forest-accumulate fn (cdr (children tree))))

1-point solutions were too diverse to list; one interesting case was the
use of a BINARY tree abstraction (with left-branch and right-branch); we
took this to mean copying from the text without understanding.

The most noteworthy 0-point solutions were those that built a specific
example (like the functions + and max) into the program.


Just in case you're still thinking "but my procedure works!" think about
this example:

> (tree-accumulate (lambda (a b) (if (> (count a) (count b)) a b))
		   (make-node '(new york)
			      (list (make-node '(albany) '())
				    (make-node '(new hyde park) '())
				    (make-node '(new york) '())
				    (make-node '(yorktown heights) '()))))
(NEW HYDE PARK)

Your car/cdr procedure probably gives the incorrect answer YORKTOWN.


4.  Manifest type/data-directed sets

(a)  Typed empty sets.

(define (make-empty-unordered-set)
  (attach-type 'unordered '()))

(define (make-empty-ordered-set)
  (attach-type 'ordered '()))

Scoring:  2 if correct, 1 if the right answer but violating the manifest-type
data abstraction or if the set isn't empty, 0 if even worse.

Several people wondered what's the point of indicating ordered or unordered
if the set is empty.  That's a good question; the answer is that once we
use adjoin-set, we'll have a typed nonempty set.


(b) data-directed element-of-set?

We expected one of two possible answers.  One uses get and put:

(put 'element? 'ordered element-of-ordered-set?)
(put 'element? 'unordered element-of-unordered-set?)

(define (element-of-set? elt set)
  ((get 'element? (type set)) elt (contents set)))

The other uses an association list:

(define (element-of-set? elt set)
  ((cadr (assq (type set)
	       (list (list 'ordered element-of-ordered-set?)
		     (list 'unordered element-of-unordered-set?))))
   elt
   (contents set)))


A solution would *not* be considered data-directed if it looks like
(define (element-of-set? elt set)     ;; wrong
  (cond ((eq? (type set) 'ordered) ...)
	...))

Scoring:
3  correct
2  data-directed, not quite right
1  data-directed but very wrong, or
   right or almost right but not data-directed
0  not right, not data-directed


A typical one-point solution was one in which element-of-set? takes only
one argument, but uses GET to select a procedure (also called with only
one argument).  We figured this means you at least know what the phrase
"data-directed" means but just copied an example from the book without
thinking about the fact that this problem is about a two-argument procedure.


5.  Message-passing characters

The solution we wanted was

(define (subscript char)
  ((char 'reposition) (make-point 0 -3)))

The crucial point in solving this problem was to understand what a
"character" is.  A character is an abstract data type, represented in
this project by a procedure.  Two other things that are *not* characters:

   *  a command list like '((forward 5) (right 90)) is not a character.
   *  some lines drawn on the computer screen are not a character!

So "having the idea" in this problem means that your procedure takes
a character (a procedure) as its argument and returns a character (a
procedure).

Scoring:

5  correct
4  ((char 'reposition) --something--)
3  returns a character
2  does (char 'reposition) but doesn't invoke the result
   returns an old-style character (not message-passing)
   (char 'reposition --extra-arguments--)
   (some-char 'draw)
   takes a command list as argument
1  even worse
0  even *worse*