SICP Section 3.5 Streams

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))))))
Answer:
(define (stream-map proc . argstreams) (if (stream-null? (car argstreams)) the-empty-stream (cons-stream (apply proc (map stream-car argstreams)) (apply stream-map (cons proc (map stream-cdr argstreams))))))
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?
(define x (stream-map show (stream-enumerate-interval 0 10))) (stream-ref x 5) (stream-ref x 7)
Answer:
(define x (stream-map show (stream-enumerate-interval 0 10))) ;; prints 0 (stream-ref x 5) ;; Prints 1, 2, 3, 4 and 5 separated by newlines. (stream-ref x 7) ;; Prints 6, 7
(stream-ref x 7) does not print 1 through 5 as show is not invoked thanks to memo-proc. Instead the stored results from previous invocations is reused.

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 using the optimization provided by memo-proc ? Explain.

Answer:
(define seq (stream-map accum (stream-enumerate-interval 1 20))) ;; Sum becomes 1 (define y (stream-filter even? seq)) ;; Sum becomes 6 (define z (stream-filter (lambda (x) (= (remainder x 5) 0)) seq)) ;; Sum becomes 10 (stream-ref y 7) ;; Prints 136 ;; Sum becomes 136 (display-stream z) ;; Prints 10, 15, 45, 55, 105, 120, 190, 210 ;; Sum becomes 210
Without memo-proc:
;; (define y (stream-filter even? seq)) Sum becomes 6 (define z (stream-filter (lambda (x) (= (remainder x 5) 0)) seq)) ;; Sum becomes 15 (6 +2 +3 +4) (stream-ref y 7) ;; Prints 162 ;; Sum becomes 162 (15 +4 +5 +6 +... +17) (display-stream z) ;; Prints 15, 180, 230, 305 ;; Sum becomes 362
Exercise 3.53. Without running the program, describe the elements of the stream defined by
(define s (cons-stream 1 (add-streams s s)))
Answer: This is the stream 1, 2, 4, 8, 16, 32, 64 etc. It represents the powers of 2: 2⁰, 2¹, 2², 2³, 2⁴ etc.

The very first value is 1, the hard-coded start value for s. Subsequent elements are created by invoking add-streams. Add-streams creates a new stream whose car is the result of adding the car of its argument streams. The very first time around this yields 1 + 1 = 2. As the stream is defined self-referentially, the car of s becomes 2 following the first call to add-streams. subsequent calls to add-streams causes addition of 2 and 2, yielding 4; 4 and 4 yielding 8 and so on.

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 nth element (counting from 0) is n + 1 factorial:
(define factorials (cons-stream 1 (mul-streams <??> <??>)))
Answer:
(define (mul-streams s1 s2) (stream-map * s1 s2)) (define factorials (cons-stream 1 (mul-streams factorials (integers-starting-from 2))))
Exercise 3.55. Define a procedure partial-sums that takes as argument a stream S and returns the stream whose elements are S0, S0 + S1, S0 + S1 + S2, .... For example, (partial-sums integers) should be the stream 1, 3, 6, 10, 15, ....

Answer: This is an interesting exercise. As with many other exercises related to Streams it becomes easier if the solution is initially worked out on paper. In this case, the key to the solution is realizing that partial sum at any point is the sum of the partial sum up to that point and the element at the point. This yields the following self-referential definition:
(define (partial-sums stream) (cons-stream (stream-car stream) (add-streams (partial-sums stream) (stream-cdr stream))))
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 (merge s1 s2) (cond ((stream-null? s1) s2) ((stream-null? s2) s1) (else (let ((s1car (stream-car s1)) (s2car (stream-car s2))) (cond ((< s1car s2car) (cons-stream s1car (merge (stream-cdr s1) s2))) ((> s1car s2car) (cons-stream s2car (merge s1 (stream-cdr s2)))) (else (cons-stream s1car (merge (stream-cdr s1) (stream-cdr s2)))))))))
Then the required stream may be constructed with merge, as follows:
(define S (cons-stream 1 (merge <??> <??>)))
Fill in the missing expressions in the places marked <??> above.

Answer:
(define (merge s1 s2) (cond ((stream-null? s1) s2) ((stream-null? s2) s1) (else (let ((s1car (stream-car s1)) (s2car (stream-car s2))) (cond ((< s1car s2car) (cons-stream s1car (merge (stream-cdr s1) s2))) ((> s1car s2car) (cons-stream s2car (merge s1 (stream-cdr s2)))) (else (cons-stream s1car (merge (stream-cdr s1) (stream-cdr s2))))))))) (define S (cons-stream 1 (merge (merge (scale-stream S 2) (scale-stream S 3)) (scale-stream S 5))))
Exercise 3.57. How many additions are performed when we compute the nth 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 ) simply as (lambda () ), without using the optimization provided by the memo-proc procedure described in section 3.5.1.64

Answer: First, let us define the Fibonacci series as a stream.
(define fibs (cons-stream 0 (cons-stream 1 (add-streams (stream-cdr fibs) fibs))))
Tracing the flow on paper reveals that n-2 additions are required to calculate the nth Fibonacci number (counting n from 1).

Without memo-proc, each call to (stream-cdr fibs) would calculate the series from the beginning up to that point. This would exponentially increase the number of additions performed.

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

Answer: This procedure produces the series of digits after the decimal point from the result of long division of the numerator (num) by the denominator (den) using the given radix base.

