CS 61A -- Week 6 Solutions LAB 1 ASSIGNMENT: Here are the key points: 1. CORRECTNESS. We are required to ensure that two philosophers can't decide to pick up the same chopstick at the same time. So anything of the form (if (chopstick-free? n) (get-chopstick n) ...) has to be protected by a serializer. 2. EFFICIENCY. We don't want to restrict the program so much that only one philosopher can eat at a time. More or less half of the people should be able to eat at once. So we can't just serialize the try-to-eat procedure; we have to serialize the smallest possible parts of it. 3. DEADLOCK. If you have a separate serializer for each chopstick (a plausible approach), you have to be careful not to get into the situation in which everyone gets their left chopstick and can't get the right one. You have to ensure that you can get both chopsticks before you actually pick up either one. Here's one way: (define s (make-serializer)) (define free (list #t #t #t #t #t)) (define (philosopher num) (think) (try-to-eat num) (philosopher num)) (define (try-to-eat num) (if ((s (lambda () (if (and (list-ref free (left num)) (list-ref free (right num))) (begin (set-car! (nth-cdr (left num) free) #f) (set-car! (nth-cdr (right num) free) #f) #t) #f)))) (begin (eat) (set-car! (nth-cdr (left num) free) #t) (set-car! (nth-cdr (right num) free) #t)) (try-to-eat num))) LAB2 Assignment: 1. The result of (delay ...) is of type procedure. The result of (force (delay ...)) is of whatever type the "..." would be without delay; in this case it's (force (delay (+ 1 27))) and that's of type integer. 2. (stream-cdr (stream-cdr (cons-stream 1 '(2 3)))) causes an error because (2 3) isn't a stream. (stream-cdr (cons-stream 1 '(2 3))) --> (2 3) (stream-cdr '(2 3)) --> (force (cdr '(2 3))) --> (force '(3)) but (3) isn't a promise! 3. (delay (enumerate-interval 1 3)) returns a promise. (stream-enumerate-interval 1 3) returns a stream, i.e., a pair whose car is 1 and whose cdr is a promise. The only thing you can do with the result of (delay ...) is FORCE it; you can't ask for its stream-car or stream-cdr, etc. By contrast, with the stream, you can stream-car or stream-cdr it, but *not* force it, because it's not a promise. 4. the 4-2-1 stream. (define (next-num n) (if (even? n) (/ n 2) (+ (* n 3) 1))) (define (num-seq n) (cons-stream n (num-seq (next-num n)))) (define (seq-length s) (if (= (stream-car s) 1) 1 (+ 1 (seq-length (stream-cdr s))))) HOMEWORK: 1 Abelson and Sussman exercises 3.38 (a). Peter then Paul then Mary: 100 -> 110 -> 90 -> 45. Peter then Mary then Paul: 100 -> 110 -> 55 -> 35. Paul then Peter then Mary: 100 -> 80 -> 90 -> 45. Paul then Mary then Peter: 100 -> 80 -> 40 -> 50. Mary then Peter then Paul: 100 -> 50 -> 60 -> 40. Mary then Paul then Peter: 100 -> 50 -> 30 -> 40. So the possible final values are 35, 40, 45, and 50. (b). There are lots of extra possibilities. It's especially bad because Mary's command is (set! balance (- balance (/ balance 2))) which examines the value of balance twice, instead of the mathematically equivalent (set! balance (/ balance 2)) which only examines the value once. Here are just a few possibilities: Peter examines balance, then Paul and Mary run in either order, then Peter sets balance. Paul's and Mary's activities become irrelevant; the final balance will be 110. Mary looks at balance, then Paul runs, then Mary looks at balance again to compute (/ balance 2), then Peter runs, then Mary sets the balance. Peter's work is irrelevant, but Paul's isn't; Mary computes (- 100 (/ 80 2)) and the final balance is 60. Paul examines balance, then Peter and Mary run in any order, then Paul sets balance. The result is 80. 3.39 buggy serialization Because multiplying x by itself is serialized, we can eliminate the case in which (* x x) gets two different values of x, which is the one that leads to a final answer of 110. However, because the setting of x in P1 is not serialized along with P1's reading of x, we can still get the incorrect answer 100. And because only the computation part of P1 is serialized, the incorrect answer 11 is also still possible. It can't happen the way it's described in the book: P2 accesses x, then P1 sets x to 100, then P2 sets x but it can happen in this more complicated way: P1 reads x and computes the value 100, then P2 accesses x (still 10), then P1 sets x to 100 (since this part isn't serialized), then P2 sets x to 11. (And of course the correct answers 101 and 121 are still possible.) 3.40 The smallest possible result is the one you get if P1 reads and squares 10, then P2 runs completely, and then P1 sets x to 100. The largest possible result is the correct one, in which the two processes run serially (in either order); the result is 1,000,000. Any power of 10 between these limits is also possible: 1000: P2 cubes 10, then P1 runs completely, then P2 sets x to 1000. 10000: P2 reads x=10 twice, then P1 runs completely, setting x to 100, then P2 reads x=100 for its third factor and sets x to 10*10*100. 100000: P2 reads x=10 once, then P1 runs, then P2 reads x=100 twice. If the processes are serialized, only the correct result 1,000,000 is possible. Either P1 sets x to 100 and then P2 cubes that, or else P2 sets x to 1000 and P1 squares that. 3.42 when to serialize procedures Ben is right. The key point to understand is that there are three distinct steps in using a serializer: 1. Create the serializer. 2. Create a serialized procedure. 3. Invoke the serialized procedure. Only step 3 involves concurrency problems. Ben's proposal is to reduce the number of times step 2 is taken, which is fine. 3.44 Transferring money Louis is wrong, as usual. In the case of transferring a fixed (given as argument) amount of money, there really are two entirely separate steps: Withdraw the money from one account, and deposit the money in another. Each step is serialized by the account itself. It doesn't matter if something else happens between the two steps! You might think "another process could change the value of the variable AMOUNT" but that's not so; AMOUNT is a *local* variable within this transfer, not shared with any other process. We only have to worry about synchronization when a state variable is shared among different processes. Also, in the case of TRANSFER, the only constraint on correct answers when several transfers are done in parallel is that the sum of the balances should be the same after the transfers as before. EXCHANGE has a more stringent requirement; after several parallel exchanges, the balances of all accounts should be the same as before, except in a different order. It's not good enough for the sum of the balances to be preserved; the individual balances must be, too. Since the amount to be transferred is a function of the starting balances, we can't let another process intervene between computing that amount and adjusting the balances. 3.46 Why test-and-set! must be atomic Suppose the mutex is initially false. P1 starts doing (if (car cell) ...) and gets the value FALSE, so it thinks the mutex is free. Now P2 runs, before P1 does anything else. It, too, does (if (car cell) ...), reads the value FALSE, and thinks the mutex is free. Then they both set the value to TRUE and claim the mutex. We have to make sure that there is no intervening process between reading (car cell) and (set-car! cell true). 3.48 deadlock The problem we're solving is that P1 and P2 want the same two serializers S1 and S2. Deadlock will happen under the following order of events: 1. P1 gets S1. 2. P2 gets S2. 3. P1 wants S2, can't have it, waits. 4. P2 wants S1, can't have it, waits. Both processes wait forever because they're trying to use a busy serializer. This problem appeared because P1 and P2 asked for the serializers in reverse order from each other. If they both use the same order, the worst sequence of events will be this: 1. P1 gets S1. 2. P2 wants S1, can't have it, waits. 3. P1 gets S2. 4. P1 finishes, releases both serializers. 5. P2 finally gets S1. 6. P2 gets S2. 7. P2 finishes, releases both serializers. Here's the code: (define make-account-and-serializer (LET ((NEXT-ID-NUMBER 1)) (lambda (balance) (define (withdraw amount) ...) (define (deposit amount) ...) (let ((balance-serializer (make-serializer)) (ID-NUMBER NEXT-ID-NUMBER)) (define (dispatch m) (cond ((eq? m 'withdraw) withdraw) ((eq? m 'deposit) deposit) ((eq? m 'balance) balance) ((eq? m 'serializer) balance-serializer) ((EQ? M 'ID) ID-NUMBER) (else (error ...)))) (SET! NEXT-ID-NUMBER (+ NEXT-ID-NUMBER 1)) dispatch)))) (define (serialized-exchange account1 account2) (IF (> (ACCOUNT1 'ID) (ACCOUNT2 'ID)) (SERIALIZED-EXCHANGE ACCOUNT2 ACCOUNT1) (let ((serializer1 (account1 'serializer)) (serializer2 (account2 'serializer))) ...))) This solution, by the way, assumes that only one account is *created* at a time! If accounts can be created in parallel, then the assigning of account numbers must also be serialized, this way: (define make-account-and-serializer (let ((next-id-number 1) (ID-SERIALIZER (MAKE-SERIALIZER))) (lambda (balance) (define (withdraw amount) ...) (define (deposit amount) ...) ((ID-SERIALIZER (LAMBDA () (let ((balance-serializer (make-serializer)) (id-number next-id-number)) (define (dispatch m) (cond ((eq? m 'withdraw) withdraw) ((eq? m 'deposit) deposit) ((eq? m 'balance) balance) ((eq? m 'serializer) balance-serializer) ((eq? m 'id) id-number) (else (error ...)))) (set! next-id-number (+ next-id-number 1)) dispatch))))))) There is a separate balance-serializer for each account, but a single id-serializer for the entire account class. In our OOP notation we might say (define-class (account balance) (class-vars (next-id-number 1) (id-serializer (make-serializer))) (instance-vars (balance-serializer (make-serializer)) (id-number #f)) (initialize ((id-serializer (lambda () (set! id-number next-id-number) (set! next-id-number (+ next-id-number 1)))))) (method (withdraw amount) ...) (method (deposit amount) ...)) 3.50 stream-map (define (stream-map proc . argstreams) (if (STREAM-NULL? (car argstreams)) the-empty-stream (CONS-STREAM (apply proc (map STREAM-CAR argstreams)) (apply stream-map (cons proc (map STREAM-CDR argstreams)))))) 3.51 stream-ref > (stream-ref x 5) 1 2 3 4 5 5 > (stream-ref x 7) 6 7 7 > The repeated last number in each case is the actual value returned by stream-ref; the other numbers are printed by show. The only numbers shown are the ones we haven't already computed. If we ask for a value nearer the front of the stream, nothing is SHOWn at all: > (stream-ref x 4) 4 > Notice that the first element of the stream is zero, not one -- why isn't the zero printed? Answer: It was printed when you defined X in the first place. NOTE: The important thing to take away from this example is that if DELAY didn't involve memoization, the printed results would be quite different. All the numbers would be printed every time. 3.52 accum/filter To make the situation more visible, I've chosen to define accum to use show (as above), so we can see intermediate results: > (define sum 0) SUM > (define (accum x) (set! sum (+ (show x) sum)) sum) ACCUM > (define seq (stream-map accum (stream-enumerate-interval 1 20))) 1 SEQ ;; map applies the function argument to the stream-car of the stream only. > sum 1 > (define y (stream-filter even? seq)) 2 3 Y ;; filter keeps forcing stream elements until it finds an even sum, 1+2+3. > sum 6 > (define z (stream-filter (lambda (x) (= (remainder x 5) 0)) seq)) 4 Z ;; 1+2+3+4 is divisible by 5. > (stream-ref y 7) 5 6 7 8 9 10 11 12 13 14 15 16 136 ;; even sums are 6, 10, 28, 36, 66, 78, 120, 136 (1+...+16). ;; (Notice how they come in pairs, by the way. Two odd sums, then two even.) > sum 136 > (print-stream z) {10 15 45 55 105 120 17 18 19 190 20 210} ;; This may look confusing. Had I not used show, print-stream would have ;; printed {10 15 45 55 105 120 190 210}. This is the entire stream z. ;; The numbers 17 to 20 were printed by show as the stream seq was forced. > sum 210 > Had we not used the memoizing version of delay, the computation of z would have forced the stream seq over again, from the beginning. Not only would accum have shown the results 1, 3, 6, 10, etc. over again, it would have gotten the wrong answers! Since it uses the global variable sum, it only works if each term is added to the sum only once. 3.53 implicit definition Try it yourself! We know the first element of S is 1 and the STREAM-CDR is the result of adding S and S, so we get: 1 ... + 1 ... -------- 2 ... So the second element must be 2. That means we have: 1 2 ... + 1 2 ... ---------- 2 4 ... So the third element is 4, and so on. 3.55 partial sums (define (partial-sums s) (define result (cons-stream (stream-car s) (add-streams (stream-cdr s) result))) result) Alternatively, it can be done explicitly: (define (partial-sums s) (define (helper s sofar) (cons-stream sofar (helper (stream-cdr s) (+ sofar (stream-car s))))) (helper (stream-cdr s) (stream-car s))) but the first version is way cooler. 3.56 merge and Hamming's problem This is easy: > (define S (cons-stream 1 (merge (scale-stream S 2) (merge (scale-stream S 3) (scale-stream S 5))))) S > (show-stream S 41) (1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54 60 64 72 75 80 81 90 96 100 108 120 125 128 135 144 150 ...) 3.68 Louis INTERLEAVE is an ordinary Scheme procedure, so its arguments must be computed before INTERLEAVE is called. One of those arguments is a recursive call to PAIRS. This will be an infinite loop. The book's version works because it uses CONS-STREAM, which doesn't evaluate its second argument until later, if ever. 2. fract-stream problem (define (fract-stream numer denom) (cons-stream (quotient (* numer 10) denom) (fract-stream (remainder (* numer 10) denom) denom))) (define (approximation str num) (if (= num 0) '() (cons (stream-car str) (approximation (stream-cdr str) (- num 1))) )) Extra Practice 3.41 serialize reading balance? The reason we need serialization in the first place is that if a process makes more than one reference to the same variable, we want to be sure its value is consistent throughout that process. But reading the balance only looks at the balance once; how could another process interrupt that? Actually, this answer is a slight handwave. In order to be confident about it, you must know that a number can be read from the computer's memory in a single, indivisible hardware operation. This is true for every modern computer, provided that the number fits in the usual hardware representation of numbers. However, Scheme supports "bignums", which are unlimited-precision integers. That's why in Scheme you can compute the factorial of 1000 and get a precise answer, even though that answer has 2568 decimal digits. Reading a bignum requires more than one memory reference, and so Ben is right if bignums are allowed. The usual indivisible-lookup kind of integer can support values up to about 2 billion, so this means that the bank that handles Bill Gates' account should take Ben's advice, but the rest of us don't have to worry about it. 3.54 factorials (define (mul-streams s1 s2) (stream-map * s1 s2)) (define factorials (cons-stream 1 (mul-streams FACTORIALS INTEGERS))) will give you the stream {1 1 2 6 24 ...} starting with zero factorial, or (define factorials (cons-stream 1 (mul-streams FACTORIALS (STREAM-CDR INTEGERS)))) will give the stream {1 2 6 24 ...} starting with one factorial. 3.64 stream-limit (define (stream-limit s tolerance) (if (< (abs (- (stream-car s) (stream-car (stream-cdr s)))) tolerance) (stream-car (stream-cdr s)) (stream-limit (stream-cdr s) tolerance))) 3.66 examine the pairs of integers One thing to try is to look at each half of the pairs separately. > (ss (stream-map car p) 100) (1 1 2 1 2 1 3 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 ...) Every other element is 1. Leaving those out, we get 1 2 2 3 2 3 2 4 2 3 2 4 2 3 2 5 2 3 2 4 ... Except right at the beginning, every other element is 2. Leaving those out we are left with 2 3 3 4 3 4 3 5 3 4 ... Looks like every other element is 3... sounds like a pattern! > (ss (stream-map cadr p) 100) (1 2 2 3 3 4 3 5 4 6 4 7 5 8 4 9 6 10 5 11 7 12 5 13 8 14 6 15 9 16 5 17 10 18 7 19 11 20 6 21 12 22 8 23 13 24 6 25 14 26 9 27 15 28 7 29 16 30 10 31 17 32 6 33 18 34 11 35 19 36 8 37 20 38 12 39 21 40 7 41 22 42 13 43 23 44 9 45 24 46 14 47 25 48 7 49 26 50 15 51 ...) The even-numbered elements are 2 3 4 5 6 7 8 9 10 11 12 ... The odd-numbered ones are 1 2 3 3 4 4 5 4 6 5 7 5 8 6 ... What can you make of those? Another approach is to compute the position of the first occurrence of each integer. (define (firstone s n) ;; (firstone s n) is first index where the element is equal to n (define (f1 s count) (if (= (stream-car s) n) count (f1 (stream-cdr s)(+ 1 count)))) (f1 s 0)) the firstone of 1 is 1 the firstone of 2 is 3 3 7 4 15. Notice a pattern? So the firstone of 100 is (would you believe count = (- (expt 2 100) 1) --> 1267650600228229401496703205375 ... So the pair (100 1) would be half that length or so. 4/11/2000 RJF