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

Re: Much simpler leak-free implementation possible?

This page is part of the web mail archives of SRFI 40 from before July 7th, 2015. The new archives for SRFI 40 contain all messages, not just those from before July 7th, 2015.

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))
            (if first?
                  (set! first? #f)
                  (force f))

> (force f)

gives 'second.

With the definitions of delay and force below, the naive definition of

(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

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


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)])
           [else 'match-error]))]))