Skip to main content

Applicative-Order vs Normal-Order Evaluation

What This Concept Is​

Given (f (g x)), when do we evaluate (g x)?

  • Applicative order: evaluate operator and operands first, then apply the procedure. This is what Scheme, Python, Java, C, and almost every mainstream language do. Arguments are values by the time the body runs.
  • Normal order ("call by name", "lazy"): substitute the expression for the parameter and only evaluate it when its value is actually needed. Haskell is famously normal-order; SICP discusses lazy variants in §4.2.

Both produce the same result for every program that terminates and has no side effects -- SICP makes that claim precise. They differ on:

  • Termination. Normal order can give answers where applicative order loops. (define (loop) (loop)) passed as an argument to a function that never uses it kills an applicative evaluator and is harmless in a normal-order one.
  • Work. Applicative order evaluates each argument once; normal order may evaluate the same argument many times (unless memoization -- "call by need" -- is added).
  • Mutation. Once side effects exist, the two models give different observable behavior. Order and count of effects change.

Why It Matters Here​

It is SUPPORTING in this module because most engineers will spend their careers in applicative-order languages. It matters anyway because:

  • Streams (Concept 14) are exactly a way to smuggle a little normal-order into an applicative-order language. The point of delay/force is to postpone evaluation until forced.
  • Interpreter design (Concepts 10-12) requires you to pick an evaluation order consciously. SICP's metacircular evaluator is applicative; §4.2 builds the lazy variant.
  • Short-circuit operators (and, or, if) are the little bits of normal-order every applicative language already has. Knowing that helps you see why they are not ordinary functions.

Concrete Example​

(define (try p q) (if (= p 0) 1 q))
(try 0 (/ 1 0))
  • In applicative order (Scheme default): (/ 1 0) is evaluated before try is called. Division by zero error.
  • In normal order: (/ 1 0) is not evaluated because q is not used when p = 0. Result: 1.

This is why if in all applicative languages is a special form, not a function: otherwise you could never use it to guard against evaluating an undefined branch.

A cost example in normal order:

(define (square x) (* x x))
(square (+ 1 2))
; Applicative: (+ 1 2) -> 3; then (* 3 3) -> 9. One + and one *.
; Normal:     (* (+ 1 2) (+ 1 2)) -> 9. Two + calls.

Lazy (memoized normal) evaluates (+ 1 2) once and caches.

In Python, you can simulate normal order with zero-argument lambdas:

def if_fn(cond, then_thunk, else_thunk):
    return then_thunk() if cond else else_thunk()

if_fn(p == 0, lambda: 1, lambda: 1/q)   # safe when q == 0

Common Confusion / Misconception​

  1. "Lazy and normal are the same." Strictly, lazy = normal order + memoization ("call by need"). Haskell is lazy; pure normal order would re-compute. Stream memoization (delay/force) turns normal into lazy.
  2. "Scheme is lazy." It is not. Streams are a library on top of ordinary applicative Scheme. Racket's #lang lazy exists but is opt-in.
  3. "Normal order is always better." It gives termination on more programs, but it interacts badly with side effects and can repeat work arbitrarily. It is a choice, not an improvement.
  4. Confusing with short-circuit logic. a && b in C is not "normal order evaluation" -- it is a specific operator the language short-circuits. Most of C is strictly applicative.

How To Use It​

When writing:

  • Prefer applicative order for code that has side effects; mental model is simpler.
  • Use explicit laziness (delay, lazy, generators, thunks) where you need to postpone work or build infinite data structures.

When reviewing:

  • If a function argument could be expensive or might blow up, and is conditional, flag that it is being computed eagerly at the call site.
  • If a language has both if-expression and user-defined functions, notice which cannot be user-defined -- it tells you the evaluation order of the rest.

Check Yourself​

  1. Why must if be a special form in an applicative-order language?
  2. Give a one-line program that terminates under normal order and diverges under applicative order.
  3. What is the precise difference between "normal order" and "call by need"?

Mini Drill or Application​

Write a Scheme my-if procedure that is not a special form: (my-if c t e) = (cond (c t) (else e)). Now use it to guard a division by zero. Watch it fail under applicative order. Then rewrite it taking two thunks: (my-if c (lambda () t) (lambda () e)). Verify the thunked version works, and state in one sentence why.

Read This Only If Stuck​