6.001 Structure and Interpretation of Computer Programs
Recitation #23
Friday, December 3, 2004

Review

Practice

Give all possible values of x that can result from the following code.  (As a help, the important atomic operations are labeled by letters.)
(define x 10)
                                 C      A B
(parallel-execute (lambda () (set! x (* x x)))
                  (lambda () (set! x (* x x x)))
                                 G      D E F
x2   (for example, from the interleaving AB DEFG C)
x3   (DEF ABC G)
x4   (A DEFG BC)
x5   (ABD C EF G)
x6   (ABC DEFG)


What possible values of x remain if the procedures are serialized, as below?
(define x 10)
(define s (make-serializer))
                                    C      A B
(parallel-execute (s (lambda () (set! x (* x x))))
                  (s (lambda () (set! x (* x x x))))
                                    G      D E F
Only x6   (ABC DEFG).



What if the procedures are serialized in a different way, as shown below?
(define x 10)
(define s (make-serializer))
(define t (make-serializer))
                                    C      A B
(parallel-execute (s (lambda () (set! x (* x x))))
                  (t (lambda () (set! x (* x x x))))
                                    G      D E F
Different serializers don't block each other, so any interleaving is possible again:
x2 , x3, x4, x5, x6