7.5.29 SRFI-45 - Primitives for Expressing Iterative Lazy Algorithms

This subsection is based on the specification of SRFI-45 written by André van Tonder.

Lazy evaluation is traditionally simulated in Scheme using delay and force. However, these primitives are not powerful enough to express a large class of lazy algorithms that are iterative. Indeed, it is folklore in the Scheme community that typical iterative lazy algorithms written using delay and force will often require unbounded memory.

This SRFI provides set of three operations: {lazy, delay, force}, which allow the programmer to succinctly express lazy algorithms while retaining bounded space behavior in cases that are properly tail-recursive. A general recipe for using these primitives is provided. An additional procedure eager is provided for the construction of eager promises in cases where efficiency is a concern.

Although this SRFI redefines delay and force, the extension is conservative in the sense that the semantics of the subset {delay, force} in isolation (i.e., as long as the program does not use lazy) agrees with that in R5RS. In other words, no program that uses the R5RS definitions of delay and force will break if those definition are replaced by the SRFI-45 definitions of delay and force.

Guile also adds promise? to the list of exports, which is not part of the official SRFI-45.

Scheme Procedure: promise? obj

Return true if obj is an SRFI-45 promise, otherwise return false.

Scheme Syntax: delay expression

Takes an expression of arbitrary type a and returns a promise of type (Promise a) which at some point in the future may be asked (by the force procedure) to evaluate the expression and deliver the resulting value.

Scheme Syntax: lazy expression

Takes an expression of type (Promise a) and returns a promise of type (Promise a) which at some point in the future may be asked (by the force procedure) to evaluate the expression and deliver the resulting promise.

Scheme Procedure: force expression

Takes an argument of type (Promise a) and returns a value of type a as follows: If a value of type a has been computed for the promise, this value is returned. Otherwise, the promise is first evaluated, then overwritten by the obtained promise or value, and then force is again applied (iteratively) to the promise.

Scheme Procedure: eager expression

Takes an argument of type a and returns a value of type (Promise a). As opposed to delay, the argument is evaluated eagerly. Semantically, writing (eager expression) is equivalent to writing

(let ((value expression)) (delay value)).

However, the former is more efficient since it does not require unnecessary creation and evaluation of thunks. We also have the equivalence

(delay expression) = (lazy (eager expression))

The following reduction rules may be helpful for reasoning about these primitives. However, they do not express the memoization and memory usage semantics specified above:

(force (delay expression)) -> expression
(force (lazy  expression)) -> (force expression)
(force (eager value))      -> value

Correct usage

We now provide a general recipe for using the primitives {lazy, delay, force} to express lazy algorithms in Scheme. The transformation is best described by way of an example: Consider the stream-filter algorithm, expressed in a hypothetical lazy language as

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

This algorithm can be expressed as follows in Scheme:

(define (stream-filter p? s)
  (lazy
     (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))))))

In other words, we

• wrap all constructors (e.g., '(), cons) with delay,
• apply force to arguments of deconstructors (e.g., car, cdr and null?),
• wrap procedure bodies with (lazy ...).

This document was generated on April 20, 2013 using texi2html 5.0.