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.

- Returning `nil` from a `compactMap()` closure fails result type check
- What is it called and what does it mean when a function "equals" another function and provides a body?
- Can you explain closures (as they relate to Python)?
- Is there a way to 'restrict' elm function f : A -> Maybe B into f0 : ProperA -> B without using Debug.todo?
- When can a pointful function be refactored to be point free?
- Why is it done in std::ranges that I can't split the range that I got from join with transform
- Is environment model necessary for higher-order procedures?
- Compile to xslt?
- Using ML in "Real-World" Applications
- Functional pipes in python like %>% from R's magrittr
- Is there something like the threading macro from Clojure in Python?
- What is the difference between functions and data?
- Optimization of tail recursion in R
- Python method chaining in functional programming style
- trace a nested recursion in Ocaml
- How can I map a String to a function in Java?
- Tail recursion on R Statistical Environment
- What is the way to chain methods with different signatures describing a business process?
- How to properly propagate an error through non-error function?
- Groovy: what is analogue for java stream anyMatch
- Dart: mapping a list (list.map)
- Is there a Functional Programming library for .NET?
- Python recursion challenge
- Does JavaScript have a method like "range()" to generate a range within the supplied bounds?
- functional programming efficiency vs imperative
- Why can I pass a getter reference to stream().mapToInt(...)?
- Would an Option or Optional type (Option<T>) make sense in TypeScript?
- What is the advantage of using Option instead of typescript's optional `?` operator?
- Writing an isPrime function in Haskell
- How does functools partial do what it does?