Next: Repeat patterns and expressions, Previous: Local binding constructs, Up: Program structure [Contents][Index]
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,
and a force
function to force evaluation of a promise.
This functionality is enhanced in
SRFI 45,
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.
The 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.
The 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.)
The returned
promise, when forced, will evaluate to whatever the original
promise would have evaluated to if it had been forced.
The expression (delay-force expression)
is
conceptually similar to (delay (force expression))
, with
the difference that forcing the result of delay-force
will
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 delay
and force
can be rewritten
using delay-force to prevent consuming unbounded space
during evaluation.
Using delay-force
or lazy
is equivalent.
The name delay-force
is from R7RS; the name lazy
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.
The 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
returned.
(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
of (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
Does force
as many times as necessary to produce a non-promise.
(A non-promise is a value that does not implement gnu.mapping.Lazy
,
or if it does implement gnu.mapping.Lazy
then forcing the value
using the getValue
method yields the receiver.)
The force*
function is a Kawa extension.
Kawa will add implicit calls to force*
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 delay
, lazy
, and 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
forced.
(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 sqrt
if must first be forced to a number. In general, Kawa does this
automatically (implicitly) as needed, depending on the context.
For example:
(+ (delay (* 3 7)) 13) ⇒ 34
Other functions,
like 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 Object
).
Implicit forcing happens for:
string-ref
;
eqv?
and equal?
are forced,
though the operands to eq?
are not;
display
but not the
value to be emitted by a write
;
Type membership tests, such as the instance?
operation,
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))
Calling promise
as a zero-argument constructor
creates a new blank promise.
This calls the constructor for gnu.mapping.Promise
.
You can also create a non-blank promise, by setting one
of the value
, alias
, thunk
, or exception
properties.
Doing so is equivalent to calling promise-set-value!
,
promise-set-alias!
, promise-set-thunk!
, or
promise-set-exception!
on the resulting promise.
For example: (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.
The make-promise
procedure returns a promise which,
when forced, will return obj. It is similar to delay
, but
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 T
.
It is equivalent to the Java interface gnu.mapping.Lazy<T>
.
The implementation class for promises is usually gnu.mapping.Promise
,
though there are other classes that implement Lazy
,
most notably gnu.mapping.Future
, used for futures,
which are promises evaluated in a separate thread.
Note the distinction between the types integer
(the type of actual (eager) integer values), and promise[integer]
(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 integer
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.
Next: Repeat patterns and expressions, Previous: Local binding constructs, Up: Program structure [Contents][Index]