CS 61A		Spring 1994		Midterm 2 solutions

1.  Box & pointer diagrams

> (list '(2 3) '(4 5))
((2 3) (4 5))

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

             2           3                     4           5

The LIST constructor makes a list whose elements are its arguments.
In this case, that means a list of two elements, whose spine is the
two pairs on the top row of the diagram.


> cons (list 2 3) 4)
((2 3) . 4)


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

             2           3

CONS always constructs exactly one pair -- in this case, the one on the
top row of the diagram.  Because the second argument to CONS isn't a
list, the return value isn't a list either, so there's a dot in its
printed representation.


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


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

             H           I           J

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

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

(cdr '(f g h i j)) ===> (g h i j)

(cdr '(g h i j)) ===> (h i j)


> (cons (cdr '(a)) (cdr '(b)))
(())


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

This seems to have been the hardest for most people.  The printed form
can't be (() . ()), because Scheme *never* prints a dot if the next thing
would be a left parenthesis.  If in your diagram you drew an arrow
pointing to () we accepted it, but if your arrow pointed to '() we
didn't, since that means you don't understand what the quote means.
There is only one pair in this diagram!

Scoring:  One point each.


2.  Binary search trees.

Although the ADT doesn't include empty trees, the program is easier to
write if you allow for the possibility of getting an empty list as
argument instead of a tree, because that's what happens when you try to
recur for the children of a leaf node.  On that assumption, here's one
way to write it:

(define (all-smaller? tree num)
  (or (null? tree)
      (and (< (entry tree) num)
	   (all-smaller? (left-branch tree) num)
	   (all-smaller? (right-branch tree) num))))

(define (bst? tree)
  (or (null? tree)
      (and (all-smaller? (left-branch tree) (entry tree))
	   (all-larger? (right-branch tree) (entry tree))
	   (bst? (left-branch tree))
	   (bst? (right-branch tree)))))

Most people wrote equivalent programs using COND, which is fine, but I
find this style cleaner when writing predicates.

A BINARY TREE is just a tree in which each node has at most two
children.  A BINARY SEARCH TREE is a binary tree with the ordering
constraints as described in the text.  The text doesn't make that
entirely clear, because their only use of binary trees is to represent
the SET ADT, for which a BST is needed.  Therefore, we didn't take off
points if in part (a) you assumed the ordering relationship and therefore
only checked the right branch of the tree, as long as you did the tree
recursion properly in (b).

Scoring:  This and the remaining problems are graded on the scale
		5    correct
		3-4  has the idea
		1-2  has an idea
		0    other

Having the idea, in this problem, means doing a tree recursion.  The most
common form of not having the idea was to think, in part (b), that the
ordering must be checked only with respect to the root node, so you left
out the recursive calls to BST?.

We took off one point if you violated the binary tree ADT, using CAR and
CDR instead of ENTRY, LEFT-BRANCH, and RIGHT-BRANCH.  (If you thought
that those three things are names of trees, rather than of procedures,
you didn't have the idea.)

A too-common error was to say things like
	(< (left-branch tree) (entry tree))
as if the left branch were a number!  It's not; it's a tree.


3.  Song ADT.

(define (who-sang song)
  (define (helper songs)
    (cond ((null? songs) #f)
	  ((equal? song (title (car songs)))
	   (artist (car songs)))
	  (else (helper (cdr songs)))))
  (helper great-songs))

The crucial point here was to respect the data abstraction; just finding
your way through the list shouldn't be a challenge at this point in the
course.  So in order to "have the idea" you must say
		(title (car songs))
and not
		(caar songs)

Some people made up an ADT for list-of-songs.  That's perfectly okay, but
not required by the problem.  But it's *not* okay if you used TITLE to
mean CAR when referring to the list of songs!

Some people compromised and made up a different ADT in which they had
selectors like
		(define title-of-first-song caar)
We weren't quite as unhappy about this as we were if you just ignored data
abstraction altogether, but this, too, violates the song ADT.  In your
list-of-songs type, you shouldn't make assumptions about the
representation of an individual song.

I was surprised at how many people were nervous about the idea of a global
variable.  You seemed to think this is a new idea, but in fact every time
you invoke CAR or + or SQUARE or WHO-SANG you are using a global variable!
A variable is a connection between a name and a value, even if the value
is a procedure.

Several people tried to solve the problem with FILTER.  This is a great
idea, except that almost nobody quite got it to work, because they all
left out the invocation of CAR shown in capitals here:

(define (who-sang song)
  (let ((songs (filter (lambda (great) (equal? (title great) song))
		       great-songs)))
    (if (null? songs)
	#f
	(artist (CAR songs)))))

The point is that FILTER returns a *list* of things that match the
condition.  Even if there is only one such thing, FILTER will return a
list of length one.  So you have to extract the song from that one-long
list of songs.

Many people used EQ? instead of EQUAL?.  We didn't take off for that,
because it's not something we've made a fuss about, but it wouldn't
work.  For now, the rule is that EQ? can be used only to compare atoms,
not lists.  In a week or two we'll learn what EQ? means for lists, when
we talk about mutation.

We didn't take off points from the people who expressed incorrect
opinions regarding the quality of Led Zeppelin.


4.  Combine DDP and M-P.

This was the hardest problem for most people, probably because you don't
really understand the essential ideas (as opposed to the specific A&S
implementation) of DDP and M-P.

The answer we wanted was this; the change to operate-2 is shown in
capitals:

(define (operate-2 op arg1 arg2)
  (let ((t1 (type arg1)))
    (let ((proc (DISPATCH t1 op)))
      (proc (contents arg1) (contents arg2)))))

(define (dispatch method-table message)
  (if (equal? (caar method-table) message)
      (cdar method-table)
      (dispatch (cdr method-table) message)))

I've shown DISPATCH as a recursive procedure with no base case.  What
makes that okay is that we said you could leave out the error checks, and
for method-table to run out without finding the correct message would be
an error.  But it's fine if you want to use a COND and check also for
(null? method-table).

Some people didn't change operate-2 at all, but instead wrote a new
procedure GET equivalent to what I've called DISPATCH here; that was
okay.  There are other possible solutions but it's very hard to do it
without a helper procedure to look through the type.

Having the idea means extracting the type from an argument and searching
through it to find the message.  If you built into your program the
assumption that all numbers are complex, you got zero points -- that
defeats the whole point of the enterprise!

One point off for violating the typed-data ADT (using CAR instead of
TYPE, for example).

We were unsympathetic to people who merely copied the solution to a
similar but different problem in one of the sample midterms.

Instead of trying to list all the various ways people got this wrong, let
me try to explain the point about DDP and M-P.  A lot of people thought
that if message-passing is involved, then the program has to look like

(define (operate-2 op arg1 arg2)
  (lambda (message) ...))

but that's a superficial understanding.  Here's the point:

MESSAGE-PASSING means that the knowledge of methods is located in the
data themselves, and that those methods are accessed by sending the data
messages, which are names for the methods.

DATA-DIRECTED PROGRAMMING means that the knowledge of which method goes
with what operation and type takes the form of a table, understandable by
a general-purpose procedure like operate-2, rather than the form of a
COND that checks all the possibilities explicitly.

So the idea is that each datum carries around a manifest type consisting
of a table that associates methods with messages for that type.  Since
the table includes the messages, it's possible for different types to
accept different messages; this is quite different from that sample
midterm problem, in which the four specific operations addition,
subtraction, multiplication, and division are built into the mechanism.