Evaluation of a self-referencing stream

Question

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?

Answer 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

Answer 2

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