SICP Exercise 3.39 parallel-execute

Exercise 3.39.  Which of the five possibilities in the parallel execution shown above remain if we instead serialize execution as follows:

(define x 10)

(define s (make-serializer))

(parallel-execute (lambda () (set! x ((s (lambda () (* x x))))))
                  (s (lambda () (set! x (+ x 1)))))

 SOLUTION

 1. YES 101: P1 sets x to 100 and then P2 increments x to 101.
2. YES 121: P2 increments x to 11 and then P1 sets x to x times x.
3. NO 110: P2 changes x from 10 to 11 between the two times that P1 accesses the value of x during the evaluation of (* x x).
4. NO 11: P2 accesses x, then P1 sets x to 100, then P2 sets x.
5. YES 100: P1 accesses x (twice), then P2 sets x to 11, then P1 sets x.

 Note: In P1, the set! is not serialized and so can happen at any time. But the access of x and the computation (* x x) are inside a serialized function. Option 5 above is a possibility because, between the double access of x in P1 and the set! in P1, P2 can execute.

Comments

Post a Comment

Popular posts from this blog

SICP Exercise 3.56 merge streams

Exercise 3.56.   A famous problem, first raised by  R. Hamming, is to enumerate, in ascending order with no repetitions, all positive integers with no prime factors other than 2, 3, or 5. One obvious way to do this is to simply test each integer in turn to see whether it has any factors other than 2, 3, and 5. But this is very inefficient, since, as the integers get larger, fewer and fewer of them fit the requirement. As an alternative, let us call the required stream of numbers  S  and notice the following facts about it. S  begins with 1. The elements of  (scale-stream S 2)  are also elements of  S . The same is true for  (scale-stream S 3)  and  (scale-stream 5 S) . These are all the elements of  S . Now all we have to do is combine elements from these sources. For this we define a procedure  merge  that combines two ordered streams into one ordered result stream, eliminating repetitions: (define...
Read more

SICP Exercise 4.9 do for while until

Exercise 4.9.    Many languages support a variety of iteration constructs, such as  do ,  for ,  while , and  until . In Scheme, iterative processes can be expressed in terms of ordinary procedure calls, so special iteration constructs provide no essential gain in computational power. On the other hand, such constructs are often convenient. Design some iteration constructs, give examples of their use, and show how to implement them as derived expressions. SOLUTION The code and tests are  here . I have implemented the following expressions: do-while do-until for while The 'do-while' construct can be as follows: (do   (<one or more statements>)   while (condition) ) Use the while block construct to convert it as follows: (begin   <statements>   (while (condition)   <statements>   ) ) The 'do-until' construct can be as follows: (do   (<one or more statements>) ...
Read more

SICP Exercise 3.77 delayed integrand

Exercise 3.77.   The  integral  procedure used above was analogous to the ``implicit'' definition of the infinite stream of integers in section  3.5.2 . Alternatively, we can give a definition of  integral  that is more like  integers-starting-from  (also in section  3.5.2 ): (define (integral integrand initial-value dt)   (cons-stream initial-value                (if (stream-null? integrand)                    the-empty-stream                    (integral (stream-cdr integrand)                         ...
Read more