CS 61A Solutions to sample midterm 2 #2 1. What will Scheme print? 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. > (list (cons 2 3) 4) ((2 . 3) 4) +---+---+ +---+---+ | | | | | /| --------->| | | ------->| | | / | | | | | | | |/ | +-|-+---+ +-|-+---+ | | | V | | 4 | V +---+---+ | | | | | | | | | | | | | +-|-+-|-+ | | V V 2 3 Most people got this. The ones who didn't most often left out the dot in the printed version. > (append (cons '(a) '(b)) '(c)) ((A) B C) +---+---+ +---+---+ +---+---+ | | | | | | | | /| ---------> | | | ----->| | | ----->| | | / | | | | | | | | | | | |/ | +-|-+---+ +-|-+---+ +-|-+---+ | | | | V V | | B C V +---+---+ | | /| | | | / | | | |/ | +-|-+---+ | V A Many people were confused about this one, especially the CONS part. Here is a box and pointer diagram of (cons '(a) '(b)). The starred pair is the one created by the CONS: *********** *+---+---+* +---+---+ *| | |* | | /| --------->*| | | ----------->| | | / | *| | | |* | | |/ | *+-|-+---+* +-|-+---+ ***|******* | | V | | B | V +---+---+ | | /| | | | / | | | |/ | +-|-+---+ | V A Even though this structure was created using CONS rather than LIST, it's a list, because the cdr of the new pair is a list. This list has two elements; the first is (A) and the second is B. So in effect the call to APPEND is (append '((a) b) '(c)). We weren't very sympathetic to people who drew diagrams like this: +---+---+ | | | ---------->| | | ------> etc | | | | +-|-+---+ | V (A) Things in parentheses in the printed representation must be shown as pairs in the diagram! > (cdadar '((e (f) g) h)) () Note that the result is (), not '()! There really is no need for a box-and-pointer diagram for an empty list, which is an atom. We accepted +---+ | /| ---------->| / | |/ | +---+ but *NOT* this: +---+---+ | /| /| ---------->| / | / | |/ |/ | +---+---+ because that would be a pair, representing the list (()), not an empty list. Some people got this wrong because they figured the cdadar incorrectly. Here's how to get there: (car '((e (f) g) h)) ===> (e (f) g) (cdr '(e (f) g)) ===> ((f) g) (car '((f) g)) ===> (f) (cdr '(f)) ===> () CDADAR is an abbreviation for (cdr (car (cdr (car ...)))), so you have to start at the inside and take the CAR of the argument first. Some people read CDADAR left to right as "take the cdr, then the car, ..." but that's wrong. Scoring: One point for each, with both printed form and b&p diagram correct to get the point. One point total for people who got all three printed results correct but left out the b&p diagrams. 2. Fill in the blank. > (CADADR '(g (h i) j)) I The letter I is the second element of (H I), so it's (cadr '(h i)) But the sublist (h i) is the second element of the entire argument, so it's (cadr '(g (h i) j)) So we want (cadr (cadr '(g (h i) j))) and that's abbreviated as CADADR. Scoring: one point, all or nothing! 3. Proj2 data abstraction (a) Type-tagged segment ADT. The solution we wanted was this: (define (make-segment start end) (attach-tag 'segment (cons start end))) (define (start-segment seg) (car (contents seg))) (define (end-segment seg) (cdr (contents seg))) Alternatively, you could use LIST instead of CONS and CADR instead of CDR. Here is the crucial point to understand about data abstraction: WE WANT THIS CHANGE NOT TO BREAK EXISTING PROCEDURES IN THE PROJECT! That means that start-segment, for example, must return a vector, just as it did before the change. Some people wrote (define (start-segment seg) ;; wrong!!! (attach-tag 'segment (car seg))) One problem with this is that the start-segment of a segment isn't the car of the argument anymore, once we have a type attached. But it's much worse to attach the SEGMENT type to the result, because the result isn't a segment! It's a vector. Other people gave make-segment only one argument. Probably this means that you don't know what a segment is, because you let your partner do all the work on the project. Scoring: 2 As shown above. 1 Working code, but not respecting the tagged-data abstraction (e.g., cons instead of attach-tag, cadr and cddr in the selectors). 0 Anything else. (b) Find the midpoint of a segment or frame. (define (midpoint shape) (cond ((eq? (type-tag shape) 'segment) (scale-vect 0.5 (add-vect (start-segment shape) (end-segment shape)))) ((eq? (type-tag shape) 'frame) ((frame-coord-map shape) (make-vect 0.5 0.5))) (else #f))) We accepted less elegant but correct algorithms for the midpoints of the shapes. For a segment another approach is (make-vect (/ (+ (xcor-vect (start-segment shape)) (xcor-vect (end-segment shape))) 2) (/ (+ (ycor-vect (start-segment shape)) (ycor-vect (end-segment shape))) 2)) For frames we saw two other correct approaches. One was essentially to rewrite frame-coord-map: (add-vect (origin-frame shape) (scale-vect 0.5 (add-vect (edge1-frame shape) (edge2-frame shape)))) Another was to find the midpoint of a diagonal of the parallelogram: (midpoint (make-segment (add-vect (origin-frame shape) (edge1-frame shape)) (add-vect (origin-frame shape) (edge2-frame shape)))) Most people had correct algorithms for the midpoint of a segment. There were two common incorrect algorithms for frames; one wrong approach was to ignore the frame's origin, and the other was to assume that the frame's edge1 contributes only to the x-coordinate of the midpoint and that its edge2 contributes only to the y-coordinate. One reason for incorrect solutions to the midpoint of a frame was that people confused the origin of the FRAME with the origin of the COORDINATE SYSTEM -- that is, the point (0, 0). The vector returned by (origin-frame shape) points from the coordinate system origin (0, 0) to the frame's origin, which is one of its corners. That corner might or might not be at (0,0)! For example, when you wrote procedures like BELOW in the project that combine two pictures in adjacent frames, at least one of those frames doesn't begin at (0, 0). Some people wrote a data-directed solution, including things like (put 'frame 'midpoint frame-midpoint) This was okay, but more work than the problem required. Other people tried to use message passing, with less success. A correct use of message passing means that the data -- the frames and segments -- must be represented as procedures: (define (make-segment start end) (lambda (message) ...)) But this is incompatible with part (a)! Some people tried to use a dispatch procedure for the *operator*: (define (midpoint shape) ;; wrong! (lambda (message) ...)) but that doesn't make any sense. You send messages to objects, not to operators. In general, the way to learn in this course is to focus on the IDEAS, not on the SYNTAX. Don't think: "Message passing means that you say (lambda (message) ...) somewhere." Instead think: "Message passing means that the data objects in the system know how to carry out operations on themselves." Some people either didn't read or didn't understand the sample exams in the course reader. Here is a quote from the spring 1995 solutions: *** 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 same thing is true here, except that instead of Trees, this problem used tagged data. RESPECTING THE DATA ABSTRACTION DOES **NOT** MEAN SAYING "TYPE-TAG" WHENEVER YOU MEAN CAR, AND "CONTENTS" WHENEVER YOU MEAN CDR! That is precisely DISrespecting the data abstraction! Respecting it means to distinguish between a type-tagged datum, whose component parts are called type-tag and children, and other data types that have other component parts, such as segments, frames, and vectors. Scoring: 3 Correct. 2 The structure of the COND correct, and also (a) both algorithms work, but have data abstraction violations, or (b) one algorithm is correct, and there are no DAVs. 1 At least one working algorithm. 0 Other. 4. Maximum path in Tree (define (maxpath tree) (if (null? (children tree)) (datum tree) (+ (datum tree) (biggest (map maxpath (children tree)))))) Notice that there is no CAR or CDR in this program! If you didn't want to use MAP, the equivalent recursive solution is (define (maxpath tree) (if (null? (children tree)) (datum tree) (+ (datum tree) (maxpath-forest (children tree))))) (define (maxpath-forest forest) (if (null? (cdr forest)) (maxpath (car forest)) (max (maxpath (car forest)) (maxpath-forest (cdr forest))))) This solution does take the CAR and the CDR of a forest (which is a sequence of Trees), but still does not apply CAR or CDR to a Tree. In either case, the algorithm is to find the maxpath of each child, take the biggest of those, and add the value at the root. So, for the example in the exam, the maxpath values for the three children are 10 (7+3), 11 (2+9), and 10 (4+6). The biggest of those is 11, so we add 5 to that and the overall answer is 16. It doesn't work to find the largest immediate child of the root and work downward from there. In this example, the largest of the children is 7, the first child, but the largest overall path doesn't go through that child. PLEASE don't ever try to solve a tree problem iteratively! Iteration is good for sequences of information -- that is, for one-dimensional structures. But tree problems are fundamentally recursive. A lot of solutions had the form (define (maxpath tree) (maxpath-helper tree (children tree) tree '() '() 0 (datum tree))) or some similar thing with zillions of extra arguments. All such solutions turned out to be quite wrong, and what's worse, they take a long time for us to grade! :-( Here's another correct solution that some people tried: (define (maxpath tree) (biggest (maxpath-helper tree))) (define (maxpath-helper tree) (if (null? (children tree)) (LIST (datum tree)) (map (lambda (t) (+ (MAXPATH t) (datum tree))) (children tree)))) Unfortunately, most people who tried this made two mistakes; one was to leave out the LIST, using just (datum tree) as the base case, and the other was to call maxpath-helper instead of the capitalized MAXPATH above. Both of these errors could be avoided by thinking about the domains and ranges of the functions involved: function argument return biggest list of numbers number maxpath Tree number maxpath-helper Tree list of numbers Since BIGGEST expects a list as its argument, maxpath-helper must return a list, even in the base case. And since + expects numbers as arguments, you can't use maxpath-helper to provide one of the arguments to +, because maxpath-helper returns a list. This was apparently the hardest problem, mainly because people don't understand the Tree Abstract Data Type. The two parts of a Tree are its DATUM, which is a number, and its CHILDREN, which is a forest, that is, a list of Trees. A list of Trees is not a Tree! An expression such as (maxpath (children tree)) has to be wrong because maxpath requires a Tree as its argument, not a list of Trees. Scoring: There were so many wrong approaches that I can't possibly list them all. The general strategy we tried to follow was 5 correct 3-4 has the idea 1-2 has an idea 0 no idea Here are a few common cases: 4 correct except for the base case 3 recursive call to maxpath-helper as described above 2 (maxpath (children tree)) 2 binary tree ADT (e.g., calls to left-branch and right-branch) 1 (biggest (children tree)) with no recursion 5. Debugging the broken EVAL-1. Of the six test cases given, the four that don't give error messages give the correct answer; it's the two that say ERROR that are wrong. What do those two have in common? A compound expression -- a procedure call -- is used as an argument to another procedure. (In the first case, the expression (* 2 2) provides an argument to +; in the second, the expression (+ 1 1) provides an argument to the procedure created by the lambda expression.) So there's something wrong with the evaluation of argument subexpressions. That evaluation of subexpressions happens on line 11. The correct line is (map eval-1 (cdr exp)) )) ; closing earlier open parentheses The reason some of the test cases *do* work is that numbers are self-evaluating, so using the argument expressions instead of the argument values doesn't matter if the argument is just a number. The student said (cdr exp) )) ; This is what you should have in your solution. leaving out the MAP EVAL-1 part. The most common error was to say that the error was (eval-1 (cdr exp)) )) omitting just the MAP. But that would be a disaster; none of the examples would have worked. Take the first test case: (+ 2 3). If that's EXP, then (CDR EXP) is (2 3). But if we try to EVAL-1 that list, we are asking to invoke the procedure 2 with the argument 3! By the way, the reason the last test case doesn't fail is that IF is a special form, so eval-1 never reaches line 11; the subexpressions are evaluated on lines 6-8. Scoring: 5 if correct, 2 if line 11 changed incorrectly, otherwise 0. (But in the rare cases where the correct change was attributed to line 10 or 12, we figured you just misread the line numbers and didn't take off points.) We ignored any explanations you gave, which was a good thing in some cases because the explanations were iffy. 6. Data directed programming 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 tagged data 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. 7. OOP (a) Parents and children. A child class is /a kind of/ the parent class, or /a specialization of/ the parent class, /not/ a part or subset of the parent. Is a keypad a kind of cell phone? NO, a keypad is part of a cell phone. Is an office building a kind of building? YES. Is a staple a kind of stapler? NO, it's something you put into a stapler. Is an arm bone a kind of arm? NO, it's part of the arm. Is an arm bone a kind of bone? YES. Is an arm bone a kind of person? NO, it's part of a person. (b) Class or instance variable. It's a class variable if it's the same for every instance of the class; it's an instance variable if each instance has its own value. The number of taxis in the city isn't different for each taxi; it's a property of the entire CLASS of taxis. The number of milk cartons in a fridge is different for each fridge; mine has quite a few because my son and I can't agree about whether to use fat-free milk or high-fat (2%) milk, so we get both kinds. A fridge in a photographic studio might be full of film, and have no milk cartons at all. So the number is different for each INSTANCE of the fridge class. Scoring: 1/2 point each, rounded down to an integer.