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 some-list) 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 lower-case 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. (define-class (automobile mpg) (instance-vars (odometer 0) (gas 0)) (method (add-gas amount) (set! gas (+ gas amount)) 'done) (method (go distance) (let ((gas-used (/ distance mpg))) (if (> gas-used gas) '(you do not have enough gas to get there!) (begin (set! odometer (+ odometer distance)) (set! gas (- gas gas-used)) '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 ((> gas-used gas) '(you do no have enough gas to get there!)) (else (set! odometer (+ odometer distance)) (set! gas (- gas gas-used)) 'done)) Scoring: 6 correct 5 trivial mistake 3-4 has the idea 1-2 has an idea 0 other The main common mistake, not checking for having enough gas, got 4 points if nothing else was wrong. 3. Scheme-1 Here are all the calls, in order: (eval-1 '((lambda (x) (if (> x 0) 1 -1)) 2)) ; the whole expression. (eval-1 '(lambda (x) (if (> x 0) 1 -1))) ; proc call, so eval the (eval-1 2) ; two subexpressions. (apply-1 (lambda (x) (if (> x 0) 1 -1)) '(2)) ; apply proc to list of args. (eval-1 '(if (> 2 0) 1 -1)) ; eval body after substitution. (eval-1 '(> 2 0)) ; first step in EVALing the IF. (eval-1 '>) ; proc call, so eval the (eval-1 2) ; three subexpressions. (eval-1 0) ; ... (apply-1 > '(2 0)) ; apply proc to list of args. (eval-1 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 (eval-1 '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). APPLY-1'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. "Self-evaluating" doesn't mean there's no call to EVAL-1, just that EVAL-1 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) (tree-member? 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) (tree-member? young tree)) (ancestor-forest? old young (children tree)))) (define (ancestor-forest? old young forest) (cond ((null? forest) #f) ((ancestor? old young (car forest)) #t) (else (ancestor-forest? old young (cdr forest))))) Scoring: 7 perfect 6 trivial 5-4 "the idea" 3-1 "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 Accumulate-or 6 5. Data-directed programming (a) This is where we use PUT to add the new ADT to the table; the return value isn't interesting: (define (make-adt 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 LIST-REF: (define (make-adt adt fields) (define (help fields n) (if (null? fields) 'okay (begin (put adt (car fields) (lambda (x) (list-ref 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 (make-oneof 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 LIST-REF), 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) (LIST-REF 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 LIST-REF 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 TYPE-TAG and CONTENTS as synonyms for CAR and CDR. There's nothing about type-tagged 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 deep-reverse, which you wrote in lab: (define (deep-reverse lst) (if (atom? lst) lst (reverse (map deep-reverse 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 odd-numbered levels and one for even-numbered levels, but each of which looks a lot like deep-reverse: (define (semirev lst) (if (atom? lst) lst (reverse (map semi-help lst)))) (define (semi-help 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 higher-order 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 7-6 Trivial errors 5-4 "the idea" 3-1 "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