my attempt to do the exercises in sicp.

Wednesday, March 24, 2010

sicp exercise 3.49



;; Exercise 3.49.  Give a scenario where the deadlock-avoidance mechanism described above does not work. (Hint: In the exchange problem, each process knows in advance which accounts it will need to get access to. Consider a situation where a process must get access to some shared resources before it can know which additional shared resources it will require.)

;; Ans: If the resources are not acquired in order, there is always a chance of deadlock.


sicp exercise 3.48




;; Exercise 3.48.  Explain in detail why the deadlock-avoidance method described above, (i.e., the accounts are numbered, and each process attempts to acquire the smaller-numbered account first) avoids deadlock in the exchange problem. Rewrite serialized-exchange to incorporate this idea. (You will also need to modify make-account so that each account is created with a number, which can be accessed by sending an appropriate message.)

;; Ans:
;; if both processes acquire the mutex in the same order, deadlock can be avoided. By checking the account number and locking the least numbered account maintain the same order.


(define (serialized-exchange account1 account2)
  (let ((serializer1 (account1 'serializer))
        (serializer2 (account2 'serializer)))
    (if (< (account1 'getid) (account2 'getid))
        ((serializer1 (serializer2 exchange)) account1 account2)
        ((serializer2 (serializer1 exchange)) account1 account2))))

sicp exercise 3.47



;; Exercise 3.47.  A semaphore (of size n) is a generalization of a mutex. Like a mutex, a semaphore supports acquire and release operations, but it is more general in that up to n processes can acquire it concurrently. Additional processes that attempt to acquire the semaphore must wait for release operations. Give implementations of semaphores

;; a. in terms of mutexes

;; b. in terms of atomic test-and-set! operations.


;; Ans: a:
;; a shared variable, protected by a mutex, keeps count of the times the semaphore has been acquired.
(define (make-sem n)
  (let ((m (make-mutex))
        (count n))
    (define (the-sem s)
      (cond ((eq? s 'acquire)
             (m 'acquire)                   ;; acquire the mutex
             (if (> count 0)                ;; check if semaphore available
                 (begin                     ;; if semaphore available
                   (set! count (- 1 count)) ;; reduce by one
                   (m 'release))            ;; release mutex
                 (begin                     ;; if semaphore not available
                   (m 'release)             ;; release mutex
                   (the-sem 'acquire))))    ;; retry to acquire semaphore
            ((eq? s 'release)
             (m 'acquire)
             (set! count (+ 1 count))
             (m 'release))))
     the-sem))

;; Ans: b:
;; The implementation of make-sem with test-and-set! is same as above. Replace mutex code with test-and-set! code and increment the counter in different branches.







sicp exercise 3.46


;; Exercise 3.46.  Suppose that we implement test-and-set! using an ordinary procedure as shown in the text, without attempting to make the operation atomic. Draw a timing diagram like the one in figure 3.29 to demonstrate how the mutex implementation can fail by allowing two processes to acquire the mutex at the same time.

;; Ans:
;; If the test-and-set! is not atomic, the while one process is checking its value to be false, other process can set the value to be true and take control of the mutex, while first process also does the same. So both processes acquire the mutex and enter the critical section. Which is not the desired behavior.

Thursday, March 18, 2010

sicp exercise 3.45



;; Exercise 3.45.  Louis Reasoner thinks our bank-account system is unnecessarily complex and error-prone now that deposits and withdrawals aren't automatically serialized. He suggests that make-account-and-serializer should have exported the serializer (for use by such procedures as serialized-exchange) in addition to (rather than instead of) using it to serialize accounts and deposits as make-account did. He proposes to redefine accounts as follows:

(define (make-account-and-serializer balance)
  (define (withdraw amount)
    (if (>= balance amount)
        (begin (set! balance (- balance amount))
               balance)
        "Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount))
    balance)
  (let ((balance-serializer (make-serializer)))
    (define (dispatch m)
      (cond ((eq? m 'withdraw) (balance-serializer withdraw))
            ((eq? m 'deposit) (balance-serializer deposit))
            ((eq? m 'balance) balance)
            ((eq? m 'serializer) balance-serializer)
            (else (error "Unknown request -- MAKE-ACCOUNT"
                         m))))
    dispatch))

;; Then deposits are handled as with the original make-account:

(define (deposit account amount)
((account 'deposit) amount))

;; Explain what is wrong with Louis's reasoning. In particular, consider what happens when serialized-exchange is called.

;; Ans:
;; when serialized-exchange is called, the serializer is invoked twice. once by the serialized-exchange and once more by the (account 'withdraw) invoked from exchange.
;; So the whole process will lock upon itself.


sicp exercise 3.44


;; Exercise 3.44.  Consider the problem of transferring an amount from one account to another. Ben Bitdiddle claims that this can be accomplished with the following procedure, even if there are multiple people concurrently transferring money among multiple accounts, using any account mechanism that serializes deposit and withdrawal transactions, for example, the version of make-account in the text above.

;; (define (transfer from-account to-account amount)
;;   ((from-account 'withdraw) amount)
;;   ((to-account 'deposit) amount))

;; Louis Reasoner claims that there is a problem here, and that we need to use a more sophisticated method, such as the one required for dealing with the exchange problem. Is Louis right? If not, what is the essential difference between the transfer problem and the exchange problem? (You should assume that the balance in from-account is at least amount.)

;; Ans:
;; Louis is not right. The exchange problem and transfer problem are different. The exchange problem involving two accounts makes the two accounts dependent on each other. while the transfer problem doesnt do so. The account being deposited doesnt care where the amount being deposited is coming from.




sicp exercise 3.43


;; Exercise 3.43.  Suppose that the balances in three accounts start out as $10, $20, and $30, and that multiple processes run, exchanging the balances in the accounts. Argue that if the processes are run sequentially, after any number of concurrent exchanges, the account balances should be $10, $20, and $30 in some order. Draw a timing diagram like the one in figure 3.29 to show how this condition can be violated if the exchanges are implemented using the first version of the account-exchange program in this section. On the other hand, argue that even with this exchange program, the sum of the balances in the accounts will be preserved. Draw a timing diagram to show how even this condition would be violated if we did not serialize the transactions on individual accounts.

;; Ans:
;; Assume that accounts a1 and a2 are being exchanged, and simulaneously a2 and a3 are being exchanged. since a2 is being locked by both processes, a2 will take part in only one exchange at a time. The exchange procedure releases the serializer only after the exchange has completed. So both exchage processes will be serialzed, and the account balances will be $10,$20 or $30 in whatever order.
;; Similar reasoning applies to the sum of the account balances.


sicp exercise 3.42



;; Exercise 3.42.  Ben Bitdiddle suggests that it's a waste of time to create a new serialized procedure in response to every withdraw and deposit message. He says that make-account could be changed so that the calls to protected are done outside the dispatch procedure. That is, an account would return the same serialized procedure (which was created at the same time as the account) each time it is asked for a withdrawal procedure.

(define (make-account balance)
  (define (withdraw amount)
    (if (>= balance amount)
        (begin (set! balance (- balance amount))
               balance)
        "Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount))
    balance)
  (let ((protected (make-serializer)))
    (let ((protected-withdraw (protected withdraw))
          (protected-deposit (protected deposit)))
      (define (dispatch m)
        (cond ((eq? m 'withdraw) protected-withdraw)
              ((eq? m 'deposit) protected-deposit)
              ((eq? m 'balance) balance)
              (else (error "Unknown request -- MAKE-ACCOUNT"
                           m))))
      dispatch)))

;; Is this a safe change to make? In particular, is there any difference in what concurrency is allowed by these two versions of make-account ?

;; Ans:

;; Yes, this is a safe change to make. There is no difference in concurrency in two versions.


sicp exercise 3.41


;; Exercise 3.41.  Ben Bitdiddle worries that it would be better to implement the bank account as follows (where the commented line has been changed):

(define (make-account balance)
  (define (withdraw amount)
    (if (>= balance amount)
        (begin (set! balance (- balance amount))
               balance)
        "Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount))
    balance)
  ;; continued on next page

  (let ((protected (make-serializer)))
    (define (dispatch m)
      (cond ((eq? m 'withdraw) (protected withdraw))
            ((eq? m 'deposit) (protected deposit))
            ((eq? m 'balance)
             ((protected (lambda () balance)))) ; serialized
            (else (error "Unknown request -- MAKE-ACCOUNT"
                         m))))
    dispatch))

;; because allowing unserialized access to the bank balance can result in anomalous behavior. Do you agree? Is there any scenario that demonstrates Ben's concern?


;; Ans:
;; The message 'balance only reads the current value, it has no effect on the behavior of 'withdraw or 'deposit.

sicp exercise 3.40


;; Exercise 3.40.  Give all possible values of x that can result from executing

;; (define x 10)

;; (parallel-execute (lambda () (set! x (* x x)))
;;                   (lambda () (set! x (* x x x))))

;; Which of these possibilities remain if we instead use serialized procedures:

;; (define x 10)

;; (define s (make-serializer))

;; (parallel-execute (s (lambda () (set! x (* x x))))
;;                   (s (lambda () (set! x (* x x x)))))

(use-modules (ice-9 threads))

(define (make-serializer)
  (let ((mutex (make-mutex)))
    (lambda (p)
      (define (serialized-p . args)
        (lock-mutex mutex)
        (let ((val (apply p args)))
          (unlock-mutex mutex)
          val))
      serialized-p)))

(define x 10)

(parallel ((lambda () (set! x (* x x))))
          ((lambda () (set! x (* x x x)))))
(display x) (newline)
;; x can be set to 100, 1000, 10000, 100000, 1000000


(define x 10)

(define s (make-serializer))

(parallel ((s (lambda () (set! x (* x x)))))
          ((s (lambda () (set! x (* x x x))))))
(display x) (newline)
;; x is set to 1000000


sicp exercise 3.39



;; 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)))))

;; Required for (parallel) on Guile
(use-modules (ice-9 threads))

;; Following is the version of (make-serializer) on Guile
(define (make-serializer)
  (let ((mutex (make-mutex)))
    (lambda (p)
      (define (serialized-p . args)
        (lock-mutex mutex)
        (let ((val (apply p args)))
          (unlock-mutex mutex)
          val))
      serialized-p)))

(define x 10)

(define s (make-serializer))

(parallel ((lambda () (set! x ((s (lambda () (* x x)))))))
          ((s (lambda () (set! x (+ x 1))))))
(display x) (newline)
;; Evaluates to 101
;; But if the order is swapped, the output is changed

(set! x 10)
(parallel  ((s (lambda () (set! x (+ x 1)))))
           ((lambda () (set! x ((s (lambda () (* x x))))))))

(display x) (newline)
;; Evaluates to 121

;; Ans:
;; theoretical possibiities are : 121, 100, 101



Wednesday, March 17, 2010

sicp exercise 3.38



;; Exercise 3.38.  Suppose that Peter, Paul, and Mary share a joint bank account that initially contains $100. Concurrently, Peter deposits $10, Paul withdraws $20, and Mary withdraws half the money in the account, by executing the following commands:
;; Peter:        (set! balance (+ balance 10))
;; Paul:        (set! balance (- balance 20))
;; Mary:        (set! balance (- balance (/ balance 2)))

;; a. List all the different possible values for balance after these three transactions have been completed, assuming that the banking system forces the three processes to run sequentially in some order.

;; b. What are some other values that could be produced if the system allows the processes to be interleaved? Draw timing diagrams like the one in figure 3.29 to explain how these values can occur.

;; Ans: a.
;; Peter->Paul->Mary 45
;; Peter->Mary->Paul 35
;; Paul->Peter->Mary 45
;; Paul->Mary->Peter 50
;; Mary->Peter->Paul 40
;; Mary->Paul->Peter 40

;;Ans: b.
;; If interleving is allowed, many possibilities exist because one command can change the value read by other commands in between second command's operation.
;; e.g. the 'balance' can be written by Paul in between two reads by Mary.
;; skipping the timing diagrams

Monday, March 15, 2010

sicp exercise 3.37


;; Exercise 3.37.  The celsius-fahrenheit-converter procedure is cumbersome when compared with a more expression-oriented style of definition, such as

;; (define (celsius-fahrenheit-converter x)
;;   (c+ (c* (c/ (cv 9) (cv 5))
;;           x)
;;       (cv 32)))
;; (define C (make-connector))
;; (define F (celsius-fahrenheit-converter C))
;;
;; Here c+, c*, etc. are the ``constraint'' versions of the arithmetic operations. For example, c+ takes two connectors as arguments and returns a connector that is related to these by an adder constraint:
;;
;; (define (c+ x y)
;;   (let ((z (make-connector)))
;;     (adder x y z)
;;     z))
;;
;; Define analogous procedures c-, c*, c/, and cv (constant value) that enable us to define compound constraints as in the converter example above.33

(define (c+ x y)
  (let ((z (make-connector)))
    (adder x y z)
    z))

(define (c- x y)
  (let ((z (make-connector)))
    (adder z y x)
    z))

(define (c* x y)
  (let ((z (make-connector)))
    (multiplier x y z)
    z))

(define (c/ x y)
  (let ((z (make-connector)))
    (multiplier z y x)
    z))

(define (cv x)
  (let ((z (make-connector)))
    (constant x z)
    z))


sicp exercise 3.36


;; Exercise 3.36.  Suppose we evaluate the following sequence of expressions in the global environment:

;; (define a (make-connector))
;; (define b (make-connector))
;; (set-value! a 10 'user)

;; At some time during evaluation of the set-value!, the following expression from the connector's local procedure is evaluated:

;; (for-each-except setter inform-about-value constraints)

;; Draw an environment diagram showing the environment in which the above expression is evaluated.

;; Ans:
;; The environment is the environment which is created after evaluating (define a (make-connector)) in the global environment.



sicp exercise 3.35



;; Exercise 3.35.  Ben Bitdiddle tells Louis that one way to avoid the trouble in exercise 3.34 is to define a squarer as a new primitive constraint. Fill in the missing portions in Ben's outline for a procedure to implement such a constraint:

;; (define (squarer a b)
;;   (define (process-new-value)
;;     (if (has-value? b)
;;         (if (< (get-value b) 0)
;;             (error "square less than 0 -- SQUARER" (get-value b))
;;             <alternative1>)
;;         <alternative2>))
;;   (define (process-forget-value) <body1>)
;;   (define (me request) <body2>)
;;   <rest of definition>
;;   me)


(define false #f)
(define true  #t)

(define (inform-about-value constraint)
  (constraint 'I-have-a-value))
(define (inform-about-no-value constraint)
  (constraint 'I-lost-my-value))


(define (constant value connector)
  (define (me request)
    (error "Unknown request -- CONSTANT" request))
  (connect connector me)
  (set-value! connector value me)
  me)

(define (probe name connector)
  (define (print-probe value)
    (display "Probe: ")
    (display name)
    (display " = ")
    (display value)
    (newline))
  (define (process-new-value)
    (print-probe (get-value connector)))
  (define (process-forget-value)
    (print-probe "?"))
  (define (me request)
    (cond ((eq? request 'I-have-a-value)
           (process-new-value))
          ((eq? request 'I-lost-my-value)
           (process-forget-value))
          (else
           (error "Unknown request -- PROBE" request))))
  (connect connector me)
  me)


(define (make-connector)
  (let ((value false) (informant false) (constraints '()))
    (define (set-my-value newval setter)
      (cond ((not (has-value? me))
             (set! value newval)
             (set! informant setter)
             (for-each-except setter
                              inform-about-value
                              constraints))
            ((not (= value newval))
             (error "Contradiction" (list value newval)))
            (else 'ignored)))
    (define (forget-my-value retractor)
      (if (eq? retractor informant)
          (begin (set! informant false)
                 (for-each-except retractor
                                  inform-about-no-value
                                  constraints))
          'ignored))
    (define (connect new-constraint)
      (if (not (memq new-constraint constraints))
          (set! constraints
                (cons new-constraint constraints)))
      (if (has-value? me)
          (inform-about-value new-constraint))
      'done)
    (define (me request)
      (cond ((eq? request 'has-value?)
             (if informant true false))
            ((eq? request 'value) value)
            ((eq? request 'set-value!) set-my-value)
            ((eq? request 'forget) forget-my-value)
            ((eq? request 'connect) connect)
            (else (error "Unknown operation -- CONNECTOR"
                         request))))
    me))

(define (for-each-except exception procedure list)
  (define (loop items)
    (cond ((null? items) 'done)
          ((eq? (car items) exception) (loop (cdr items)))
          (else (procedure (car items))
                (loop (cdr items)))))
  (loop list))

(define (has-value? connector)
  (connector 'has-value?))
(define (get-value connector)
  (connector 'value))
(define (set-value! connector new-value informant)
  ((connector 'set-value!) new-value informant))
(define (forget-value! connector retractor)
  ((connector 'forget) retractor))
(define (connect connector new-constraint)
  ((connector 'connect) new-constraint))

;;--------------------------------------------------

;; here we must use exercise 1.7 to find square roots
(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x)
                 x)))

(define (improve guess x)
  (average guess (/ x guess)))

(define (average x y)
  (/ (+ x y) 2))

(define (square x) (* x x))

(define (good-enough? guess x)
  (< (/ (abs (- (square guess) x)) x) 0.00001))

(define (sqrt x)
  (sqrt-iter 1.0 x))

;;--------------------------------------------------

(define (squarer a b)
  (define (process-new-value)
    (cond ((has-value? b)
           (if (< (get-value b) 0)
            (error "square less than 0 -- SQUARER" (get-value b))
            (set-value! a (sqrt (get-value b)) me)))
          ((has-value? a)
           (set-value! b (square (get-value a)) me))))
  (define (process-forget-value)
    (forget-value! a me)
    (forget-value! b me)
    (process-new-value))
  (define (me request)
    (cond ((eq? request 'I-have-a-value) 
           (process-new-value))
          ((eq? request 'I-lost-my-value)
           (process-forget-value))
          (else
           (error "Unknown request -- SQUARER" request))))
  (connect a me)
  (connect b me)
  me)


(define a (make-connector))   
(define b (make-connector))   

(probe "A" a)
(probe "B" b)

(squarer a b)

;(set-value! a 30 'user)
(set-value! b 9 'user)

sicp exercise 3.34


;; Exercise 3.34.  Louis Reasoner wants to build a squarer, a constraint device with two terminals such that the value of connector b on the second terminal will always be the square of the value a on the first terminal. He proposes the following simple device made from a multiplier:

;; (define (squarer a b)
;;   (multiplier a a b))

;;   There is a serious flaw in this idea. Explain.

;; Ans:
;; In this scheme, squarer uses multiplier. multiplier needs two terminals to be specified in order to deduce the third. so to duduce the value of 'a', we need to specify 'a'.
;; Now i understand why square is a basic mathematical operation. otherwise finding square-roots would have been so easy.

sicp exercise 3.33


;; Exercise 3.33.  Using primitive multiplier, adder, and constant constraints, define a procedure averager that takes three connectors a, b, and c as inputs and establishes the constraint that the value of c is the average of the values of a and b.

(define false #f)
(define true  #t)

(define (adder a1 a2 sum)
  (define (process-new-value)
    (cond ((and (has-value? a1) (has-value? a2))
           (set-value! sum
                       (+ (get-value a1) (get-value a2))
                       me))
          ((and (has-value? a1) (has-value? sum))
           (set-value! a2
                       (- (get-value sum) (get-value a1))
                       me))
          ((and (has-value? a2) (has-value? sum))
           (set-value! a1
                       (- (get-value sum) (get-value a2))
                       me))))
  (define (process-forget-value)
    (forget-value! sum me)
    (forget-value! a1 me)
    (forget-value! a2 me)
    (process-new-value))
  (define (me request)
    (cond ((eq? request 'I-have-a-value) 
           (process-new-value))
          ((eq? request 'I-lost-my-value)
           (process-forget-value))
          (else
           (error "Unknown request -- ADDER" request))))
  (connect a1 me)
  (connect a2 me)
  (connect sum me)
  me)

(define (inform-about-value constraint)
  (constraint 'I-have-a-value))
(define (inform-about-no-value constraint)
  (constraint 'I-lost-my-value))

(define (multiplier m1 m2 product)
  (define (process-new-value)
    (cond ((or (and (has-value? m1) (= (get-value m1) 0))
               (and (has-value? m2) (= (get-value m2) 0)))
           (set-value! product 0 me))
          ((and (has-value? m1) (has-value? m2))
           (set-value! product
                       (* (get-value m1) (get-value m2))
                       me))
          ((and (has-value? product) (has-value? m1))
           (set-value! m2
                       (/ (get-value product) (get-value m1))
                       me))
          ((and (has-value? product) (has-value? m2))
           (set-value! m1
                       (/ (get-value product) (get-value m2))
                       me))))
  (define (process-forget-value)
    (forget-value! product me)
    (forget-value! m1 me)
    (forget-value! m2 me)
    (process-new-value))
  (define (me request)
    (cond ((eq? request 'I-have-a-value)
           (process-new-value))
          ((eq? request 'I-lost-my-value)
           (process-forget-value))
          (else
           (error "Unknown request -- MULTIPLIER" request))))
  (connect m1 me)
  (connect m2 me)
  (connect product me)
  me)

(define (constant value connector)
  (define (me request)
    (error "Unknown request -- CONSTANT" request))
  (connect connector me)
  (set-value! connector value me)
  me)

(define (probe name connector)
  (define (print-probe value)
    (display "Probe: ")
    (display name)
    (display " = ")
    (display value)
    (newline))
  (define (process-new-value)
    (print-probe (get-value connector)))
  (define (process-forget-value)
    (print-probe "?"))
  (define (me request)
    (cond ((eq? request 'I-have-a-value)
           (process-new-value))
          ((eq? request 'I-lost-my-value)
           (process-forget-value))
          (else
           (error "Unknown request -- PROBE" request))))
  (connect connector me)
  me)


(define (make-connector)
  (let ((value false) (informant false) (constraints '()))
    (define (set-my-value newval setter)
      (cond ((not (has-value? me))
             (set! value newval)
             (set! informant setter)
             (for-each-except setter
                              inform-about-value
                              constraints))
            ((not (= value newval))
             (error "Contradiction" (list value newval)))
            (else 'ignored)))
    (define (forget-my-value retractor)
      (if (eq? retractor informant)
          (begin (set! informant false)
                 (for-each-except retractor
                                  inform-about-no-value
                                  constraints))
          'ignored))
    (define (connect new-constraint)
      (if (not (memq new-constraint constraints))
          (set! constraints
                (cons new-constraint constraints)))
      (if (has-value? me)
          (inform-about-value new-constraint))
      'done)
    (define (me request)
      (cond ((eq? request 'has-value?)
             (if informant true false))
            ((eq? request 'value) value)
            ((eq? request 'set-value!) set-my-value)
            ((eq? request 'forget) forget-my-value)
            ((eq? request 'connect) connect)
            (else (error "Unknown operation -- CONNECTOR"
                         request))))
    me))

(define (for-each-except exception procedure list)
  (define (loop items)
    (cond ((null? items) 'done)
          ((eq? (car items) exception) (loop (cdr items)))
          (else (procedure (car items))
                (loop (cdr items)))))
  (loop list))

(define (has-value? connector)
  (connector 'has-value?))
(define (get-value connector)
  (connector 'value))
(define (set-value! connector new-value informant)
  ((connector 'set-value!) new-value informant))
(define (forget-value! connector retractor)
  ((connector 'forget) retractor))
(define (connect connector new-constraint)
  ((connector 'connect) new-constraint))

;;--------------------------------------------------

(define (averager a b c)
  (let ((u (make-connector))
        (w (make-connector)))
    (multiplier c w u)
    (adder a b u)
    (constant 2 w)))

(define C (make-connector))
(define a (make-connector))   
(define b (make-connector))   

(probe "C" C)
(probe "A" a)
(probe "B" b)

(averager a b C)

(set-value! a 30 'user)
(set-value! b 10 'user)
;(set-value! C 20 'user)