andreuri2000

Previous threads both in this newsgroup and in SRFI-40 have
discussed shortcomings of the traditional implementation of
promises in Scheme with respect to space leaks. The problem
is essentially that most Scheme implementations of promises
(including the R5RS ref. impl.) break tail recursion.

With this in mind, I am posting an alternative implementation of
delay and force that

- does not break tail-recursion.
- preserves the correct semantics of reentrant promises.
- is practical for Schemes that have *efficient* call/cc
(such as Chez, others?).

The problem can be illustrated very simply.
Let us define a function that traverses an infinite stream:

(define (traverse s)
(traverse (cdr (force s))))

then given the definition of a stream of integers:

(define (from n)
(delay (cons n (from (+ n 1)))))

the following expression runs forever in constant space, as
expected:

(let ((integers (from 0)))
(traverse integers))

;===> Runs in constant space in MzScheme, Petite Chez

However, the apparently equivalent expression:

(let ((integers (from 0)))
(force (delay (traverse integers))))

causes a rapid space leak (in both Mz and Petite). The reason is that
in the usual implementation of delay and force (see e.g. R5RS), the
thunk being forced is not invoked in tail position, so that the reference
to the variable "integers" cannot be dropped until "traverse" returns.
Since "integers" refers to the head of the stream, the whole stream
has to be kept in memory.

In my view, this is a fundamental violation of the very reasonable
expectation that

force o delay = identity,

which is now observationally false (assuming finite memory, the first
expression above will loop forever while the second will terminate in error).
It should be true, because the above behaviour makes it extremely difficult
to reason about the space behaviour of lazy programs in Scheme (see, e.g.,
the SRFI40 discussions).

A solution with the correct tail-behavior is expressible in standard Scheme.

I adapted it from an idea concerning a CPS-style implementation of
promises by Stephen McCracken last year in this group, modified here to access
the implicit internal continuation using call/cc and allow direct-style
use instead.

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

Here the promise is always invoked in tail position.
Since it uses call/cc, it is best suited to Schemes with an
*efficient* implementation of call/cc, such as Petite Chez, where it runs
very efficiently. I have also tested it in MzScheme, where it does
not appear to *leak* memory either but is unfortunatly so memory-inefficient
as to make it impractical for more complex programs (probably due to repeated
copying of the stack during call/cc).

With these definitions, the expressions

(let ((integers (from 0)))
(traverse integers))

and

(let ((integers (from 0)))
(force (delay (traverse integers))))

will indeed run in constant space in both Petite Chez (very efficiently) and
Mz (very inefficiently). So the expected equivalence "force o delay = id"
does indeed hold on this domain.

Finally, the solution has the correct semantics w.r.t. reentrancy:

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

(force f) ;===> Should give 'second if correct.
; True in Mz and Petite Chez.

Regards
Andre v. T.

Code below:

;================================================= ===============
; Testing primitive delay and force:

; Traversing a stream

(define (traverse s)
(traverse (cdr (force s))))

(define (from n)
(delay (cons n (from (+ n 1)))))

;-------------------------------------

;(let ((integers (from 0)))
; (traverse integers))

;===> Runs in constant space in MzScheme, Petite Chez

;(let ((integers (from 0)))
; (force (delay (traverse integers))))

;===> Rapid leak in Mz, Petite

;================================================= ==============
; Delay and force that do not break tail recursion:
; Based on CPS-style idea of Stephen McCracken, but modified
; to use implicit internal continuation:

; Practical for Schemes with efficient implementations of call/cc.
; Correct reentrancy behavior.

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

;================================================= ================
; Testing tail-recursive delay and force:

(define (traverse s)
(traverse (cdr (force s))))

(define (from n)
(delay (cons n (from (+ n 1)))))

;-----------------------------------

;(let ((integers (from 0)))
; (traverse integers))

;===> Runs in constant space in MzScheme, Petite Chez
; Very space-efficient in Chez, which has efficient
; call/cc.
; Mz uses lots of memory before it stabilizes.

;(let ((integers (from 0)))
; (force (delay (traverse integers))))

;===> Runs in constant space in Mz, Petite
; Once again, veru efficient in Petite, very
; inefiicient in Mz.


;================================================= ==========
; Reentrancy test

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

(force f) ;===> Should give 'second if correct.
; True in Mz and Petite Chez.

matthias blume

andreuri2000@yahoo.com (Andre) writes:

[ snip ]

I don't quite see your point. We also have

(lambda (x) x) = identity

but

(fun (loop x) ((lambda (x) x) (loop x)))

is allowed to run out of memory (*), while

(fun (loop x) (loop x))

is not.

(*) Most implementations will probably not run out of memory on the first
expression either. So, instead, consider

(define identity (lambda (x) x))

(fun (loop x) (identity (loop x))

where (lambda (x) x) cannot be so readily inlined and then
beta-expanded away at compile time (because someone might set! it
somewhere else in the program).

[ rest, although clever, snipped ]

Matthias

joe marshall

Matthias Blume <find@my.address.elsewhere> writes:

True. But it is trivial to `fix' this by a simple code transformation.
It is quite difficult to fix the force/delay problem that way.

matthias blume

Joe Marshall <jrm@ccs.neu.edu> writes:


I'm not sure what you mean by "fix" and by "simple code
transformation". Who is supposed to do the transforming?

Notice that my example was just the most trival of the cases where
something (or the combination of several things) ought to act like an
identity but still destroys tail-recursion. Here are a few more
examples of a FOO and a BAR so that (BAR o FOO) is an identity (modulo
the tail-recursiveness isssue):

(define FOO (lambda (x) (cons x '()))
(define BAR (lambda (x) (car x)))

(define FOO (lambda (x) (vector x)))
(define BAR (lambda (v) (vector-ref v 0)))

(define FOO (lambda (x) (if (and (integer? x) (exact? x)) (+ x 1) x)))
(define BAR (lambda (x) (if (and (integer? x) (exact? x)) (- x 1) x)))

...

See my point?

Matthias