delayed-computation


What is delayed computation?

Eager and Lazy Evaluation

Scheme eagerly evaluates the components of a procedure combination; that is, it will evaluate all arguments and the procedure itself in a call before transferring control to the procedure. Certain special forms do not eagerly evaluate their operands, however; the most common example is if. It must be a special form; otherwise both of the branches could be evaluated, whereas only one of them should have been. Observe this procedure my-if that uses cond to conditionalize:

 (define (my-if predicate consequent alternative) 
   (cond (predicate consequent) 
         (else alternative))) 

If one tried to use it, the results would be not what was intended:

 (my-if #t  
        (display "my if was true!")  
        (display "my if was false!")) 
   ; prints: my if was true! 
   ;         my if was false! 
   ; or:     my if was false! 
   ;         my if was true! 

What is going on here is that the arguments to my-if are being evaluated first; only after all the arguments are evaluated is my-if called and the conditionalization with cond performed. The result of this is that the consequent and alternative expressions are already evaluated before the predicate is actually checked.

By contrast, there is lazy evaluation. Using a lazy evaluation order, the arguments in a function call are not evaluated before the function is called. Only once the function needs its arguments -- for example, if the function itself applies one of the arguments, or if the function passes one of the arguments to a primitive operation -- will they be evaluated. Lazy evaluation is also known as call-by-need, because arguments are evaluated only when needed. In a lazily evaluated language, my-if would be a valid conditional operator, because the consequent & alternative branches would be evaluated only when needed (as the result of the cond expression).

Delaying computation to make an eager evaluator lazy

By delaying the computation, we can avoid the evaluation of our consequent & alternative, until it is actually necessary, at which point evaluation of only one of them is necessary. One method of delaying the computation is by wrapping the consequent & alternative by in thunk?s and applying the thunk?s when their return values are desired, like so:

 (define (my-verbose-and-thunkified-if predicate consequent alternative) 
   (cond (predicate (consequent)) 
         (else (alternative)))) 
  
 (my-verbose-and-thunkified-if #t  
   (lambda () (display "my if was true!"))   ; THUNK! 
   (lambda () (display "my if was false!"))) ; THUNK! 
   ; prints: my if was true! 

As one can see, it works just fine, if not a little unwieldy.

How do I do it in scheme?

The name my-verbose-and-thunkified-if should have tipped you off that I am up to something. Instead of using thunks, and applying them all the time, Scheme has a special form and a procedure for automatically delaying memoized computations.

I promise I will do it... later.

A promise is, quite simply, the promise to evaluate an expression later. It is not evaluated until explicitly requested, although R5RS permits promises to be evaluated implicitly when passed to primitive operations and their result be used instead. R5RS provides two primitives for lazy evaluation, the syntax delay and the procedure force.

R5RS's two laziness primitives

(delay expression)

creates a promise to execute the expression.

(force promise)

either returns the cached result of promise, if it has already been run, or forces the evaluation of promise and caches & returns the result.

Why should I do it?

Infinite streams

Of course you cannot represent an infinite series of numbers inside a computer. However, you can represent the potential of an infinite series, and streams are a common way to do this.

Streams are quite simply lists whose construction is computationally delayed. From the SICP:

Cons-stream is a special form defined so that (cons-stream a b) is equivalent to (cons a (delay b)). What this means is that we will construct streams using pairs. However, rather than placing the value of the rest of the stream into the cdr of the pair we will put there a promise to compute the rest if it is ever requested. Stream-car and stream-cdr can now be defined as procedures:

 (define (stream-car stream) (car stream)) 
 (define (stream-cdr stream) (force (cdr stream))) 

Stream-car selects the car of the pair; stream-cdr selects the cdr of the pair and evaluates the delayed expression found there to obtain the rest of the stream

So, a list of infinine ones can be defined as:

 (define ones (cons 1 (delay ones))) 

Or, using the above definition:

 (define ones (cons-stream 1 ones)) 

We can also define operations to work on streams. For instance, now that we have the stream of ones defined, we can define an operation to add the parallel elements of two streams together:

 (define (add-stream-elements s1 s2) 
   (cons (+ (stream-car s1) (stream-car s2)) 
         (delay (add-stream-eltements (stream-cdr s1) 
                                      (stream-cdr s2))))) 

For further information see: SICP Chapter-3.5


category-code