(expand 1 7 10) produces a series whose first six elements are 1, 4, 2, 8, 5 and 7. The rest of the elements is a repetition of these six. (1/7 = 0.1428571428...)

(expand 3 8 10) produces a series whose first three elements are 3, 7 and 5. The rest of the elements are all 0. (3/8 = 0.3750000...)

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 a0 + a1 x + a2 x² + a3 x³ + ··· as the stream whose elements are the coefficients a0, a1, a2, a3, ....

a. The integral of the series a0 + a1 x + a2 x² + a3 x³ + ··· is the series



where c is any constant. Define a procedure integrate-series that takes as input a stream a0, a1, a2, ... representing a power series and returns the stream a0, (1/2)a1, (1/3)a2, ... of coefficients of the non-constant terms of the integral of the series. (Since the result has no constant term, it doesn't represent a power series; when we use integrate-series, we will cons on the appropriate constant.)

b. The function x |--> e^x is its own derivative. This implies that ex and the integral of ex are the same series, except for the constant term, which is e0 = 1. Accordingly, we can generate the series for e^x as
(define exp-series (cons-stream 1 (integrate-series exp-series)))
Show how to generate the series for sine and cosine, starting from the facts that the derivative of sine is cosine and the derivative of cosine is the negative of sine:
(define cosine-series (cons-stream 1 <??>)) (define sine-series (cons-stream 0 <??>))
Answer:
;; a. (define (integrate-series s) (stream-map / s integers)) ;; b. (define exp-series (cons-stream 1 (integrate-series exp-series))) (define cosine-series (cons-stream 1 (integrate-series (scale-stream sine-series -1)))) (define sine-series (cons-stream 0 (integrate-series cosine-series)))
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 sin2 x + cos2 x = 1, using the series from exercise 3.59.

Answer:
(define (mul-series s1 s2) (cons-stream (* (stream-car s1) (stream-car s2)) (add-streams (scale-stream (stream-cdr s2) (stream-car s1)) (mul-series (stream-cdr s1) s2)))) (define S (add-streams (mul-series sine-series sine-series) (mul-series cosine-series cosine-series))) (map (lambda (x) (stream-ref S x)) (enumerate-interval 0 10)) (1 0 0 0 0 0 0 0 0 0 0)
Exercise 3.61. Let S be a power series (exercise 3.59) whose constant term is 1. Suppose we want to find the power series 1/S, that is, the series X such that S · X = 1. Write S = 1 + SR where SR is the part of S after the constant term. Then we can solve for X as follows:



In other words, X is the power series whose constant term is 1 and whose higher-order terms are given by the negative of SR times X. Use this idea to write a procedure invert-unit-series that computes 1/S for a power series S with constant term 1. You will need to use mul-series from exercise 3.60.

Answer:
(define (invert-unit-series s) (cons-stream 1 (mul-series (scale-stream (stream-cdr s) -1) (invert-unit-series s))))
Exercise 3.62. Use the results of exercises 3.60 and 3.61 to define a procedure div-series that divides two power series. Div-series should work for any two series, provided that the denominator series begins with a nonzero constant term. (If the denominator has a zero constant term, then div-series should signal an error.) Show how to use div-series together with the result of exercise 3.59 to generate the power series for tangent.

Answer:
(define (div-series s1 s2) (let ((constant2 (stream-car s2))) (if (= constant2 0) (error "Constant term of denominator is 0 -- DIV-SERIES" s2) (scale-stream (mul-series s1 (invert-unit-series (scale-stream s2 (/ 1 constant2)))) (/ 1 constant2))))) (define tangent-series (div-series sine-series cosine-series))
Exercise 3.63. Louis Reasoner asks why the sqrt-stream procedure was not written in the following more straightforward way, without the local variable guesses:
(define (sqrt-stream x) (cons-stream 1.0 (stream-map (lambda (guess) (sqrt-improve guess x)) (sqrt-stream x))))
Alyssa P. Hacker replies that this version of the procedure is considerably less efficient because it performs redundant computation. Explain Alyssa's answer. Would the two versions still differ in efficiency if our implementation of delay used only (lambda () <exp>) without using the optimization provided by memo-proc (section 3.5.1)?

Answer: In Louis' version all stream-cdr calls to a given square root stream executes the procedure sqrt-stream. This in turn creates a new stream object each time. Calls to sqrt-stream and subsequent creation of new stream objects are avoided by using the local variable.

The two versions would still differ in efficiency as the difference is not dependent on the use of memo-proc.

Exercise 3.64. Write a procedure stream-limit that takes as arguments a stream and a number (the tolerance). It should examine the stream until it finds two successive elements that differ in absolute value by less than the tolerance, and return the second of the two elements. Using this, we could compute square roots up to a given tolerance by
(define (sqrt x tolerance) (stream-limit (sqrt-stream x) tolerance))
Answer:
(define (stream-limit stream tolerance) (define (iter stream v1) (let ((v2 (stream-car stream))) (if (<= (abs (- v2 v1)) tolerance) v2 (iter (stream-cdr stream) v2)))) (iter (stream-cdr stream) (stream-car stream)))
Exercise 3.65. Use the series



to compute three sequences of approximations to the natural logarithm of 2, in the same way we did above for . How rapidly do these sequences converge?

Answer: We'll start by defining the summands of the log2 stream.
(define (log2-summands n) (cons-stream (/ 1.0 n) (stream-map - (log2-summands (+ n 1)))))
1. Straightforward summation using partial-sums. The value of log2 oscillates between 0.6687714031754279 and 0.7163904507944756 after 20 iterations.
(define log2-stream (partial-sums (log2-summands 1)))
2. Log2 using Euler Transformation. Value converges to 0.6932106782106783 after 10 iterations.
(define log2-stream-euler (euler-transform log2-stream))
3. Accelerated summation. Value converges to 0.6931488693329254 in 4 iterations.
(define log2-stream-accelerated (accelerated-sequence euler-transform log2-stream))
Exercise 3.66. Examine the stream (pairs integers integers). Can you make any general comments about the order in which the pairs are placed into the stream? For example, about how many pairs precede the pair (1,100)? the pair (99,100)? the pair (100,100)? (If you can make precise mathematical statements here, all the better. But feel free to give more qualitative answers if you find yourself getting bogged down.)

Answer: (1, 100) will be preceded by 197 pairs. (1, n) will be preceded by 2n-3 pairs.

(99, 100) will be preceded by 1 + 3(2^98 - 1) pairs. (n, n+1) preceded by 1 + 3(2^(n - 1) - 1) pairs.

(100, 100) will be preceded by 6 + (2^96 - 1) pairs. (n, n) will be preceded by 6 + (2^(n - 4) - 1) pairs.

Exercise 3.67. Modify the pairs procedure so that (pairs integers integers) will produce the stream of all pairs of integers (i,j) (without the condition i <= j). Hint: You will need to mix in an additional stream.

Answer:
(define (pairs-all s t) (cons-stream (list (stream-car s) (stream-car t)) (interleave (interleave (stream-map (lambda (x) (list (stream-car s) x)) (stream-cdr t)) (stream-map (lambda (x) (list x (stream-car t))) (stream-cdr s))) (pairs (stream-cdr s) (stream-cdr t)))))
Exercise 3.68. Louis Reasoner thinks that building a stream of pairs from three parts is unnecessarily complicated. Instead of separating the pair (S0,T0) from the rest of the pairs in the first row, he proposes to work with the whole first row, as follows:
(define (pairs s t) (interleave (stream-map (lambda (x) (list (stream-car s) x)) t) (pairs (stream-cdr s) (stream-cdr t))))
Does this work? Consider what happens if we evaluate (pairs integers integers) using Louis's definition of pairs.

Answer: When (pairs s t) is evaluated a call is made to stream-map and pairs (arguments for interleave). The call to pairs in turn spawns another call to pairs and so on, causing an infinite loop.

Exercise 3.69. Write a procedure triples that takes three infinite streams, S, T, and U, and produces the stream of triples (Si,Tj,Uk) such that i <= j <= k. Use triples to generate the stream of all Pythagorean triples of positive integers, i.e., the triples (i,j,k) such that i <= j and i² + j² = k².

Answer:
(define (triple s t u) (cons-stream (list (stream-car s) (stream-car t) (stream-car u)) (interleave (stream-map (lambda (x) (cons (stream-car s) x)) (stream-cdr (pairs t u))) (triple (stream-cdr s) (stream-cdr t) (stream-cdr u))))) (define py-triples (stream-filter (lambda (t) (= (+ (square (car t)) (square (cadr t))) (square (caddr t)))) (triple integers integers integers)))
Exercise 3.70. It would be nice to be able to generate streams in which the pairs appear in some useful order, rather than in the order that results from an ad hoc interleaving process. We can use a technique similar to the merge procedure of exercise 3.56, if we define a way to say that one pair of integers is ``less than'' another. One way to do this is to define a ``weighting function'' W(i,j) and stipulate that (i1,j1) is less than (i2,j2) if W(i1,j1) < W(i2,j2). Write a procedure merge-weighted that is like merge, except that merge-weighted takes an additional argument weight, which is a procedure that computes the weight of a pair, and is used to determine the order in which elements should appear in the resulting merged stream.69 Using this, generalize pairs to a procedure weighted-pairs that takes two streams, together with a procedure that computes a weighting function, and generates the stream of pairs, ordered according to weight. Use your procedure to generate

a. the stream of all pairs of positive integers (i,j) with i <= j ordered according to the sum i + j

b. the stream of all pairs of positive integers (i,j) with i <= j, where neither i nor j is divisible by 2, 3, or 5, and the pairs are ordered according to the sum 2 i + 3 j + 5 i j.

Answer:
(define (merge-weighted s1 s2 weight) (cond ((stream-null? s1) s2) ((stream-null? s2) s1) (else (let ((s1car (stream-car s1)) (s2car (stream-car s2))) (let ((w1 (weight (car s1car) (cadr s1car))) (w2 (weight (car s2car) (cadr s2car)))) (cond ((<= w1 w2) (cons-stream s1car (merge-weighted (stream-cdr s1) s2 weight))) (else (cons-stream s2car (merge-weighted s1 (stream-cdr s2) weight))))))))) (define (weighted-pairs s t weight) (cons-stream (list (stream-car s) (stream-car t)) (merge-weighted (stream-map (lambda (x) (list (stream-car s) x)) (stream-cdr t)) (weighted-pairs (stream-cdr s) (stream-cdr t) weight) weight))) ;; a (define S1 (weighted-pairs integers integers (lambda (i j) (+ i j)))) ;; b. (define S2 (stream-filter (lambda (pair) (let ((ij (* (car pair) (cadr pair)))) (and (not (= (remainder ij 2) 0)) (not (= (remainder ij 3) 0)) (not (= (remainder ij 5) 0))))) (weighted-pairs integers integers (lambda (i j) (+ (* 2 i) (* 3 j) (* 5 i j))))))
Exercise 3.71. Numbers that can be expressed as the sum of two cubes in more than one way are sometimes called Ramanujan numbers, in honor of the mathematician Srinivasa Ramanujan.70 Ordered streams of pairs provide an elegant solution to the problem of computing these numbers. To find a number that can be written as the sum of two cubes in two different ways, we need only generate the stream of pairs of integers (i,j) weighted according to the sum i³ + j³ (see exercise 3.70), then search the stream for two consecutive pairs with the same weight. Write a procedure to generate the Ramanujan numbers. The first such number is 1,729. What are the next five?

Answer:
(define (cube-weight . pair) (+ (expt (car pair) 3) (expt (cadr pair) 3))) (define ramanujan-stream (weighted-pairs integers integers cube-weight)) (define (ramanujan-numbers stream) (define (iter s1 s2) (let ((w1 (apply cube-weight (stream-car s1))) (w2 (apply cube-weight (stream-car s2)))) (if (= w1 w2) (begin (newline) (display w1))) (iter s2 (stream-cdr s2)))) (iter stream (stream-cdr stream)))
Next five after 1729 are 4104, 13832, 20683, 32832, 39312.

Exercise 3.72. In a similar way to exercise 3.71 generate a stream of all numbers that can be written as the sum of two squares in three different ways (showing how they can be so written).

Answer:
(define (square-weight . pair) (+ (square (car pair)) (square (cadr pair)))) (define square-stream (weighted-pairs integers integers square-weight)) (define (display-sum-of-squares sum . pairs) (define (display-iter pair) (display (car pair)) (display "^2") (display " + ") (display (cadr pair)) (display "^2") (display ", ")) (newline) (display sum) (display " = ") (for-each display-iter pairs)) (define (sum-of-squares stream) (define (iter s1 s2 s3) (let ((w1 (apply square-weight (stream-car s1))) (w2 (apply square-weight (stream-car s2))) (w3 (apply square-weight (stream-car s3)))) (if (= w1 w2 w3) (display-sum-of-squares w1 (stream-car s1) (stream-car s2) (stream-car s3))) (iter s2 (stream-cdr s2) (stream-cdr (stream-cdr s2))))) (iter stream (stream-cdr stream) (stream-cdr (stream-cdr stream)))) (sum-of-squares square-stream) 325 = 1^2 + 18^2, 6^2 + 17^2, 10^2 + 15^2, 425 = 5^2 + 20^2, 8^2 + 19^2, 13^2 + 16^2, ...
Exercise 3.73. v = v₀ + (1/C)₀^ti dt + R i





Figure 3.33: An RC circuit and the associated signal-flow diagram.

We can model electrical circuits using streams to represent the values of currents or voltages at a sequence of times. For instance, suppose we have an RC circuit consisting of a resistor of resistance R and a capacitor of capacitance C in series. The voltage response v of the circuit to an injected current i is determined by the formula in figure 3.33, whose structure is shown by the accompanying signal-flow diagram.

Write a procedure RC that models this circuit. RC should take as inputs the values of R, C, and dt and should return a procedure that takes as inputs a stream representing the current i and an initial value for the capacitor voltage v0 and produces as output the stream of voltages v. For example, you should be able to use RC to model an RC circuit with R = 5 ohms, C = 1 farad, and a 0.5-second time step by evaluating (define RC1 (RC 5 1 0.5)). This defines RC1 as a procedure that takes a stream representing the time sequence of currents and an initial capacitor voltage and produces the output stream of voltages.

Answer:
(define (RC R C dt) (define (proc i v0) (add-streams (scale-stream (integral i v0 dt) (/ 1 C)) (scale-stream i R))) proc)
Exercise 3.74. Alyssa P. Hacker is designing a system to process signals coming from physical sensors. One important feature she wishes to produce is a signal that describes the zero crossings of the input signal. That is, the resulting signal should be + 1 whenever the input signal changes from negative to positive, - 1 whenever the input signal changes from positive to negative, and 0 otherwise. (Assume that the sign of a 0 input is positive.) For example, a typical input signal with its associated zero-crossing signal would be

...1 2 1.5 1 0.5 -0.1 -2 -3 -2 -0.5 0.2 3 4 ...... 0 0 0 0 0 -1 0 0 0 0 1 0 0 ...

In Alyssa's system, the signal from the sensor is represented as a stream sense-data and the stream zero-crossings is the corresponding stream of zero crossings. Alyssa first writes a procedure sign-change-detector that takes two values as arguments and compares the signs of the values to produce an appropriate 0, 1, or - 1. She then constructs her zero-crossing stream as follows:
(define (make-zero-crossings input-stream last-value) (cons-stream (sign-change-detector (stream-car input-stream) last-value) (make-zero-crossings (stream-cdr input-stream) (stream-car input-stream)))) (define zero-crossings (make-zero-crossings sense-data 0))
Alyssa's boss, Eva Lu Ator, walks by and suggests that this program is approximately equivalent to the following one, which uses the generalized version of stream-map from exercise 3.50:
(define zero-crossings (stream-map sign-change-detector sense-data <expression>))
Complete the program by supplying the indicated <expression>.

Answer:
(define zero-crossings (stream-map sign-change-detector sense-data (stream-cdr sense-data)))
Exercise 3.75. Unfortunately, Alyssa's zero-crossing detector in exercise 3.74 proves to be insufficient, because the noisy signal from the sensor leads to spurious zero crossings. Lem E. Tweakit, a hardware specialist, suggests that Alyssa smooth the signal to filter out the noise before extracting the zero crossings. Alyssa takes his advice and decides to extract the zero crossings from the signal constructed by averaging each value of the sense data with the previous value. She explains the problem to her assistant, Louis Reasoner, who attempts to implement the idea, altering Alyssa's program as follows:
(define (make-zero-crossings input-stream last-value) (let ((avpt (/ (+ (stream-car input-stream) last-value) 2))) (cons-stream (sign-change-detector avpt last-value) (make-zero-crossings (stream-cdr input-stream) avpt))))
This does not correctly implement Alyssa's plan. Find the bug that Louis has installed and fix it without changing the structure of the program. (Hint: You will need to increase the number of arguments to make-zero-crossings.)

Answer: I couldn't come up with an answer. If you know the answer and can explain it, do let me know.

Exercise 3.76. Eva Lu Ator has a criticism of Louis's approach in exercise 3.75. The program he wrote is not modular, because it intermixes the operation of smoothing with the zero-crossing extraction. For example, the extractor should not have to be changed if Alyssa finds a better way to condition her input signal. Help Louis by writing a procedure smooth that takes a stream as input and produces a stream in which each element is the average of two successive input stream elements. Then use smooth as a component to implement the zero-crossing detector in a more modular style.

Answer:
(define (smooth stream) (stream-map (lambda (x y) (average x y)) (cons-stream 0 stream) stream)) (define (make-zero-crossings smoothened-stream last-avpt) (cons-stream (sign-change-detector (stream-car smoothened-stream) last-avpt) (make-zero-crossings (stream-cdr smoothened-stream) (stream-car smoothened-stream))))
Exercise 3.77. The integral procedure used above was analogous to the ``implicit'' definition of the infinite stream of integers in section 3.5.2. Alternatively, we can give a definition of integral that is more like integers-starting-from (also in section 3.5.2):
(define (integral integrand initial-value dt) (cons-stream initial-value (if (stream-null? integrand) the-empty-stream (integral (stream-cdr integrand) (+ (* dt (stream-car integrand)) initial-value) dt))))
When used in systems with loops, this procedure has the same problem as does our original version of integral. Modify the procedure so that it expects the integrand as a delayed argument and hence can be used in the solve procedure shown above.

Answer:
(define (integral delayed-integrand initial-value dt) (cons-stream initial-value (let ((integrand (force delayed-integrand))) (if (stream-null? integrand) the-empty-stream (integral (delay (stream-cdr integrand)) (+ (* dt (stream-car integrand)) initial-value) dt))))) (define (solve f y0 dt) (define y (integral (delay dy) y0 dt)) (define dy (stream-map f y)) y)
Exercise 3.78.



Figure 3.35: Signal-flow diagram for the solution to a second-order linear differential equation.

Consider the problem of designing a signal-processing system to study the homogeneous second-order linear differential equation



The output stream, modeling y, is generated by a network that contains a loop. This is because the value of d²y/dt² depends upon the values of y and dy/dt and both of these are determined by integrating d²y/dt². The diagram we would like to encode is shown in figure 3.35. Write a procedure solve-2nd that takes as arguments the constants a, b, and dt and the initial values y₀ and dy₀ for y and dy/dt and generates the stream of successive values of y.

Answer:
(define (solve-2nd a b dt y0 dy0) (define y (integral (delay dy) y0 dt)) (define dy (integral (delay ddy) dy0 dt)) (define ddy (add-streams (scale-stream dy a) (scale-stream y b))) y)
Exercise 3.79. Generalize the solve-2nd procedure of exercise 3.78 so that it can be used to solve general second-order differential equations d² y/dt² = f(dy/dt, y).

Answer:
(define (solve-2nd f y0 dy0 dt) (define y (integral (delay dy) y0 dt)) (define dy (integral (delay ddy) dy0 dt)) (define ddy (stream-map f dy y)) y)
Exercise 3.80. A series RLC circuit consists of a resistor, a capacitor, and an inductor connected in series, as shown in figure 3.36. If R, L, and C are the resistance, inductance, and capacitance, then the relations between voltage (v) and current (i) for the three components are described by the equations



and the circuit connections dictate the relations



Combining these equations shows that the state of the circuit (summarized by vC, the voltage across the capacitor, and iL, the current in the inductor) is described by the pair of differential equations



The signal-flow diagram representing this system of differential equations is shown in figure 3.37.



Figure 3.36: A series RLC circuit.



Figure 3.37: A signal-flow diagram for the solution to a series RLC circuit.

Write a procedure RLC that takes as arguments the parameters R, L, and C of the circuit and the time increment dt. In a manner similar to that of the RC procedure of exercise 3.73, RLC should produce a procedure that takes the initial values of the state variables, vC0 and iL0, and produces a pair (using cons) of the streams of states vC and iL. Using RLC, generate the pair of streams that models the behavior of a series RLC circuit with R = 1 ohm, C = 0.2 farad, L = 1 henry, dt = 0.1 second, and initial values iL0 = 0 amps and vC0 = 10 volts.

Answer:
(define (RLC R L C dt) (define (proc vC0 iL0) (define vC (integral (delay dvC) vC0 dt)) (define iL (integral (delay diL) iL0 dt)) (define dvC (scale-stream iL (- (/ 1 C)))) (define diL (add-streams (scale-stream iL (- (/ R L))) (scale-stream vC (/ 1 L)))) (cons vC iL)) proc) (define RLC1 ((RLC 1 1 0.2 0.1) 10 0))
Exercise 3.81. Exercise 3.6 discussed generalizing the random-number generator to allow one to reset the random-number sequence so as to produce repeatable sequences of ``random'' numbers. Produce a stream formulation of this same generator that operates on an input stream of requests to generate a new random number or to reset the sequence to a specified value and that produces the desired stream of random numbers. Don't use assignment in your solution.

Answer:
(define (rand m) (define (generate-random-stream initial-value) (define random-numbers (cons-stream initial-value (stream-map rand-update random-numbers))) random-numbers) (cond ((eq? m 'generate) (lambda () (generate-random-stream random-init))) ((eq? m 'reset) (lambda (new-value) (generate-random-stream new-value)))))
Exercise 3.82. Redo exercise 3.5 on Monte Carlo integration in terms of streams. The stream version of estimate-integral will not have an argument telling how many trials to perform. Instead, it will produce a stream of estimates based on successively more trials.

Answer:
(define (random-in-range low high) (let ((range (- high low))) (+ low (random range)))) (define (rect-area x1 x2 y1 y2) (abs (* (- x2 x1) (- y2 y1)))) (define (monte-carlo experiment-stream passed failed) (define (next passed failed) (cons-stream (/ passed (+ passed failed)) (monte-carlo (stream-cdr experiment-stream) passed failed))) (if (stream-car experiment-stream) (next (+ passed 1) failed) (next passed (+ failed 1)))) (define (estimate-integral P x1 x2 y1 y2) (define (experiment) (P (random-in-range x1 x2) (random-in-range y1 y2))) (define (make-experiment-stream) (cons-stream (experiment) (make-experiment-stream))) (define ratio-stream (monte-carlo (make-experiment-stream) 0 0)) (define area (rect-area x1 x2 y1 y2)) (stream-map (lambda (r) (* area r 1.0)) ratio-stream)) (define (in-unit-circle? x y) (<= (+ (square x) (square y)) 1)) (define pi (estimate-integral in-unit-circle? -1 1 -1 1))

SICP Section 3.4 Concurrency: Time Is of the Essence

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.

Answer: a. Processes run sequentially in some order
45 (Peter, Paul, Mary)
35 (Peter, Mary, Paul)
45 (Paul, Peter, Mary)
50 (Paul, Mary, Peter)
40 (Mary, Peter, Paul)
40 (Mary, Paul, Peter)

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)))))
Answer: Possible values are 10^4, 10^5, 10^6. If serialized procedures are used only 10^6 remains.

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?

