Lazy evaluation (or call-by-need) delays evaluating an expression until it is actually needed; when it is evaluated, the result is saved so repeated evaluation is not needed. Lazy evaluation is a technique that can make some algorithms easier to express compactly or much more efficiently, or both. It is the normal evaluation mechanism for strict functional (side-effect-free) languages such as Haskell. However, automatic lazy evaluation is awkward to combine with side-effects such as input-output. It can also be difficult to implement lazy evaluation efficiently, as it requires more book-keeping.
Kawa, like other Schemes, uses “eager evaluation” - an expression
is normally evaluated immediately, unless it is wrapped in a special form.
Standard Scheme has some basic building blocks for “manual”
lazy evaluation, using an explicit
delay operator to
indicate that an expression is to be evaluated lazily,
yielding a promise,
force function to force evaluation of a promise.
This functionality is enhanced in
in R7RS-draft (based on SRFI 45),
and SRFI 41 (lazy lists aka streams).
Kawa makes lazy evaluation easier to use, by implicit forcing: The promise is automatically evaluated (forced) when used in a context that requires a normal value, such as arithmetic needing a number. Kawa enhances lazy evaluation in other ways, including support for safe multi-threaded programming.
delay construct is used together with the procedure
force to implement lazy evaluation or call by need.
The result of
(delay expression) is a
promise which at some point in the future may be asked (by the
force procedure) to evaluate expression, and deliver the
resulting value. The effect of expression returning multiple
values is unspecified.
delay-force construct is similar to
delay, but it is expected
that its argument evaluates to a promise.
(Kawa treats a non-promise value as if it were a forced promise.)
promise, when forced, will evaluate to whatever the original
promise would have evaluated to if it had been forced.
(delay-force expression) is
conceptually similar to
(delay (force expression)), with
the difference that forcing the result of
in effect result in a tail call to
(force expression), while
forcing the result of
(delay (force expression)) might
not. Thus iterative lazy algorithms that might result in a
long series of chains of
force can be rewritten
using delay-force to prevent consuming unbounded space
lazy is equivalent.
delay-force is from R7RS; the name
is from the older SRFI-45.
Returns a promise that when forced will return obj.
It is similar to
delay, but does not delay its argument;
it is a procedure rather than syntax.
The Kawa implementation just returns obj as-is. This is because Kawa treats as equivalent a value and forced promise evaluating to the value.
force procedure forces the value of promise.
As a Kawa extension, if the promise is not a promise (a value that
does not implement
gnu.mapping.Lazy) then the argument is returned unchanged.
If no value has been computed for the promise, then a value is computed and
returned. The value of the promise is cached (or “memoized”) so that
if it is forced a second time, the previously computed value is
(force (delay (+ 1 2))) ⇒ 3 (let ((p (delay (+ 1 2)))) (list (force p) (force p))) ⇒ (3 3) (define integers (letrec ((next (lambda (n) (cons n (delay (next (+ n 1))))))) (next 0))) (define head (lambda (stream) (car (force stream)))) (define tail (lambda (stream) (cdr (force stream)))) (head (tail (tail integers))) ⇒ 2
The following example is a mechanical transformation of
a lazy stream-filtering algorithm into Scheme. Each call
to a constructor is wrapped in
delay, and each argument
passed to a deconstructor is wrapped in
force. The use
(lazy ...) instead of
(delay (force ...)) around
the body of the procedure ensures that an ever-growing
sequence of pending promises does not exhaust the heap.
(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)))))) (head (tail (tail (stream-filter odd? integers)))) ⇒ 5
force as many times as necessary to produce a non-promise.
(A non-promise is a value that does not implement
or if it does implement
gnu.mapping.Lazy then forcing the value
getValue method yields the receiver.)
force* function is a Kawa extension.
Kawa will add implicit calls to
in most contexts that need it, but you can also call it explicitly.
The following examples are not intended to illustrate good
programming style, as
force are mainly
intended for programs written in the functional style.
However, they do illustrate the property that only one value is
computed for a promise, no matter how many times it is
(define count 0) (define p (delay (begin (set! count (+ count 1)) (if (> count x) count (force p))))) (define x 5) p ⇒ a promise (force p) ⇒ 6 p ⇒ a promise, still (begin (set! x 10) (force p)) ⇒ 6
If you pass a promise as an argument to a function like
if must first be forced to a number. In general, Kawa does this
automatically (implicitly) as needed, depending on the context.
(+ (delay (* 3 7)) 13) ⇒ 34
cons have no problems with promises, and automatic forcing
would be undesirable.
Generally, implicit forcing happens for arguments that require a
specific type, and does not happen for arguments that work on
any type (or
Implicit forcing happens for:
equal?are forced, though the operands to
displaybut not the value to be emitted by a
Type membership tests, such as the
generally do not force their values.
The exact behavior for when implicit forcing happens is a work-in-progress: There are certainly places where implicit forcing doesn’t happen while it should; there are also likely to be places where implicit forcing happens while it is undesirable.
Most Scheme implementations are such that a forced promise behaves differently from its forced value, but some Scheme implementions are such that there is no means by which a promise can be operationally distinguished from its forced value. Kawa is a hybrid: Kawa tries to minimize the difference between a forced promise and its forced value, and may freely optimize and replace a forced promise with its value.
A blank promise is a promise that doesn’t (yet) have a value or a rule for calculating the value. Forcing a blank promise will wait forever, until some other thread makes the promise non-blank.
Blank promises are useful as a synchronization mechanism - you can use it to safely pass data from one thread (the producer) to another thread (the consumer). Note that you can only pass one value for a given promise: To pass multiple values, you need multiple promises.
(define p (promise)) (future ;; Consumer thread (begin (do-stuff) (define v (force promise)) ; waits until promise-set-value! (do-stuff-with v))) ;; Producer thread ... do stuff ... (promise-set-value! p (calculate-value))
promise as a zero-argument constructor
creates a new blank promise.
This calls the constructor for
You can also create a non-blank promise, by setting one
Doing so is equivalent to calling
promise-set-exception! on the resulting promise.
(delay exp) is equivalent to:
(promise thunk: (lambda() exp))
The following four procedures require that their first arguments be blank promises. When the procedure returns, the promise is no longer blank, and cannot be changed. This is because a promise is conceptually a placeholder for a single “not-yet-known” value; it is not a location that can be assigned multiple times. The former enables clean and safe (“declarative") use of multiple threads; the latter is much trickier.
Sets the value of the promise to value, which makes the promise forced.
Associate exception with the promise. When the promise is forced the exception gets thrown.
Bind the promise to be an alias of other. Forcing promise will cause other to be forced.
Associate thunk (a zero-argument procedure) with the promise. The first time the promise is forced will causes the thunk to be called, with the result (a value or an exception) saved for future calls.
make-promise procedure returns a promise which,
when forced, will return obj. It is similar to
does not delay its argument: it is a procedure rather than
syntax. If obj is already a promise, it is returned.
Because of Kawa’s implicit forcing, there is seldom a
need to use
make-promise, except for portability.
This parameterized type is the type of promises that evaluate to
an value of type
It is equivalent to the Java interface
The implementation class for promises is usually
though there are other classes that implement
gnu.mapping.Future, used for futures,
which are promises evaluated in a separate thread.
Note the distinction between the types
(the type of actual (eager) integer values), and
(the type of (lazy) promises that evaluate to integer).
The two are compatible: if a
promise[integer] value is provided
in a context requiring an
integer then it is automatically
evaluated (forced). If an
integer value is provided
in context requiring a
promise[integer], that conversion is basically
a no-op (though the compiler may wrap the
in a pre-forced promise).
In a fully-lazy language there would be no distinction, or at least the promise type would be the default. However, Kawa is a mostly-eager language, so the eager type is the default. This makes efficient code-generation easier: If an expression has an eager type, then the compiler can generate code that works on its values directly, without having to check for laziness.