max@Neon.Stanford.EDU (Max Hailperin) (09/30/89)
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) fibs)))) 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.