Answer: There are no scenarios that call for Ben's changes. The set! command is the only one that affects balance. Anyone trying to view the balance will see the value before or after setting and nothing else.

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 ?

Answer: This is a safe change to make. Serialization is not affected by whether the procedure is serialized inside dispatch or outside it.

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

Answer: ouis is wrong. Ben's procedure is sufficient to handle the requirement.

The difference between the transfer and exchange problems is that the latter calculates the difference in account balances before withdrawing/depositing. There is no way to guarantee that the account balances do not change between the calculation of the difference and the subsequent actions.

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.

Answer: Louis's logic will lead to a deadlock situation when serialized-exchange is called. This procedure invokes a (doubly) serialized version of exchange. Exchange in turn invokes the serialized versions of withdraw and deposit. Exchange cannot finish until both these are completed; due to serializing neither withdraw nor deposit can start until exchange is over. This leads to a deadlock.

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.

Answer: a. Semaphore in terms of mutexes
(define (make-semaphore n) (let ((mutex (make-mutex)) (count 0)) (define (the-semaphore m) (cond ((eq? m 'acquire) (mutex 'acquire) (if (< count n) (set! count (+ count 1))) (mutex 'release)) ((eq? m 'release) (mutex 'acquire) (if (> count 0) (set! count (- count 1))) (mutex 'release)))) the-semaphore))
b. Semaphore in terms of atomic test-and-set! operations
(define (make-semaphore n) (let ((cell (list false)) (count 0)) (define (the-semaphore m) (cond ((eq? m 'acquire) (test-and-set! cell) (if (< count n) (set! count (+ count 1))) (clear! cell)) ((eq? m 'release) (test-and-set! cell) (if (> count 0) (set! count (- count 1))) (clear! cell)))) the-semaphore))

