CS 61A Fall 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-car! (cdr x) (cddr x)) x) (1 (3 4) 3 4) !!!!!!!!!!!!! ! V +---+---+ +-!-+---+ +---+---+ +---+---+ | | | | ! | | | | | | | /| ---------> | | | ----->| ! | ----->| | | ----->| | | / | | | | | | . | | | | | | | | |/ | +-|-+---+ +-.-+---+ +-|-+---+ +-|-+---+ | . | | | . | | V V V V 1 2 3 4 [Notice that there are only four pairs in this diagram. It would be an error to draw two extra pairs whose cars are 3 and 4.] > (let ((x (list 1 2 3 4))) (set-cdr! (cdr x) (caddr x)) x) (1 2 . 3) [Note the dot!! Also, it's not (1 (2 . 3)), which would be a proper (null-terminated) list of two elements.] +---+---+ +---+---+ +---+---+ +---+---+ | | | | | | | | | | | /| ---------> | | | ----->| | | +....>| | | ----->| | | / | | | | | | | | ! | | | | | | | |/ | +-|-+---+ +-|-+-!-+ +-|-+---+ +-|-+---+ | | ! | | | | ! | | V V ! V V ! 1 2 !!!!!!> 3 4 > (let ((x (list 1 '(2 3) 4))) (set-car! x (caddr x)) x) (4 (2 3) 4) +---+---+ +---+---+ +---+---+ | | | | | | | | /| ---------> | | | ----->| | | ----->| | | / | | | | | | | | | | | |/ | +-|-+---+ +-|-+---+ +-|-+---+ | | | | | V .\ | . \!!!!!!!!!|!!!!!!!!> 4 . | . | V | | 1 | V +---+---+ +---+---+ | | | | | /| | | | ----->| | | / | | | | | | | |/ | +-|-+---+ +-|-+---+ | | V V 2 3 [Note that the new arrow points to the 4, not to the pair above it. It's okay if you wrote another 4 near the 1 instead of drawing an arrow across to the right. (It's *not* okay to duplicate pairs, because that obscures the fact that modifying the one pair would change two parts of the printed representation. But numbers aren't mutable, so it doesn't really matter whether there's one four or two fours.)] Scoring: One point each. Both the printed form and the diagram had to be right. 2. make-alist! The easiest way to do a problem like this is to use a LET in which you give names to every relevant piece of the list structure. Then, inside the LET, you can mutate the pairs in any old order without risk of error: (define (make-alist! lst) (if (null? lst) 'done (let ((car1 (car lst)) (cdr1 (cdr lst)) (car2 (cadr lst)) (cdr2 (cddr lst))) (set-car! lst cdr1) (set-cdr! lst cdr2) (set-car! cdr1 car1) (set-cdr! cdr1 car2) (make-alist! cdr2)))) But that's more work than is really needed. If you're clever about the order in which you do the mutation, you can get by with only one temporary variable. There are several such solutions; here's one: (define (make-alist! lst) (if (null? lst) 'done (let ((tmp (cddr lst))) (set-cdr! (cdr lst) (cadr lst)) (set-car! (cdr lst) (car lst)) (set-car! lst (cdr lst)) (set-cdr! lst tmp) (make-alist! tmp)))) Both of these solutions use the original first pair as the top-left pair of the resulting association list; the original second pair becomes the bottom-left pair. Several people noticed that you can rearrange the pairs with no temporary variables at all if you reverse those roles, so that what used to be the second pair becomes the head of the new association list. Unfortunately, this isn't quite a correct solution, because the caller of MAKE-ALIST! probably has some variable that still has the original first pair as its value, so the caller will think that that first pair is the new a-list. Note that you must check (NULL? LST) *before* you try to take its CAR or CDR. Scoring of typical solutions: 4 OK 3 Bad/missing base case; rearranges by mutation but the order isn't quite right; leaves second pair on top; uses return value from recursive call but doesn't return a value. 2 No temporary variable (via LET or helper procedure). 1 Uses CONS (or LIST or APPEND, etc). 0 (set! (car lst) ...) or similar confusions. Solutions using CONS scored lower than other errors because the problem explicitly said not to allocate new pairs. It's important that you understand the difference between allocating a pair and making a new pointer to an already-existing pair. Although it's true that the old pairs would be reclaimed, so the total storage requirement of the program wouldn't increase with solutions using CONS, sometimes it's important not to allow a delay for garbage collection. For example, if your program is creating video animation in real time, a garbage collection would bring the animation to a halt for a substantial time, perhaps half a second. 3. All-integers. The answer we expected was (define all-integers (cons-stream 0 (interleave integers (scale-stream -1 integers)))) The stream generated by this expression looks like this: 0, 1, -1, 2, -2, 3, -3, 4, -4, ... You had to understand two key points to get this solution: 1. You can't have all the integers in size order. A stream must have a definite first element! There's no smallest negative integer. Some people tried to REVERSE the stream of integers; that's meaningless. 2. You can't APPEND-STREAMS two infinite streams. This is explained in the handout you got in lecture. Since the first stream will never finish, it's as if the second stream isn't there at all! (A few people used MERGE, which works for two sorted, increasing streams, but not in a case like this where one stream is growing up and one growing down.) There were many other correct solutions, most of which essentially reinvented INTERLEAVE. Special mention for the following beautiful solution (which the student unfortunately didn't get quite right): (define zeros-ones (cons-stream 0 (cons-stream 1 zeros-ones))) (define all-integers (subtract-streams zeros-ones (cons-stream 0 all-integers))) where subtract-streams is like add-streams with the obvious difference. Work this out to convince yourself that it really works! Scoring: 4 correct 3 small mistakes, like leaving out zero 2 append-stream etc. 1 stream of streams, like (cons-stream negatives positives) 0 not a stream at all I've heard from several students who think that the stream-of-streams solution was graded too harshly. Here's the reasoning behind this grading policy: Most errors come from uncertainty about how to implement an infinite stream successfully. But this error indicates a misunderstanding about what the stream abstraction is for! Think about the example of testing whether a number is prime. We create a stream containing a range of numbers (range 2 14) and then we use that as an argument to FILTER: (filter (lambda (number) (= (remainder 15 number) 0)) (range 2 14)) If RANGE returned a stream of streams, then this FILTER wouldn't work, because the elements of the stream wouldn't be numbers! So, even though the problem said "a stream containing all the integers" instead of "a stream containing all the integers, in which each element is a single integer," it's unreasonable to think that a stream whose elements aren't numbers would be acceptable. 4. Hyperspace (define-class (hyperspace name) (parent (place name)) (class-vars (all-hyperspaces '())) (initialize (set! all-hyperspaces (cons self all-hyperspaces))) (method (enter who) (usual 'enter who) (if (coin-heads?) (ask who 'go-directly-to (choose-randomly all-hyperspaces))))) It's important that we specialize the ENTER method rather than the APPEAR method. When APPEAR is invoked, the person hasn't entirely entered the place yet; in particular, the person's PLACE variable doesn't reflect where the person actually is. The overall grading scheme was this: 4 OK 3 You don't understand the specific classes in the project. 2 You don't understand message passing in general. 1 You don't even inherit from the PLACE class. 0 Even worse. Typical examples: 3 Copied code from PLACE class's ENTER instead of using USUAL. Didn't SET! the class variable. Used a global variable instead of a class variable. Tried to use APPEAR instead of ENTER and didn't quite manage. 2 No initialization at all. Tried to use messages with wrong number of arguments. Tried to set variables in other objects directly instead of sending the object a message. Made a list of *names* of hyperspace objects instead of a list of the actual objects. Group problem: ____________________ G: | | |<---------+ | | every-nth ------------------> OO | p: num, lst ____________________| b: (define ...) (help ...) ^ | | | _________|____________ E1: | | num = 2 | lst = (she loves you) | |<---------+ | | help -------------------------> OO | p: lst, pos ______________________| b: (cond ...) ^ | | | _________|____________ E2: | | lst = (she loves you) | pos = 1 | ______________________| ______________________ E3: | | lst = (loves you) |-----> E1 pos = 2 | ______________________| ______________________ E4: | | lst = (you) |-----> E1 pos = 3 | ______________________| ______________________ E5: | | lst = () |-----> E1 pos = 4 | ______________________| The crucial point is that all of the frames E2 through E5 point back to E1, not to each other. (Not, for example, E4 to E3.) That's the meaning of lexical scope. Scoring: 4 OK. 3 Lexically scoped but with some errors. 2 Correctly dynamically scoped. 1 Dynamically scoped with additional errors (or no E3-E5). 0 Even worse.