CS 61A Solutions to sample midterm 3 #3 1. Box and pointer. (let ((x (list 1 2 3))) (set-cdr! (cdr x) (cddr x)) x) (1 2 3) is printed. X-->[o|o]-->[o|o]==>[o|/] | | | V V V 1 2 3 In this example the SET-CDR! call effectively does nothing, since it replaces the cdr of (cdr x) with the cddr -- the cdr of the cdr -- of X. The arrow drawn with = instead of - above is the one that's replaced with itself. (let ((x (list 1 2 3))) (set-car! x (cddr x)) x) ((3) 2 3) is printed. +----------------+ | | | V X-->[o|o]-->[o|o]-->[o|/] | | V V 2 3 The set-car! invocation changes (car x), i.e., the first element of X. It's changed to (cddr x), which is a *sublist*, not just an element, of X. Thus the new first element is not 3, but (3). (let ((x (list 1 2 3))) (set-car! (cdr x) (cdr x)) x) (1 ((((((((( ... is printed. +-+ | | | V X-->[o|o]-->[o|o]-->[o|/] | | V V 1 3 Note that the arrow at the top of the diagram points *from the car* of the second pair, but points *to the entire pair* (because that's how pointers always work), not just to the cdr, even though that's where the arrowhead happens to be. There's still a 3 in this list, but it'll never be printed. (let ((x (list 1 2 3 4))) (set-cdr! (cddr x) (cadr x)) x) (1 2 3 . 2) is printed. X-->[o|o]-->[o|o]-->[o|o]--> 2 | | | V V V 1 2 3 In this example we change the cdr of a pair (because we're doing SET-CDR!) to point to a non-pair, (CADR X), the second element of X, which is 2. Thus the result is an improper list, so there's a dot in the printed version. It doesn't matter, in the diagram, whether you have two 2s, as above, or have two arrows pointing to the same 2. It *does* matter when the thing being pointed to is a pair; then there's a big difference between two pointer to the same pair, and two pairs that have the same values in them. Scoring: One point per printed representation; one point per diagram. 2. Local state. Does Louis's MEMOIZE give wrong answers? YES. Explanation: It has one table shared among all memoized functions, instead of a separate table per function. Example: [Louis has defined MEMO-FIB, as shown in the question.] > (memo-fib 4) 3 > (define memo-square (memoize (lambda (x) (* x x)))) > (memo-square 4) 3 Since MEMO-FIB and MEMO-SQUARE share the same table, (memo-square 4) returns the value previously remembered from (memo-fib 4). Some students who checked NO explained why the answer is really YES, so we figured people misread the question, and went by your explanantion rather than by which choice you checked. Pretty much any explanation with a phrase like "a single table" or "universal table" or "global table" was accepted. (It's not quite right to say "a table in the global environment"; the table is actually a local state variable of MEMOIZE.) Explanations that merely restate the form of Louis's change to the program were not accepted: "The program gives wrong answers because Louis has moved the LET to outside of the LAMBDA." You had to explain what *effect* that would have on the program's *behavior*. The example didn't necessarily have to take the form of a specific Scheme interaction as above, but did have to assert that two different functions are memoized. Scoring: 4 correct 2 correct explanation, no/bad example; iffy explanation (like "global environment" discussed above) 0 bad explanation (including saying that it doesn't give wrong answers) No odd scores were assigned. 3. Environment diagram. Bindings A=8 and B=9 go in the global environment. Then comes the LET, which is equivalent to an invocation of the procedure generated by an implicit LAMBDA: ((lambda (a f) (f 5)) 3 (lambda (b) (+ a b))) As with any procedure invocation, **first all the subexpressions are evaluated!** This evaluation takes place in the global environment -- we haven't invoked any procedures yet. Thus, two procedures are created whose right bubbles point to the global environment. Only then do we invoke the (lambda (a f) ...) procedure, which creates a frame in which A is bound to 3, and F is bound to the (lambda (b) ...) procedure. That new frame, of course, extends the global environment. With that frame as (the first frame of) the current environment, we can evaluate the body of the LET, which is (F 5). We find a binding for F in the current environment; it's the (lambda (b) ...) procedure. So we can invoke that with the argument 5. Since F's right bubble points to the global environment, that's what we extend with the new frame that binds B=5. So when we evaluate F's body, which is (+ A B), we find the bindings A=8 and B=5. Thus, the final answer is 13. The overwhelmingly most common mistake was to think that the (lambda (b) ...) procedure's right bubble points to the A=3 frame, so the B=5 frame points there also, and the final value is 8. You should know, though, that a LET binding can't depend on another binding in the same LET; for example, if the problem had been (let ((a 3) (c (+ a b))) (+ a c)) I hope most people would have known that C would be 8+9, using the global bindings for both A and B. The fact that the computation using A happens inside a lambda body doesn't change the fact that the LET's binding for A isn't available to it. A few people drew the environment diagram that would give an answer of 8, but instead wrote 13 as their final answer, which means either that they copied someone else's final answer or that they *do* know how Scheme evaluates expressions, but don't make any connection between that and the environment model. We graded this as if they'd said 8. A couple of people had procedure F's right bubble correctly pointing to the global environment, but nevertheless had the B=5 frame extending the A=3 frame, using dynamic scope instead of lexical scope. This gave the same wrong final answer of 8. Scoring: 6 correct. 3 answer was (or should have been) 8, as discussed above. 0 even worse (too many frames, no arrows at all -- there weren't many). 4. List mutation (define a (list 'x)) (define b (list 'x)) (define c (cons a b)) (define d (cons a b)) (eq? a b) => #F Each call to LIST generates new pairs (one new pair, in this case, because each list has only one element). (eq? (car a) (car b)) => #T Both CARs are the symbol X, and equal symbols are always EQ. (eq? (cdr a) (cdr b)) => #T Both CDRs are the empty list, and there's only one empty list. (eq? c d) => #F Each call to CONS generates a new pair. (eq? (cdr c) (cdr d)) => #T Both CDRs are the pair named B -- the same pair. (define p a) (set-car! p 'squeegee) (eq? p a) => #T P and A are two names for the same pair. Mutating the pair doesn't change the variable bindings. (define q a) (set-cdr! a q) (eq? q a) => #T This one looks trickier because the pair now points to itself, but it's really the same as the previous question: Q and A are two names for the same pair. (define r a) (set! r 'squeegee) (eq? r a) => #F This time we didn't mutate a pair; we changed the binding of one of the variables. So R and A now name two different things; A is still a pair, but R is now a symbol. Score: 1/2 point each, rounded down to the nearest whole point. 5. Vector programming (define (ssort! vec) (define (help start) (if (= start (vector-length vec)) vec (let ((smallest (subvec-min-start vec start))) (let ((temp (vector-ref vec smallest))) (vector-set! vec smallest (vector-ref vec start)) (vector-set! vec start temp) (help (+ start 1)))))) (help 0)) The key point to understand is that you need to walk through the vector, bringing the smallest element out to position 0, then the next-smallest to position 1, and so on, until you run out of elements. Thus we have a helper procedure with an argument, START, whose value is the position that we're up to in the vector; it starts at 0 and is increased by 1 on each recursive invocation. The next important point is that you can't exchange two elements without using a temporary variable to remember one of them, hence the LET that creates the variable TEMP. There are two nested LETs because the value of SMALLEST is needed to find the value of TEMP in this solution; I could have simplified things a little by remembering the other value in the swap instead: (define (ssort! vec) (define (help start) (if (= start (vector-length vec)) vec (let ((smallest (subvec-min-start vec start)) (temp (vector-ref vec start))) (vector-set! vec start (vector-ref vec smallest)) (vector-set! vec smallest temp) (help (+ start 1)))))) (help 0)) Scoring: 6 correct 5 trivial error (e.g. base case off by one) 3 right structure, gets swap wrong 2 serious algorithm confusion 0 allocates new vector, uses lists, or incoherent 6. Concurrency (define (make-mutex) (let ((in-use #f) (s (make-serializer))) (define (the-mutex m) (cond ((eq? m 'acquire) (if ((s (lambda () (if in-use #t (begin (set! in-use #t) #f))))) (the-mutex 'acquire))) ; retry ((eq? m 'release) (set! in-use #f)))) the-mutex)) The structure of the above is just like that of the MAKE-MUTEX in the book, except that when an atomic test-and-set operation is needed, it's done by including the (IF IN-USE ...) and the (SET! IN-USE #T) within the same serialized procedure, rather than by relying on a TEST-AND-SET! primitive. Many people found the problem deeply confusing. You learned that serialization has three levels of abstraction: the hardware support, the critical section mechanism (mutex) based on the hardware, and the more abstract level in which procedures are protected rather than sequences of instructions. So what does it mean to define a mutex in terms of a serializer? But actually this could happen. Suppose you are using a language such as Java, with high-level serialization built in (and presumably implemented using hardware support), to write an operating system that is supposed to provide a mutex capability to its users. You would then write something equivalent to what this problem asks for. What defines an abstraction is its behavior, not how it's implemented -- this is the whole idea behind abstraction. The SICP version uses (LET ((CELL (LIST FALSE))) ...) because their TEST-AND-SET! tests and modifies a pair, not a variable, mainly so that it can be an ordinary procedure rather than a special form. In this version there's no need to use a pair, although it wouldn't be wrong. The ugly (IF ((S (LAMBDA () ...))) ...) is necessary because of the way serializers work: they take a procedure as argument and return a protected version of that procedure, which must then actually be invoked. We didn't take off for minor failures in the notation, accepting even solutions in which the argument to the serializer was an expression to be evaluated atomically: (IF (S (IF IN-USE ...)) ...) But we didn't accept solutions in which the serializer was given data, rather than activity, as its argument. (More on that below.) The reason for the nested IFs is a little subtle; the recursive call to THE-MUTEX to retry the operation if it fails can't be inside the serialized procedure, because then it'll block waiting for S, which is held by this process itself -- in effect, setting up a deadlock within a single process. But we didn't take off points for missing this subtlety. Some people used a single global serializer instead of a separate one for each mutex. At first we considered this a serious error, because it means that two mutexes can't be acquired at the same time. But then we realized that the serializer just protects the acquiring of the mutex, not the critical section that the mutex itself protects, so any mutex holds the serializer only for a very short time. So we allowed a global serializer, except in papers that also missed the point in the previous paragraph. If a mutex can get into a deadlock with itself, while holding a serializer needed by all the other mutexes, that's serious enough to lose a point. Some solutions never actually tested whether the mutex was in use before acquiring it. Presumably those people thought that the serializer would protect the entire critical section, not just the acquiring, so that if an acquire operation could get into the serializer the mutex must be free. But that's not the case; the mutex returns to its caller once it has set its in-use flag, so the caller's critical section is *not* keeping the serializer busy. Such solutions got at most one point. There were a few common zero-point solutions. The strangest were the ones that called parallel-execute. The job of a mutex is to protect critical sections against other processes, not to create other processes. Another zero-point solution had expressions such as (S CELL) that showed a lack of understanding of the key fact that a serializer protects activities, not data. Similarly, no points for anything that included (something . args) ;; pfui which indicated mindless copying from the MAKE-SERIALIZER in the book without understanding. Serializers accept as arguments procedures with any number of arguments, but any particular use of a serializer isn't going to be that complicated -- and none of these solutions found any use for the ARGS variable anyway. Scoring: 3 OK 2 at least an atomic test-and-set implementation 1 no test-and-set, but some idea 0 way off 7. Streams. 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 We heard from several students who thought 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.