On Thursday, February 20, 2003 12:39 PM, Richard Kelsey [SMTP:xxxxxx@s48.org] wrote:
>    From: Phil Bewig <xxxxxx@swbell.net>
>    Date: Thu, 20 Feb 2003 15:08:05 +0100
>
>    Stream-filter and
>    the various stream-drop functions leak space if they are not implemented
>    properly, something that is hard to do.  In fact, in a private e-mail
>    yesterday someone pointed out another space leak involving stream-filter
>    (they were also kind enough to show how to fix it).
>
> Comparing the new version of STREAM-FILTER with the one in the proposed SRFI,
> it appears that this latest space leak could be fixed by including your own
> versions of DELAY and FORCE in the sample implementation, using one where forcing
> a stream caused it to stop retaining the generating thunk.  You could merge this
> delay into the STREAM record:
>
>   (define-record-type stream-type
>     (really-make-stream thunk-then-result already-run?)
>     stream?
>     (thunk-then-result stream-thunk-then-result set-stream-thunk-then-result!)
>     (already-run?      stream-already-run?      set-stream-already-run?!))
>
>   (define (make-stream thunk)
>     (really-make-stream thunk #f))
>
>   ; This is the sample code for FORCE from R5RS except that it:
>   ;   - uses a stream record instead of a closure
>   ;   - uses the same location for the thunk and its value to avoid retaining
>   ;     the thunk
>   (define (stream-value stream)
>     (if (stream-already-run? stream)
>         (stream-thunk-then-result stream)
>         (let ((result ((stream-thunk-then-result stream)))
>               (cond ((not (stream-already-run? stream))
>                      (set-stream-already-run?! stream #t)
>                      (set-stream-thunk-then-result! stream result)))
>               (stream-thunk-then-result stream)))))
>
>    And it is not possible to confine the effects of this space leak to just a few
>    functions implemented in the core srfi.  There are doubtless circumstances where
>    users will need to write functions that skip stream elements and are thus subject
>    to the space leak.
>
> I would think that a few general functions would be sufficient for almost
> everyone, modulo (minor?) efficiency considerations.  You might want a
> STREAM-UNFOLD that produced multiple streams, for example:
>
>    (stream-unfoldn generator seed n) -> n streams
>
>    STREAM-UNFOLDN returns N streams whose contents are produced by successive calls
>    to GENERATOR, which takes the current seed as an arguments and returns two values:
>      (proc seed) -> seed results
>    where results contains N values that indicate how each result streams proceeds:
>       (value)  -> value is the next CAR of this result stream
>       #f       -> no new information for this result stream
>       ()       -> the end of this result stream has been reached
>    Note that getting the next element in any particular result stream may require
>    multiple calls to GENERATOR.
>
> The implementation is left as an exercise for the reader, as is the related
> STREAM-FILTERN function.
>
>    Thus, I propose it would be useful for the srfi to provide syntax that would
>    allow this to be a valid, non-leaking implementation of stream-filter:
>
>        (stream-define-leaky (stream-filter pred? strm)
> 	 (cond ((stream-null? strm) stream-null)
> 	       ((pred? (stream-car strm))
> 		 (stream-cons (stream-car strm)
> 			      (stream-filter pred? (stream-cdr strm))))
> 	       (else (stream-filter pred? (stream-cdr strm)))))
>
> I doubt that this is feasible.  It would be much simpler, but still not simple,
> if the user indicated which variables were needed where.  Something like
>
>    (lift-lambdas my-lambda ... (my-lambda spec (free-vars ...) body ...) ...)
>
> where each of the LIFT-LAMBDA's were lifted out the level of the LIFT-LAMBDAS
> expression, along with the given free variables.  This would have to be the subject
> of a separte SRFI, and even then you have the problem that the LAMBDAs created
> by DELAY are implicit.
>                                                   -Richard
>

Thanks for the suggestion about changing the underlying stream-type.  I'll
take a look at that.

The only functions that come to mind after thinking about this for a day are
STREAM-EVERY-NTH, where you want to take every nth item from a
stream and throw out the rest, and STREAM-RANDOM-NTH, which is
similar but chooses the items randomly.  Something like the SIEVE used
to calculate prime numbers would also be similar, if you select the items
by counting instead of using modulo.  Your STREAM-UNFOLDN and
STREAM-FILTERN look interesting, though I'd be interested to know how
often they would actually be useful.

I didn't think my stream-define-leaky was possible.

Phil