Lazy evaluation

With lazy evaluation, an actual parameter in a function call is not evaluated until the first time the value of the formal parameter is accessed. At that time, the actual parameter is evaluated, and the formal parameter is bound to the value. Subsequent references to the formal parameter do not cause reevaluation of the actual parameter. The major difference is that, if the formal parameter is never needed, the actual parameter is never evaluated.

E.g. suppose function F calls G(B,E1,E2) where E1 and E2 are complicated expressions, and G is defined as

function G(B,E1,E2)
 { if (B) then return(E1) else return(E2);
If B is true, then E2 is never evaluated; if B is false, then E1 is never evaluated.

In Scheme use (delay EXP) and (force P) to achieve this. (In ML one can get it, but it's not straightfoward. In Haskell, it is the default.)

E.g. (this is not good coding style, but makes the point).

(define (writeln X) (write X) (newline) X)

(define (f B) (g B (delay (writeln 'A)) (delay (writeln 'B))))

(define (g B X Y)
  (if B 
      (list (force X) (force X)) 
      (list (force Y) (force Y))))
(delay EXP) returns a promise. Once the promise is evaluated, it is destructively replaced by its value
top[32]=>(set! I 2)
value := 2
top[33]=>(set! Q (delay (set! I (+ I 1))))
value := #[]
top[34]=>(force Q)
value := 3
value := #[ fulfilled]
top[36]=>(force Q)
value := 3

Note the difference from pass by name, where the formal parameter is evaluated every time its value is referneced. Here the parameter is evaluated only the first time it is referenced, and that value is used afterward.

Useful when you have a long list of things to combine but you may stop before you need all the things. E.g.

;  adds up the elements in L as long as the sum is less than M; else, return M. 
;  note this evaluates only the elements of L that it needs.
(define (boundedSum L M)
   (define  (boundedSum1 L SUM)                  ; recursive subroutine
      (if (null? L) 
          (let ((S (+ SUM (force (car L)))))
              (if (> S M) 
                  (boundedSum1 (cdr L) S)))))  ; end boundedSum1

   (boundedSum1 L 0))    ; body of boundedSum

(boundedSum (list (delay EXP1) (delay EXP2) ... (delay EXPn)) M)  ; i
     typical call.

With pure side-effect free programming, lazy evaluation has the same semantics as pass by value, since the value of the actual parameter can't change between the time the function is called, and the time the formal parameter is referenced. Except that sometimes pass by value goes into an infinite loop or encounters an error condition, which lazy evaluation avoids.

Infinite lists and data structures

(define (f I) (delay (cons I (f (+ I 1)))))
; Note: A recursive function with no base case.

(define (icar L) (car (force L)))

(define (icdr L) (cdr (force L)))

(define (nth I L) 
  (if (> 0 I) 
      (let ((L1 (force L)))
        (cond ((null? L1) #f)
              ((= I 0) (car L1))
              (#t (nth (- I 1) (cdr L1)))))))

Binary tree

(define (node T) (car (force T)))
(define (left T) (cadr (force T)))
(define (right T) (caddr (force T)))

(define (bt1 L) (delay (list L (bt1 (cons 'A L)) (bt1 (cons 'B L)))))