3.5.3 · Exploiting the stream paradigm

A numerical process can become a stream of improving observations.

Generate exact partial sums and square-root guesses as delayed sequences, then demand only the finite prefix needed for one comparison.

Guiding question

What changes when a numerical iteration describes every successive approximation instead of hiding all but the final answer?

Represent successive numerical states as stream elements
Accumulate an infinite term stream into exact partial sums
Generate Newton square-root guesses without a fixed iteration loop
Demand a finite prefix while leaving the remaining process delayed
Observe a finite sequence of Newton improvements

alternating-terms describes 1, −1/2, 1/3, −1/4, and so on. partial-sums carries the completed total into the delayed tail, so each stream element is a reusable approximation to the infinite alternating harmonic series. stream-take forces only the five pairs displayed in the result.

sqrt-stream exposes every Newton improvement for √2. Its exact rational sequence begins 1, 3/2, 17/12, 577/408, and 665857/470832. Later consumers can inspect more guesses without changing the producer. The displayed prefix records the improvement sequence for the selected starting value.

SICP code583 of 1,048,576 UTF-8 bytes

(begin
  (define (stream-take stream count)
    (if (= count 0)
        '()
        (cons (car stream)
              (stream-take
                (force (cdr stream))
                (- count 1)))))
  (define (alternating-terms n sign)
    (cons-stream
      (/ sign n)
      (alternating-terms (+ n 1) (- sign))))
  (define (partial-sums stream total)
    (let ((next-total (+ total (car stream))))
      (cons-stream
        next-total
        (partial-sums
          (force (cdr stream))
          next-total))))
  (stream-take
    (partial-sums (alternating-terms 1 1) 0)
    5))

Examples

Result—

Output: —
Value: —
Diagnostic: —

Execution trace0 / 0 events

Expected result

The partial sums are (1 1/2 5/6 7/12 47/60). The square-root guesses are (1 3/2 17/12 577/408 665857/470832).

Trace focus

Count force operations rather than imagining an already materialized infinite list. In partial-sums, follow the previous total into the next delayed step. In sqrt-stream, separate the current guess from the formula captured in the promise for the following guess.

Try it yourself

Change the program and compare the result.

Create a stream of reciprocal-square partial sums and take six values. Then write a stream-limit consumer that stops when two successive inexact guesses differ by less than a visible tolerance.

Show hint

Keep the producer independent from the stopping policy. A consumer may compare adjacent elements while the stream retains every intermediate state.

Complete this lesson

0 of 21 lessons complete in this chapter0%