CS 61A Fall 2008 Midterm 2 solutions
1. What will Scheme print?
> (cons (list 'a '(b)) (cons (cons 'c 'd) (cons (list 'e) (list 'f))))
((a (b)) (c . d) (e) f)
One way to get there is from the inside out:
(cons (list 'a '(b)) (cons (cons 'c 'd) (cons (list 'e) (list 'f))))
   
( a (b)) ( c . d) ( e) ( f)

( (e) f )

( (c . d) (e) f )

( (a (b)) (c . d) (e) f )
Don't forget that (CONS something somelist) makes a list with the same
/elements/ as in the second argument, but with the first argument as a
new first element. So (cons '(e) '(f)) ==> ((e) f).
This is a list of four elements, so the top of the box and pointer diagram
will be a spine of length four:
>XX>XX>##>*/
   
   
V V V V
xx>x/ XX>d */ f
   
   
V V V V
a X/ c e


V
b
The pairs represented as "*/" above are the ones generated by (list 'e)
and (list 'f). You can see from the diagram that they are indeed
identical to each other in shape, but treated differently by the pair
marked as "##" above, which CONSes them together into ((e) f).
The lowercase pairs "xx" and "x/" are made by the call to LIST in the
subexpression (list 'a '(b)).
Scoring: 2 points for the print form, 2 points for the diagram.
2. OOP.
(defineclass (automobile mpg)
(instancevars (odometer 0) (gas 0))
(method (addgas amount)
(set! gas (+ gas amount))
'done)
(method (go distance)
(let ((gasused (/ distance mpg)))
(if (> gasused gas)
'(you do not have enough gas to get there!)
(begin (set! odometer (+ odometer distance))
(set! gas ( gas gasused))
'done)))))
You don't need explicit methods for GAS and ODOMETER because our oop system
provides them automatically for all object variables.
Many students had trouble with the notation for doing more than one thing in
a branch of an IF. The official right way is with BEGIN, as above. Some
people used AND, which makes more sense in English (where the word "and" has
more than one meaning) than in Scheme, although AND will work, as long as
the things you're doing (the SET! expressions) don't return #F, which would
stop the AND early. Another way would be to use COND, since each COND clause
can have any number of expressions:
(cond ((> gasused gas)
'(you do no have enough gas to get there!))
(else
(set! odometer (+ odometer distance))
(set! gas ( gas gasused))
'done))
Scoring:
6 correct
5 trivial mistake
34 has the idea
12 has an idea
0 other
The main common mistake, not checking for having enough gas, got 4 points
if nothing else was wrong.
3. Scheme1
Here are all the calls, in order:
(eval1 '((lambda (x) (if (> x 0) 1 1)) 2)) ; the whole expression.
(eval1 '(lambda (x) (if (> x 0) 1 1))) ; proc call, so eval the
(eval1 2) ; two subexpressions.
(apply1 (lambda (x) (if (> x 0) 1 1)) '(2)) ; apply proc to list of args.
(eval1 '(if (> 2 0) 1 1)) ; eval body after substitution.
(eval1 '(> 2 0)) ; first step in EVALing the IF.
(eval1 '>) ; proc call, so eval the
(eval1 2) ; three subexpressions.
(eval1 0) ; ...
(apply1 > '(2 0)) ; apply proc to list of args.
(eval1 1) ; Now IF evals its true branch.
Notes:
LAMBDA is a keyword, so (LAMBDA ...) is a special form, so its parts are /not/
evaluated. So no (eval1 'lambda) and so on. And no (apply 'lambda ...)
because lambda isn't a procedure! Same with IF, although IF does evaluate
/some/ of its subexpressions (two of them, to be exact).
APPLY1's second argument is a /list of argument values/. So '(2) not just 2,
for example.
All subexpressions of a procedure call are evaluated, including numbers.
"Selfevaluating" doesn't mean there's no call to EVAL1, just that EVAL1
returns the number itself as its value.
Scoring: 6 points, minus one for each error (unchecked when should be
checked, or vice versa).
4. Trees
(define (ancestor? old young tree)
(or (and (equal? (datum tree) old)
(treemember? young tree))
(not (null? (filter (lambda (child) (ancestor? old young child))
(children tree))))))
It's more efficient to check the children one by one, stopping as soon as
a tree that works is found:
(define (ancestor? old young tree)
(or (and (equal? (datum tree) old)
(treemember? young tree))
(ancestorforest? old young (children tree))))
(define (ancestorforest? old young forest)
(cond ((null? forest) #f)
((ancestor? old young (car forest)) #t)
(else (ancestorforest? old young (cdr forest)))))
Scoring:
7 perfect
6 trivial
54 "the idea"
31 "an idea"
0 "no idea
Assume binary tree > 3 max
Returns (map (lambda (t) (ancestor? ______ (t)) (children tree)) > 5 max
Car/cdr tree DAV 1
Treats trees as lists and code is horrendously wrong > 0
Accumulateor 6
5. Datadirected programming
(a) This is where we use PUT to add the new ADT to the table; the return
value isn't interesting:
(define (makeadt adt fields)
(define (help fields fn)
(if (null? fields)
'okay
(begin (put adt (car fields) (compose car fn))
(help (cdr fields) (compose cdr fn)))))
(help fields (lambda (x) x)))
(define (compose f g) (lambda (x) (f (g x))))
The solution using COMPOSE [or, equivalently, spelling out the lambda
expressions (lambda (x) (car (fn x))) and (lambda (x) (cdr (fn x)))] is
the most elegant, I think, but you could also use the hint and use LISTREF:
(define (makeadt adt fields)
(define (help fields n)
(if (null? fields)
'okay
(begin (put adt (car fields) (lambda (x) (listref x n)))
(help (cdr fields) (+ n 1)))))
(help fields 0))
(b) Here we must look in the table to find out what selector to use:
(define (makeoneof adt values)
(lambda (field) ((get adt field) values)))
That's it! You could add error checking but in general in 61A exams you
aren't required to do that unless the question specifically asks for it.
Scoring: For each part,
4 correct
3 trivial mistake
2 has the idea
1 has an idea
0 other
Even though part (a) has more code, we gave the two parts equal weight
because they are equally important in understanding the difference between
creating an ADT and creating/using an instance of that type.
We accepted solutions that put things other than functions in the table
(e.g., index numbers for use later with LISTREF), although that really
wasn't following the spirit of the instructions  it took a broad reading
of "more or less equivalent," by which we really meant that instead of
the function CADDR you could use (LAMBDA (X) (LISTREF X 2)).
On the other hand, we didn't accept solutions that put /names/ of functions
in the table (even if you later tried to EVAL the name). For one thing,
such names are defined only up to four As and Ds, e.g., CADDDR for the fourth
element of a list. If your ADT has more than four elements, you can't eval
CADDDDR to get the right function. We treated these as "the idea" (2 points).
We also didn't take off if you forgot that LISTREF counts items from zero,
not from one.
In part (b), one point ("an idea") if you just call GET but don't apply the
procedure you get to the data list.
No points at all if there was anything about OLDEST, MIDDLE, YOUNGEST,
or FAMILY in your solution! Examples are just examples; your program has
to work for any example.
Too many people used TYPETAG and CONTENTS as synonyms for CAR and CDR.
There's nothing about typetagged data in this problem, and misusing the
selectors for an irrelevant data type is a much worse violation of data
abstraction than using CAR and CDR where abstract selectors belong.
6. Deep lists.
First, for reference, here's deepreverse, which you wrote in lab:
(define (deepreverse lst)
(if (atom? lst)
lst
(reverse (map deepreverse lst))))
We need a program with a similar structure, except that only every other
level of depth gets reversed. This means we'll want two functions, one
for oddnumbered levels and one for evennumbered levels, but each of
which looks a lot like deepreverse:
(define (semirev lst)
(if (atom? lst)
lst
(reverse (map semihelp lst))))
(define (semihelp lst)
(if (atom? lst)
lst
(map semirev lst)))
This has a somewhat counterintuitive structure  usually, /either/ you use
a helper function to sequence through the children (the elements) of a list
/or/ you use a higherorder function such as MAP. But here the helper
function isn't a "children" or "forest" sort of function; its argument is
just a deep list, same as for the overall function.
Another common approach was to use a helper function with a level counter:
(define (semirev lst)
(define (help lst count)
(cond ((atom? lst) lst)
((even? count)
(reverse (map (lambda (elt) (help elt (+ count 1))) lst)))
(else (map (lambda (elt) (help elt (+ count 1))) lst))))
(help lst 0))
The key point is that the tree recursion has to happen at every level,
but the reversing only at every other level.
This was definitely a problem for which a careful reading (including the hint)
before starting to write a solution would pay off!
Scoring:
8 Perfect
76 Trivial errors
54 "the idea"
31 "an idea"
0 "no idea"
reverses wrong level > 2
map w/o checking atom > 2
level error due to counter > 4 to 6
no deep recursion > at most 2
reverse every other element > at most 3