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.
Syntax: delay expression
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.
Syntax: delay-force expression
Syntax: lazy expression
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.
Procedure: eager obj
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.
Procedure: force promise
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
Procedure: force* promise
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:
arguments to arithmetic functions;
the sequence and the index in indexing operations, like string-ref;
the operands to eqv? and equal? are forced,
though the operands to eq? are not;
port operands to port functions;
the value to be emitted by a display but not the
value to be emitted by a write;
the function in an application.
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))
Constructor: promise
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.
Procedure: promise-set-value! promise value
Sets the value of the promise to value,
which makes the promise forced.
Procedure: promise-set-exception! promise exception
Associate exception with the promise.
When the promise is forced the exception gets thrown.
Procedure: promise-set-alias! promise other
Bind the promise to be an alias of other.
Forcing promise will cause other to be forced.
Procedure: promise-set-thunk! promise thunk
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.
Procedure: make-promise obj
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.
Type: promise[T]
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.
