CS 61A Fall 1996 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-car! x (cdr x)) x) ((2 3 4) 2 3 4) !!!!!!!!!!!!! ! ! ! V +-!-+---+ +---+---+ +---+---+ +---+---+ | ! | | | | | | | | | | /| x -------> | + | ----->| | | ----->| | | ----->| | | / | | . | | | | | | | | | | | | |/ | +-.-+---+ +-|-+---+ +-|-+---+ +-|-+---+ . | | | . | | | V V V V 1 2 3 4 [We accepted diagrams with or without the two disconnected pairs.] > (let ((x (list 1 2 3 4))) (set-car! (cdr x) (cadr x)) x) (1 2 3 4) +---+---+ +---+---+ +---+---+ +---+---+ | | | | | | | | | | | /| x -------> | | | ----->|. !| ----->| | | ----->| | | / | | | | | |. !| | | | | | | | |/ | +-|-+---+ +.-!+---+ +-|-+---+ +-|-+---+ | . ! | | | . ! | | V \ / V V V 1 2 3 4 [This operation doesn't change the list at all; it replaces a pointer with a pointer to the same place.] > (let ((x (list 1 2 3 4))) (set-cdr! (cddr x) (cdr x)) x) (1 2 3 2 3 2 3 ... [We accepted any indication that an infinite loop would result when printing this list.] !!!!!!!!!!!!!!! ! ! V ! +---+---+ +---+---+ +---+-!-+ +---+---+ | | | | | | | | ! | | | /| x -------> | | | ----->| | | ----->| | | +....>| | | / | | | | | | | | | | | | | | | |/ | +-|-+---+ +-|-+---+ +-|-+---+ +-|-+---+ | | | | | | | | V V V V 1 2 3 4 Scoring: 1/2 point per B&P, 1/2 point per printed form, rounded down to whole points. 2. parallel-execute (a) In this correctly serialized version, there are two possible answers. If the first thread runs first, it will set BAZ to 7 and then the second thread will set it to 14. If the second thread runs first, it will set BAZ to 20 (10+10) and then the first thread will set it to 7. So the answers are 7 and 14. (b) If the threads are protected by different serializers, then they are not protected against each other. In addition to the correct answers 7 and 14, two more answers are possible: If the second thread reads 10 for BAZ twice [in the expression (+ BAZ BAZ)], then the first thread sets BAZ to 7, then finally the second thread will set BAZ to 20. If the second thread reads 10 for BAZ once, then the first thread sets BAZ to 7, then the second thread reads BAZ again and finds 7, then finally the second thread will set BAZ to 17 (10+7). So the answers are 7, 14, 17, and 20. Scoring: -1 point per missed answer, -2 points per extra answer, down to a minimum of 0 points. 3. OOP radio. (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. 4. digit-stream (a) The first four elements are 1, 2, 3, and 4. (b) The result is an infinite loop, because the ninth stream-cdr can neither find a tenth element nor reach an end of the stream (an empty stream). This sieve accepts all the one-digit integers, and rejects everything else, because all the larger numbers contain some number between 1 and 9 as a digit. The crucial point in this question is to understand that here is a case in which the reordering trick that streams provide doesn't work. STREAM-FILTER doesn't ordinarily take an infinite amount of time because ordinarily there are always more elements in the result stream. Each time we STREAM-CDR a filtered stream, STREAM-FILTER calls itself recursively (right then, not delayed) until it finds an element that satisfies the predicate. It then returns that element along with a promise to find more elements when necessary. But in this case it will never succeed in finding a next element. "The empty stream" is a wrong answer. Although the result stream has no elements, Scheme doesn't know that. We know it by doing mathematics, not by trying possible elements until we lose patience! Scoring: one point for (a), two points for (b). 5. traverse! Many people found this question difficult. Some people had the good idea of starting by writing TRAVERSE, the version that solves the problem functionally, making a new list, rather than by mutation: (define (traverse tree) (if (null? tree) '() (append (traverse (left-branch tree)) (cons (datum tree) (traverse (right-branch tree)))))) [Unfortunately some of the people who tried this thought that the APPEND above could be CONS, which is wrong.] This functional version gives us the key idea, which is to make two recursive calls for the two branches. In order to turn this into a version that works by mutation and doesn't allocate new pairs, we must eliminate the calls to APPEND and CONS, both of which do allocate pairs. The easiest solution is based on remembering that Scheme has an APPEND! procedure that does an append-by-mutation: (define (traverse! tree) (if (null? tree) '() (let ((lh (traverse! (left-branch tree)))) (set-cdr! tree (traverse! (right-branch tree))) (if (null? lh) tree (append! lh tree))))) I've used the binary tree selectors for clarity, even though, as the exam noted, this entire problem violates the idea of data abstraction by mutating one data type into another. If you didn't think of APPEND! you'd basically have to invent it yourself: (define (traverse! tree) (if (null? tree) '() (let ((lh (traverse! (left-branch tree)))) (set-cdr! tree (traverse! (right-branch tree))) (if (null? lh) tree (begin (set-cdr! (last-pair lh) tree) lh))))) The reason the LET is needed is that once the (SET-CDR! TREE ...) has been done, we no longer have access to the pair that pointed to the left and right branches. This was the most common error: processing a branch too late, after you no longer have a pointer to it. Very few solutions were this clean. Most were cluttered with special cases: "Is the left branch a leaf node?" and so on. The only special case that's needed here is to check for an empty tree. Scoring: 3 correct 2 has the idea 1 has an idea 0 other Solutions using CONS or APPEND got zero unless they were really nice in some other way, in which case one. GROUP PROBLEM (environment diagram): Everyone knew that (FOO 5) would return -3, even with bizarre diagrams, because all the variables had different names. If we'd written one of those mean questions in which all the variables are named X, you'd have seen why environment diagrams matter! Procedures are made by LAMBDA expressions. In this problem, there are three LAMBDA expressions: an implicit one from the LET, and two explicit ones. (There is no implicit LAMBDA in the DEFINE, because there are no parentheses around FOO. This was a common mistake.) P1: (lambda (g) (lambda (y) (g (- y 6)))) P2: (lambda (x) (* x 3)) P3: (lambda (y) (g (- y 6))) The LET expression expands to (P1 P2), where P1 and P2 are the LAMBDA expressions shown above. In other words, P1 is invoked with P2 as its argument (which will be bound to the parameter G). The expressions P1 and P2 are both evaluated in the global environment! The most common error was to think that P2 would be evaluated in the frame in which G is bound to P2, but that couldn't be right: the binding of G to P2 happens when P1 is invoked, which can't happen until *after* its argument, P2, has been evaluated. So we have the following steps: 1. The lambda expressions for P1 and P2 are evaluated in the global environment, creating procedures P1 and P2 whose right bubbles point to the global environment. 2. Procedure P1 is invoked. A frame (E1) is created, extending the global environment, in which G is bound to procedure P2. (Another common mistake was to say that G is bound to the LAMBDA expression. That would be normal order evaluation.) 3. In environment E1, we evalaute the body of P1, namely, the lambda expression P3, producing a procedure P3 whose right bubble points to E1. 4. Since procedure P3 is the value returned by the LET, back in the global environment we bind the name FOO to procedure P3. That's all that happens during the DEFINE expression. Now for (FOO 5). 5. The argument 5 is self-evaluating; nothing happens to the diagram when we evaluate it. But then we call FOO, which requires us to make a new frame E2 in which parameter Y is bound to 5. This frame extends E1, because FOO's right bubble points to E1. 6. With E2 as the current environment, we evaluate the body of FOO, which is (G (- Y 6)). Since - is primitive, calling it doesn't affect the diagram; the argument to G will be -1 [5 minus 6]. 7. We make a frame in which X (the parameter of G) is bound to -1. This new frame E3 extends *the global environment* (not E1, as if G had been created there; not E2, which would be dynamic scope). 8. In that new environment we evaluate (* X 3), whose value is -3. Scoring: 3 correct 2 one mistake (almost always creating P2 in E1 and therefore having E3 extend E1). 1 some idea 0 incoherent (e.g., binding G to -3) The most interesting error, seen more than once, was to have the frame in which Y is bound extend the environment in which X is bound. This gets the sequence of events backwards in time! ----------------------------------- If you don't like your grade, first check these solutions. If we graded your paper according to the standards shown here, and you think the standards were wrong, too bad -- we're not going to grade you differently from everyone else. If you think your paper was not graded according to these standards, bring it to Brian or your TA. We will regrade the entire exam carefully; we may find errors that we missed the first time around. :-) If you believe our solutions are incorrect, we'll be happy to discuss it, but you're probably wrong!