functional-programmingschemelispsicplazy-sequences# Space complexity of streams in Scheme

I am reading *Structure and Interpretation of Computer Programs* (SICP) and would like to make sure that my thinking is correct.

Consider the following simple stream using the recursive definition:

```
(define (integers-starting-from n)
(cons-stream n (integers-starting-from (+ n 1))))
(define ints (integers-starting-from 1))
(car (cdr-stream (cdr-stream (cdr-stream (cdr-stream ints)))))
```

If we adopt the implementation in SICP, whenever we `cons-stream`

, we are effectively consing a variable and a lambda function (for delayed evaluation). So as we `cdr-stream`

along this stream, *nested lambda functions* are created and a chain of frames is stored for the evaluation of lambda functions. Those frames are necessary since lambda functions evaluate expressions and find them in the enclosing frame. Therefore, I suppose that in order to evaluate the n-th element of the stream, you need to store **n** extra frames that take up linear space.

This is different from the behavior of iterators in other languages. If you need to go far down the stream, much space will be taken. Of course, it is possible to only keep the direct enclosing frame and throw away all the other ancestral frames. Is this what the actual scheme implementation does?

Solution

"nested lambda functions are created"

nope. There is *no* nested scope. In

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

definition, in the `(integers-starting-from (+ n 1))`

call, `integers-starting-from`

is a *function* and `(+ n 1)`

is its argument. So *when* that call is made, the *value* of `(+ n 1)`

is found first and only then the execution enters the `integers-starting-from`

definition body. Thus there's no more reference to `n`

being held by anything, at that point.

**Scheme is an eager programming language, not a lazy one.**

So the lambda inside the result of `cons-stream`

holds a reference to the call frame at first, yes, but there is no nesting of environments in the tail of that stream after that tail is produced. The value of `(+ n 1)`

is already obtained, *before* the new lambda is created and returned as part of the next `cons`

cell representing the stream's next state, i.e. the stream's tail.

Unfolding the calls to lambda functions as the equivalent `let`

expressions, we get

```
(define ints (integers-starting-from 1))
=
(define ints (let ((n 1))
(cons-stream n (integers-starting-from (+ n 1)))))
=
(define ints (let ((n 1))
(cons n (lambda () (integers-starting-from (+ n 1))))))
```

and the call proceeds as

```
(car (cdr-stream (cdr-stream ints)))
=
(let* ((ints (let ((n 1))
(cons n
(lambda ()
(integers-starting-from (+ n 1))))))
(cdr-ints ((cdr ints)))
(cddr-ints ((cdr cdr-ints)))
(res (car cddr-ints)))
res)
=
(let* ((ints (let ((n 1))
(cons n
(lambda ()
(integers-starting-from (+ n 1))))))
(cdr-ints ((cdr ints))
=
((let ((n 1))
(lambda () (integers-starting-from (+ n 1)))))
=
(let ((n 1))
((lambda () (integers-starting-from (+ n 1)))))
=
(let ((n 1))
(integers-starting-from (+ n 1)))
=
(integers-starting-from 2) ;; args before calls!
=
(let ((n 2))
(cons n
(lambda ()
(integers-starting-from (+ n 1))))))
(cddr-ints ((cdr cdr-ints)))
(res (car cddr-ints)))
res)
=
(let* ((ints (let ((n 1))
(cons n ;; inde-
(lambda ()
(integers-starting-from (+ n 1))))))
(cdr-ints (let ((n 2))
(cons n ;; pen-
(lambda ()
(integers-starting-from (+ n 1))))))
(cddr-ints (let ((n 3))
(cons n ;; dent
(lambda ()
(integers-starting-from (+ n 1))))))
(res (car cddr-ints)))
res)
=
(let* ((res (let ((n 3))
n)))
res)
=
3
```

So there's no nested lambdas here. Not even a chain of lambdas, because the implementation is non-memoizing. The values for `cdr-ints`

and `cddr-ints`

are ephemeral, liable to be garbage-collected while the 3rd element is being calculated. Nothing holds any reference to them.

Thus getting the *n*th element is done *in constant space modulo garbage*, since all the interim *O(n) space* entities are eligible to be garbage collected.

In (one possible) memoizing implementation, each `lambda`

would be actually replaced by its result *in the cons cell*, and there'd be a chain of three -- still non-nested -- lambdas, congruent to an open-ended list

```
(1 . (2 . (3 . <procedure-to-go-next>)))
```

In programs which do not hold on to the top entry of such chains, all the interim `cons`

es would be eligible for garbage collection as well.

One such example, even with the non-memoizing SICP streams, is the sieve of Eratosthenes. Its performance characteristics are consistent with no memory retention of the prefix portions of its internal streams.

- Do Java 8 streams produce slower code than plain imperative loops?
- Are Databases and Functional Programming at odds?
- In Scala, how to define a `val` in a `if block`?
- What is the most minimal functional programming language?
- How to implement the Elvis operator in Java 8?
- Understanding Peter Norvig's permutation solution in PAIP
- Lack of Finite Element Method implementations in Haskell - Any specific reasons?
- Trying to get the number of even and odd integers in a list
- Currying vs. anonymous function in Scala
- OCaml higher order functions
- How do I use lambda to replace for loop and still maintained functional programming?
- How does functools partial do what it does?
- How can I implement a splay tree that performs the zig operation last, not first?
- How to thread, pipe or compose functions in lua?
- List to dictionary using functional programming in python
- How to compose functions through purely using Python's standard library?
- Why functional languages?
- What is wrong with this code for creating lists in OCaml?
- How to correctly identify pure functions in functional programming?
- Why the same function prints different output?
- Just want choose some random elements of a list and return them in OCaml
- Haskell Depth-First Graph Traversal has Infinite Loop
- How can I get a flat result from a list comprehension instead of a nested list?
- How to interleave (merge) two Java 8 Streams?
- Running an array of TaskEithers in parallel, but continue if 1 or more task fails
- How to create an anonymous object dynamically in .NET?
- Change all values of an array without a loop construct
- Flattening a Nested List in OCaml
- How does recursion looks like for let-in-end in SML
- Haskells bind operator and the >> operator and their relation