SICP

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))))) SOLUTION When there is no serialization: 1000000: P1 executes fully first, then P2 executes 1000000: P2 executes fully first, then P1 executes 10000: P2 changes x from 10 to 1000 between th...

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 t...

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. SOLUTION The diagrams are here: Page 1 , Page 2 and Page 3 .

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) t...

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. SOLUTION The progressive environment diagrams are here .

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...

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. EXPLANATION The code is here . See tests in the code link above. After creating the squarer, when we set the value of 'a', 'b' is set correctly to  be the square of a. However, the reverse does not work. When b is set, a does not change. So the  non-directionality of computation that we expect from constraint-based systems is not there. The reason for this can be seen by looking at the logic of the procedure "process-new-value" in  the multiplier. This procedure expects two of the multiplier's three pieces of data (m1,...

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 . SOLUTION The code is here . The picture below shows how the constraints and connectors are assembled:

Exercise 3.32.   The procedures to be run during each time segment of the agenda are kept in a queue. Thus, the procedures for each segment are called in the order in which they were added to the agenda (first in, first out). Explain why this order must be used. In particular, trace the behavior of an and-gate whose inputs change from 0,1 to 1,0 in the same segment and say how the behavior would differ if we stored a segment's procedures in an ordinary list, adding and removing procedures only at the front (last in, first out). SOLUTION The code is here . EXPLANATION Let us look more closely at the logic of how action-procedures run. The call sequence is: action-proc --> after-delay --> add-to-agenda The action-proc first computes the new value *to be set* on the output wire, and this new value  becomes available to the lambda function that is constructed and passed to after-delay. after-delay adds the delay to the current agenda time and passes this com...

Exercise 3.31.     The internal procedure  accept-action-procedure!  defined in  make-wire  specifies that when a new action procedure is added to a wire, the procedure is immediately run. Explain why this initialization is necessary. In particular, trace through the half-adder example in the paragraphs above and say how the system's response would differ if we had defined  accept-action-procedure!  as (define (accept-action-procedure! proc)   (set! action-procedures (cons proc action-procedures))) SOLUTION The code is here . EXPLANATION This program contains the complete implementation of the agenda operations and the after-delay  proc as explained in the SICP text. The test results below show the behavior of the simulator  in both cases: 1. When action procedures are run immediately after they are added to wires 2. When they are not run immediately after they are added to wires...

Exercise 3.30.   Figure  3.27  shows a  ripple-carry adder  formed by stringing together  n  full-adders. This is the simplest form of parallel adder for adding two  n -bit binary numbers. The inputs A 1 , A 2 , A 3 ,  ... , A n  and B 1 , B 2 , B 3 ,  ... , B n  are the two binary numbers to be added (each A k  and B k  is a 0 or a 1). The circuit generates S 1 , S 2 , S 3 ,  ... , S n , the  n  bits of the sum, and C, the carry from the addition. Write a procedure  ripple-carry-adder  that generates this circuit. The procedure should take as arguments three lists of  n  wires each -- the A k , the B k , and the S k  -- and also another wire C. The major drawback of the ripple-carry adder is the need to wait for the carry signals to propagate. What is the delay needed to obtain the complete output from an  n -bit ripple-carry adder, expressed in terms of the delays f...

Exercise 3.29.    Another way to construct an or-gate is as a compound digital logic device, built from and-gates and inverters. Define a procedure  or-gate  that accomplishes this. What is the delay time of the or-gate in terms of  and-gate-delay  and  inverter-delay ? SOLUTION The code is here . Note: I made an enhancement to all the function procedures such as and-gate, or-gate etc. to  call the action procedure once as soon as the gate is constructed. This way we ensure that  the output of the gate is correct right from the beginning. (OR A B) = (NOT (AND (NOT A) (NOT B))) Delay time of the compound-or-gate = (3 * inverter-delay) + (and-gate-delay)

Exercise 3.28.    Define an or-gate as a primitive function box. Your  or-gate  constructor should be similar to  and-gate . SOLUTION The code is here . Note: I enhanced the or-action-procedure (from the and-action-procedure in the textbook) to call set! on the output wire only if the set! will change the signal on the wire. 

Exercise 3.27.    Memoization  (also called  tabulation ) is a technique that enables a procedure to record, in a local table, values that have previously been computed. This technique can make a vast difference in the performance of a program. A memoized procedure maintains a table in which values of previous calls are stored using as keys the arguments that produced the values. When the memoized procedure is asked to compute a value, it first checks the table to see if the value is already there and, if so, just returns that value. Otherwise, it computes the new value in the ordinary way and stores this in the table. As an example of memoization, recall from section  1.2.2  the exponential process for computing Fibonacci numbers: (define (fib n)   (cond ((= n 0) 0)         ((= n 1) 1)         (else (+ (fib...

Exercise 3.26.    To search a table as implemented above, one needs to scan through the list of records. This is basically the unordered list representation of section  2.3.3 . For large tables, it may be more efficient to structure the table in a different manner. Describe a table implementation where the (key, value) records are organized using a binary tree, assuming that keys can be ordered in some way (e.g., numerically or alphabetically). (Compare exercise  2.66  of chapter 2.) SOLUTION The code and tests are here . This took more time than I expected probably because of the number of interruptions I had to handle while working on this problem. My approach was to replace the list data structure from the previous exercise with a binary tree. This was not straightforward because in the previous (Exercise 3.25) implementation there is no clean separation between the procedure "make-table" and the list data structure that it uses. Operati...