Re: Much simpler leak-free implementation possible?

[Andre van Tonder <andre@xxxxxxxxxxxxx>]

For what it's worth, I have adapted the CPS-style solution to a direct-style
delay and force (below), that has the correct tail call behavior and should
work well in Schemes with an efficient implementation of call/cc (I have
tested in Petite Chez, where it runs very efficiently).  On other Schemes
I do not expect it to work well (e.g. MzScheme, where it works on simple
examples but otherwise call/cc creates garbage too fast for the GC to keep
up without explicit GC management in the code).

What's nice about this solution is that it has the correct reentrancy
semantics.  In other words, the canonical example

(define f
        (let ((first? #t))
          (delay
            (if first?
                (begin
                  (set! first? #f)
                  (force f))
                'second))))

> (force f)

gives 'second.

With the definitions of delay and force below, the naive definition of
stream-filter:

(define (stream-filter p? s)
  (delay (force
          (match (force s)
            [()      (delay '())]
            [(h . t) (if (p? h)
                         (delay (cons h (stream-filter p? t)))
                         (stream-filter1 p? t))]))))

runs the times3 example very efficiently in absolutely constant space in
Petite.

I have posted a related message to comp.lang.scheme, describing the problem
from a slightly different angle.  

Regards
Andre


Code below:

; Definition of delay and force:

(define-syntax delay
  (syntax-rules ()
    [(delay exp)
     (memoize (lambda (k) exp))]))

(define (force p)
  (call/cc p))

(define (memoize p)
  (let ([memo-pair (cons #f #f)])
    (lambda (k)
      (if (car memo-pair)
          (k (cdr memo-pair))
          (p (make-memoizer memo-pair k))))))

(define (make-memoizer memo-pair k)
  (lambda (x)
    (set-car! memo-pair #t)
    (set-cdr! memo-pair x)
    (k x)))

;=========================================================================
; list deconstructor used above:

(define-syntax match
  (syntax-rules ()
    [(match exp
       [()      exp1]
       [(h . t) exp2])
     (let ([lst exp])
       (cond [(null? lst) exp1]
                 [(pair? lst) (let ([h (car lst)]
                                           [t (cdr lst)])
                                       exp2)]
           [else 'match-error]))]))