Next: SRFI-46, Previous: SRFI-43, Up: SRFI Support [Contents][Index]
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.
Return true if obj is an SRFI-45 promise, otherwise return false.
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.
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.
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.
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
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
'(), cons) with delay,
force to arguments of deconstructors (e.g., car,
cdr and null?),
(lazy ...).
Next: SRFI-46, Previous: SRFI-43, Up: SRFI Support [Contents][Index]