r7rs-small-texinfo

R7RS-small Scheme converted to Texinfo.
git clone https://kaka.farm/~git/r7rs-small-texinfo
Log | Files | Refs | README | LICENSE

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