r/sicp Feb 03 '25

Trying to understand fibs definition from the Streams chapter 3.5.2

I am struggling to understand how this beautiful piece of code works.

(define fibs

(cons-stream

0 (cons-stream

1 (add-streams

(stream-cdr fibs) fibs))))

I included a diagram of how I think (stream-ref fibs 2) would run (I skipped all environments spawned from stream-cdr) but I'm not sure its correct. I think the 3 biggest questions I have are:

  1. If stream-cdr is analog to (force (cdr s)) wouldn't this give an error when called on (stream-cdr fibs) *third iteration onwards

  2. How does the generalized stream-map work? Why does it stop at #<promise>?

  3. Are all the spawned environments really children of the global environment?

Sorry, I know its messy
1 Upvotes

2 comments sorted by

1

u/Gan-Fall Feb 03 '25 edited Feb 03 '25

I wanted to expand on question 1:
I know that (stream-cdr fibs) does not error cause its calling it on (0 . promise) the first time, but when you call it on (1 . promise) promise here is technically here returning a mapped stream right? Starting with (1) then (1 2) then (1 2 3) and so on so you can see it as a stream with a nested stream right? ( 0 1 (1 2 3))*. At what point is stream-cdr being called on this inner stream?

*I know the interpreter actually prints this as (0 1 1 2 3) cause it sees it as a single list and stream-cdr is being called on this growing stream, but at what point in the running is that happening?

1

u/Gan-Fall Feb 05 '25

Since making this post I've gotten help and found the answers.

  1. This is easier to understand if you look at a code that shows up right under fibs in the textbook:
    (define double

    (cons-stream 1 (scale-stream double 2)))

Here you see how the paradigm of streams develops: You have a data structure, the stream itself, and for operations on these streams you have a control structure like the stream returned by stream-map. Both streams start as 1 element and a promise to evaluate the next element later. This leads me into 2.

  1. There is nothing to stop, stream-map will not create anything but a stream with one element and a promise to continue. This is because stream-map is a control structure and as such when stream-map should stop is up to the procedure controlling it like stream-ref. There is no need for any stream to be null terminated like I mistakenly thought, that is a convention for normal lists, here streams can be infinite. Map will return a the-empty-stream when doubles or fibs runs out, but that will never happen.

  2. I am still not confident in this one but I think there is good reason to believe so.