HW 7 Solution

1.

First we add the "remainder" primitive into our non-deterministic evaluator.

(define (factor num)
  (let ((x (an-integer-between 2 num)))
     (require (= (remainder num x) 0))
     x))

(define (an-integer-between start finish)
   (require (> finish start))
   (choose start
           (an-integer-between (+ start 1) finish)))


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. 

(define (save-withdraw x)
  (if (<= x saving-acct)
      (set! saving-acct (- saving-acct x))
      #f))

(define serial-save-withdraw (T save-withdraw))

(define (transfer x)
  (if (serial-save-withdraw x)
      (serial-deposit x)
      "Don't have enough"))

4. 

He is wrong because after we assigned "temp" to the amount of money in checking-acct and right before we called "serial-withdraw", another process can interrupt and drain money from the checking account. 

Then, serial-withdraw would fail because we're trying to withdraw too much money.

To fix this, we could do:

(define (checking-drain)
  (let ((amount checking-acct))
     (set! checking-acct 0)
     amount))

(define serial-checking-drain (S (checking-drain)))

(define (save-up)
  (serial-deposit (serial-checking-drain)))


5.

(define (protected? p)
   (and (list? p)
          (eq? (car p) 'protected)))

(define (get-content p)
   (caddr p))

(define (get-mutex p)
   (cadr p))   

(define (make-lock)
  (let ((mutex (make-mutex)))
     (lambda (p)
        (list 'protected mutex p)) ) )

(define (safe-set-car! p val)
   (if (protected? p)
       (begin ((get-mutex p) 'acquire)
                 (set-car! (get-content p) val)
                 ((get-mutex p) 'release))
      (error "Not a protected pair")))

(define (safe-set-cdr! p val)
   (if (protected? p)
      (begin ((get-mutex p) 'acquire)
                (set-cdr! (get-content p) val)
                ((get-mutex p) 'release))
      (error "Not a protected pair")))

Of course, in order to call car and cdr on the protected pairs, we would have to redefine car and cdr:

(define car
  (let ((old-car car))
    (lambda (p)
       (if (protected? p) (old-car (get-content p))
           (old-car p)))))

and same for cdr...

Some people have correctly pointed out though that this doesn't actually solve the concurrency problem in the example. That is because when you do 

(safe-set-cdr! protect-p (cdr protected-p))

The (cdr protected-p) is evaluated before the safe-set-cdr! and another process can still interrupt between the two and modify protect-p.


6. 

This implementation of mutex is wrong. The key is in

(if (not taken) (set! taken #t) ...

Here, checking whether the mutex is taken or not and setting the mutex is not atomic. Hence, another process could interrupt in between.

So, process A could check "taken", see that it's false, and before it sets the "taken" variable to #t, another process tries to acquire mutex and checks "taken" is false. Now, both processes will have successfully acquired the mutex.