SICP Chapter 3.5.2 infinite streams integers definition

Question

I am reading SICP and am having difficulty understanding one example provided for infinite streams:

https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-24.html#%_sec_3.5.2

We can do more interesting things by manipulating streams with operations such as add-streams, which produces the elementwise sum of two given streams:62

(define (add-streams s1 s2)
  (stream-map + s1 s2))

Now we can define the integers as follows:

(define integers (cons-stream 1 (add-streams ones integers)))

I can obviously understand the intent behind the integers definition but I'm struggling to "simulate" this stream in my head. Prior examples haven't been an issue because the maintenance of state has been explicit. Such as in this example:

(define (integers-starting-from n)
  (cons-stream n (integers-starting-from (+ n 1))))

(define integers (integers-starting-from 1))

I have no problem understanding this definition of integers.

The book describes the definition of ones:

(define ones (cons-stream 1 ones))

This works much like the definition of a recursive procedure: ones is a pair whose car is 1 and whose cdr is a promise to evaluate ones. Evaluating the cdr gives us again a 1 and a promise to evaluate ones, and so on.

Perhaps this line is throwing me off. Ones is simple, because on each stream-cdr the procedure is evaluated and a new "1" is provided and the next promise.

When I try to apply this reasoning to integers, I'm struggling to understand why the resultant stream isn't "1 2 2 2 2 2 ..." as integers gets continually re-evaluated and essentially restarting at 1.

edit I was remiss in not elaborating on whether or not memoization was to be assumed in my question. SICP does indeed mention the concern of quadratic behavior raised in the answers and provides a solution in the form of a memoizing delay function:

(define (memo-proc proc)
  (let ((already-run? false) (result false))
    (lambda ()
      (if (not already-run?)
          (begin (set! result (proc))
                 (set! already-run? true)
                 result)
          result))))

Delay is then defined so that (delay ) is equivalent to

(memo-proc (lambda () <exp>))

If you're struggling to simulate it in your head, why not evaluate it with pen and paper (or some electronic equivalent)? SICP teaches you the evaluation model that Scheme uses, so this should be possible to do mechanically. If you've done this and still don't understand, you can point to what steps you don't get. — amalloy
check out this alternative streams implementation with explicit state, see if it's clearer to you. sometimes (often?) it helps to look at a problem from two different vantage points at once. — Will Ness

codybartfast codybartfast · Accepted Answer · 2020-06-09T15:24:21

If our streams are memoized then the integers passed as an argument to add-streams is always "one step behind" the integers that we are enumerating, so it always has access to the memoized value. With numbers in (parens) showing the use of memoized values:

Integers: 1, add-streams /    Ones: 1,     1,     1,     1,     1,     1,  ...
                         \Integers: 1,    (2),   (3),   (4),   (5),   (6), ...
                                   ===    ===    ===    ===    ===    ===
Results:  1                         2,     3,     4,     5,     6,     7,  ...

Memoized:                           2,     3,     4,     5,     6,

If our streams are not memoized then each time stream-cdr is called on integers a new series of ones is created and added to all the previous ones.

integers                          1
    ones                              1,  1,  1,  1,  1,  1,  ...
    integers                          1
        ones                              1,  1,  1,  1,  1,  ...
        integers                          1
            ones                              1,  1,  1,  1,  ...
            integers                          1
                ones                              1,  1,  1,  ...
                integers                          1
                    ones                              1,  1,  ...
                    integers                          1
                        ones                              1,  ...
                        integers                          1
                                 ==  ==  ==  ==  ==  ==  ==  
                                  1,  2,  3,  4,  5,  6,  7,  ...

So 100 is generated by adding an element of ones 99 times and the stream-car of the integers that is the result of the previous 99 calls to integers.

Although the first add-streams is only combining two streams, the second stream will (after returning 1) be returning results from a new add-streams, the second stream of which will be will be the result of another add-streams:

1, add-streams / 1,               1,               1, ...
               \ 1, add-streams / 1,               1, ...
                                \ 1, add-streams / 1, ...
                                                 \ 1, add-streams ...

So add-streams, a bit like using cons to create a list, is creating pairs of streams where the first is a stream of ones and the second is another pair of streams.

Without memoizing this is not a practical implementation of integers because its performance is O(n^2):

Time to Access Elements

Element of    CPU Time
 integers      (msec)
==========    ========
      1 st           0
      2 nd           0
      4 th           0
      8 th           0
     16 th           0
     32 nd          47
     64 th          78
    128 th         313
    256 th       1,171
    512 th       4,500
  1,024 th      17,688
  2,048 th      66,609
  4,096 th     272,531

SICP Chapter 3.5.2 infinite streams integers definition

4 Answers