2

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>))
Gregory Kuhn
  • 1,627
  • 2
  • 22
  • 34
  • 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 Jun 09 '20 at 09:54
  • check out this alternative [streams implementation](https://stackoverflow.com/a/11700092/849891) 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 Jun 09 '20 at 17:36

4 Answers4

2

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
codybartfast
  • 7,323
  • 3
  • 21
  • 25
  • I don't believe this is correct at all. I believe `(take n integers)` is an *O(n)* operation; as per this answer it must be *O(n^2)*. this *can* be tested. in any case a *particular* implementation of `cons-stream` in use (or equivalently, `force`) must be examined and evaluation steps of a *specific test code* followed according to Scheme's evaluation rules, to see for sure. – Will Ness Jun 10 '20 at 08:42
  • I'm not so sure about it anymore. I've added an answer, but it needs to be finished... – Will Ness Jun 10 '20 at 18:42
  • I've tested peformance and without memoization it is quadratic. I also verified that in accessing the n-th element `add-streams` is called n times. (as expected because `integers` calls `add-streams` but `integers` is also one of the arguments to `add-streams`) – codybartfast Jun 10 '20 at 18:49
  • right. indeed with the non-memoizing streams looks like `ones` and `integers` are re-entered anew. it's pretty tiring to do this by hand (as seen in my answer), and I don't have a tool to do it for me. these subtle differences matter a lot. – Will Ness Jun 10 '20 at 18:49
  • 1
    so to recap, for memoizing streams implementation the performance being linear means that there's only *one* stream of each of `ones` and `integers` there, not the cascade of them as shown in this answer - which, the cascade, does happen for the non-memoizing streams. – Will Ness Jun 10 '20 at 19:01
  • Good point, and as streams are usually memoized I've edited the answer to put that behaviour at the top as it's more relevant. – codybartfast Jun 11 '20 at 08:54
2

With the simplest, non-memoizing streams implementation, we get:

(define (stream-map2 f s1 s2)
  (cons (f (car s1) (car s2)) 
    (lambda ()
      (stream-map2 f ((cdr s1)) ((cdr s2))))))

(define ones (cons 1 (lambda () ones)))

(define integers
    (cons 1 
      (lambda ()
        (stream-map2 + ones integers)))       ;; 1
  = 
    (cons 1 
      (lambda () 
        (cons (+ (car ones) (car integers))
          (lambda () 
            (stream-map2 + ones 
              (stream-map2 + ones integers))))))      ;; 2
  =
    (cons 1 
      (lambda () 
        (cons (+ (car ones) (car integers))
          (lambda () 
            (let ((i2 (stream-map2 + ones integers)))
              (stream-map2 + ones i2))))))

i.e.

  = 
    (cons 1 
      (lambda () 
        (cons (+ (car ones) (car integers))
          (lambda () 
            (let ((i2 (cons (+ (car ones) (car integers))   ;; <---- 1
                        (lambda () 
                          (stream-map2 + ones 
                            (stream-map2 + ones integers))))))
              (cons (+ (car ones) (car i2))
                (lambda ()
                  (stream-map2 + ones ((cdr i2))))))))))
  = 
    (cons 1 
      (lambda () 
        (cons (+ (car ones) (car integers))
          (lambda () 
            (cons (+ (car ones) 
                     (+ (car ones) (car integers)))
              (lambda ()
                (stream-map2 + ones 
                  (stream-map2 + ones 
                    (stream-map2 + ones integers)))))))))     ;; 3
  =
    ....

Indeed we see a triangular, quadratic computation unfolding here.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
  • 1
    Will Ness, you've gone to a great deal of effort to answer my question. In it's current form, and with @codybartfast's answer, the means by which this works is now crystal clear. Big thanks for going to the trouble! It's a shame I can't mark both as accepted answers. Hopefully both will serve anyone else with lingering confusion as to how this works. – Gregory Kuhn Jun 11 '20 at 21:15
0

See the foot note 56.

cons-stream must be a special form. If cons-stream were a procedure, then, according to our model of evaluation, evaluating (cons-stream <a> <b>) would automatically cause <b> to be evaluated, which is precisely what we do not want to happen.

ceving
  • 21,900
  • 13
  • 104
  • 178
0

The piece I was missing here was that integers isn't being re-evaluated at all. The promise that add-streams returns is the stream-cdr of each of the input streams. The "state" previously referred to is maintained in the feedback loop.
Its quite mind-bending and to be honest still seems almost magical in it's power.

Gregory Kuhn
  • 1,627
  • 2
  • 22
  • 34
  • if `integers` isn't being re-evaluated then the accepted answer is certainly incorrect (the only mention of `add-streams` is inside `integers`, not inside `add-streams` itself). – Will Ness Jun 10 '20 at 08:44
  • *'The "state" previously referred to is maintained in the feedback loop.'* could you show a specific piece of code to which this is referring? `integers` by itself does nothing. – Will Ness Jun 10 '20 at 08:46
  • @WillNess I don't stand by this anymore at all. I will delete this answer. I will try and do a more thorough simulation on paper and see if I can get a better handle on it. I'm no authority at all on Lisp! – Gregory Kuhn Jun 10 '20 at 09:48
  • but your answer does make sense. I just want to see some specific code snippet, so we have something specific to talk about, not guessing. – Will Ness Jun 10 '20 at 09:56
  • You comments certainly serve to push me to understand this further. My understanding when I wrote that was tenuous at best. I agree that my own answer is at odds with the accepted one. When I have a free moment later today I'll try running through this again on paper. – Gregory Kuhn Jun 10 '20 at 10:06
  • I would like to answer as well but I need some specific piece of code from you, like e.g. `(take 3 integers)` or `(stream-nth 3 integers)` or something. more importantly, how do you run it? are you using some Racket package, or your own implementation of `force`/`cons-stream`, and if so, what is it? – Will Ness Jun 10 '20 at 14:20
  • Well, full disclosure, I have never run LISP code :) I'm reading SICP and have thus far haven't gotten stuck, I've been able to follow just by reading. – Gregory Kuhn Jun 10 '20 at 15:28