Re: Stream-filter and space leaks

[Richard Kelsey <kelsey@xxxxxxx>]

   From: sperber@xxxxxxxxxxxxxxxxxxxxxxxxxxx (Michael Sperber [Mr.  Preprocessor])
   Date: Fri, 21 Feb 2003 11:04:03 +0100

   The code you posted seems to be essentially the definition of
   DELAY/FORCE from Scheme 48.  However, Phil's old code does leak in
   Scheme 48 and doesn't leak with the proposed fix.

Right.  I was mistaken about the source of the leak.  This time around
I have actually tested the code.

The problem is that the Scheme 48 version of DELAY, as well as the
R5RS version, keeps the delayed thunk around in case it is reentrant:

 > (define f (let ((first? #t))
               (delay (if first?
                          (begin
                            (set! first? #f)
                            (force f))
                          'second))))
 ; no values returned
 > (force f)
 'second

In the case of the SRFI version of STREAM-FILTER the thunk is closed over
the filtered stream.  The new version drops that thunk's reference to the
stream before forcing it.

DELAY and FORCE can be modified to plug the leak, at the cost of making
promises non-reentrant.  In the version below the promise's thunk clears
the promise's reference to itself before executing the closed-over
expression.  The SRFI's version of STREAM-FILTER doesn't leak when using
MY-DELAY and MY-FORCE.

 (define-syntax my-delay
   (syntax-rules ()
     ((delay ?exp) (make-promise (lambda (clear-me)
                                   (set-car! clear-me #f)
                                   ?exp)))))

 (define (make-promise thunk)
   (let ((already-run? #f)
         (thunk-then-result (list thunk)))
     (lambda ()
       (if already-run?
           (car thunk-then-result)
           (cond ((procedure? (car thunk-then-result))
                  (let ((result ((car thunk-then-result) thunk-then-result)))
                    (cond ((not already-run?)
                           (set! already-run? #t)
                           (set-car! thunk-then-result result)))
                    (car thunk-then-result)))
                 (else
                  (error "circular promise")))))))

 (define (my-force promise)
   (promise))

As promised, promises are no longer reentrant:

 > (define g (let ((first? #t))
               (my-delay (if first?
                             (begin
                               (set! first? #f)
                               (my-force g))
                             'second))))
 ; no values returned
 > (my-force g)

 Error: circular promise
 1> 

This might be acceptable for streams.

   This is just a note---I intend to check next week why this is so.

I was unwilling to wait...
                                            -Richard