Lazy evaluation

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.

Delayed evaluation

Syntax: delay expression

The delay construct is used together with the procedure force to implement lazy evaluation or call by need.

(delay expression) returns an object called 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

Implicit forcing

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 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.

Blank promises

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 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.

Lazy and eager types

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).

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.