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-cdr! x (cdr 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-car! (cddr x) (cdr x)) x) (1 2 (2 (2 (2 (2 ... [We accepted minor variations such as "(1 2 2 2 ... " or "infinite loop" but not responses claiming that a 3 would be printed.] +!!!!!!!!!+ ! ! V ! +---+---+ +---+---+ +-!-+---+ +---+---+ | | | | | | | ! | | | | /| x -------> | | | ----->| | | ----->| | ----->| | | / | | | | | | | | | | . | | | | |/ | +-|-+---+ +-|-+---+ +-.-+---+ +-|-+---+ | | . | | | . | V V V V 1 2 3 4 [The new pointer points to the second pair, not to the 2. A common wrong answer was (1 2 (2 3 4) 4), from people who thought "replace the third element with THE ORIGINAL VALUE OF (cdr x)." Some of these people drew correct diagrams but ignored what the diagram meant; others drew diagrams in which three new pairs were magically allocated for a list (2 3 4).] > (let ((x (list 1 2 3 4))) (set-cdr! (cdr x) (cadr x)) x) (1 2 . 2) [Note the dot!] +---+---+ +---+---+ +---+---+ +---+---+ | | | | | | | | | | | /| x -------> | | | ----->| | | +....>| | | ----->| | | / | | | | | | | | ! | | | | | | | |/ | +-|-+---+ +-|-+!--+ +-|-+---+ +-|-+---+ | | ! | | | |! | | V V V V 1 2 3 4 [We accepted diagrams with or without the two disconnected pairs.] Scoring: One point each; both printed form and diagram had to be correct. 2. deep-fix! There are two basic approaches to this problem. One of them relies on having deep-fix! return the modified structure as its return value, and on allowing non-pairs as a base case: (define (deep-fix! p) (cond ((pair? p) (set-car! p (deep-fix! (car p))) (set-cdr! p (if (pair? (cdr p)) (deep-fix! (cdr p)) '())) p) (else p))) The other approach doesn't depend on a return value, so it need not return a value at all. It can assume its argument is always a pair: (define (deep-fix! p) (if (pair? (car p)) (deep-fix! (car p))) (if (pair? (cdr p)) (deep-fix! (cdr p)) (set-cdr! p '()))) In both cases, the code is simplified by letting the procedure do an unnecessary set-cdr! if the cdr of a pair is already the empty list. If you don't like that, you can add additional checks for that case. If you're not sure how to attack a problem like this, a good first step is to write a functional version: (define (deep-fix p) (cond ((pair? p) (cons (deep-fix (car p)) (if (pair? (cdr p)) (deep-fix (cdr p)) '()))) (else p))) You can see how the first solution above follows this structure, except that instead of the CONS there is a sequence of steps including a set-car! and a set-cdr! to reuse the existing pair. Typical problems: The worst common problem was a lack of tree recursion -- that is, recursion for the car as well as for the cdr. This is a tree problem, although it doesn't use the tree abstract data type; it deals with a multi-level list structure, which is a tree. A special case of the above was a program that deals with lists two levels deep -- lists of lists -- but not more than that. Instead of recursion it does things like (set-car (cadr p) ...). Less common, but equally bad, was to use CONS or something that implies CONS, such as APPEND or MAP. MAP wouldn't work anyway, because its argument must be a proper list; it will blow up if given an improper list. The next most common error, still pretty bad, is the "magic COND" problem, in which you think that *all* true conditions have their actions performed, instead of just *the first* true condition. A minor error in several papers was to use EMPTY? rather than NULL? to test for an empty list. This is a data abstraction violation, since EMPTY? is for words and sentences, not structured lists. Scoring: We graded this question *very* leniently: 4 correct 3 mutation without allocating new pairs, AND is tree-recursive 2 mutation without allocating new pairs, OR is tree-recursive 1 neither, but some relevant effort (typical case: no mention of CAR) 0 even worse 3. Over/under stream Many people noticed that this problem is almost, but not quite, isomorphic to the ones-zeros stream problem in one of the old exams in the reader. We can take advantage of this by solving the problem in two steps. First we make a stream exactly like the ones-zeros stream: (define foo (cons-stream '() (interleave (stream-map (lambda (p) (cons 'over p)) foo) (stream-map (lambda (p) (cons 'under p)) foo)))) (By the way, we could tell who just copied the old code from the reader without thinking about it, because they're the ones who said MAP rather than STREAM-MAP. It was called MAP in the first edition of SICP.) Then you filter out the unacceptable elements to get the desired stream: (define patterns (stream-filter (lambda (p) (and (member 'over p) (member 'under p))) foo)) You can't combine these two steps; several people tried this: (define patterns ;;; wrong! (stream-filter (lambda ...) (cons-stream '() (interleave (stream-map ... patterns) (stream-map ... patterns))))) The trouble is that this process will never get started, because the two calls to stream-map can only operate on patterns that have previously been generated, and there won't be any of those until something makes it through the filter. As a result, the variable PATTERNS hasn't been defined when the calls to stream-map try to use it. Another wrong solution was to try to avoid the need for filtering by "priming the pump" with initial patterns other than the empty one, like this: (define patterns ;;; wrong! (cons-stream '(over under) (cons-stream '(under over) (interleave ...)))) This indeed gets started correctly, and generates only legal patterns, but it doesn't generate all of them. In particular, it won't generate the example shown in the problem: (over over under over under under) because this pattern, although legal, doesn't end with OVER UNDER or UNDER OVER. Some people, recognizing the problem with that last solution, tried to get around it by adding words both front and back. That might possibly work, but the people who tried it wanted to add words at the end with (cons p 'over) which of course doesn't make a valid list. Another intriguing method involved the use of random numbers to make a randomly chosen pattern for each element of the stream. It can be argued that if the random number generator has perfectly well-distributed results, this approach will eventually generate any desired pattern. (And, since the number of already-generated patterns is finite, and the number of not-yet-generated patterns is infinite, the probability of duplication of patterns is zero! Alas, this doesn't mean it can't happen. :-) But we didn't accept these solutions because part of the idea in an infinte stream is that you have to be able to guarantee that any particular element is reachable in bounded time. Scoring: We graded this one very leniently also: 3 correct 2 interleave correct, filtering missing or incorrect 1 interleave wrong, but a good try 0 not close 4. Wizards. Because the total number of points for the exam added up to 21, we demoted this from a four-point problem to a three-point one. Details aside, a good solution would have to have roughly this form: (define-class (wizard name place) (parent (person name place)) (instance-vars (places (list place))) (method (go direction) (usual 'go direction) (set! places (cons (ask self 'place) places))) (method (go-directly-to new-place) (usual 'go-directly-to new-place) (set! places (cons (ask self 'place) places))) (method (revisit place-name) (let ((new-places (filter (lambda (place) (eq? (ask place 'name) place-name)) places))) (if (not (null? new-places)) (ask self 'go-directly-to (car new-places)) (error "Wizard hasn't been there before."))))) This solution allows places to appear in the PLACES list repeatedly. It could be improved by replacing the SET! lines with (if (not (memq (ask self 'place) places)) (set! ...)) Two details that didn't concern us too much are that the wizard's initial place should be in the PLACES list, and that GO-DIRECTLY-TO must be overridden as well as GO. A more important detail is the difference between a place and its name. The argument to go-directly-to is a place (that is, an object); the argument to revisit is a place name (that is, a word). Some people tried to override the GO method by copying its entire definition from the PERSON class into this class. That isn't just ugly; it won't work at all, because a method in the WIZARD class can't modify the binding of the variable PLACE in the PERSON class! You have to use USUAL to make this work. Scoring: 3 correct 2 all four of the following: parent is PERSON USUAL used in overriding GO method instance variable correctly updated has REVISIT method but other details can be wrong (e.g., name vs. object) 1 two or more of the four points above 0 less than two of them 5. Concurrency (a) The only possible value is 10. If the first process runs first, it sets BAZ to 5, and then the second process sets it back to 10. If the second process runs first, it sets BAZ to 20, and then the first process sets it back to 10. (b) 5: P1 computes baz/2 = 5, then P2 runs completely, then P1 stores 5. 10: either correct sequential order 15: P2 loads BAZ once from memory (getting 10), then P1 runs completely (setting BAZ to 5), then P2 loads BAZ again (getting 5), adds 10+5, stores 15. 20: P2 computes baz+baz = 20, then P1 runs completely, then P2 stores 20. Scoring: 3 correct 2 (a) correct, (b) missing one value and no wrong ones added 1 (a) correct or (b) correct 0 neither correct Group problem: This is a typical class/instance sort of problem. Defining MAKE-FOO creates a class, with class variable Y. Each invocation of MAKE-FOO creates an instance, with instance variable Z. So the environment should look *roughly* like this: G <---- Y-frame <----- foo1-z-frame ^ | | foo2-z-frame The actual solution also includes some procedures and some empty frames (from the invocations of procedures created with (lambda () ...) so there are no argument bindings). To avoid ASCII art, instead of a picture, here is a table with the elements all named: Frames Name Extends Bindings G --- make-foo --> P2 foo1 --> P4 foo2 --> P6 E1 G y --> 4, then 8, then 16 E2 E1 --- E3 E2 z --> 8, then 9 E4 E1 --- E5 E4 z --> 16, then 17 E6 E3 --- E7 E5 --- Procedures Name Environment Text P1 G (lambda (y) (lambda () ...)) P2 E1 (lambda () (set! y ...) ...) P3 E2 (lambda (z) (lambda () ...)) P4 E3 (lambda () (set! z ...) ...) P5 E4 (lambda (z) (lambda () ...)) P6 E5 (lambda () (set! z ...) ...) You should be able to draw the diagram from these tables. The values printed are 9 and 17. We didn't take off for missing empty frames (E2, E4, E6, E7) or missing LET procedures (P1, P3, P5). There were three main categories of error. One was getting the shape of the environment tree wrong: Two frames with bindings for Y, or only one frame with a binding for Z, or the Z frame not extending the Y environment. The next category was to draw a frame containing the binding z: y No! When a procedure is called (including the implicit procedure in a LET), *first* the argument expressions are *evaluated* and only then are the formal parameters bound to the argument *values*. Z is not bound to Y; it's bound to the value of Y in the current environment at the time the binding is made (8 for foo1, 16 for foo2). Changing Y later does not change either Z. People who made this mistake generally also gave the same printed answer for both instance invocations (9 and 9, or 17 and 17, generally). The third category was to get confused about what's a number and what's a procedure. Y and Z are numbers. FOO1 and FOO2 are procedures. I can't figure out the papers that had wildly incorrect diagrams but the right 9 and 17 printed. Either those people copied someone else's solution, or they don't think that the environment diagrams they draw actually mean anything. I don't see how you could work out the 9 and 17 if you really believed some of these diagrams! Scoring: 3 correct. 2 correct shape, like the abbreviated picture earlier, and correct types for the variable values. 1 one Z frame, or two Z frames not attached to the Y frame, or two Y frames, but types correct. 0 less than that. ----------------------------------- 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!