CS 61A Midterm 3 solutions Fall 2008 1. Box and pointer. (let ((x (list 'a 'b 'c))) (SET! (CAR X) (CADDR X)) x) Result: ERROR Of course the SET! expression should be (set-car! x (caddr x)). SET! is a special form whose first argument must be a symbol, not an arbitrary expression. Scoring: 2 points, all or nothing. (define a (list (list 3) 5)) (define b (APPEND A A)) (set-car! (cdr b) (caddr b)) (set-car! a (cons 3 4)) b Result: ((3) (3) (3 . 4) 5) box and pointer diagram key: XX X/ original pairs ** pair made by (CONS 3 4) | --- | original pointers | : : original pointers eliminated by mutation : ! === ! new pointers added by mutation ! a | V b ----->XX---->XX---->XX-------->X/ | :\ :\ | | : ! : ! | | V ! : V V | 5 ! : **-->4 5 | ! : | | ! : | | ! : V | ! : 3 | ! : +--------+----+--->X/ | | V 3 The key to understanding this diagram is knowing how APPEND works: it makes a copy of /all but the last/ argument, but shares memory with the last one. This is why the last two pairs of B are the same as the two pairs of A, and this is why there is only one pair representing all instances of (3) in the diagram. And this is why changing the car of A changes the third element, but not the first element, of B. Scoring: One point for the printed result, one point for the diagram. 2. Mutation. The two parts of this question start with the same diagram before the mutation you have to provide: foo ----->XX---->XX---->X/ | | | V V V 1 2 XX---->X/ | | V V 3 4 bar ----->XX----------->XX---->X/ | | | | V V | c d V XX---->X/ | | V V a b The value of BAR in this initial diagram is ((a b) c d). In the first problem, you are asked to change the value of BAR to ((a b (3 4)) c d). That is, you are supposed to add one new element, the list (3 4), at the end of the list (a b) which is the first element of BAR. To add an element at the end of a list, you SET-CDR! the last pair of the list's spine to point, /not to the element itself/, but to a spine pair whose car is the element and whose cdr is the empty list. So this is the change: +==========+ ! ! V ! foo ----->XX---->XX---->X/ ! | | | ! V V V ! 1 2 XX---->X/ ! | | ! V V ! 3 4 ! ! bar ----->XX----------->XX---->X/ ! | | | ! | V V ! | c d ! V ! XX---->XX================+ | | V V a b The pair we're changing is the CDR of the list (A B), which is the CAR of BAR, so we want to (SET-CDR! (CDAR BAR) ...). The pair we want to point to is the third spine pair of FOO, so the desired solution is (SET-CDR! (CDAR BAR) (CDDR FOO)) Scoring: One point for SET-CDR!, one point for (CDAR BAR), one point for (CDDR FOO). No points if the expression starts with SET!. Since we are changing the cdr of the last spine pair of a list, it turns out that the following expressions are equivalent to the given solution: (APPEND! (CAR BAR) (CDDR FOO)) (APPEND! (CDAR BAR) (CDDR FOO)) We accepted either of those, scored as above except APPEND! instead of SET-CDR!. (No points for APPEND instead of APPEND!.) In the second problem, you are asked to change ((a b) c d) to (((2 (3 4)) b) c d). In other words, you are asked to replace the first element of (a b) with something different. That means you SET-CAR! the first pair of the spine of (a b): +===================+ ! ! ! V ! foo ----->XX---->XX---->X/ ! | | | ! V V V ! 1 2 XX---->X/ ! | | ! V V ! 3 4 ! ! bar ----->XX----------->XX---->X/ ! | | | ! | V V ! | c d ! V +============XX---->X/ : | V V a b So the solution is (SET-CAR! (CAR BAR) (CDR FOO)). Scoring: Same as the first part, except that in this problem there's no equivalent solution using APPEND!. 3. OOP below the line. (a) A class variable is a /local state variable/ of /the class constructor procedure/. We make local state variables by putting a LET /outside/ the lambda that creates the procedure. So we want (define make-person (let ((people '())) (lambda (name) ... so the answer is Point A. (b) SELF in the OOP language is a name for the dispatch procedure that represents an object. In the ordinary-Scheme code we're writing as an equivalent to the define-class code, there is nothing called SELF! There is something called MAKE-PERSON, but that's the /class/ constructor, not the instance. So the answer is DISPATCH. (c) It can't be Point B because DISPATCH isn't defined at that point. It can't be Point C because that would cause the initialization to be done every time a message is sent to the object! It has to be during the creation of the object, but somewhere where DISPATCH exists. So the answer is Point E. (d) Point D corresponds to the expression (ASK OTHER 'NAME) in the define-class code. In the plain-Scheme version, there's no ASK; we just invoke the object's dispatch procedure: (OTHER 'NAME). But the result of calling the dispatch procedure with a message argument is that it returns /a method/, i.e., a procedure; we have to invoke that procedure to get the result we want, the other person's name. So the answer is ((OTHER 'NAME)). Scoring: 1.5 points each. In part (d), 0.5 points for (OTHER 'NAME). The total is rounded down to an integer value. 4. Vectors. During the exam, many students asked questions that were answered in the introductory text on page 6 of the exam booklet. This was definitely a question for which you should have spent much more time reading than writing. As you'll see below, the actual solution is not that much code, provided that you understand what you're doing. We chose insertion sort rather than some other sorting algorithm because you'd already seen the list version, when we talked about orders of growth of time in algorithms. (a) INSERT! works by shifting some elements of the vector one slot leftward. So the non-base case of INSERT! will do one such shift, plus a recursive call. There are two base cases: running off the right end of the vector, or finding an element larger than the one we want to insert. It's important to understand that an invariant of this procedure is that the slot to the left of FROM always exists (FROM is never zero), and is always free (either the new value or some shifted-left value used to be in it). (define (insert! vect value from to) (cond ((> from to) ; fall off right edge (vector-set! vect to value)) ((< value (vector-ref vect from)) (vector-set! vect (- from 1) value)) (else (vector-set! vect (- from 1) (vector-ref vect from)) (insert! vect value (+ from 1) to)))) That's it! Some students worried about how to handle two equal values in the vector, but if they're equal, it doesn't matter which goes first, so we were happy with either < or <= as the comparison operator. Scoring: We checked whether your procedure could insert at the beginning of the region, in the middle, and at the end. 4 correct 3 trivial error (off by 1, sort backwards) 2 two out of three of beginning, middle, end 1 an idea 0 other (b) SORT! needs a helper procedure, because it doesn't take an index as an argument, so we need one to keep track of where we're up to in the vector. As page 6 makes clear, we are inserting elements from right to left. We start with one already-sorted element, so from = to = length-1. There are various ways to write this, depending on what index you want to use as the argument to the helper. The candidates are FROM (the index of the first already-sorted element) and the position of VALUE (the value to be inserted). (TO never changes from length-1, so it doesn't have to be an argument, although it could be.) In the following solution, I use FROM as the index: (define (sort! vect) (define (help index) (cond ((= index 0) ; when from=0 there's nothing left to insert vect) (else (insert! vect (vector-ref vec (- index 1)) index (- (vector-length vect) 1)) (help (- index 1))))) (help (- (vector-length vect) 1))) Scoring: 4 correct 3 trivial error 2 has the idea 1 has an idea 0 other 5. Streams. The quickest way to solve this problem is to observe that addition is associative, so the given code is equivalent to (define mystery (cons-stream 1 (stream-map + (STREAM-MAP + ONES INTS) mystery))) The capitalized part obviously generates the stream of integers starting from 2. So we draw this picture: mystery 1 ____ ____ ____ ____ ints-from-2 2 3 4 5 6 ----------- --- ---- ---- ---- ---- sum 3 ____ ____ ____ ____ As we compute numbers in the SUM line, we copy them up to the MYSTERY line one space over: mystery 1 3 ____ ____ ____ ints-from-2 2 3 4 5 6 ----------- --- ---- ---- ---- ---- sum 3 6 ____ ____ ____ mystery 1 3 6 ____ ____ ints-from-2 2 3 4 5 6 ----------- --- ---- ---- ---- ---- sum 3 6 10 ____ ____ mystery 1 3 6 10 ____ ints-from-2 2 3 4 5 6 ----------- --- ---- ---- ---- ---- sum 3 6 10 15 ____ mystery 1 3 6 10 15 ints-from-2 2 3 4 5 6 ----------- --- ---- ---- ---- ---- sum 3 6 10 15 21 So the answer is 1, 3, 6, 10, 15. (These are the "triangle numbers.") Scoring: 5 correct 4 one arithmetic error (which then propagates to later numbers), e.g., 1, 4, 7, 11, 16; 1, 2, 5, 9, 14. 3 ints instead of ints-from-2: 1, 2, 4, 7, 11. 3 add 1 only to first int, not all ints: 1, 3, 5, 8, 12. 0 Anything with a constant increment between elements, e.g.: 1, 2, 3, 4, 5 1, 3, 5, 7, 9 4, 6, 8, 10, 12 1, 3, 4, 5, 6 6. Concurrency. We /did/ give the hint "Read the code carefully! We didn't make a mistake; this is what we intended to write." In other words, you were warned that something in this problem is a little peculiar. The thing you had to notice was that the first thunk in the parallel-execute just computes a value, but doesn't change X. So we can ignore it; the problem is equivalent to (define x 16) (parallel-execute (lambda () (set! x (* x 2))) (lambda () (set! x (+ x 1)))) There are two possible correct answers and two possible incorrect answers. The correct ones are consistent with a sequential ordering of the tasks, either (define x 16) (set! x (* x 2)) ==> 32 (set! x (+ x 1)) ==> 33 or (define x 16) (set! x (+ x 1)) ==> 17 (set! x (* x 2)) ==> 34 Since each of the relevant tasks just loads X once, the only possible wrong answers are from sequences of LOAD, LOAD, STORE, STORE, so that one of the two threads is overruled by the other. So in effect we do (define x 16) (set! x (* x 2)) ==> 32 or (define x 16) (set! x (+ x 1)) ==> 17 So the answers are (a) 33, 34, 32, 17 (b) 33, 34 Scoring: (a) was worth 4 points. We subtracted 1 for each missing or wrong value, and we subtracted 1 for each extra answer, except that the penalty for extra answers was limited to -2. (In other words, -1 for one extra answer, -2 for more than one extra answer.) (b) was worth 2 points, computed with the same formula. Of course the most common mistake was to work as if the first thunk were (lambda () (set! x (if (even? x) (+ x 5) (- x 5)))) This gave rise to many extra answers for both (a) and (b); people who did include the correct answers therefore got 2 points for (a) and 0 for (b). Group problem (environment diagram): (define y 6) adds binding Y=6 to global frame (G). (define (foo y) (lambda (x) (+ x y))) creates procedure P1 with parameter Y and body (LAMBDA ...), right bubble points to G. adds binding FOO=P1 to G. The LAMBDA expression is not evaluated at this time. (define (baz x) (let ((+ *) (y 10) (garply (foo (+ x y)))) (garply y))) creates procedure P2 with parameter X and body (LET ...), right bubble points to G. adds binding BAZ=P2 to G. The LET expression is not evaluated at this time. (baz 10) This is a procedure call, so we first evaluate subexpressions. The value of BAZ is P2; the value of 10 is 10. Now we invoke P2 with argument 10. This creates a frame E1, pointing to G (because P2's right bubble points to G), with the binding X=10. With E1 as current environment, we evaluate the body of P2, which is the LET expression. It's worth expanding this to what it abbreviates, a LAMBDA expression which is surrounded by its invocation: ((lambda (+ y garply) (garply y)) * 10 (foo (+ x y))) This is a procedure call, so we start by evaluating its four subexpressions: The LAMBDA creates procedure P3, parameters +, Y, GARPLY, body (GARPLY Y), right bubble points to E1. * is the multiplication primitive, 10 is 10. (FOO (+ X Y)) is a procedure call, so we evaluate its subexpressions: FOO is procedure P1. (+ X Y) is a procedure call, so we evaluate its subexpressions: + is the /addition/ primitive, X=10, /Y=6/. Then we call the addition primitive, which returns 16. Now we invoke P1 (i.e., FOO). To do this we create a new frame E2, which extends /G/ (because P1's right bubble points to G), with the binding Y=16. P1's body is a LAMBDA expression, so it creates procedure P4, with parameter X and body (+ X Y), whose right bubble points to E2. P4 is the return value from P1. /Now/ we can call P3. This creates a new frame, E3, extending E1 (because P3's right bubble points to E1), with three bindings: + is the multiplication primitive (but this binding will never be used for anything!), Y=10, GARPLY=P4. The body of P3 is (GARPLY Y). We evaluate this in the current environment, which is E3. So we evaluate the subexpressions in E3, where we find GARPLY=P4, Y=/10/ (not 16, which isn't in the current environment). So we call P4 with argument 10. This creates frame E4, extending E2 (because that's where P4's right bubble points), containing the binding X=10. With E4 as current environment, we evaluate the body of P4, which is (+ X Y). This is a procedure call, so we evaluate its subexpressions, which are all symbols. For the + symbol, the only binding in our environment is the addition primitive, in G. (E3, which binds + to the multiplication primitive, is not in the current environment.) We find X=10 in frame E4, and Y=16 in E2. So the return value from GARPLY, which is also the return value from the LET, and therefore the return value from BAZ, is 26 (10+16). Scoring: We allowed the omission of the LET procedure, P3. Since FOO and BAZ are plain old top-level procedures, I figured (incorrectly, as it turns out) that everyone would get those correct in the diagram. This leaves four frames, one procedure (P4), and six arrows: the ones from the four frames to the environments they extend, the one from P4's right bubble, and the one for the binding of GARPLY. So my first thought was to score -1 for a missing frame, -0.5 for an incorrect arrow. But students found other ways to make mistakes. One was to use the substitution model, e.g., showing the body of P4 as (+ X 16) by substituting argument value 16 for parameter Y in the call to FOO. This was a half-point error. Another was normal order; for example, in E4, binding X to Y rather than to 10. That was a one-point error. But these errors were combined in complicated ways; sometimes the consistent working out of an early error led to more half-point losses than it really seemed to deserve, and sometimes a late error seemed so wrong-headed that it deserved a lower score than the formula gave. I tried to keep to the usual correct/trivial error/the idea/an idea/other scale. The papers with grades of 4, 3, and 0 were easy to grade, but the difference between 1 and 2 was harder to decide. One common mistake was to use dynamic scope, which would make E2 extend E1. Another was to think that E2 should extend E3, although this is actually backwards in time! Another common error was to treat the definition of BAZ as though the LET established local state variables for the procedure, i.e., as if the code were (define baz (let (...) (lambda (x) (garply y)))) Another pretty common error, surprising to me, was to merge frames, e.g., adding the LET variables as additional bindings in E1 rather than creating a new frame E3. A few groups bound GARPLY to either FOO or BAZ, rather than to a newly created procedure. I didn't take points off for the /very/ common error of labelling E2 as E3 and vice versa, as long as the arrows pointed to the right places. Please be careful about putting arrowheads at one end of your arrows! This is especially important if you're also careless about whether each end of the arrow is inside or outside the box. Many groups who had pretty bizarre diagrams nevertheless got the answer 26. I consider this a weakness, not a strength, of those papers; the ultimate result of the computation should be consistent with the diagram! But I didn't adjust the score either way based on the final answer.