SICP Infinite Streams (Chapter 3.5.2)

Question

This is a question related to the SICP Book Chapter 3.5.2.

I'm implementing a stream data structure in other programming languages. And I'm not sure if I understand the following snippet correctly.

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

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

From what I understood at (integers-starting-from (+ n 1)) will execute the function which return a value by executing(cons-stream n (integers-starting-from (+ n 1)))). Because the second formal parameter of the cons-stream is (integers-starting-from (+ n 1)), and because it is enclosed by( ), thus it will execute the function again and again infinitely instead of delaying the execution.

From what I see before executing this snippet, It seems that the following integer will leads to an infinite recursive before even the seconds element of the stream being executed.

Why does this seems to work for scheme as shown during the lecture?

From my understand it should be written something like this instead:

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

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

Does this means that scheme has some kinds of magic that delay the execution of (integers-starting-from (+ n 1)) ?

Thank you in advance

Answer 1

The trick lies in how we implement cons-stream. You explicitly created an evaluation promise when you defined the (lambda () ...) thunk. The special form cons-stream does this, but implicitly and using Scheme's primitives. For example, it can be implemented like this, notice how we use delay:

(define-syntax stream-cons
  (syntax-rules ()
    ((stream-cons head tail)
     (cons head (delay tail)))))

It makes more sense to encapsulate all the promise-creation logic in a single place, say cons-stream, instead of explicitly creating thunks everywhere.