CS 61A Spring 1994 Final exam solutions 1a. (let ((x (cons '() '()))) (set-car! x x) (set-cdr! x x) x) --------- | | | ------->| * | * | /--->| | | | |<---\ | --|---|-- | | | | | | | | | \____/ \____/ 1b. (define (funny! x) (if (null? x) '() (let ((temp (cdr x))) (funny! temp) (set-cdr! x (car x)) (set-car! x temp) x))) (funny! (list 1 2)) On first entry to funny! we have: --------- --------- | | | | | /| ------->| * | *--------->| * | / | | | | | | | |/ | --|------ --|------ | | V V 1 2 Let's call the left pair I and the right pair II. So the first thing we do is bind TEMP to pair II and call funny! again on that pair. The second invocation of funny! binds TEMP to '() and invokes funny! for a third time, with '() as the argument. This third invocation has no effect. Back in the second invocation, X is pair II and TEMP is '(), so after the set-cdr! and the set-car! we have --------- --------- | | | | /| | ------->| * | *--------->| / | * | | | | | |/ | | | --|------ ------|-- | | V V 1 2 That finishes the second funny! so we are back in the first funny! with X bound to pair I and TEMP bound to pair II. So after the set-cdr! and the set-car! we have --------- --------- | | | | /| | ------->| * | * | /-->| / | * | | | | | | | |/ | | | --|---|-- | ------|-- | | | | | V | V | | | 1 | 2 | | \_________/ Basically, what funny! does is to interchange the car and cdr of each pair of the list. A typical one-point error was to swap the parts of only one pair. 1c. We want to generate the structure .-----------------------------. | | V | --------- --------- | | | | | | /| | -------->| | | ----------->| | | / | | | | | | | | |/ | | --|------ --|------ | | ^ | | | | | | | | | | V | V | ------|-- --------- | | | | | | | | | | | | | | | | | --------' | | | | | | | | --|------ --|------ | | | | | | V V A B Call the pairs in the top row I and II, and the ones in the bottom row III and IV. One straightforward way to generate any such structure is to create four isolated pairs and make all the links by hand. Many people did this on the exam: (let ((I (cons '() '())) (II (cons '() '())) (III (cons '() '())) (IV (cons '() '()))) (set-car! I III) (set-cdr! I II) (set-car! II IV) ; we could say (set-cdr! II '()) but it's not needed (set-car! III 'A) (set-cdr! III I) (set-car! IV 'B) (set-cdr! IV I) I) This is perfectly fine. You can do it more easily if you notice that most of the structure is perfectly ordinary, a list of two singleton lists: (let ((x (list (list 'A) (list 'B)))) (set-cdr! (car x) x) (set-cdr! (cadr x) x) x) Note that it's not permissible to say (let ((x '((A) (B)))) ...) because you aren't allowed to mutate constant (quoted) lists, but we didn't take off points for that. Other shortcut solutions are possible, such as this one: (let ((x (list '() '()))) (set-car! x (cons 'A x)) (set-car! (cdr x) (cons 'B x)) x) A very common one-point error was to think that the arrow from the cdr of the lower-left pair points to the CDR of the upper-left pair, rather than to the whole pair, like this: (set-cdr! (car x) (CDR X)) ;; wrong! A much worse error was to think that an expression like (LIST Y Y) makes two copies of Y, as in this sort of solution: (let ((y (cons '() '()))) ;; wrong! (let ((x (list y y))) (set-car! (car x) 'A) (set-car! (cadr x) 'B) ...)) This makes a structure with only three pairs, not four. The first set-car! is useless because it is overruled by the second. 2. Ternary tree ADT. (a) Create the ADT: (define (make-ternary datum left middle right) (cons (cons datum left) (cons middle right))) (define datum caar) (define left-branch cdar) (define middle-branch cadr) (define right-branch cddr) (define (set-datum! node value) (set-car! (car node) value)) (define (set-left-branch! node value) (set-cdr! (car node) value)) (define (set-middle-branch! node value) (set-car! (cdr node) value)) (define (set-right-branch! node value) (set-cdr! (cdr node) value)) (b) flip the tree (define (flip node) (if (null? node) '() (let ((temp (left-branch node))) (flip temp) (flip (middle-branch node)) (flip (right-branch node)) (set-left-branch! node (right-branch node)) (set-right-branch! node temp)))) Scoring: For (a), 2 points if correct, 1 point if implements an ADT but not looking like the picture in the problem, 0 if you didn't seem to understand what a constructor or a selector or a mutator is. The most common 1-point error was to make the constructor with (list datum left middle right), but some people also got cars and cdrs backwards. There were two common 0-point errors: writing mutators that only take one argument, and using SET!. For (b), 3 points if correct, 2 points if tree-recursive and uses a temporary variable for swapping, 1 point if it mutates a node more or less correctly but only one node, 0 points if even worse. The most common 2-point errors were to forget the recursion for the middle branch (even though you aren't *moving* that branch, you still have to flip *every node* in the tree!) and to construct new nodes with make-ternary instead of using mutation. The most common 1-point error was to flip one node correctly, or to flip every node but without using a temp variable. We took one point off of what the score would otherwise be for a solution that didn't respect the data abstraction (for example, one that used CAR or CDR). 3. Find the bugs and data abstraction violations in ... Here is the relevant code: (define (+money amt1 amt2) (make-dollar (+ (contents (dollarize amt1)) (contents (dollarize amt2))))) (define (dollarize amt) (* (conversion (car amt)) (cdr amt))) The result returned by dollarize is a plain old number, with no type information attached, and yet +money tries to take its CONTENTS. This can be fixed in either of two ways: eliminate the two calls to contents in +money, or add a call to make-dollar in dollarize. (But not both changes!) The gross violation of data abstraction is the use of car and cdr in dollarize. So, the easiest fix is (define (dollarize amt) (make-dollar (* (conversion (type amt)) (contents amt)))) and leave everything else alone. Scoring: 2 points for fixing the bug, 2 points for fixing the DAV, 1 point for saying which was which, -1 point for claiming something was wrong that wasn't wrong. (We didn't take off points if you had stylistic objections to other things, as long as you didn't call them bugs or DAVs.) Some people were upset about the use of "type" as the name of the formal parameter to conversion, because it's also the name of a procedure. This is a confusing thing to do, I agree, and so it's bad style, but it's not a violation of data abstraction and it's certainly not a bug. As long as I don't try to use the procedure named TYPE inside of CONVERSION, which I don't, everything will work fine. Another valid stylistic complaint, but not a bug or a DAV, is that the formal parameter AMT in procedures MAKE-DOLLAR and so on represents a pure number, whereas the same name AMT is used in DOLLARIZE to mean a manifest-typed amount of money. Many people objected to (define attach-type cons) (define type car) (define contents cdr) wanting us instead to say (define (attach-type foo baz) (cons foo baz)) and so on. There is absolutely nothing wrong with what we did here! It has all the advantages of data abstraction and it's a little faster than what you want us to change it to. 4. Regroup. There are several ways to do this. Probably the easiest is to use a helper procedure: (define (regroup template) (lambda (lst) (regroup-help template lst))) (define (regroup-help template lst) (if (number? template) (nth template lst) (cons (regroup-help (car template) lst) (regroup-help (cdr template) lst)))) A variation is to write the helper procedure using MAPCAR: (define (regroup-help template lst) (if (number? template) (nth template lst) (mapcar (lambda (subtemplate) (regroup-help subtemplate lst)) template))) Alternatively, the program can be written without a helper by using a somewhat tricky recursive call: (define (regroup template) (lambda (lst) (if (number? template) (nth template lst) (cons ((regroup (car template)) lst) ((regroup (cdr template)) lst))))) The important point is to notice that the recursive call to regroup returns a procedure, and we must invoke that procedure on the data list. This, too, can be done using MAPCAR: (define (regroup template) (lambda (lst) (if (number? template) (nth template lst) (mapcar (lambda (subtemplate) ((regroup subtemplate) lst)) template)))) Scoring: The standard BH five-point scale: 5 correct 3-4 has the idea 1-2 has an idea 0 other In this problem, "has the idea" means that the domain and range of regroup are correct (takes one argument, a list structure with numbers, and returns a function of one argument, a data list) and also that the program is tree recursive. (It's not good enough if you can handle a template with lists of lists of numbers, but not lists of lists of lists of numbers.) Several people found an old example called PERMUTE that's similar to this problem but with a sentence, rather than a tree, as the template. They essentially copied that old solution, so their procedure was a sequential process using one call to MAPCAR, rather than a tree process. These solutions got two points. Another way to not have the idea is to mutate the template instead of constructing a new list. For one thing, it's illegal to mutate quoted lists; for another, supposing it were legal, a second call to F in the example would fail because the template wouldn't be a template any more! 5A. OOP tapes. (a) 2 points, tape class. There are two basic ways to approach this. Probably the most straightforward is to keep a local state variable containing a number that indicates where we're up to in the tape: (define-class (tape words) (instance-vars (position 0)) (method (left) (if (= position 0) #f (sequence (set! position (- position 1)) (nth position words)))) (method (right) (if (= position (length words)) #f (sequence (set! position (+ position 1)) (nth (- position 1) words))))) Notice that the two methods are not quite symmetrical. In one case the return value should be the word at element number POSITION of the lyrics, and in the other case it should be the word to the left of that. In both cases it's the word that the tape has just moved past. But we didn't take off for off-by-one errors, mainly because it made the grading go a lot faster! Some people who did notice the asymmetry tried to solve the problem by using the *old* value of position to choose the return value in the RIGHT method. That's okay if you do it this way: (method (right) (if (= position (length words)) #f (let ((result (nth position words))) (set! position (+ position 1)) result))) but it's a terrible mistake to say (method (right) ;; wrong!!!! (if (= position (length words)) #f (sequence (nth (- position 1) words) (set! position (+ position 1))))) The value that SEQUENCE returns is the value of its last argument expression. It can't read your mind and discover that you'd rather return the value of the first expression in this case. By the way, the best way to think about position numbers to avoid making off-by-one errors is to think of the tape's position as being *between* two words, rather than on a word. So if there are N words, there are N+1 possible positions: two at the ends and N-1 between words. The only good thing about the Macintosh is that they got this right; the cursor in a text editing window is a thin vertical line between two characters, rather than a big blob on top of one character as in most machines. The other approach to this problem is not to use numbers at all. Instead, keep two local state variables with lists of words, one for the words to the right of the position and one for the words to the left. (define-class (tape words) (instance-vars (to-left '()) (to-right words)) (method (left) (if (null? to-left) #f (let ((result (car to-left))) (set! to-left (cdr to-left)) (set! to-right (cons result to-right)) result))) (method (right) (if (null? to-right) #f (let ((result (car to-right))) (set! to-right (cdr to-right)) (set! to-left (cons result to-left)) result)))) In this version the two methods are symmetrical. The list called to-left has the words in reverse order, so after moving the HELP! tape three words to the right, to-left has the value (NEED I HELP!). (b) Three points, tape-player class. (define-class (tape-player) (instance-vars (tape #f)) (method (load new-tape) (if tape (error "Tape already loaded") (sequence (set! tape new-tape) 'loaded))) (method (eject) (if tape (sequence (set! tape #f) 'ok) (error "No tape loaded"))) (method (play n) (if (= n 0) '() (let ((wd (ask tape 'right))) (if wd (se wd (ask self 'play (- n 1))) '())))) (method (fast-forward n) (ask self 'play n) 'ok) (method (rewind) (if (ask tape 'left) (ask self 'rewind) 'ok))) There were two common errors. First, many people put extra methods in the TAPE class for the benefit of the TAPE-PLAYER class. It's possible to get this to work, but it shows a real misunderstanding of the object metaphor. The whole idea is that each class is defined in terms of the things that that kind of object should be able to do, and you don't hack up one class to make things easier for another if that would ruin the metaphor. So, think about actual tapes and tape players. All the tape knows is the information recorded on it. It's the tape player, not the tape, that deals with rewinding and fast forwarding and so on. An equivalent error was to create variables in the tape player that duplicate the information in the tape, and then ignore the tape. The tape has to know its position; what if you take a tape out of one machine and put it into another machine? It doesn't magically get rewound! The other common error was to confuse printing with returning a value. The most obvious form of this error was to invoke PRINT in a method, but many people also got in trouble with the fast-forward method because they couldn't figure out how to move the tape without printing the words passed over. That's because they think that the tape object *prints* those words, whereas it actually *returns* them. They get printed only if the tape object is sent a message from the top-level Scheme prompt. If a tape player sends a tape a message, which is the usual situation, the tape player decides what to do with the return value. Ignoring the return value is a reasonable choice. A less common error was to give the tape player a tape as its parent. This, too, is a real misunderstanding of the object metaphor. Is a tape player a kind of tape? No! Something like metal-bias-tape or dolby-recorded-tape would be the sort of object that would have TAPE as its parent. 5B. Declicking with streams. There were several good alternatives for each of the three procedures. We'll show some samples of each here. Of course you would only use one alternative for each! (define (differences strm) (if (empty-stream? (tail strm)) the-empty-stream (cons-stream (- (head (tail strm)) (head strm)) (differences (tail strm))))) (define (differences strm) (add-streams (tail strm) (map - strm))) (define (limit strm value) (cond ((empty-stream? strm) the-empty-stream) ((> (head strm) value) (cons-stream value (limit (tail strm) value))) ((< (head strm) (- value)) (cons-stream (- value) (limit (tail strm) value))) (else (cons-stream (head strm) (limit (tail strm) value))))) (define (limit strm value) (map (lambda (num) (cond ((> num value) value) ((< num (- value)) (- value)) (else num))) strm)) (define (sums strm) (sums-help 0 strm)) (define (sums-help total strm) (if (empty-stream? strm) the-empty-stream (let ((new-total (+ total (head strm)))) (cons-stream new-total (sums-help new-total (tail strm)))))) (define (sums strm) (if (empty-stream? strm) the-empty-stream (cons-stream (head strm) (sums (cons-stream (+ (head strm) (head (tail strm))) (tail (tail strm))))))) (define (sums strm) (define result (cons-stream (head strm) (add-streams result (tail strm)))) result) Many people didn't know how to find the negative of a number. We did accept (word '- number) because that'll work in our hacked-up Scheme, but you should know that it won't work elsewhere in the world. By the way, those of you comfortable with calculus may understand the motivation for these procedures better if you think of DIFFERENCES as modeling the derivative of a signal, and SUMS as modeling the integral. Scoring: Start with five points; for each of the three procedures, if it's really awful subtract 2, if it's a little wrong subtract 1, but with a lower bound of zero. If the same error is repeated in more than one procedure, only take off for it once. (A common one was to forget about the base case for finite streams.) 6A. Remove in logic programming. (rule (remove ?word () ())) (rule (remove ?word (?word . ?rest) ?result) (remove ?word ?rest ?result)) (rule (remove ?word (?other . ?rest) (?other . ?result)) (and (remove ?word ?rest ?result) (not (same ?word ?other)))) The first of these is the base case; the second handles the case in which the word we want to remove appears as the first word of the starting list; the third handles the case in which the word isn't at the beginning of the list. Scoring: Standard BH scale. There were too many wildly different answers to categorize; we tried to figure out what you meant but sometimes it was hard. Anything that involves composition of functions was a clear zero. Anything in which a REMOVE pattern only has two other elements was a good candidate for a zero. Many people had unnecessary special cases, such as lists of length 1. You wouldn't do that in the Scheme program, would you? In Scheme you'd say (define (remove wd lst) (cond ((null? lst) '()) ((eq? wd (car lst)) (remove wd (cdr lst))) (else (cons (car lst) (remove wd (cdr lst)))))) Each clause of the cond corresponds to one of the rules above. A surprising number of people think that a list of length one is the same thing as the word inside it. 6B. Active variables. The crucial thing to understand in this problem is that there are two parts to the solution. First, you must invent the ACTIVATE special form. (As part of that, you'll change the way bindings are represented.) Second, you must change the operation of SET! to carry out the activation procedure when an active variable is changed. We gave two points to solutions that listed procedures relevant to both of these, even if there was no code at all or the code was all wrong. A three-point solution had bad code for both parts, or good code for one part. (a) This is a change to EVAL, not to APPLY. Both halves are about special forms, not about invoking procedures. (You'll have to *invoke* apply to carry out the activation procedure, of course, but there's nothing special about what it means to invoke that procedure as opposed to any other procedure.) (b) Since we're inventing a new special form, EVAL itself will need a new clause added to the COND. Since we're changing what a binding looks like, we'll modify MAKE-BINDING and some of the procedures that implement the binding ADT, such as BINDING-VALUE and SET-BINDING-VALUE!. Finally, we change the way SET! works by modifying SET-VARIABLE-VALUE!. (A more obvious choice is EVAL-ASSIGNMENT, but it turns out to be a bit more robust this way, as you'll see in a moment.) (c) The details depend on how you represent active variables. I think the most elegant solution is to notice that we could consider *every* variable to be active, as long as its activation procedure is (lambda (old new) new) This procedure has no side effects (such as printing messages) and chooses the original new value as the final new value. Based on that choice, I modified the binding ADT this way: (define (make-binding variable value) (LIST VARIABLE VALUE (LAMBDA (OLD NEW) NEW))) (define (binding-value binding) (CADR binding)) (define (set-binding-value! binding value) (SET-CAR! (CDR binding) value)) (DEFINE (BINDING-ACTIVATOR BINDING) (CADDR BINDING)) (DEFINE (SET-BINDING-ACTIVATOR! BINDING PROC) (SET-CAR! (CDDR BINDING) PROC)) Now we can invent the ACTIVATE special form. In MINI-EVAL, we add the clause ((ACTIVATE? EXP) (EVAL-ACTIVATE EXP ENV)) to the cond. It doesn't matter exactly where you put it. To make this work we define ACTIVATE? similarly to the other special form testing predicates: (DEFINE (ACTIVATE? EXP) (AND (LIST? EXP) (EQ? (CAR EXP) 'ACTIVATE))) Changing the activation procedure of a binding is very much like changing the value of the binding, so eval-activate looks a lot like set-variable-value!: (DEFINE (EVAL-ACTIVATE EXP ENV) (LET ((B (BINDING-IN-ENV (CADR EXP) ENV))) (IF (FOUND-BINDING? B) (SET-BINDING-ACTIVATOR! B (MINI-EVAL (CADDR EXP) ENV)) (ERROR "UNBOUND VARIABLE" (CADR EXP))))) Actually, to make this look more like the SET! code, we could break this up into a procedure that parses the expression into its pieces and another one that actually modifies the binding, like this: (define (eval-activate exp end) (let ((new-activator (mini-eval (activate-value exp) env))) (set-variable-activator! (activate-variable exp) new-activator env) 'ok)) (define activate-variable cadr) (define activate-value caddr) (define (set-variable-activator! var proc env) (let ((b (binding-in-env var env))) (if (found-binding? b) (set-binding-activator! b proc) (error "Unbound variable" var)))) This ends the first half of the project. Now we have to modify the operation of SET!. I did this by changing SET-VARIABLE-VALUE! but it could also be done in EVAL-ASSIGNMENT. The difference is that if we had two different ways to change the value of a variable, SET! and something else, making the change in SET-VARIABLE-VALUE! will ensure that the other way also respects the active nature of the variable. (define (set-variable-value! var val env) (let ((b (binding-in-env var env))) (if (found-binding? b) (set-binding-value b (MINI-APPLY (BINDING-ACTIVATOR B) (LIST (BINDING-VALUE B) VAL))) (error "Unbound variable" var)))) That's all there is to it. (It would have been more complicated if I'd chosen a representation for bindings in which active variables have a different form from ordinary ones.)