CS 61A Spring 1992 Midterm 2 solutions
1. Box & pointer diagrams
(cons (cdr '(x)) 3)
(cdr '(x)) is the empty list, so this is the same as (cons '() 3) and
therefore the result is:
(() . 3)
There is a dot in the printed result because it is not a proper list;
it contains a pair (its only pair, in fact) whose cdr is neither a pair
nor the empty list.
Diagram:
+---+---+
| /| |
---------> | / | | |
|/ | | |
+---+-|-+
|
|
V
3
It's okay if the left side of the box has a pointer to a SINGLE box
with a slash (representing the empty list) or a pointer to (), but
it's wrong if the left side of the box points to a PAIR with two
slashes. That would be a list containing an empty list, (()).
It's also wrong if you said that Scheme would print (nil . 3); the
symbol "nil" happens to be a name for the empty list, as if we'd said
(define nil '()), but it's not the empty list itself. If this is
confusing, think about what would happen if you said (define a 3) and
then said (+ 1 2). You wouldn't expect Scheme to print "a," would you?
(Yes, this is different in Common Lisp, where "nil" is not an ordinary
symbol but a special magic cookie.)
(list 2 '(3 4))
LIST creates a list containing its arguments as members. Here we are
calling it with two arguments, so we end up with a list of two elements,
one of which is itself a list:
(2 (3 4))
No improper lists here, so no dots. Diagram:
+---+---+ +---+---+
| | | | | /|
---------> | | | ----->| | | / |
| | | | | | |/ |
+-|-+---+ +-|-+---+
| |
| |
V V
+---+---+ +---+---+
2 | | | | | /|
| | | ----->| | | / |
| | | | | | |/ |
+-|-+---+ +-|-+---+
| |
| |
V V
3 4
((lambda (s) (cons (car s) (cddr s))) '(w x y z))
If "s" represents the list (w x y z), then (car s) is w and (cddr s) is
(y z). In effect we are doing (cons 'w '(y z)), creating a three-element
list. (Note that CONS and LIST do different things! CONS always creates
exactly one new pair; LIST creates as many new pairs as it has arguments.)
So this prints
(w y z)
Diagram:
+---+---+ +---+---+ +---+---+
| | | | | | | | /|
---------> | | | ----->| | | ----->| | | / |
| | | | | | | | | | |/ |
+-|-+---+ +-|-+---+ +-|-+---+
| | |
| | |
V V V
w y z
The worst mistake here was that some people had the word S in their
results! "S" is a formal parameter of the function we're invoking;
the actual argument (w x y z) is substituted for it when we call the
function!
(cons (list 2 3) '(a))
CONS always creates one new pair. Its first argument is a list that has
two pairs in it; the second argument is a list with one pair. We'll end
up with four pairs altogether.
When the second argument to CONS is a list, the result is also a list,
with one new element at the front. So there won't be any dots in the
printed form:
((2 3) a)
Note that it isn't ((2 3) (a)), which is what you'd get if you used
LIST instead of CONS. Diagram:
+---+---+ +---+---+
| | | | | /|
---------> | | | ----->| | | / |
| | | | | | |/ |
+-|-+---+ +-|-+---+
| |
| V
|
| a
|
V
+---+---+ +---+---+
| | | | | /|
| | | ----->| | | / |
| | | | | | |/ |
+-|-+---+ +-|-+---+
| |
| |
V V
2 3
Scoring: One point each; you had to get both the printed result and the
diagram to get the point. Also, if you would have had four points but
you left out all the arrows pointing to the heads of the lists, we took
off a point.
2. uniq
Is this sequential or tree recursion? We are looking at each element of
the list as one whole thing, not delving into the structure of sublists,
so it's sequential recursion.
Is it more like mapping or like filtering? It's more like filtering,
because we are selecting a subset of the argument, not transforming each
element into something else. So we can expect the solution to look much
like the filtering examples you've seen earlier, like this one:
(define (evens seq)
(cond ((null? seq) '())
((even? (car seq)) (cons (car seq) (evens (cdr seq))))
(else (evens (cdr seq))) ))
Our solution will look much like this, but NOT EXACTLY like this.
(In general, how can old problems help you solve new problems? There
are two different wrong ways to think about this. One wrong way is to
approach every problem as if you've never seen any other programs before.
The other wrong way is to find some old problem that looks similar and
then slavishly copy it down without thinking about what it means and how
this problem might be different.) The crucial difference is that the
predicate we'll use to do the selection of elements isn't just a function
of (car seq). Instead, we have to check
(equal? (car seq) (cadr seq))
If this is true we want to REJECT the element. An important implication
is that the base case can't just be a check for an empty list. We have
to have at least two elements in order for this predicate to be legal.
(define (uniq seq)
(cond ((null? seq) '()) ; just in case we are given () as argument
((null? (cdr seq)) seq)
((equal? (car seq) (cadr seq)) (uniq (cdr seq)))
(else (cons (car seq) (uniq (cdr seq)))) ))
We didn't take off points if you left out the first cond clause.
Of course this is not the only possible solution, but it's the most
straightforward. We did say "takes a list as its argument," not a sentence,
but it wouldn't be so terrible if you used the sentence data type instead of
the list data type, as long as you did it consistently:
(define (uniq sent)
(cond ((empty? sent) '())
((empty? (bf sent)) sent)
((equal? (first sent) (first (bf sent))) (uniq (bf sent)))
(else (se (first sent) (uniq (bf sent)))) ))
A lot of people didn't read the problem carefully and missed the part
about "repeated several times IN A ROW." You solved a different
problem, removing all duplicates instead of only consecutive duplicates.
We gave these solutions three points.
I keep saying, don't try for iterative solutions! A bunch of people
tried to do this iteratively and they mostly ended up with hideous
messes, usually not even working ones.
Scoring: All of questions 2-4 are graded on the following scale:
5 if correct and not hideous
3-4 if you have the right idea
1-2 if you have an idea
0 if you have no idea
In this case, having the idea means writing a sequential filtering function
that has something to do with looking for duplicates.
3. add-numbers.
Is this sequential or tree recursion? We are looking for numbers that
are elements of sublists of the argument list, not just elements of the
argument list itself, so it's tree recursion. That means that the base
case is a leaf node. Within that category, there are numbers and
non-numbers; the latter count as zero:
(define (add-numbers tree)
(cond ((number? tree) tree)
((atom? tree) 0)
(else (+ (add-numbers (car tree))
(add-numbers (cdr tree)) )) ))
It's okay if you had an additional cond clause to check for a null argument,
but in this case it isn't necessary because what we want to return for a
null argument is the same thing we want to return for any other non-numeric
atom, namely zero.
The crucial point is that there have to be two recursive calls, one for
the car and one for the cdr. That's the hallmark of tree recursion.
Trying for an iterative solution here is not merely perverse but downright
wrong. Tree problems are inherently non-iterative.
If your solution includes things like (number? (car tree)) then you might
have a working program, but it means you don't really understand the fact
that a leaf node is a valid argument in itself. The base case of tree
recursion is leaf nodes, not lists of leaf nodes.
This could also be done by setting up a data abstraction for trees, but
to be faithful to the example it has to be the kind of tree in which only
leaf nodes have data, so the appropriate selectors are something like:
(define leaf? atom?)
(define (datum leaf-node) leaf-node)
(define (children branch-node) branch-node)
and then you'd end up with something like
(define (add-numbers tree)
(if (leaf? tree)
(if (number? (datum tree)) (datum tree) 0)
(sum-list (mapcar add-numbers (children tree))) ))
(define (sum-list seq)
(if (null? seq)
0
(+ (car seq) (sum-list (cdr seq))) ))
This is all okay, but not necessary. Abstract data types are most important
for specific things like rational numbers or line segments or poker hands,
not so much for generic trees (or sequences). Expressions of the form
(combine (recur (car tree)) (recur (cdr tree)))
are a Lisp cliche -- everyone will understand what it means. (Of course,
if a test problem GIVES you selectors and constructors for an abstract
data type, you should certainly respect the abstraction.)
4. 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