Stream-filter and space leaks

[Phil Bewig <pbewig@xxxxxxxxxx>]

As I am rewriting the reference implementation, I have noticed that there
seems to be a fundamental abstraction that I am missing.  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).  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.

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)))))

The purpose of stream-define-leaky would be to perform the lambda lifting
and other program transformations that plug the space leak.  Writing
stream-define-leaky would at least be hard, and I'm not sure if it's even
possible.  A more descriptive name for this function would also be useful.

Does this make sense?  Does anyone here know how to write stream-define-leaky?

For reference, my current implementation of stream-filter is shown below, with
the recently-discovered space leak fixed.

;; STREAM-FILTER pred? stream -- new stream including only items passing pred?
(define (stream-filter pred? strm)
  (define (stream-filter-helper strm prom)
    (make-stream
      (delay
        (let ((strm2 strm))
          (set! strm #f)
          (stream-filter-helper-1 (force (stream-promise strm2)) prom)))))
  (define (stream-filter-helper-1 stuff prom)
    (cond ((null? stuff) '())
          ((pred? (car stuff))
            (cons (car stuff)
                  (let ((prom (list #f)))
                    (set-car! prom
                              (stream-filter-helper-2 (cdr stuff) prom))
                    (stream-filter-helper-3 prom))))
          (else (let ((more (stream-filter-helper-2 (cdr stuff) prom)))
                  (if prom (set-car! prom more))
                  (more)))))
  (define (stream-filter-helper-2 strm prom)
    (lambda () (stream-filter-helper-1 (force (stream-promise strm)) prom)))
  (define (stream-filter-helper-3 prom)
    (make-stream (delay ((car prom)))))
  (cond ((not (procedure? pred?))
          (stream-error "non-functional argument to stream-filter"))
        ((not (stream? strm))
          (stream-error "non-stream argument to stream-filter"))
        (else (stream-filter-helper strm #f))))

Phil