SICP

Exercise 3.60.    With power series represented as streams of coefficients as in exercise  3.59 , adding series is implemented by  add-streams . Complete the definition of the following procedure for multiplying series: (define (mul-series s1 s2)   (cons-stream < ?? > (add-streams < ?? > < ?? >))) You can test your procedure by verifying that  s i n 2   x  +  c o s 2   x  = 1, using the series from exercise  3.59 . SOLUTION Logic used in mul-series: (a0 + a1x + a2x^2 + a3x^3 + ...) * (b0 + b1x + b2x^2 + b3x^3 + ...) is: (a0 * b0) + {a0 * (b1x + b2x^2 + b3x^3 + ...)} + {b0 * (a1x + a2x^2 + a3x^3 + ...)} + {(a1x + a2x^2 + a3x^3 + ...) * (b1x + b2x^2 + b3x^3 + ...)} The coefficients after multiplying the two series above will be: Variable | Coefficient ------------------------------- x^0 | a0*b0 x^1 | a0*b1 + a1*b0 x^2 | a0*b2 + a1*b1 ...

Exercise 3.59.    In section  2.5.3  we saw how to implement a polynomial arithmetic system representing polynomials as lists of terms. In a similar way, we can work with  power series , such as represented as infinite streams. We will represent the series  a 0  +  a 1   x  +  a 2   x 2  +  a 3   x 3  +  ···  as the stream whose elements are the coefficients  a 0 ,  a 1 ,  a 2 ,  a 3 ,  ... . a. The integral of the series  a 0  +  a 1   x  +  a 2   x 2  +  a 3   x 3  +  ···  is the series where  c  is any constant. Define a procedure  integrate-series  that takes as input a stream  a 0 ,  a 1 ,  a 2 ,  ... representing a power series and returns the stream  a 0 , (1/2) a 1 , (1/3) a 2 ,  ...  of coefficients of the non-constant terms o...

Exercise 3.58.   Give an interpretation of the stream computed by the following procedure: (define (expand num den radix)   (cons-stream    (quotient (* num radix) den)    (expand (remainder (* num radix) den) den radix))) ( Quotient  is a primitive that returns the integer quotient of two integers.) What are the successive elements produced by  (expand 1 7 10)  ? What is produced by  (expand 3 8 10)  ? SOLUTION The code and tests are here . EXPLANATION (expand 1 7 10) produces: 1, 4, 2, 8, 5, 7, 1, 4, 2, 8, 5, 7, 1, 4 ... (expand 3 8 10) produces 3, 7, 5, 0, 0, 0, 0 ...

Exercise 3.57.    How many additions are performed when we compute the  n th Fibonacci number using the definition of  fibs  based on the  add-streams  procedure? Show that the number of additions would be exponentially greater if we had implemented  (delay < exp >)  simply as  (lambda () < exp >) , without using the optimization provided by the  memo-proc  procedure described in section  3.5.1 . 64 SOLUTION The Racket code and explanation is here . The Scheme code and tests are here . EXPLANATION (define fibs (stream-cons 0 (stream-cons 1 (add-streams (stream-rest fibs) fibs) ) ) ) Number of additions performed: 0th Fibonacci number (0): 0 additions 1st Fibonacci number (1): 0 additions 2nd Fibonacci number (1): 1 addition 3rd Fibonacci number (2): 2 additions 4th Fibonacci number (3): 3 additions As we can see above, for every higher Fibonacci number, one additional ...

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

Exercise 3.55.   Define a procedure  partial-sums  that takes as argument a stream  S  and returns the stream whose elements are  S 0 ,  S 0  +  S 1 ,  S 0  +  S 1  +  S 2 ,  ... . For example,  (partial-sums integers)  should be the stream 1, 3, 6, 10, 15,  ... . SOLUTION The code and tests are here .

Exercise 3.54.   Define a procedure  mul-streams , analogous to  add-streams , that produces the elementwise product of its two input streams. Use this together with the stream of  integers  to complete the following definition of the stream whose  n th element (counting from 0) is  n  + 1 factorial: (define factorials (cons-stream 1 (mul-streams < ?? > < ?? >))) SOLUTION The code and tests are here .

Exercise 3.53.   Without running the program, describe the elements of the stream defined by (define s (cons-stream 1 (add-streams s s))) SOLUTION The explanation and tests are here . EXPLANATION (add-streams s s) produces a stream the first element of which is 1 + 1 = 2. So s produces: 1, 2 ... The next element in the stream will be the addition of the next element of s with itself i.e. 2 + 2 = 4. So s will be 1, 2, 4 ... So the elements of s will be: 1, 2, 4, 8, 16, 32 ...

Exercise 3.52.    Consider the sequence of expressions (define sum 0) (define (accum x)   (set! sum (+ x sum))   sum) (define seq (stream-map accum (stream-enumerate-interval 1 20))) (define y (stream-filter even? seq)) (define z (stream-filter (lambda (x) (= (remainder x 5) 0))                          seq)) (stream-ref y 7) (display-stream z) What is the value of  sum  after each of the above expressions is evaluated? What is the printed response to evaluating the  stream-ref  and  display-stream  expressions? Would these responses differ if we had implemented  (delay < exp >) simply as  (lambda () < exp >)  without usi...

Exercise 3.51.    In order to take a closer look at delayed evaluation, we will use the following procedure, which simply returns its argument after printing it: (define (show x)   (display-line x)   x) What does the interpreter print in response to evaluating each expression in the following sequence? 59 (define x (stream-map show (stream-enumerate-interval 0 10))) (stream-ref x 5) (stream-ref x 7) SOLUTION The code and tests are here . Note: I spent a lot of time tracing through the logic to see what really happens here. The delayed evaluation of items in streams combined with new streams being produced in procedure stream-map makes it really confusing.  Also, note that in Racket, both the car part and the cdr part of the stream are delayed evaluations until the point of need.

Exercise 3.50.   Complete the following definition, which generalizes  stream-map  to allow procedures that take multiple arguments, analogous to  map  in section  2.2.3 , footnote  12 . (define (stream-map proc . argstreams)   (if (< ?? > (car argstreams))       the-empty-stream       (< ?? >        (apply proc (map < ?? > argstreams))        (apply stream-map               (cons proc (map < ?? > argstreams)))))) SOLUTION The code and tests are here .

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.) EXPLANATION Consider the case where we have two bank branches in different locations and an account can be accessed  at each branch. For fast local access, we allow withdrawals and deposits at each location and design  a way to keep the account balance at both locations synchronized. Concurrent processes can access and change  the balance in either location. In order to keep the balance the same in both locations, we write a procedure  similar to 'synchronized-exchange' but which first updates the local balance and then the remote balance. This  procedure acquires a lock on the local account...

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.) SOLUTION The code and tests are here . Explanation: I run four tests here: Test 1: Main thread runs serialized-exchange. There is no concurrency. So it just works. Test 2: Two threads run serialized-exchange in parallel with opposite account orders. In this case  the first thread almost always acquires both the accounts before the 2nd thread tries to acquire account 2.  So again, thread 1 is able to complete the exchange and thread 2 starts its work only after that. So  even though a deadlock is the...