Re: Stream-filter and space leaks

[Richard Kelsey <kelsey@xxxxxxx>]

   From: Phil Bewig <pbewig@xxxxxxxxxx>
   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