[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Stream-filter and space leaks

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

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