CS 61A Solutions to sample midterm 2 #3 1. What will Scheme print? Note: Please draw actual boxes, as in the book and the lectures, not XX and X/ as in these ASCII-art solutions. Also, please put in the start arrows! Sometimes it's hard to know where your diagrams are supposed to begin, especially if you use leftward and upward pointing arrows. > (append (list 'a 'b) '(c d)) (A B C D) --->XX----->XX----->XX----->X/ | | | | V V V V A B C D Most people got this. The most common problem was to put quotation marks in the answer, in the printed result and/or in the diagram. The quotation marks are part of Scheme expressions, but not part of the value of those expressions! In other words, the value of the expression 'A is just A, not 'A. > (cons (list 'a 'b) (cons 'c 'd)) ((A B) C . D) --->XX------------->XX--->D | | V V XX----->X/ C | | V V A B The pair at the top, to which the initial arrow points, is the one created by the CONS. This was the part most commonly answered incorrectly. The least bad wrong answer was ((A B) . (C . D)). This is close to correct, in that if you quoted it to Scheme, you'd get this data structure. But Scheme never prints a dot followed by an open parenthesis! It uses list notation instead. (In this case it's an "improper list" because it doesn't end with an empty list in the last cdr.) Other wrong answers were ((A B) C D), which would be a proper list with an extra pair, as if the problem had been (cons (list 'a 'b) (LIST 'c 'd)) and (A B C . D), a structure of only three pairs, as if the problem had been (APPEND (list 'a 'b) (cons 'c 'd)) > (list (list 'a 'b) (append '(c) '(d))) ((A B) (C D)) --->XX------------->X/ | | V V XX----->X/ XX----->X/ | | | | V V V V A B C D The two pairs in the top row are the ones generated by LIST. It always creates a list whose length is the number of arguments, which is two in this example. The first element is (A B); the second is (C D). > (cdar '((1 2) (3 4))) (2) --->X/ | V 2 (car '((1 2) (3 4))) --> (1 2) (cdr '(1 2)) --> (2) Scoring: 1/2 point per printed form, 1/2 point per box and pointer diagram, rounded down to the nearest point. Exception: Side-issue mistakes made consistently in all problems, such as putting quotation marks in the result, lost no more than 1 point altogether in the printed form and 1 point altogether in the diagram. Note: When drawing box and pointer diagrams, please be careful about the arrows; it makes your diagrams much easier to read. There should be an arrowhead at the end (next to the thing the arrow points at). The tail of the arrow should be INSIDE a box; the head should be NEXT TO a box or other datum. For example: +-----+-----+ | | /| ----->| | | / | | | |/ | +--|--+-----+ | V 2 Note how the arrow that points to the 2 starts inside the car of the pair. 2. deep-accumulate Here's the solution I was hoping for: (define (deep-accumulate op init struct) (cond ((null? struct) init) ((not (pair? struct)) struct) (else (op (deep-accumulate op init (car struct)) (deep-accumulate op init (cdr struct)))))) Many other correct solutions are possible. One variant, for people who didn't quite have the courage to use a single value as the base case, was to replace the second COND clause with this: ((not (pair? (car struct))) (op (car struct) (deep-accumulate op init (cdr struct)))) Also, instead of using car/cdr recursion, you could replace the last COND clause with this: (else (accumulate op init (map (lambda (s) (deep-accumulate op init s)) struct))) but most people who tried this got it wrong, because they tried to map deep-accumulate itself instead of using a LAMBDA as above. Another clever solution was to use the FRINGE procedure from exercise 2.28 to turn the deep list into a flat list of atoms: (define (deep-accumulate op init struct) (accumulate op init (fringe struct))) To test for a leaf of the structure, we accepted ATOM? and NUMBER? in place of (NOT (PAIR? STRUCT)) even though there's no ATOM? in the current version of Scheme, and nothing in the problem restricts the elements to numbers. One common error was to use the Tree abstract data type (with selectors DATUM and CHILDREN) although this problem is not about those Trees. People who did that may have been copying a solution from an earlier year's exam. Another too-common error was to build the operation + or the identity element 0 into the code; this isn't having the idea, which is about higher-order functions. Scoring: The possible answers to this were too varied for us to make up a detailed enumeration of them. Instead we used my standard grading scale for programming questions: 5 correct 3-4 has the idea 1-2 has an idea 0 other 3. Tree recursion. This is a question in which it's essential to understand the domain and range of the procedure you're writing, before you start writing it! The arguments to datum-filter are a predicate and a *tree*. What it returns is *not* a tree, but a sequential list whose elements are DATUMs from the tree. So you should expect to use tree selectors (DATUM and CHILDREN), but a list constructor (CONS or LIST or APPEND). There are several ways this can be written. The most straightforward is to use recursion, with a helper for forests: (define (datum-filter pred tree) (if (pred (datum tree)) (cons (datum tree) (forest-datum-filter pred (children tree))) (forest-datum-filter pred (children tree)))) (define (forest-datum-filter pred forest) (if (null? forest) '() (append (datum-filter pred (car forest)) (forest-datum-filter pred (cdr forest))))) Some notes on the above: 1. There's no such thing as an empty tree (this is different from the convention for binary trees), so there's no need for a NULL? check in datum-filter. But we didn't take points off for including one. 2. Why is it CONS in datum-filter, but APPEND in forest-datum-filter? Because in datum-filter we are sticking exactly one datum onto the front of a list of data. But in forest-datum-filter, both of the arguments to APPEND are *lists* of data, not a single datum. We want to combine the elements of the two lists into one big list of those elements. 3. Datum-filter doesn't use CAR or CDR, because its argument is a tree; forest-datum-filter doesn't use DATUM or CHILDREN, because its argument *isn't* a tree! 4. PRED is called to decide whether or not to include a particular datum, but we're including the datum, not the value returned by PRED! 5. Many people threw in unnecessary tests for special cases, such as leaft nodes, nodes with exactly one child, etc. Often this unnecessary code had errors, losing points! Another solution uses higher order functions: (define (datum-filter pred tree) (let ((kids (flatmap (lambda (c) (datum-filter pred c)) (children tree)))) (if (pred (datum tree)) (cons (datum tree) kids) kids))) I used the LET so that I wouldn't have to type the FLATMAP call twice; it's not strictly necessary. If you didn't remember about FLATMAP (SICP page 123) you could say (let ((kids (accumulate append '() (map ...)))) ...) Some people used car/cdr recursion, applying PRED to the words in the tree. Not only is this a data abstraction violation, it also doesn't work! There is no guarantee that the datum in each node is a word; lists are allowed as data, as in the (SAN FRANCISCO) datum in the world tree. You don't want to apply the predicate to the word SAN and separately to the word FRANCISCO. Another common error was (datum-filter pred (children tree)) ; WRONG! This confuses trees with forests. Scoring: 2 points for visiting all the nodes 2 points for selecting with the predicate 2 points for flattening the result correctly 1 point for respecting the data abstraction. In the 2-point categories, it was possible to get one point for code that was clearly trying to do the right thing, but incorrectly. It's possible for one error to lose points in multiple categories. For example, the (datum-filter pred (children tree)) error lost the two points for visiting all the nodes, but in most cases also lost the points for flattening correctly. If forest-datum-filter calls append, but datum-filter also calls append (instead of the correct call to cons), that lost one point. 4. Message passing. A correct solution appears below. The solution required the use of message- passing; a working solution that involved get/put data-directed style got no credit. (define (make-rat num den) (define (dispatch msg) (cond ((eq? msg 'numer) num) ((eq? msg 'denom) den) ((eq? msg 'type) 'rational) ((eq? msg 'raise) (make-real (/ num den))) (else ((dispatch 'raise) msg)) )) dispatch) (define (type r) (r 'type)) (define (raise r) (r 'raise)) You could have used the "operate" function, e.g. (define (type r) (operate 'type r)) Essentially, two points could be earned for each part: implementing the type function, implementing the raise function, and implementing "inheritance" (the "pass-the-buck" action of part c). Some common errors, and the points they lost, were the following. -2 Everything perfect, and working, but raise implemented as a cond. -2 Type implemented as a cond. Many of these people would have lost other points for using car, rational?, or (eq? x 'make-rat). Some people even tried to use the selectors to tell what type something was, e.g. (cond ((number? (numer x)) 'rational) ...) We noticed no way to implement type as an cond and not make some other disastrous mistake. -1 Else clause to dispatch said (else (raise ...)) instead of (else ((raise...) msg)). -1 People tried to inherit with (msg (raise...)) instead of ((raise ...) msg). -1 Any number of missing single quotes, particularly (define (type x) (x type)). 5. OOP (a) button object: (define-class (button) (instance-vars (freq 0)) (method (set-freq! value) (set! freq value))) Note that there is no need to write a FREQ method, since the OOP system automatically provides methods to read the object's variables. (b) radio object: (define-class (radio) (instance-vars (freq 90.7) (buttons (list (instantiate button) (instantiate button) (instantiate button) (instantiate button) (instantiate button) (instantiate button)))) (method (set-button! num) (ask (list-ref buttons num) 'set-freq! freq)) (method (push num) (set! freq (ask (list-ref buttons num) 'freq))) (method (up) (set! freq (+ freq 0.2))) (method (down) (set! freq (- freq 0.2)))) The most common serious error was to make the variable BUTTONS a list of names of buttons, such as '(0 1 2 3 4 5) or '(BUT0 BUT1 BUT2 ...). First of all, there is no need for the buttons to have names at all. Second, there is no way to look up a name and then use it as the first argument to SET!, as in (set! (list-ref buttons num) freq) ;; WRONG! SET! is a special form whose first argument *is not evaluated* and must be a symbol -- the actual name of a variable, not an expression whose value would be the name. Such solutions got at most one point. Another fairly common error was to define six global variables containing buttons, so that all radios share the same buttons! These solutions got at most two points. Some people tried to avoid that last error by using DEFINE as a clause within a DEFINE-CLASS. Sorry, but that doesn't work; you can only use the clauses that DEFINE-CLASS understands: METHOD, INSTANCE-VARS, CLASS-VARS, and so on. In this case, INSTANCE-VARS was what you wanted. If otherwise correct, these solutions got three points. Some people tried to make RADIO the parent of BUTTON, or even sometimes the other way around. This doesn't make any sense. A radio is not a special kind of button, and a button is not a special kind of radio. These solutions got at most one point. Finally, several people gave the RADIO class six instantiation variables to hold the buttons, so that when creating a radio you'd say something like (instantiate radio (instantiate button) (instantiate button) (instantiate button) ...) This works, but isn't a very realistic simulation. When you buy a radio, you don't also buy six buttons and install them; the radio just comes with six buttons. We gave these solutions two points.