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

*To*: srfi-40@xxxxxxxxxxxxxxxxx*Subject*: Re: Much simpler leak-free implementation possible?*From*: Andre van Tonder <andre@xxxxxxxxxxxxx>*Date*: Wed, 27 Aug 2003 21:09:08 -0400 (EDT)*Delivered-to*: srfi-40@xxxxxxxxxxxxxxxxx

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

**Follow-Ups**:**Re: Much simpler leak-free implementation possible?***From:*Andre van Tonder

- Prev by Date:
**Monad for lazy evaluation** - Next by Date:
**Re: Much simpler leak-free implementation possible?** - Previous by thread:
**Re: Much simpler leak-free implementation possible?** - Next by thread:
**Re: Much simpler leak-free implementation possible?** - Index(es):