5.6. Delayed Evaluation


5.6. Delayed Evaluation

The syntactic form delay and the procedure force may be used in combination to implement lazy evaluation. An expression subject to lazy evaluation is not evaluated until its value is required and once evaluated is never reevaluated. delay and force appear in the Revised5 Report but not in the ANSI/IEEE standard.

(delay exp)

syntax

returns: a promise

The first time the promise is forced (with force), it evaluates exp, "remembering" the resulting value. Thereafter, each time the promise is forced, it returns the remembered value instead of reevaluating exp. See the examples given for force below.

(force promise)

procedure

returns: result of forcing promise

delay may be defined as

 (define-syntax delay   (syntax-rules ()     (( exp) (make-promise (lambda () exp))))) 

where make-promise is defined as

 (define make-promise   (lambda (p)     (let ((val #f) (set? #f))       (lambda ()         (if (not set?)             (let ((x (p)))               (if (not set?)                   (begin (set! val x)                          (set! set? #t)))))         val)))) 

With this definition of delay, force simply invokes the promise to force evaluation or to retrieve the saved value.

 (define force   (lambda (promise)     (promise))) 

The second test of the variable set? in make-promise is necessary in the unlikely event that, as a result of applying p, the promise is recursively forced. Since a promise must always return the same value, the result of the first application of p to complete is returned.

delay and force are typically used only in the absence of side effects, e.g., assignments, so that the order of evaluation is unimportant.

The benefit of using delay and force is that some amount of computation might be avoided altogether if it is delayed until absolutely required. Delayed evaluation may be used to construct conceptually infinite lists, or streams. The example below shows how a stream abstraction may be built with delay and force. A stream is a promise that, when forced, returns a pair whose cdr is a stream.

 (define stream-car   (lambda (s)     (car (force s)))) (define stream-cdr   (lambda (s)     (cdr (force s)))) (define counters   (let next ((n 1))     (delay (cons n (next (+ n 1)))))) (stream-car counters)  1 (stream-car (stream-cdr counters))  2 (define stream-add   (lambda (s1 s2)     (delay (cons              (+ (stream-car s1) (stream-car s2))              (stream-add (stream-cdr s1) (stream-cdr s2)))))) (define even-counters   (stream-add counters counters)) (stream-car even-counters)  2 (stream-car (stream-cdr even-counters))  4 




The Scheme Programming Language
The Scheme Programming Language
ISBN: 026251298X
EAN: 2147483647
Year: 2003
Pages: 98

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net