Re: Scheme style auto-resizing hashtable (fwd)

[Maciej Stachowiak <mstachow@mit.edu>]

bothner@cygnus.com writes:
> > Reading SICP, stream primitives are used to do this sort of of "iterator" 
> > thing, right?
> 
> 
> Thus SICP streams still involve creating a "lazy cons" for each
> element of the collection that you are iterating over (unless
> you break off the iteration early).  This makes streams much
> more expensive than cursor-style iterators.  On the other hand,
> Waters' "series" implementation (see CLtL:2 appendix A) suggests
> that with some compiler smarts it may be possible to remove
> much of the overhead in most cases (assuming the compiler is
> allowed to inline the series functions).
> 

Hmm, I just realized, you can get a decent amount of memory efficiency
even without very smart compilers or inlining (contrary to my earlier
post). If I do

(stream-for-each my-procedure (generate-some-stream))

and stream-for-each is written to be tail recursive, and taking some
care not to leave a pointer to the head of the stream on the stack,
then the head of the list up to stream-for-each's current position can
be garbage collected. You _do_ still have the memory overhead of
creating the cons cells and GC-ing them. A GC that is very good at
collecting short-lived objects efficiently should make this less of a
time hit than it would otherwise be though. And since stream mappers
and filters generate unforced streams as output, even the following:

(stream-for-each 
 do-something-imperative!
 (stream-map do-a-mystic-transform
	     (stream-filter translucent-and-bubbly?
			    (generate-stream-of-random-things))))

will be about as memory efficient as a cursor-style iterator with a
decent GC.

The problematic case I was thinking of before was code like

(let ((my-stream (generate-a-stream)))
  (stream-for-each my-proc my-stream))

But first of all this is tail recursive, and even if there were a call
after the stream-for-each, even a compiler that was only slightly
smart would be able to eliminate the let.

Conclusion: streams really are iterators done right; they are memory
efficient without much work, but still support applying various
high-level transforms to the sequence as a whole without having to
walk down it for each one.

 - Maciej