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 #)
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. Data-directed finite state machines.
I said at least twice in lecture that data-directed programming does NOT
mean using get and put; the book's example of data-directed programming
is just one example of a more general idea. The idea is that instead of
building the specific details of one problem into our procedures, we
write more general procedures that use some auxiliary data structure to
specify the precise problem we're supposed to solve. In this case, the
list of transitions ((1 A 2) (1 B 3) ...) is the data structure that
tells our GENERAL fsm interpreter which SPECIFIC fsm we're using.
To make that clearer, here is a program for the particular fsm used as
the example in the question, NOT using data-directed programming:
(define (transition state letter)
(cond ((= state 1) (state1 letter))
((= state 2) (state2 letter))
((= state 3) (state3 letter))
((= state 4) (state4 letter)) ))
(define (state1 letter)
(cond ((eq? letter 'A) 2)
((eq? letter 'B) 3)
((eq? letter 'C) 4)
(else 0) ))
(define (state2 letter)
(cond ((eq? letter 'A) 1)
(else 0) ))
... and so on for the other two states. This program has the specific
transition information built into its procedures. If you wanted to
change a transition, you'd have to rewrite some procedure. Some people
did in fact offer solutions like this, and got no credit. Here is the
solution we had in mind:
(define (transition fsm state letter)
(cond ((null? fsm) 0)
((and (= state (caar fsm))
(eq? letter (cadar fsm)) )
(caddar fsm) )
(else (transition (cdr fsm) state letter)) ))
(define (process fsm state wd)
(if (empty? wd)
state
(process fsm (transition fsm state (first wd)) (bf wd)) ))
This program works not only for the particular fsm diagrammed in the
question, but for ANY fsm, if we give it the appropriate list of
transitions as an argument.
For some reason that I don't understand, practically everyone returned
(cddar fsm) instead of the correct (caddar fsm). You want the third
ELEMENT of the transition sublist, not a SUBLIST of the transition sublist.
But we didn't take off for that.
It's perfectly fine if you want to avoid things like "caddar" (pretty hard
to work through, isn't it?) by defining an abstract data type for
transitions. But please don't think that "data-directed programming"
MEANS using abstract data types. The two ideas are quite distinct, even
though we talked about manifest types during the same week as ddp. If
you want to use an abstract data type your program will look like this:
(define start-state car)
(define arrow-label cadr)
(define end-state caddr)
(define (transition fsm state letter)
(cond ((null? fsm) 0)
((and (= state (start-state (car fsm)))
(eq? letter (arrow-label (car fsm)) )
(end-state (car fsm)) )
(else (transition (cdr fsm) state letter)) ))
You could also define selectors like first-transition and rest-transitions
for the fsm list itself, but I wouldn't bother. Car and cdr are clear
enough for a sequence of any number of the same kind of thing, such as a
sequence of transition triples.
But, speaking of data types, it won't work at all to use car and cdr on
the word we're processing in part B! Car and cdr only work on pairs
(and lists, which are made of pairs), not on words.
It would indeed be possible to use GET and PUT to implement a data-directed
fsm program. You'd set up the program for a particular fsm by PUTting each
transition, with the start state and letter as the row and column labels,
and the end state as the contents of each cell. This isn't exactly what we
asked for, but we gave full credit if you did that properly. But we gave
no credit at all if you tried to invoke the contents of the cell as a
procedure! If you did that, you were just blindly copying the example from
the book without understanding it.
Scoring: Having the idea in part A meant using the fsm list to write a
general program. No credit if the letters A, B, and C appeared in your
program (not data directed) nor if you invoked something you found in a
table (totally off the wall). Having the idea in part B meant using the
procedure you wrote in part A! People who tried to do part B from scratch
invariably wrote programs that CDRed down the fsm list once, then lost it
and couldn't process the second letter. If you got part A completely right
but totally messed up part B, that was three points. The other way around
was two points. If you partially messed up both parts, we used our
judgement in accord with the standard five-point formula.
Go back to the questions
Back to the Midterm/Final page