Next: , Previous: , Up: srfi lazy   [Index]

2.24.2 Rationale

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:

  1. Wrap all constructors (e.g., (), cons) with delay.
  2. Apply force to arguments of deconstructors (e.g., car, cdr and null?).
  3. Wrap procedure bodies with (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))))

Why the space leak occurs

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.

Why the above is not call–by–need

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 solution

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: , Previous: , Up: srfi lazy   [Index]