1

I came across the following example in Lecture 6B of the SICP lecture series, and need some help understanding how it is evaluated.

The example uses stream processing to create an infinite stream of integers greater than 1:

; utility procedure
(define (add-streams s1 s2)                                     ; Returns a stream containing the element-wise sums of s1 and s2 
  (cond ((empty-stream? s1) s2)                                 ; If either stream is empty, return the non-empty one
        ((empty-stream? s2) s1)
        (else                                                    
         (cons-stream (+ (head s1) (head s2))                   ; Otherwise, return a new stream whose first element is the sum of the heads of s1 and s2
                      (add-streams (tail s1) (tail s2)))))      ; ...and whose tail is the result of recursively adding the streams in the tails of s1 and s2.


(define ones (cons-stream 1                                     ; infinite stream of 1s                              
                              ones))

(define integers (cons-stream 1                                 ; infinite stream of increasing integers, starting from 1                              
                              (add-streams integers ones)))

I understand that integers is built up by incrementing the head of the stream returned by successive add-streams calls, but I'm not quite sure if I understand how it is evaluated.

integers is the stream of all integers greater than 1, so we can access the 3rd integer in this set as follows:

(head (tail (tail integers)))

The innermost tail forces the (add-streams integers ones) promise to evaluate:

(add-streams integers ones) ----->  (cons (+ (head integers) (head ones))
                                          (delay (add-streams (tail integers) (tail ones))))
                            
                            ----->  (cons 2
                                          (delay (add-streams (tail integers) (tail ones))))

The outer tail call then forces the (add-streams (tail integers) (tail ones)) promise to evaluate:

(add-streams (tail integers)
             (tail ones))       -----> (add-streams (cons 2 (delay ...))
                                                    (cons 1 (delay ...)))
                                          
                                -----> (cons (+ (head (cons 2 (delay ...)))
                                                (head (cons 1 (delay ...))))
                                             (delay (add-streams (tail (cons 2 (delay ...)))
                                                                 (tail (cons 1 (delay ...))))))
                                    
                                -----> (cons 3
                                             (delay (add-streams (cons 3 (delay ...))
                                                                 (cons 1 (delay ...)))))

When we call head on the result of the outer tail call, we get 3, which is the expected answer.

However, I'm not sure if I've evaluated this correctly. I'm especially unsure about the (tail integers) call that shows in the second reduction step. I reduce it to (add-streams (cons 2 (delay ...)) (cons 1 (delay ...))) in the third reduction step, is this correct?

Will Ness
  • 70,110
  • 9
  • 98
  • 181
user51462
  • 1,658
  • 2
  • 13
  • 41
  • it depends on the implementation of `delay`. do you know what it is? does it store the calculated value, when it is forced, so that on subsequent forcings it directly returns that value? – Will Ness Apr 22 '23 at 15:55
  • Looks correct. Both `force`,`delay` and the memoization stuff is just boilerplate to avoid recalculations and it's convoluted to avoid memory leaks. Just to understand how it works it is easier to assume `cons-stream` is just `cons` but puts a lambda around the `cdr` and that `tail` calls that function, giving you a `cons` with a lambda in their `cdr` or `'()`. – Sylwester Apr 22 '23 at 20:56
  • @Sylwester `(cons 1 (delay ...))` in `(add-streams (cons 2 (delay ...)) (cons 1 (delay ...)))` *can't* be correct *if* `delay` is memoizing its result. then it would be equivalent to `(cons 1 ones)` because `ones`'s `cdr` was (presumably) already forced by a `tail` call at this point. or if not at that step exactly, then certainly at a later steps. and if not `ones`'s `cdr` then the promise that's stored in it, and that *forced* promise can not be written as `(delay ...)` call. it depends on the exact details of an implementation. – Will Ness Apr 23 '23 at 18:27
  • OP, you can find one non-memoizing and two memoizing implementations of these streams in [this answer](https://stackoverflow.com/questions/11654004/given-a-recursive-function-how-do-i-change-it-to-tail-recursive-and-streams/11700092#11700092) of mine, for a comparison. – Will Ness Apr 23 '23 at 18:33
  • https://youtu.be/qp05AtXbOP0 is better quality video. – Will Ness Apr 23 '23 at 20:08
  • @WillNess Memoization, by design, should never change the outcome. It should work transparently. `cons-stream` will delay the call to `add-streams` and the forcing of either tail so only the non lazy heads are becoming a new unlazy head. – Sylwester Apr 24 '23 at 10:21
  • @Sylwester yes, no outcome is changed. but I understand this question as being about *operational* details of the evaluation process. so without changing the produced value, it can turn an exponential process into a linear one which is producing the same result (as you are no doubt well aware). – Will Ness Apr 24 '23 at 10:23
  • @WillNess I don't think your link shows memoization since you are altering streams to become pairs. That is not transparent. The memoization demonstrated in SICP is transparent. You'll need to call each tail, but you get the same calculated value that was forced the first time around. – Sylwester Apr 24 '23 at 10:32
  • @Sylwester I don't get what you mean. the calculated value is retained, so it is memoized, whether it is put directly into a car field, or inside a struct stored in a car field, changes nothing if each type of stream is accessed by its appropriate means. – Will Ness Apr 24 '23 at 10:35
  • @WillNess OK, base don your link I made this `(define-syntax cons-stream (syntax-rules () ((_ a d) (letrec ((pair (cons a (lambda () (set-cdr! pair d) (cdr pair))))) pair))))` which does the same as your `make-stream` and `(head (tail (tail integers))) ; ==> 3`, then `ones ; ==> #0=(1 . #0#)` and `integers ; ==> (1 2 3 . #)` so it isn't equivalent to `(cons 1 ones)` but works the same way as one expect without memoization. – Sylwester Apr 24 '23 at 13:40
  • @Sylwester `ones ; ==> #0=(1 . #0#)` literally says `ones=(cons 1 ones)`. :) – Will Ness Apr 24 '23 at 17:22
  • @WillNess Ah, you meant ones would end up referencing itself. Yes, but so would the standard delay one as well. `(tail ones) ;=> ones` no matter if its memoized with SICP, your mutating tail or not at all. – Sylwester Apr 26 '23 at 00:50
  • @Sylwester semantically, yes, of course, but not operationally. Without memoization there will be repeated creation and execution of thunks. With self-mutating promise there's still a record-inspecting step. With tail-cdr mutation the value is just there though a type-inspecting step still needs to be performed. – Will Ness Apr 26 '23 at 07:10
  • 1
    @Sylwester I've added your macro into my answer, thanks. (with full attribution of course). I presume you ran that code in MIT Scheme? – Will Ness Apr 26 '23 at 10:29

