All the parameter-passing mechanisms we have discussed so far are eager: they always find a value for each operand. We now turn to a very different form of parameter passing, called lazy evaluation. Under lazy evaluation, an operand in a procedure call is not evaluated until it is needed by the procedure body. If the body never refers to the parameter, then there is no need to evaluate it.

• Under lazy evaluation, we do not evaluate an operand expression until it is needed.
• Therefore we associate the bound variable of a procedure with an unevaluated operand.
• When the procedure body needs the value of its bound variable, the associated operand is evaluated.
• We sometimes say that the operand is frozen when it is passed unevaluated to the procedure, and that it is thawed when the procedure evaluates it.

Interpreter

(define value-of
	...
	(call-exp (rator rand)
		(let ((proc (expval->proc (value-of rator env)))
					(arg (value-of-operand rand env)))
			(apply-procedure proc arg)))
	...)

;; apply-procedure : Proc × Ref → ExpVal 
(define apply-procedure
    (lambda (proc1 val)
      (cases proc proc1
        (procedure (var body saved-env)
          (value-of body (extend-env var val saved-env))))))

Values

We need to accommodate both lazy evaluation, effects, and eager evaluation (for let). We therefore let our denoted values be references to locations containing either expressed values or thunks.

• ExpVal = Int + Bool + Proc
• DenVal = Ref(ExpVal + Thunk)

Thunk

Of course we will also have to include the environment in which that procedure is to be evaluated. To do this, we introduce a new data type of thunks. A thunk consists of an expression and an environment.

• When a procedure needs to use the value of its bound variable, it will evaluate the associated thunk.

(define-datatype thunk thunk? 
	(a-thunk
    (exp1 expression?)
    (env environment?)))

Our policy for allocating new locations will be similar to the one we used for call-by-reference:

• If the operand is a variable, then we pass its denotation, which is a reference.
• Otherwise, we pass a reference to a new location containing a thunk for the unevaluated argument.

;; value-of-operand : Exp × Env → Ref 
(define value-of-operand
    (lambda (exp env)
      (cases expression exp
				(var-exp (var) (apply-env env var)) 
				(else (newref (a-thunk exp env))))))

;; value-of-thunk : Thunk → ExpVal 
(define value-of-thunk
    (lambda (thnk)
      (cases thunk thnk
        (a-thunk (exp1 saved-env)
          (value-of exp1 saved-env))))

Call By Name