Space-safe Lazy Computation
Andre
Philip Wadler, Walid Taha, and David MacQueen in the paper
"How to add laziness to a strict language without even being odd" provide a
useful recipe for translating lazy data structures and algorithms into a strict
language with delay/force.
However, as has been discussed previously on this newsgroup (see also
SRFI-40), with the typical implementation of delay/force it is easy to
write programs that suffer from serious space leaks whereas the same
algorithm in a truly lazy language would run in bounded space. A good
example of this is discussed by Philip Bewig and others in SRFI-40
(filtering an infinite stream).
An ingenious attempt at ameliorating this problem, provided
by Richard Kelsey, was incorporated into SRFI-40, but does not work
uniformly (see below) and does not allow reentrant promises.
In this message I provide a solution to the space leak problem that
- has bounded space behavior in all the benchmarks (see below).
- allows reentrant promises.
I provide a set of benchmark tests for leaky behavior. While the new solution
passes all tests (inlcuding the stream-filter example of SRFI-40) with bounded
space behaviour, the existing solutions (R5RS and SRFI-40) fail all the leak
benchmarks on the systems I have tested, in most cases badly.
Here are the results of the benchmarks. The same results were obtained
in MzScheme and Petite Chez.
Present Solution R5RS SRFI-40
Reentrancy Pass Pass Fail
Leak Test 1 Pass Fail Fail
Leak Test 2 Pass Fail Fail
Leak Test 3 Pass Fail Fail
Leak Test 4 Pass Fail Fail
Leak Test 5 Pass Fail Fail
Leak Test 6 Pass Fail Fail
Leak Test 7 Pass Fail Fail
Leak Test 8 Pass Fail Fail
The simplest benchmark, which actually isolates the problem quite well,
is an infinite loop written in a hypothetical lazy language as
(define (loop) (loop))
which, using the Wadler translation, would become
(define (loop) (delay (force (loop))))
Running (force (loop)) will very quickly run out of space using both the
R5RS and SRFI-40 implementations of delay/force, even though the original
algorithm appeared tail-recursive.
The problem is not hard to understand. Taking the semantics of delay/force
to be essentially:
(force (delay expr)) = update promise : (delay expr)
with value of expr
we get
(force (loop)) = update promise1 : (delay (force (loop)))
with value of (force (loop))
= update promise1 : (delay (force (loop)))
with update promise2 : (delay (force (loop)))
with value of (force (loop))
= update promise1 : (delay (force (loop)))
with update promise2 : (delay (force (loop)))
with update promise3 : (delay (force (loop)))
with ...
so we see that an infinite sequence of promises builds up until the heap
space is exhausted.
In a lazy language with naive graph reduction semantics, the above algorithm
would run in bounded space. Indeed, naive graph reduction is known to be
tail-safe (see e.g. R. Jones - Tail recursion without space leaks.)
and the above example shows that the above delay-force translation
does not express this semantics. Graph reduction corresponds roughly to the
promise at the root being overwritten at each step with the next expression
so that we don't get an infinite sequence as above.
The solution provided here is to introduce a new primitive "lazy", which can be
regarded as an "atomic" (delay (force .)). The semantics is
(force (lazy expr)) = update promise : (lazy expr)
with value of expr
force promise (iteratively)
So we have three primitives instead of two:
delay : a -> Promise a
force : Promise a -> a
lazy : Promise a -> Promise a
Our example would be written
(define (loop) (lazy (loop)))
which would evaluate as follows:
(force (lazy (loop))) = update promise : (lazy (loop))
with value of (loop)
force promise
= update promise : (lazy (loop))
with (lazy (loop))
force promise (iteratively)
= (force (lazy (loop)))
running in constant space.
Here is the solution and the benchmarks. To test the same benchmarks
against the R5RS or SRFI-40 implementations of delay/force, just replace
all occurrences of (lazy .) with (delay (force .)) (or define a macro to
do it).
Regards
Andre v.T.
;==========================================================
; Primitives for lazy evaluation:
; 2003: Andre van Tonder
(define (box x) (list x))
(define unbox car)
(define set-box! set-car!)
; Type Promise a = lazy (Promise a) | strict a
; lazy : Promise a -> Promise a
(define-syntax lazy
(syntax-rules ()
[(lazy exp)
(box (cons 'suspension (lambda () exp)))]))
; strict : a -> Promise a
(define (strict x)
(box (cons 'value x)))
; delay : a -> Promise a = lazy o strict
(define-syntax delay
(syntax-rules ()
[(delay exp) (lazy (strict exp))]))
; force : Promise a -> a
(define (force promise)
(let ((content (unbox promise)))
(case (car content)
[(value) (cdr content)]
[(suspension) (set-box! promise (unbox ((cdr content))))
(force promise)])))
;============================================================
; Test memoization:
(define s (delay (begin (display 'hello) 1)))
(force s)
(force s)
;===> Should display 'hello once
(let ((s (delay (begin (display 'bonjour) 2))))
(+ (force s) (force s)))
;===> Should display 'bonjour once
;=============================================================
; Test from R5RS: memoization and reentrancy
(define count 0)
(define p
(delay (begin (set! count (+ count 1))
(if (> count x)
count
(force p)))))
(define x 5)
(force p) ;===> 6
(begin (set! x 10)
(force p)) ;===> 6
;===========================================================
; Reentrancy test from SRFI 40
; This has correct reentrancy behavior:
(define f
(let ((first? #t))
(delay
(if first?
(begin
(set! first? #f)
(force f))
'second))))
(force f) ;===> Should give 'second if correct.
;===========================================
; Test leaks:
; Leak test 1: Infinite loop in bounded space.
(define (loop) (lazy (loop)))
;(force (loop))
;==> OK
; Leak test 2: Pending memos should not accumulate
; in shared structures.
(define s (loop))
;(force s) ;==> OK
; Leak test 3: Safe composition of lazy functions.
; Similar to 2.
(define (leaky s)
(lazy (let ((s* (force s)))
(delay 1))))
;(force (leaky (loop))) ;==> OK
; Leak test 4: Safely traversing infinite stream.
(define (from n)
(delay (cons n (from (+ n 1)))))
(define (traverse s)
(lazy (traverse (cdr (force s)))))
;(force (traverse (from 0))) ;==> OK
; Leak test 5: Safely traversing infinite stream
; while pointer to head exists.
(define s (traverse (from 0)))
;(force s) ;==> OK
;=========================================================================
; Convenient list deconstructor.
(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]))]))
;==============================================================
(define (stream-filter p? s)
(lazy (match (force s)
[() (delay '())]
[(h . t) (if (p? h)
(delay (cons h (stream-filter p? t)))
(stream-filter p? t))])))
; Leak test 6: Naive stream-filter should run in bounded space.
; Simplest case.
;(force (stream-filter (lambda (n) (= n 10000000000))
; (from 0)))
;==> OK
(define (stream-ref index s)
(lazy
(match (force s)
[() 'error]
[(h . t) (if (zero? index)
(delay h)
(stream-ref (- index 1) t))])))
; Check that evenness is correctly implemented - should terminate:
(force (stream-ref 0 (stream-filter
zero?
(from 0))))
;==> OK
; Leak test 7: Another long traversal should run in bounded space.
(define s (stream-ref 100000000 (from 0)))
;(force s)
;==> OK
(define (times3 n)
(stream-ref 3 (stream-filter
(lambda (x) (zero? (modulo x n)))
(from 0))))
; Leak test 8: Infamous example from SRFI 40.
; Shows safe composition of lazy functions.
(force (times3 7))
;(force (times3 100000000)) ;==> OK
Ray Blaak
>
> (define (box x) (list x))
> (define unbox car)
> (define set-box! set-car!)
>
> (syntax-rules ()
> [(lazy exp)
> (box (cons 'suspension (lambda () exp)))]))
>
>
> (syntax-rules ()
> [(delay exp) (lazy (strict exp))]))
>
> (let ((content (unbox promise)))
> (case (car content)
> [(value) (cdr content)]
> [(suspension) (set-box! promise (unbox ((cdr content))))
> (force promise)])))
Silence on the newsgroup? I liked it. Very cool and simple.
Code comment: make (force promise) do some error checking on its inputs --
perhaps make a promise? predicate.
How do you "run" the infinite loop tests? How can they pass or fail if they
never halt? Do you simply instrument them to terminate after some number of
cycles, reporting memory usage?
--
Cheers, The Rhythm is around me,
The Rhythm has control.
Ray Blaak The Rhythm is inside me,
rAYb...@STRIPCAPStelus.net The Rhythm has my soul.
Stephen McCracken
I appreciate Andre's innovations too. However, I am really starting to
suspect that -- except for fun examples -- nobody actually does lazy
programming in scheme, and nobody uses force/delay. Does anyone care to
contradict me with a recent project where they put these techniques to work?
Michael Sperber
>> Silence on the newsgroup? I liked it. Very cool and simple.
Stephen> I appreciate Andre's innovations too. However, I am really starting to
Stephen> suspect that -- except for fun examples -- nobody actually does lazy
Stephen> programming in scheme, and nobody uses force/delay. Does anyone care to
Stephen> contradict me with a recent project where they put these techniques to work?
Yes. Lula
http://www-pu.informatik.uni-tuebingen.de/lula/
is even a commercial system which heavily depends on stream-based
computation for doing Functional Reactive Programming.
--
Cheers =8-} Mike
Friede, Völkerverständigung und überhaupt blabla
Joe Marshall
> andreu...@yahoo.com (Andre) writes:
>>
>> (define (box x) (list x))
>> (define unbox car)
>> (define set-box! set-car!)
>>
>> (define-syntax lazy
>> (syntax-rules ()
>> [(lazy exp)
>> (box (cons 'suspension (lambda () exp)))]))
>>
>> (define (strict x) (box (cons 'value x)))
>>
>> (define-syntax delay
>> (syntax-rules ()
>> [(delay exp) (lazy (strict exp))]))
>>
>> (define (force promise)
>> (let ((content (unbox promise)))
>> (case (car content)
>> [(value) (cdr content)]
>> [(suspension) (set-box! promise (unbox ((cdr content))))
>> (force promise)])))
>
>
> Silence on the newsgroup? I liked it. Very cool and simple.
It's a tricky problem and has some subtlety to it. I wouldn't comment
until I thought about it for a while.
Andre
>
> How do you "run" the infinite loop tests? How can they pass or fail if they
> never halt? Do you simply instrument them to terminate after some number of
> cycles, reporting memory usage?
I ran them on a Windows box, observing the memory allocated to the
process in the Task Manager. In the tests that passed, this would
stabilize after a modest initial increase. The failing tests would all
run out of core memory (350MB) in less than a minute.
Andre
Stephen McCracken
> Yes. Lula
>
> http://www-pu.informatik.uni-tuebingen.de/lula/
>
> is even a commercial system which heavily depends on stream-based
> computation for doing Functional Reactive Programming.
Can you make a few remarks about the style in Lula? Was the laziness
encapsulated, or was force/delay scattered about? Was memoization
essential? Were there any streams defined by self-reference?
Andre
It is essentially an adaptation to lazy evaluation of the
trapoline technique. See e.g.
Compiling higher order languages into fully tail-recursive
portable C - Feely, Miller, Rozas, Wilson
Adapting the language of that paper, the role of the "driver loop"
("dispatcher") is played by the iterative loop in "force".
The "lazy" form marks "control points" (procedure entry and
return points). These are the places where the Wadler translation
would have required the (delay (force ...)) combination, which, as
argued in the original message, is not tail-safe.
This technique is tail-safe because now lazy procedures never call
the body of other lazy procedures directly. They simply return a
lazy suspension (control point) to be called upon the next iteration
of the dispatcher loop in "force".
Regards
Andre v.T.
Michael Sperber
Stephen> "Michael Sperber" <spe...@informatik.uni-tuebingen.de> wrote:
>> Yes. Lula
>>
>> http://www-pu.informatik.uni-tuebingen.de/lula/
>>
>> is even a commercial system which heavily depends on stream-based
>> computation for doing Functional Reactive Programming.
Stephen> Can you make a few remarks about the style in Lula? Was the laziness
Stephen> encapsulated, or was force/delay scattered about?
Encapsulated. The sampling code produces a lazy (SRFI-40-style)
stream of samples.
Stephen> Was memoization essential?
Yes. (In the sense that performance would not have been practical
without it.)
Stephen> Were there any streams defined by self-reference?
Yes. (If you mean streams defined by infinite recursion, that is.)
Jonathan Bartlett
> suspect that -- except for fun examples -- nobody actually does lazy
> programming in scheme, and nobody uses force/delay. Does anyone care to
> contradict me with a recent project where they put these techniques to work?
I do it quite a bit, except it's usually for in-house work. Lazy
evaluation allows me to properly separate parameters without
compromizing speed. For example, I have a utility which computes
several values about an object, and then passes them to a function.
That function often times only uses one of them, but in some instances
uses them all. Rather than messing up my function separation, I
simply wrap all of the computations in (delay)s, and then in my
function I only force the ones I need.
This example doesn't use memoization, and so could be solved just as
easily with 0-parameter functions. However, delay is much cleaner,
and I can think of several places where the memoization would come in
handy.
Feuer
> compromizing speed. For example, I have a utility which computes
> several values about an object, and then passes them to a function.
> That function often times only uses one of them, but in some instances
> uses them all. Rather than messing up my function separation, I
> simply wrap all of the computations in (delay)s, and then in my
> function I only force the ones I need.
Why not use the OO-style solution of splitting up the utility into
several functions and letting the function call the ones it wants?
David