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.
delayconstruct is used together with the procedure
forceto implement lazy evaluation or call by need.
(delayreturns an object called a promise which at some point in the future may be asked (by the
forceprocedure) to evaluate
expression, and deliver the resulting value. The effect of
expressionreturning multiple values is unspecified.
delay-forceconstruct 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.
(delay-forceis conceptually similar to
(delay (force, with the difference that forcing the result of
delay-forcewill in effect result in a tail call to
(force, while forcing the result of
(delay (forcemight not. Thus iterative lazy algorithms that might result in a long series of chains of
forcecan be rewritten using delay-force to prevent consuming unbounded space during evaluation.
lazyis equivalent. The name
delay-forceis from R7RS; the name
lazyis 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
objas-is. This is because Kawa treats as equivalent a value and forced promise evaluating to the value.
forceprocedure forces the value of
promise. As a Kawa extension, if the
promiseis 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
forceas 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.Lazythen forcing the value using the
getValuemethod yields the receiver.)
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
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:
arguments to arithmetic functions;
the sequence and the index in indexing operations, like
the operands to
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
the function in an application.
Type membership tests, such as the
generally do not force their values.
The exact behavior for when implicit forcing 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 distingished 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))
promiseas 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
exceptionproperties. Doing so is equivalent to calling
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 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
value, which makes the
promise. When the
promiseis forced the
promiseto be an alias of
otherto be forced.
thunk(a zero-argument procedure) with the
promise. The first time the
promiseis forced will causes the
thunkto be called, with the result (a value or an exception) saved for future calls.
make-promiseprocedure 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
objis 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
(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).
If a fully-lazy language there would be no distinction, or at least the promise type would be the default. However, Kawa is 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.