SICP Section 3.3 Modeling with Mutable Data

Exercise 3.12. The following procedure for appending lists was introduced in section 2.2.1:
(define (append x y) (if (null? x) y (cons (car x) (append (cdr x) y))))
Append forms a new list by successively consing the elements of x onto y. The procedure append! is similar to append, but it is a mutator rather than a constructor. It appends the lists by splicing them together, modifying the final pair of x so that its cdr is now y. (It is an error to call append! with an empty x.)
(define (append! x y) (set-cdr! (last-pair x) y) x)
Here last-pair is a procedure that returns the last pair in its argument:
(define (last-pair x) (if (null? (cdr x)) x (last-pair (cdr x))))
Consider the interaction
(define x (list 'a 'b)) (define y (list 'c 'd)) (define z (append x y)) z (a b c d) (cdr x) <response> (define w (append! x y)) w (a b c d) (cdr x) <response>
What are the missing <response>s? Draw box-and-pointer diagrams to explain your answer.

Answer:
(define (append x y) (if (null? x) y (cons (car x) (append (cdr x) y)))) (define (append! x y) (set-cdr! (last-pair x) y) x) (define (last-pair x) (if (null? (cdr x)) x (last-pair (cdr x))))
Exercise 3.13. Consider the following make-cycle procedure, which uses the last-pair procedure defined in exercise 3.12:
(define (make-cycle x) (set-cdr! (last-pair x) x) x)
Draw a box-and-pointer diagram that shows the structure z created by
(define z (make-cycle (list 'a 'b 'c)))
What happens if we try to compute (last-pair z)?

Answer: Terrible things happen! Make-cycle creates a circular list. This is not a bad thing to have and might actually come useful under some circumstances. However trying to compute (last-pair z) throws the interpreter into an infinite loop.

Exercise 3.16. Ben Bitdiddle decides to write a procedure to count the number of pairs in any list structure. ``It's easy,'' he reasons. ``The number of pairs in any structure is the number in the car plus the number in the cdr plus one more to count the current pair.'' So Ben writes the following procedure:
(define (count-pairs x) (if (not (pair? x)) 0 (+ (count-pairs (car x)) (count-pairs (cdr x)) 1)))
Show that this procedure is not correct. In particular, draw box-and-pointer diagrams representing list structures made up of exactly three pairs for which Ben's procedure would return 3; return 4; return 7; never return at all.

Answer:
(define length-3 (cons (list 'a) (list 'b))) (count-pairs length-3) 3 (define length-4 (list (list 'a) (list 'b))) (count-pairs length-4) 4 (define x (cons (list 'a) (list 'b))) (define length-7 (cons x x)) (count-pairs length-7) 7
Exercise 3.18. Write a procedure that examines a list and determines whether it contains a cycle, that is, whether a program that tried to find the end of the list by taking successive cdrs would go into an infinite loop. Exercise 3.13 constructed such lists.

Answer:
(define (is-circular? x) (define (iter y) (cond ((null? y) false) ((eq? (car x) (car y)) true) (else (iter (cdr y))))) (iter (cdr x))) (define z (make-cycle (list 'a 'b 'c))) (is-circular? z) #t

SICP Section 3.1 Assignment and Local State

Exercise 3.1. An accumulator is a procedure that is called repeatedly with a single numeric argument and accumulates its arguments into a sum. Each time it is called, it returns the currently accumulated sum. Write a procedure make-accumulator that generates accumulators, each maintaining an independent sum. The input to make-accumulator should specify the initial value of the sum; for example
(define A (make-accumulator 5)) (A 10) 15 (A 10) 25
Answer:
(define (make-accumulator initial) (define (accumulator value) (set! initial (+ initial value)) initial) accumulator)
Exercise 3.2. In software-testing applications, it is useful to be able to count the number of times a given procedure is called during the course of a computation. Write a procedure make-monitored that takes as input a procedure, f, that itself takes one input. The result returned by make-monitored is a third procedure, say mf, that keeps track of the number of times it has been called by maintaining an internal counter. If the input to mf is the special symbol how-many-calls?, then mf returns the value of the counter. If the input is the special symbol reset-count, then mf resets the counter to zero. For any other input, mf returns the result of calling f on that input and increments the counter. For instance, we could make a monitored version of the sqrt procedure:
(define s (make-monitored sqrt)) (s 100) 10 (s 'how-many-calls?) 1
Answer:
(define (make-monitored f) (define count 0) (define (mf arg) (cond ((eq? arg 'reset-count) (set! count 0)) ((eq? arg 'how-many-calls?) count) (else (begin (set! count (+ 1 count)) (f arg))))) mf)
Exercise 3.3. Modify the make-account procedure so that it creates password-protected accounts. That is, make-account should take a symbol as an additional argument, as in
(define acc (make-account 100 'secret-password))
The resulting account object should process a request only if it is accompanied by the password with which the account was created, and should otherwise return a complaint:
((acc 'secret-password 'withdraw) 40) 60 ((acc 'some-other-password 'deposit) 50) "Incorrect password"
Answer:
(define (make-account balance password) (define (withdraw amount) (if (>= balance amount) (begin (set! balance (- balance amount)) balance) "Insufficient funds")) (define (deposit amount) (set! balance (+ balance amount)) balance) (define (dispatch p m) (if (eq? p password) (cond ((eq? m 'withdraw) withdraw) ((eq? m 'deposit) deposit) (else (error "Unknown request -- MAKE-ACCOUNT" m))) (lambda (m) "Incorrect Password"))) dispatch)
Exercise 3.4. Modify the make-account procedure of exercise 3.3 by adding another local state variable so that, if an account is accessed more than seven consecutive times with an incorrect password, it invokes the procedure call-the-cops.

Answer:
(define (make-account balance password) (define (withdraw amount) (if (>= balance amount) (begin (set! balance (- balance amount)) balance) "Insufficient funds")) (define (deposit amount) (set! balance (+ balance amount)) balance) (define (dispatch p m) (if (eq? p password) (cond ((eq? m 'withdraw) withdraw) ((eq? m 'deposit) deposit) (else (error "Unknown request -- MAKE-ACCOUNT" m))) deal-with-incorrect-password)) (define count 0) (define (deal-with-incorrect-password m) (if (< count 7) (begin (set! count (+ 1 count)) "Incorrect Password") (call-the-cops))) (define (call-the-cops) "Calling-the-cops!") dispatch)
Exercise 3.5. Monte Carlo integration is a method of estimating definite integrals by means of Monte Carlo simulation. Consider computing the area of a region of space described by a predicate P(x, y) that is true for points (x, y) in the region and false for points not in the region. For example, the region contained within a circle of radius 3 centered at (5, 7) is described by the predicate that tests whether (x - 5)2 + (y - 7)2< 32. To estimate the area of the region described by such a predicate, begin by choosing a rectangle that contains the region. For example, a rectangle with diagonally opposite corners at (2, 4) and (8, 10) contains the circle above. The desired integral is the area of that portion of the rectangle that lies in the region. We can estimate the integral by picking, at random, points (x,y) that lie in the rectangle, and testing P(x, y) for each point to determine whether the point lies in the region. If we try this with many points, then the fraction of points that fall in the region should give an estimate of the proportion of the rectangle that lies in the region. Hence, multiplying this fraction by the area of the entire rectangle should produce an estimate of the integral.

Implement Monte Carlo integration as a procedure estimate-integral that takes as arguments a predicate P, upper and lower bounds x1, x2, y1, and y2 for the rectangle, and the number of trials to perform in order to produce the estimate. Your procedure should use the same monte-carlo procedure that was used above to estimate . Use your estimate-integral to produce an estimate of by measuring the area of a unit circle.

You will find it useful to have a procedure that returns a number chosen at random from a given range. The following random-in-range procedure implements this in terms of the random procedure used in section 1.2.6, which returns a nonnegative number less than its input.8
(define (random-in-range low high) (let ((range (- high low))) (+ low (random range))))
Answer:
(define (rect-area x1 x2 y1 y2) (abs (* (- x2 x1) (- y2 y1)))) (define (estimate-integral P x1 x2 y1 y2 trials) (define (experiment) (P (random-in-range x1 x2) (random-in-range y1 y2))) (define ratio (monte-carlo trials experiment)) (define area (rect-area x1 x2 y1 y2)) (* ratio area 1.0)) (define (estimate-pi trials) (define (in-unit-circle? x y) (<= (+ (square x) (square y)) 1)) (estimate-integral in-unit-circle? -1 1 -1 1 trials))
Exercise 3.6. It is useful to be able to reset a random-number generator to produce a sequence starting from a given value. Design a new rand procedure that is called with an argument that is either the symbol generate or the symbol reset and behaves as follows: (rand 'generate) produces a new random number; ((rand 'reset) ) resets the internal state variable to the designated . Thus, by resetting the state, one can generate repeatable sequences. These are very handy to have when testing and debugging programs that use random numbers.

Answer:
(define (rand message) (let ((x (random-init))) (cond ((eq? mesage 'generate) (lambda () (set! x (rand-update x)) x)) ((eq? message 'reset) (lambda (new-value) (set! x new-value))))))
Exercise 3.7. Consider the bank account objects created by make-account, with the password modification described in exercise 3.3. Suppose that our banking system requires the ability to make joint accounts. Define a procedure make-joint that accomplishes this. Make-joint should take three arguments. The first is a password-protected account. The second argument must match the password with which the account was defined in order for the make-joint operation to proceed. The third argument is a new password. Make-joint is to create an additional access to the original account using the new password. For example, if peter-acc is a bank account with password open-sesame, then
(define paul-acc (make-joint peter-acc 'open-sesame 'rosebud))
will allow one to make transactions on peter-acc using the name paul-acc and the password rosebud. You may wish to modify your solution to exercise 3.3 to accommodate this new feature.

Answer:
(define (make-joint account original-password joint-password) (define (dispatch p m) (if (eq? joint-password p) (account original-password m) (lambda (m) "Incorrect (Joint) Password"))) dispatch)
Exercise 3.8. When we defined the evaluation model in section 1.1.3, we said that the first step in evaluating an expression is to evaluate its subexpressions. But we never specified the order in which the subexpressions should be evaluated (e.g., left to right or right to left). When we introduce assignment, the order in which the arguments to a procedure are evaluated can make a difference to the result. Define a simple procedure f such that evaluating (+ (f 0) (f 1)) will return 0 if the arguments to + are evaluated from left to right but will return 1 if the arguments are evaluated from right to left.

Answer: This problem set me thinking about how to translate a procedure from one form to another. you can find my thoughts (and unresolved questions) here.
(define f (let ((state 1)) (lambda (x) (set! state (* state x)) state)))
Here are the snippets to test the solution. The second simulates a right-to-left order of execution. The interpreter has to be reset after executing the first snippet.
(+ (f 0) (f 1)) 0 ;; After resetting interpreter. (+ (f 1) (f 0)) 1