Next: srfi lazy spec, Previous: srfi lazy abstract, Up: srfi lazy [Index]
Wadler et al. in the paper How to add laziness to a strict
language without even being odd [Wad98], provide a straightforward
recipe for transforming arbitrary lazy data structures and algorithms
into a strict language using delay and force.
However, it is known (see e.g. the SRFI-40 discussion list) that this transformation can lead to programs that suffer from unbounded space consumption, even if the original lazy algorithm was properly tail–recursive. Example Consider the following procedure, written in a hypothetical lazy language with Scheme syntax:
(define (stream-filter p? s)
(if (null? s) '()
(let ((h (car s))
(t (cdr s)))
(if (p? h)
(cons h (stream-filter p? t))
(stream-filter p? t)))))
According to the tranformation proposed in [Wad98], this algorithm can be espressed as follows in Scheme:
(define (stream-filter p? s)
(delay (force
(if (null? (force s)) (delay '())
(let ((h (car (force s)))
(t (cdr (force s))))
(if (p? h)
(delay (cons h (stream-filter p? t)))
(stream-filter p? t)))))))
The recipe, which we will modify below, is as follows:
(), cons) with delay.
force to arguments of deconstructors (e.g., car,
cdr and null?).
(delay (force …)).
However, evaluating the following with a sufficiently value for large–number will cause a typical Scheme implementation to run out of memory, despite the fact that the original (lazy) algorithm was iterative, only needing tail calls to evaluate the first element of the result stream.
(define (from n)
(delay (cons n (from (+ n 1)))))
(define large-number 1000000000)
(car (force (stream-filter (lambda (n) (= n large-number))
(from 0))))
The problem occurring in the above stream-filter example can
already be seen in the following simple infinite loop, expressed in our
hypothetical lazy language as:
(define (loop) (loop))
which becomes, according to the [Wad98] transformation:
(define (loop) (delay (force (loop))))
Taking the semantics of {delay, force} to be informally:
(force (delay expr)) = update promise : (delay expr)
with value of expr
return value in promise
we get:
(force (loop)) = update promise1 : (delay (force (loop)))
with value of (force (loop))
return value in promise1
= update promise1 : (delay (force (loop)))
with value of
update promise2 : (delay (force (loop)))
with value of (force (loop))
return value in promise2
return value in promise1
= update promise1 : (delay (force (loop)))
with value of
update promise2 : (delay (force (loop)))
with value of
update promise3 : (delay (force (loop)))
with value of (force (loop))
return value in promise3
return value in promise2
return value in promise1
= …
We see that an ever growing sequence of pending promises builds up until the heap is exhausted.
Expressing the above algorithm in terms of {delay, force} in
fact does not correctly capture common notions of call–by–need
evaluation semantics. For example, in a call–by–need language with
naive graph reduction semantics, the above algorithm would run in
bounded space since naive graph reduction is known to be tail–safe.
For a good discussion of this issue, see e.g. R. Jones Tail
recursion without space leaks [Jon98].
Our problem may be regarded as analogous to graph reduction, with promises corresponding to graph nodes and force corresponding to reduction. As described by Jones, one has to be careful with the order in which nodes are evaluated and overwritten to avoid space leaks. In our context this would correspond to the order in which promises are evaluated and overwritten when forced.
In the above example, naive graph reduction would correspond to the promise at the root being overwritten at each step before the next iteration is evaluated, thus avoiding the need for a growing sequence of unfulfilled promises representing (unnecessary) future copy operations.
The accumulation of unnecessary promises in the above examples is a consequence of suspensions being forced in increasingly nested contexts. In order to correctly simulate naive graph reduction we should instead find a way of forcing tail suspensions iteratively, each time overwriting the previous result.
A solution to this problem exists and is described (in a different context) in Compiling higher order languages into fully tail-recursive portable C, Feely et al. [Fee97]. This reference introduces a method widely known as the trampoline technique for evaluating tail contexts iteratively.
Adapting the trampoline technique to the situation at hand, we introduce
a new primitive lazy, which behaves like an “atomic” (delay
(force …)), and which will replace the combination (delay
(force …)) at procedure entry points. We also redefine delay and
force as below:
; type Promise a = lazy (Promise a) | eager a
(define-syntax lazy
(syntax-rules ()
((lazy exp)
(box (cons 'lazy (lambda () exp))))))
(define (eager x)
(box (cons 'eager x)))
(define-syntax delay
(syntax-rules ()
((delay exp) (lazy (eager exp)))))
(define (force promise)
(let ((content (unbox promise)))
(case (car content)
((eager) (cdr content))
((lazy) (let* ((promise* ((cdr content)))
(content (unbox promise))) ; *
(if (not (eqv? (car content) 'eager)) ; *
(begin (set-car! content (car (unbox promise*)))
(set-cdr! content (cdr (unbox promise*)))
(set-box! promise* content)))
(force promise))))))
(*) These two lines re-fetch and check the original promise in case
the first line of the let* caused it to be forced. For an example
where this happens, see reentrancy test 3 below.
(define (box x) (list x))
(define unbox car)
(define set-box! set-car!)
Our example is then coded (see the full recipe below):
(define (loop) (lazy (loop)))
When we now evaluate (force (loop)), the force procedure will
execute a top–level loop which will iteratively evaluate and overwrite
subsequent suspensions.
In the language of [Fee97], the iterative loop in force plays the role of “dispatcher”. The lazy form marks “control points” (procedure entry and return points). This technique is tail–safe because lazy procedures, instead of calling other lazy procedures directly, simply return a suspension representing a control point to be called upon the next iteration of the dispatcher loop in force. For more details, see [FMRW].
Next: srfi lazy spec, Previous: srfi lazy abstract, Up: srfi lazy [Index]