4.2.5 Delayed evaluation

lazy library 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 can be asked (by the force procedure) to evaluate ⟨expression⟩, and deliver the resulting value. The effect of ⟨expression⟩ returning multiple values is unspecified.

lazy library syntax: delay-force ⟨expression⟩ ¶

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.

lazy library procedure: force promise ¶

The force procedure forces the value of a promise created by delay, delay-force, or make-promise. If no value has been computed for the promise, then a value is computed and returned. The value of the promise must be cached (or “memoized”) so that if it is forced a second time, the previously computed value is returned. Consequently, a delayed expression is evaluated using the parameter values and exception handler of the call to force which first requested its value. If promise is not a promise, it may be returned unchanged.

(force (delay (+ 1 2)))   ⇒  3
(let ((p (delay (+ 1 2))))
  (list (force p) (force p)))
                               ⇒  (3 3)

(define integers
  (letrec ((next
            (lambda (n)
              (delay (cons n (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 (delay-force …) instead of (delay (force …)) around the body of the procedure ensures that an ever-growing sequence of pending promises does not exhaust available storage, because force will in effect force such sequences iteratively.

(define (stream-filter p? s)
  (delay-force
   (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

The following examples are not intended to illustrate good programming style, as delay, force, and delay-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

Various extensions to this semantics of delay, force and delay-force are supported in some implementations:

• Calling force on an object that is not a promise may simply return the object.
• It may be the case that there is no means by which a promise can be operationally distinguished from its forced value. That is, expressions like the following may evaluate to either #t or to #f, depending on the implementation:

  (eqv? (delay 1) 1)         ⇒ unspecified
  (pair? (delay (cons 1 2))) ⇒ unspecified
  

• Implementations may implement “implicit forcing,” where the value of a promise is forced by procedures that operate only on arguments of a certain type, like cdr and *. However, procedures that operate uniformly on their arguments, like list, must not force them.

  (+ (delay (* 3 7)) 13) ⇒ unspecified
  (car
    (list (delay (* 3 7)) 13)) ⇒ a promise
  

lazy library procedure: promise? obj ¶

The promise? procedure returns #t if its argument is a promise, and #f otherwise. Note that promises are not necessarily disjoint from other Scheme types such as procedures.

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