Motivation for Lazy Evaluation

def ite[A](c : Boolean, thenV : A, elseV : A) = {
  if (c) thenV
  else elseV
def bigFraction(x : Int, y : Int) : Boolean = {
  ite(y==0, true, x/y > 100)

Ideally, each function call (like ite(c,t,e) ) can be replaced by its body without changing program behavior.

This is not the case when procedure arguments are always evaluated first

  • this semantics is called call by value and is common in imperative languages
  • it can be implemented by storing actual argument values on stack before call, as we saw

Alternative is call by name

  • parameters represent expressions
  • accessing the parameter evaluates the expression
  • if we access the variable N times, the expression is re-evaluated N times
  • expressions are represented as higher-order functions that take dummy argument (similar to replacing A with (Unit ⇒ A))

Lazy evaluation (call by need) avoids re-evaluating expression:

  • when expression is accessed for the first time, its value is cached
  • subsequent uses immediately return previously computed value


Suppose the body of function f accesses its argument x during evaluation N times, where $N \in \{ 0,1,2, \ldots \}$

evaluation strategy number of times argument expression evaluated
call by value 1
call by name N
lazy evaluation min(1,N)