CS 61A Spring 1994 Midterm 3 solutions 1. Box & pointer diagrams In the diagrams below, the arrows drawn with dots (......>) are replaced by mutation with the ones drawn in bangs (!!!!!!>). You didn't have to show the old ones to get credit. > (let ((x (list 1 2 3 4))) (set-cdr! (cdr x) (cdddr x)) x) (1 2 4) !!!!!!!!!!!!!!!!!!!!! ! V +---+---+ +---+-!-+ +---+---+ +---+---+ | | | | | ! | | | | | | /| ---------> | | | ----->| | | .....>| | | ----->| | | / | | | | | | | | | | | | | | | |/ | +-|-+---+ +-|-+---+ +-|-+---+ +-|-+---+ | | | | | | | | V V V V 1 2 3 4 > (let ((x (list 1 2 3 4))) (set-car! (cdr x) (cadr x)) x) (1 2 3 4) +---+---+ +---+---+ +---+---+ +---+---+ | | | | | | | | | | | /| ---------> | | | ----->| . | ----->| | | ----->| | | / | | | | | | ! | | | | | | | | |/ | +-|-+---+ +-.-+---+ +-|-+---+ +-|-+---+ | ! | | | . | | V V V V 1 2 3 4 [The arrow shown as .!.!.> is both old and new -- the mutation doesn't change anything in this case!] > (let ((x (list 1 2 3 4))) (set-cdr! (cdr x) (car x)) x) (1 2 . 1) [Note the dot!!] +---+---+ +---+---+ +---+---+ +---+---+ | | | | | | | | | | | /| ---------> | | | ----->| | | .....>| | | ----->| | | / | | | | | | | | ! | | | | | | | |/ | +-|-+---+ +-|-+-!-+ +-|-+---+ +-|-+---+ | | ! | | | | ! | | V V ! V V ! 1 2 ! 3 4 ! ^ ! ! ! !!!!!!!!!!!!!!!!! [Note that the new pointer points to the 1, not to the pair above the 1. A lot of people got that wrong.] > (let ((x (list 1 (list 2 3) 4))) (set-car! x (cadr x)) x) [Oops, we left out the second "list" in the exam! Sorry.] ((2 3) (2 3) 4) +---+---+ +---+---+ +---+---+ | | | | | | | | /| ---------> | .!| ----->| | | ----->| | | / | | .!| | | | | | | | |/ | +-.!+---+ +-|-+---+ +-|-+---+ .! | | .! | | V! | V ! | 1! | 4 ! V ! +---+---+ +---+---+ ! | | | | | /| !!!!!!!!>| | | ----->| | | / | | | | | | | |/ | +-|-+---+ +-|-+---+ | | | | V V 2 3 [Note that the new pointer must point to the very same pairs for the sublist (2 3). If you create two new pairs, it's wrong. It matters because a mutation of that sublist will affect it in both positions of the big list.] Scoring: One point each, all or nothing. In a few cases where someone left out all the printed return values but got all the diagrams right, or vice versa, we gave half credit. 2. deep-subst! (define (deep-subst! old new L) (cond ((eq? (car L) old) (set-car! L new)) ((pair? (car L)) (deep-subst! old new (car L)))) (cond ((eq? (cdr L) old) (set-cdr! L new)) ((pair? (cdr L)) (deep-subst! old new (cdr L)))) L) Of course many other solutions are possible, but this is probably the shortest one. Note that it's important that this procedure includes two separate COND expressions -- it would be an error to combine them into one COND with four clauses. (By the way, since all the clauses are there for effect, rather than to compute a value, this is an example in which it's reasonable to use COND without ELSE.) The last line is to provide the return value, but we didn't take off points if you left that out. The crucial points are to do the mutation with set-car! and set-cdr!, and to recur on both the car and the cdr of the argument, but only if they're pairs. Scoring: 5 Correct 4 set-car!, set-cdr!, recur on car and cdr, but bad base case (trying to take the car of an atom) or missing some cases (recur for cdr only if car wasn't the old word, for instance). 3 No set-cdr!, but recur on car and cdr. 2 No recursion on cdr. 1 Uses SET! or allocates pairs (CONS, APPEND, LIST). 0 Even worse. One common error was to say things like (cond ((eq? (car L) old) ;; wrong (set-car! (CAR L) new)) ...) This isn't quite as awful as (set! (car L) new) ;; wrong!! but was probably similarly motivated -- you thought "it's car L that I have to change" instead of thinking "it's L whose car I want to change." Many people had one huge cond with zillions of cases, like "if the car is an atom but not equal to the old word, and the cdr is a pair, then do this." A few actually got it to work. It's not good style, though, because it's really easy to miss a case. Most people who tried it that way *did* miss a case, and lost a point. 3. PROM inheriting from ROM This was the hardest problem for most of you. The key point to recognize is that the child (the prom) does *not* have direct access to the parent's (the rom) local variables, so you can't say (method (set addr val) (set! values ...)) or (set-car! (.. cdr ... values) val) There were two solutions we consider reasonable. The first one takes advantage of the fact that in our OOP system, all classes automatically have methods for all their local variables, so you can say (define-class (prom size) (parent (rom ((repeated (lambda (vals) (cons '() vals)) size) '()))) (method (set addr val) (if (null? (ask self addr)) (set-car! ((repeated cdr addr) (ask self 'values)) val) (error "PROM address already has value")))) Note 1: The fact that you can do this in our oop system shows that you can subvert the read-only nature of the rom class. This is why some oop enthusiasts don't believe in automatically "exporting" the local variables of each object. Note 2: (ask self 'values) gets the entire list of values, which is a mutable data structure. It wouldn't work at all to say things like (set! (ask self addr) val) ;; wrong!!! first of all because you can only set! a symbol, and second because any set! in the prom class could only affect a variable in that class, not in its parent. Set! is very different from set-car! even though both do mutation. Note 3: You don't have to check that the address is a number that's in the right range, because if it isn't, the (ask self addr) will cause the ROM's default-method to give an error message. Note 4: List elements are numbered starting from zero, so a ROM with N elements will have them at addresses 0 through N-1, just like a real computer memory. This means that you shouldn't add or subtract one to anything while finding what's in an address. If you didn't remember about the automatic VALUES method for the ROM class, then you really can't solve this problem reasonably without modifying the ROM class. You would add (method (set addr val) (if (null? (ask self addr)) (set-car! ((repeated cdr addr) values) val) (error "PROM address already has value")))) to the ROM class definition. In this case you don't have to do anything at all to the PROM class; all it needs is the PARENT clause we provided, because the SET message will be delegated by the prom to the rom. We would only accept this solution if accompanied by an explanation saying that the parent prom's local variable VALUES is not in the scope of the child rom, and so can't be reassigned except by the parent. Note 3: I was dismayed at the number of people who asked "what's REPEATED" during the exam, because that seems to me to mean that all those people didn't do the homework back in chapter 1. Of course you can write your own nth-cdr procedure instead, but I think this is the neatest solution. Note 4: Some people had solutions that effectively ignored the ROM parent and kept the values directly in the PROM. This can work, but defeats the whole purpose of OOP, which is to avoid rewriting methods for specializations of a class. In practice, a good programmer would probably do it the other way around, starting with a PROM class and then creating a ROM class that inherits from PROM but intercepts the SET message and makes it an error. (But most of the people who tried this had programs that didn't work. If you do this, you also have to handle the numeric messages yourself, in the PROM object, rather than delegate them to the ROM object, which doesn't have the updated values.) Scoring: The crucial do-or-die point is that the variable VALUES is not in the scope of methods in the PROM class. So solutions including things such as (set-car! (nth-pair address VALUES) value) ;; wrong got 2 points or less. An almost-correct thing that several people tried was this: (define-class (prom size) (instance-vars ((values ((repeated (lambda (vals) (cons '() vals)) size) '())))) (parent (rom values)) ...) so that the ROM and the PROM would in fact have the same data structure as the value of the variable VALUES. The trouble with this is that the creation of an object doesn't necessarily follow the order in which clauses appear. In fact, both parents and instance variables end up as part of the same LET, so the definition of PROM includes something like this: (let ((my-rom (instantiate rom values)) (values ((repeated ...) ...))) ...) (This isn't really quite how it looks, but you get the idea.) In fact it doesn't matter which comes first in the LET, because none of the values in a LET can depend on variables created by the LET. But this was a pretty good try, and we gave it 4 points. Frequent answers that got less than 2 points included ones with no mutation at all; ones with things like (set! (nth-cdr (ask self 'values) value)) [because the first argument to SET! must be a symbol; there's almost no way to use set! to solve this problem]; solutions thinking that there is a BASIC-OBJECT from the Adventure game inside a ROM; and solutions thinking that a ROM (or a PROM) is a table or some kind of list structure [they're really procedures, below the line]. 4. Pascal's triangle stream (a) next-row for streams (define (next-row row) (define (iter old) (if (EMPTY-STREAM? (TAIL old)) (CONS-STREAM 1 THE-EMPTY-STREAM) (CONS-STREAM (+ (HEAD old) (HEAD (TAIL OLD))) (iter (TAIL old))))) (CONS-STREAM 1 (iter row)) The stuff in capitals is what's changed from the sentence version. This was really easy. One student had the following brilliant solution: (define (next-row row) (add-streams row (cons-stream 0 row))) Not only is this short and sweet, but it really takes advantage of the streamness of streams; it's a solution very much in the flavor of the whole idea of streams. If you don't understand why it works, spend some time thinking about it before you ask your TA. (b) Use next-row to build the triangle. Here are two solutions: (define pascal (cons-stream (cons-stream 1 the-empty-stream) ;first row (map next-row pascal))) --or-- (define (pascal-rows row) (cons-stream row (pascal-rows (next-row row)))) (define pascal (pascal-rows (cons-stream 1 the-empty-stream))) Scoring: 2 points for (a), 3 points for (b), except that if you had the wrong base case in both parts you only lost one point for that. Since (a) was so trivial, it really had to be right for full credit. No points if your answer involved SEQUENCE or SET! -- streams are part of functional programming. To make a stream containing the number 1 you say (cons-stream 1 the-empty-stream) Some people just said 1, which is obviously wrong. Others said '(1), which is still wrong because its cdr isn't a promise. A compromise answer some people gave was (cons-stream 1 '()) ;; DAV which works, but violates the stream abstraction. A bunch of people said things like (define (triangle row) ;; wrong (cons-stream row (next-row (tail row)))) This would only compute two rows, not all of them. You wouldn't make that mistake if you really understood the abstract data types involved. To compute a bunch-of-rows, you must (cons-stream one-particular-row a-smaller-bunch-of-rows) so the second argument to cons-stream has to be a bunch of rows, not just a single row, which is what next-row returns. Far too many people more or less rewrote part (a) in their answer to part (b). This means you don't understand the idea of abstraction! Note: I was distressed by the number of people who asked "does that mean you want a stream of streams?" during the exam. If you answered part (a) and you understand data abstraction, then you should understand that if you know 1) A row is represented as a stream. 2) We want a stream of rows. then of course it's a stream of streams!