[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

SICP: not hanging onto streams

This is really a SICP teaching question, not a scheme question, but
I bet this list reaches a lot of Structure and Interpretation of Computer
Programs instructors.

I noticed while teaching the material on streams that the examples are
very casual about pointing from the global environment at streams.
This (given memoization) results in excessive memory consumption, not
unlike in "Printing streams---A supplementary exercise for the
instructor" in the Instructor's Manual.

For example, to find the 100th integer not divisible by 7, we have
 (define integers ...)
 (define no-sevens (filter ... integers))
 (nth-stream 100 no-sevens)

Wouldn't it be better to write
 (define (generate-integers) ....)
 (define (generate-no-sevens) (filter ... (generate-integers)))
 (nth-stream 100 (generate-no-sevens))

Even for implicitly defined streams one can do something similar, e.g.
 (define (generate-fibs)
   (define fibs (cons-stream 0
                             (cons-stream 1
                                          (add-streams (tail fibs)
where the pointer to the whole stream is from an environment frame that
itself will stop being pointed at.

Of course, it is not the case that you want to do this indiscriminately.  As
long as the stream generator takes time linear in the amount generated, then
there is no harm in regenerating the stream rather than saving it for resuse,
in big-O terms.  However, there are cases where this wouldn't hold.  You have
to be careful where to reuse and where not.  For examle, the implicit
definition of fibs reuseses itself, because this only requires keeping a fixed
amount of state (the last two numbers) and reduces the time complexity from
exponential to linear.  On the other hand, two seperate consumers of
fibonacci numbers might well each have calls to generate-fibs.  For example,
we might write
 (define (useless n m)
   (- (nth-stream (* n m) (generate-fibs))
      (sum-stream (substream n m (generate-fibs)))))
in order to keep the memory consuption fixed.

So, enough spouting off, time for the questions:
 Has anyone else considered teaching this idiom?
 Is there some problem with it that prevented you from doing so?
 If not, how did it go?

Thanks very much.