2 Answers2

1

I think your summary of what happens is correct. However I also think that the best way to think about this is one of two things. The first may be less helpful than the second which is why I am putting it first.

Either (1) think about the semantics of the thing and don't worry too much about evaluation.

In this case the right way to think about this is to think that:

  • the stream of ones is a stream whose head is 1 and whose tail is the stream of ones;
  • the stream of natural numbers (not integers: there is no ordered stream of integers! (why?)) is the stream whose head is 0 (or 1 if you want your natural numbers to begin at 1) and whose tail is the stream of integers with 1 added to each one.

Or (2), write an implementation of streams which you can then persuade to tell you what is going on.

Here is such an implementation. I apologise that this is written in Racket, not pure Scheme. In this implementation delay is called postpone and force is called ensure: this was done so that it an sit alongside any native implementation of these things. You can control:

  • whether a stream reports what is happening when it is ensured;
  • whether a stream memoizes the result of being ensured.

Note in particular that streams are not represented as conses: they are represented as procedures. So there is no punning between conses and streams: streams are a whole other thing. Note also that cons-stream postpones both its arguments.

(define ensure-reports
  ;; Do streams report when being ensured
  (make-parameter #t))

(define ensure-memoizes
  ;; Do streams memoize their values
 (make-parameter #t))

(define-syntax postpone
  ;; postpone is delay
  (syntax-rules ()
    [(_ form)
     (let ([ensured #f]
           [value #f])
       (thunk
        (cond
          [ensured
           (when (ensure-reports)
             (eprintf "[~S is ~S]~%" 'form value))
           value]
          [else
           (let ([v form])
             (when (ensure-reports)
               (eprintf "[~S to ~S]~%" 'form v))
             (when (ensure-memoizes)
               (set! value v)
               (set! ensured #t))
             v)])))]))

(define (ensure postponed)
  ;; ensure is force
  (postponed))

(define-syntax cons-stream
  (syntax-rules ()
    [(_ head-form tail-form)
     (let ([h (postpone head-form)]
           [t (postpone tail-form)])
       (λ (k)
         (case k
           [(head)
            (ensure h)]
           [(tail)
            (ensure t)]
           [(null-stream?)
            #f]
           [else
            (error 'cons-stream "what?")])))]))

(define (head s)
  (s 'head))

(define (tail s)
  (s 'tail))

(define null-stream
  ;; A null stream is a stream whose head and tail are itself and which
  ;; knows it is null.  This is like NIL / () in CL but unlike () in Scheme.
  (λ (k)
    (case k
      [(head) null-stream]
      [(tail) null-stream]
      [(null-stream?) #t]
      [else
       (error 'null-stream "what?")])))

(define (null-stream? s)
  (s 'null-stream?))

(define (stream-nth n stream)
  ;; nth element of a stream
  (unless (>= n 0)
    (error 'stream-nth "negative creep"))
  (let snl ([m n]
            [s stream])
    (cond
      [(null-stream? s)
       (error 'stream-nth "out of stream")]
      [(zero? m)
       (head s)]
      [else
       (snl (- m 1) (tail s))])))

(define-syntax list-stream
  ;; like list but for streams
  (syntax-rules ()
    [(_)
     null-stream]
    [(_ h more ...)
     (cons-stream h (list-stream more ...))]))

(define (stream-to-list stream)
  ;; finite stream to list of elements
  (let sll ([s stream]
            [a '()])
    (if (null-stream? s)
        (reverse a)
        (sll (tail s)
             (cons (head s) a)))))

Given this we can write add-streams, just renaming things slightly from the question:

(define (add-streams s1 s2)
  (cond [(null-stream? s1) s2]
        [(null-stream? s2) s1]
        [else
         (cons-stream (+ (head s1) (head s2))
                      (add-streams (tail s1) (tail s2)))]))

And now define ones and naturals (again, not integers):

(define ones
  (cons-stream 1 ones))

(define naturals
  (cons-stream 0 (add-streams naturals ones)))

And now, finally, you can get it to show you what is going on:

> (head (tail (tail naturals)))
[(add-streams naturals ones) to #<procedure>]
[(add-streams naturals ones) is #<procedure>]
[ones to #<procedure:ones>]
[(add-streams (tail s1) (tail s2)) to #<procedure>]
[0 to 0]
[1 to 1]
[(+ (head s1) (head s2)) to 1]
[1 is 1]
[(+ (head s1) (head s2)) to 2]
2
ignis volens
  • 7,040
  • 2
  • 12
  • the actual question as I see it is about the presence of the last delay in `(cons 3 ....)`. with your code, we need to call `(head (tail (tail (tail naturals))))` to actually show that there are no more `[ones to #]` indeed, and only `[ones is #]`, indicating the absence of `delay`s in the `ones`' representation, at that point. – Will Ness Apr 25 '23 at 15:53
  • @WillNess: my answer was really suggesting that when there are questions like this then a good approach is, rather than trying to reason about the hidden details of the implementation, to *write your own implementation* which is then far more easy to instrument and control (as in the one in my answer were you can control memoization &c). Such an implementation doesn't have to be performant: it merely needs to be correct and understandable. – ignis volens Apr 26 '23 at 13:51
  • Yes, I understood that, and I don't think I've contradicted that. I was just saying that with a small addition, your closing example could be more informative. BTW I have tried it, and the output was hard for me to follow, which motivated me to finally write my own answer. :) – Will Ness Apr 26 '23 at 16:07
1

SICP streams have (cons-stream a b) == (cons a (delay b)). I'm not sure if the authors show the actual delay implementation, but in Scheme it is memoizing -- it creates a promise as a memory structure (object) which calculates the value and stores it on first access, and directly returns it on every subsequent access.

Thus a SICP stream is represented as a cons pair whose car field contains a ready-made value and the cdr field contains the memoizing promise:

(define (head s) (car s))

(define (tail s) (force (cdr s)))

force is defined so that it will recognize a promise that is already forced, and will just return the stored value in such a case.

So then, we have:

(define ones (cons 1 (delay ones)))

;; ones :=> <1 . {promise1 DELAYED (thunk ones)}> 
;;          -- pseudocode representation of a memory object

Let's start the integers from 10, so it's easier to follow the lengthy code listing below:

(define ints (cons 10 (delay (add-streams ints ones))))

;; ints :=> <10 . {promise2 DELAYED (thunk (add-streams ints ones))}>
;;          -- pseudocode representation of a memory object

So the first tail applied to ones forces ones's cdr and thus changes the contents of the structure referred to by ones into ones :=> <1 . {promise1 FORCED ones}> (symbolically).

And now, it goes like this:

(head (tail (tail ints)))
= ;1           ; pseudocode .......
(letrec
      ([ones :=> <1 . {promise1 DELAYED (thunk ones)}> ]
       [ints :=> <10 . {promise2 DELAYED (thunk (add-streams ints ones))}>]
       [b  (tail ints)]
       [a  (tail b)])     ; single assignment transformation
  (head a))
= ;2
(letrec
      ([ones :=> <1 . {promise1 DELAYED (thunk ones)}> ]
       [ints :=> <10 . {promise2 DELAYED (thunk (add-streams ints ones))}>]
       [b  (tail ints)]
       [a  (force (cdr b))])    ; progressive evaluation
  (head a))
= ;3
(letrec
      ([ones :=> <1 . {promise1 DELAYED (thunk ones)}> ]
       [ints :=> <10 . {promise2 DELAYED (thunk (add-streams ints ones))}>]
       [b  (force (cdr ints))]
       [a  (force (cdr b))])
  (head a))
= ;4
(letrec
      ([ones :=> <1 . {promise1 DELAYED (thunk ones)}>]
       [ints :=> <10 . {promise2 FORCED b}>]
       [b  (add-streams ints ones)]          ; forcing
       [a  (force (cdr b))])
  (head a))
= ;5
(letrec
      ([ones :=> <1 . {promise1 DELAYED (thunk ones)}>]
       [ints :=> <10 . {promise2 FORCED b}>]
       [h1 (head ints)]
       [h2 (head ones)]
       [b  (cons (+ h1 h2) (delay
                   (add-streams (tail ints) (tail ones))))]
       [a  (force (cdr b))])
  (head a))
= ;6
(letrec
      ([ones :=> <1 . {promise1 DELAYED (thunk ones)}>]
       [ints :=> <10 . {promise2 FORCED b}>]
       [b    :=> <11 . {promise3 DELAYED (thunk 
                         (add-streams (tail ints) (tail ones)))}>]
       [a  (force (cdr b))])
  (head a))
= ;7
(letrec
      ([ones :=> <1 . {promise1 DELAYED (thunk ones)}>]
       [ints :=> <10 . {promise2 FORCED b}>]
       [b    :=> <11 . {promise3 FORCED a}>]
       [a  (add-streams (tail ints) (tail ones))])
  (head a))
= ;8
(letrec
      ([ones :=> <1 . {promise1 DELAYED (thunk ones)}>]
       [ints :=> <10 . {promise2 FORCED b}>]
       [b    :=> <11 . {promise3 FORCED a}>]
       [s1  (tail ints)]
       [s2  (tail ones)]
       [a  (add-streams s1 s2)])
  (head a))
= ;9
(letrec
      ([ones :=> <1 . {promise1 DELAYED (thunk ones)}>]
       [ints :=> <10 . {promise2 FORCED b}>]
       [b    :=> <11 . {promise3 FORCED a}>]
       [s1  (force (cdr ints))]
       [s2  (force (cdr ones))]
       [a  (add-streams s1 s2)])
  (head a))
= ;10
(letrec
      ([ones :=> <1 . {promise1 DELAYED (thunk ones)}>]
       [ints :=> <10 . {promise2 FORCED b}>]
       [b    :=> <11 . {promise3 FORCED a}>]
       [s1  b]            ; (cdr ints) is already forced
       [s2  (force (cdr ones))]
       [a  (add-streams s1 s2)])
  (head a))
= ;11
(letrec
      ([ones :=> <1 . {promise1 DELAYED (thunk ones)}>]
       [ints :=> <10 . {promise2 FORCED b}>]
       [b    :=> <11 . {promise3 FORCED a}>]
       [s2  (force (cdr ones))]
       [a  (add-streams b s2)])
  (head a))
= ;12
(letrec
      ([ones :=> <1 . {promise1 FORCED s2}>]
       [ints :=> <10 . {promise2 FORCED b}>]
       [b    :=> <11 . {promise3 FORCED a}>]
       [s2  ones]
       [a  (add-streams b s2)])
  (head a))

continuing,

= ;13
(letrec
      ([ones :=> <1 . {promise1 FORCED ones}>]
       [ints :=> <10 . {promise2 FORCED b}>]
       [b    :=> <11 . {promise3 FORCED a}>]
       [a  (add-streams b ones)])
  (head a))
= ;14
(letrec
      ([ones :=> <1 . {promise1 FORCED ones}>]
       [ints :=> <10 . {promise2 FORCED b}>]
       [b    :=> <11 . {promise3 FORCED a}>]
       [a    :=> <12 . {promise4 DELAYED (thunk
                         (add-streams (tail b) (tail ones)))}>])
  (head a))   ; value of a is found
= ;15
(letrec
      ([ones :=> <1 . {promise1 FORCED ones}>]
       [ints :=> <10 . {promise2 FORCED b}>]
       [b    :=> <11 . {promise3 FORCED a}>]
       [a    :=> <12 . {promise4 DELAYED (thunk
                         (add-streams (tail b) (tail ones)))}>])
  (car a))    ; head is car
= ;16
12

and hopefully this is clear enough to illustrate what is going on here.

In particular, the tail of ones, once forced, becomes ones itself, and stays so forced henceforth -- there are no further delays there afterwards.

The above of course follows the definition

(define (add-streams s1 s2)
  (cond [(null-stream? s1) s2]
        [(null-stream? s2) s1]
        [else
         (cons (+ (head s1) (head s2))
               (delay
                 (add-streams (tail s1) (tail s2))))]))

As can be seen above, the memoizing promise implementation is only superficially different but in the end functionally equivalent to the tail-mutating implementation which can be seen in this answer by yours truly, though in a different setting.

A variation for this tail-mutating approach, one matching the SICP styled use case here, was given by Sylwester in the comments above:

(define-syntax cons-stream
  (syntax-rules ()
    ((_ a d)
     (letrec ([pair (cons a 
                       (lambda ()
                          (set-cdr! pair d)
                          (cdr pair)))])
       pair))))

under which, calling (head (tail (tail ints))) results in ones ; ==> #0=(1 . #0#) and ints ; ==> (10 11 12 . #<procedure>).

ones ; ==> #0=(1 . #0#) literally means ones = <1 . ones>, which is practically the same as <1 . {promise1 FORCED ones}> that can be seen in the derivations above.

Equivalently, we can keep the cons-stream as simply delaying, and have stream-cdr do the memoizing:

(define-syntax cons-stream
  (syntax-rules () 
    ((_ h t) (cons h (lambda () t)))))

(define (stream-cdr s)
  (if (and (not (pair? (cdr s)))
           (not (null? (cdr s))))
      (set-cdr! s ((cdr s))))
  (cdr s))

A side observation, step 15 could also be followed by

= ;15
(letrec
      ([ones :=> <1 . {promise1 FORCED ones}>]
       [ints :=> <10 . {promise2 FORCED b}>]
       [b    :=> <11 . {promise3 FORCED a}>]
       [a    :=> <12 . {promise4 DELAYED (thunk
                         (add-streams (tail b) (tail ones)))}>])
  (car a))    ; head is car
= 
(letrec
      ([ones :=> <1 . {promise1 FORCED ones}>]
       [a    :=> <12 . {promise4 DELAYED (thunk
                         (add-streams a ones))}>])
  (car a))
= 
(letrec
       [a    :=> <12 . {promise4 DELAYED (thunk
                         (map-stream 1+ a))}>])
  (car a))

which suggests an alternative definition for ints,

(define (ints-from a)
  (letrec ([s (cons-stream a (map-stream 1+ s))])
     s))

or

(define (ints-from a)
  (let loop ([a a])
    (cons-stream a (loop (+ a 1)))))

or even just

(define (ints-from a)
  (cons-stream a 
    (ints-from (+ a 1))))
Will Ness
  • 70,110
  • 9
  • 98
  • 181