delayed-evaluation.texinfo (5474B)
1 @node Delayed evaluation 2 @subsection Delayed evaluation 3 4 @cindex promise 5 6 @deffn {lazy library syntax} delay @svar{expression} 7 8 The @code{delay} construct is used together with the procedure @code{force} to 9 implement @define{lazy evaluation} or @define{call by need}. 10 @code{(delay} @svar{expression}@code{)} returns an object called a 11 @define{promise} which at some point in the future can be asked (by 12 the @code{force} procedure) to evaluate 13 @svar{expression}, and deliver the resulting value. 14 The effect of @svar{expression} returning multiple values 15 is unspecified. 16 17 @end deffn 18 19 @deffn {lazy library syntax} delay-force @svar{expression} 20 21 The expression @code{(delay-force} @var{expression}@code{)} is conceptually similar to 22 @code{(delay (force} @var{expression}@code{))}, 23 with the difference that forcing the result 24 of @code{delay-force} will in effect result in a tail call to 25 @code{(force} @var{expression}@code{)}, 26 while forcing the result of 27 @code{(delay (force} @var{expression}@code{))} 28 might not. Thus 29 iterative lazy algorithms that might result in a long series of chains of 30 @code{delay} and @code{force} 31 can be rewritten using @code{delay-force} to prevent consuming 32 unbounded space during evaluation. 33 34 @end deffn 35 36 @deffn {lazy library procedure} force promise 37 38 The @code{force} procedure forces the value of a @var{promise} created 39 by @code{delay}, @code{delay-force}, or @code{make-promise}. 40 If no value has been computed for the promise, then a value is 41 computed and returned. The value of the promise must be cached (or 42 ``memoized'') so that if it is forced a second time, the previously 43 computed value is returned. 44 Consequently, a delayed expression is evaluated using the parameter 45 values and exception handler of the call to @code{force} which first 46 requested its value. 47 If @var{promise} is not a promise, it may be returned unchanged. 48 49 @lisp 50 (force (delay (+ 1 2))) @result{} 3 51 (let ((p (delay (+ 1 2)))) 52 (list (force p) (force p))) 53 @result{} (3 3) 54 55 (define integers 56 (letrec ((next 57 (lambda (n) 58 (delay (cons n (next (+ n 1))))))) 59 (next 0))) 60 (define head 61 (lambda (stream) (car (force stream)))) 62 (define tail 63 (lambda (stream) (cdr (force stream)))) 64 65 (head (tail (tail integers))) 66 @result{} 2 67 @end lisp 68 69 @end deffn 70 71 The following example is a mechanical transformation of a lazy 72 stream-filtering algorithm into Scheme. Each call to a constructor is 73 wrapped in @code{delay}, and each argument passed to a deconstructor is 74 wrapped in @code{force}. The use of @code{(delay-force @dots{})} instead of 75 @code{(delay (force @dots{}))} around the body of the procedure ensures that an 76 ever-growing sequence of pending promises does not 77 exhaust available storage, 78 because @code{force} will in effect force such sequences iteratively. 79 80 @lisp 81 (define (stream-filter p? s) 82 (delay-force 83 (if (null? (force s)) 84 (delay '()) 85 (let ((h (car (force s))) 86 (t (cdr (force s)))) 87 (if (p? h) 88 (delay (cons h (stream-filter p? t))) 89 (stream-filter p? t)))))) 90 91 (head (tail (tail (stream-filter odd? integers)))) @result{} 5 92 @end lisp 93 94 The following examples are not intended to illustrate good programming 95 style, as @code{delay}, @code{force}, and @code{delay-force} are mainly intended 96 for programs written in the functional style. 97 However, they do illustrate the property that only one value is 98 computed for a promise, no matter how many times it is forced. 99 100 @lisp 101 (define count 0) 102 (define p 103 (delay (begin (set! count (+ count 1)) 104 (if (> count x) 105 count 106 (force p))))) 107 (define x 5) 108 p @result{} @r{a promise} 109 (force p) @result{} 6 110 p @result{} @r{a promise, still} 111 (begin (set! x 10) 112 (force p)) @result{} 6 113 @end lisp 114 115 Various extensions to this semantics of @code{delay}, @code{force} and 116 @code{delay-force} are supported in some implementations: 117 118 @itemize 119 @item 120 Calling @code{force} on an object that is not a promise may simply return the object. 121 122 @item 123 It may be the case that there is no means by which a promise can be operationally 124 distinguished from its forced value. That is, expressions like the following may evaluate 125 to either @code{#t} or to @code{#f}, depending on the implementation: 126 127 @lisp 128 (eqv? (delay 1) 1) @result{} @r{unspecified} 129 (pair? (delay (cons 1 2))) @result{} @r{unspecified} 130 @end lisp 131 132 @item 133 Implementations may implement ``implicit forcing,'' where the value of a promise is 134 forced by procedures that operate only on arguments of a certain type, like 135 @code{cdr} and @code{*}. 136 However, procedures that operate uniformly on their arguments, like 137 @code{list}, must not 138 force them. 139 140 @lisp 141 (+ (delay (* 3 7)) 13) @result{} @r{unspecified} 142 (car 143 (list (delay (* 3 7)) 13)) @result{} @r{a promise} 144 @end lisp 145 @end itemize 146 147 @deffn {lazy library procedure} promise? obj 148 149 The promise? procedure returns @code{#t} if its argument is a promise, and 150 @code{#f} otherwise. Note 151 that promises are not necessarily disjoint from other Scheme types such as procedures. 152 @end deffn 153 154 @deffn {lazy library procedure} make-promise obj 155 156 The make-promise procedure returns a promise which, when forced, will return 157 @var{obj}. It is similar to delay, but does not delay its argument: it is a procedure rather than 158 syntax. If 159 @var{obj} is already a promise, it is returned. 160 @end deffn