Lazy or Eager? Order of Evaluation in Lambda Calculus and OCaml

Recall in lambda calculus, two items side by side is an application.  One applies the left item (the function) to the right item (the input).  E.g.:

f x

is read as “apply f to x“, in which f and x can be any lambda expressions.  Therefore, f and/or x may be expressions that can be evaluated first.  In fact, there can be nested expressions in them as well.  As mentioned in this post, the order of evaluating your lambda expression matters.  In which order should you evaluate the expressions?

Always Evaluate the Function Expression First

The first important rule to follow is to always evaluate the function expression (the left item) first.  Combining with currying, one can generalize this rule to “work from left to right“.  E.g., in:

(λx.λy.(y x) λp.λq.p) λi.i

The left item, (λx.λy.(y x) λp.λq.p), is the function, and the right item,  λi.i, is the argument.  We start with evaluating the function.  So:

(λx.λy.(y x) λp.λq.p) λi.i
=> λy.(y λp.λq.p) λi.i      (β-reduction of x with argument λp.λq.p)
=> λi.i λp.λq.p      (β-reduction of y with argument λi.i)
=> λp.λq.p

Applicative Order Versus Normal Order

We know what to do on the function side:  we always evaluate it first, working from left to right.  What about the argument side?  Do we evaluate it before passing it to the function?

​If we evaluate the argument first before passing it to the function, it’s called

• ‘applicative order‘, or
• ‘call by value‘, or
• ‘eager evaluation‘.

E.g., if we evaluate the following in the applicative order:

λq.q (λx.x λa.λb.a)
=> λq.q λa.λb.a      (β-reduction of x with λa.λb.a)
=> λa.λb.a

If we do not evaluate the argument first, and pass the unevaluated argument to the function, it’s called:

• ‘normal order’, or
• ‘call by name‘, or
• ‘lazy evaluation‘.

E.g.:

λq.q (λx.x λa.λb.a) 
=> λx.x λa.λb.a      (β-reduction of q with λx.x λa.λb.a) 
=> λa.λb.a

You can see that both order yield the same result.  In fact, Church and Rosser proved that if both evaluation orders yield well-defined results then they yield the same result.

Which order should you use?  The applicative order is more efficient but the normal order has the advantage that you can guarantee termination of a lambda expression if it can ever terminate!  (Also proven by Church and Rosser.)

Order of Evaluation in OCaml

Remember that lambda calculus is the basis for functional programming languages!   Popular functional programming languages like Haskell and OCaml use different orders of evaluation by default.  OCaml is by default ‘eager’, but you can delay evaluation using the Lazy module.

You can consult the Wikipedia page regarding the orders of evaluation of various programming languages.