I think it's worth pointing out that the analysis of space usage in cases like this is not always quite simple.
For instance here is a completely naïve implementation of force & delay in Racket:
(define-syntax-rule (delay form)
(λ () form))
(define (force p)
(p))
And we can build enough of something a bit compatible with SICP streams to be dangerous on this:
(define-syntax-rule (cons-stream kar kdr)
;; Both car & cdr can be delayed: why not? I think the normal thing is
;; just to delay the cdr
(cons (delay kar) (delay kdr)))
(define (stream-car s)
(force (car s)))
(define (stream-cdr s)
(force (cdr s)))
(define (stream-nth s n)
(if (zero? n)
(stream-car s)
(stream-nth (stream-cdr s) (- n 1))))
(Note there is lots missing here because I am lazy.)
And on that we can build streams of integers:
(define (integers-starting-from n)
(cons-stream n (integers-starting-from (+ n 1))))
And now we can try this:
(define naturals (integers-starting-from 0))
(stream-nth naturals 10000000)
And this last thing returns 10000000, after a little while. And we can call it several times and we get the same answer each time.
But our implementation of promises sucks: forcing a promise makes it do work each time we force it, and we'd like to do it once. Instead we could memoize our promises so that doesn't happen, like this (this is probably not thread-safe: it could be made so):
(define-syntax-rule (delay form)
(let ([thunk/value (λ () form)]
[forced? #f])
(λ ()
(if forced?
thunk/value
(let ([value (thunk/value)])
(set! thunk/value value)
(set! forced? #t)
value)))))
All the rest of the code is the same.
Now, when you call (stream-nth naturals 10000000) you are probably going to have a fairly bad time: in particular you'll likely run out of memory.
The reason you're going to have a bad time is two things:
- there's a reference to the whole stream in the form of
naturals;
- the fancy promises are memoizing their values, which are the whole tail of the stream.
What this means is that, as you walk down the stream you use up increasing amounts of memory until you run out: the space complexity of the program goes like the size of the argument to stream-nth in the last line.
The problem here is that delay is trying to be clever in a way which is unhelpful in this case. In particular if you think of streams as objects you traverse generally once, then memoizing them is just useless: you've carefully remembered a value which you will never use again.
The versions of delay & force provided by Racket memoize, and will also use enormous amounts of memory in this case.
You can avoid this either by not memoizing, or by being sure never to hold onto the start of the stream so the GC can pick it up. In particular this program
(define (silly-nth-natural n)
(define naturals (integers-starting-from 0))
(stream-nth naturals n))
will not use space proportional to n, because once the first tail call to stream-nth is made there is nothing holding onto the start of the stream any more.
Another approach is to make the memoized value be only weakly held, so that if the system gets desperate it can drop it. Here's a hacky and mostly untested implementation of that (this is very Racket-specific):
(define-syntax-rule (delay form)
;; a version of delay which memoizes weakly
(let ([thunk (λ () form)]
[value-box #f])
(λ ()
(if value-box
;; the promise has been forced
(let ([value-maybe (weak-box-value value-box value-box)])
;; two things that can't be in the box are the thunk
;; or the box itself, since we made those ourselves
(if (eq? value-maybe value-box)
;; the value has been GCd
(let ([value (thunk)])
(set! value-box (make-weak-box value))
value)
;; the value is good
value-maybe))
;; the promise has not yet been forced
(let ((value (thunk)))
(set! value-box (make-weak-box value))
value)))))
I suspect that huge numbers of weak boxes may make the GC do a lot of work.
