Evaluation Strategies: Call-by-Value, Name, and Need

An evaluation strategy (also called a reduction strategy or parameter-passing discipline at the semantic level) is a deterministic rule for choosing, at each step of computation, which subexpression to reduce next when several redexes (reducible expressions) are available. In the pure Lambda Calculus, a term $(\lambda x.\,e)\,a$ — call it a beta-redex — can be reduced by substituting `a` for `x` in `e`, written $e[x := a]$. But if `a` itself contains reducible subexpressions, and `e` may or may not use `x`, there is a genuine choice about what to do first. That choice is the evaluation strategy. Three strategies dominate the theory and practice of programming languages:

Call-by-value (CBV). Reduce the argument `a` to a value (a normal form that cannot be reduced further, such as a number or a lambda abstraction) before performing the substitution. Formally, the reduction rule is restricted:

If the argument is not yet a value, it must be reduced first. This is the strategy of C, Java, Python, OCaml, Scheme, and most mainstream languages. It corresponds operationally to the everyday notion of "evaluate the arguments, then call the function."

Call-by-name (CBN). Substitute the argument expression unevaluated directly into the body:

If `x` occurs multiple times in `e`, each occurrence carries its own copy of `a`, and each is evaluated independently, redundantly, whenever it is actually needed. If `x` does not occur in `e` at all, `a` is never evaluated — dead arguments cost nothing and cannot cause divergence or unwanted side effects.

Call-by-need. Operationally identical to call-by-name in what gets evaluated and when it is first demanded, but the argument is evaluated at most once: the first time it is forced, its value is computed and then memoized (cached) in a shared location, so every other occurrence of `x` reuses the cached value instead of recomputing. This is lazy evaluation as implemented in Haskell (via thunks, suspended computations with a mutable cell that is overwritten once forced). The essential distinction is often phrased as: CBV evaluates eagerly and unconditionally; CBN evaluates on demand but repeatedly; call-by-need evaluates on demand and at most once. All three agree on programs that terminate and never inspect an argument more than once with no side effects — they differ precisely on the cases that matter: non-terminating arguments, unused arguments, and expensive-to-recompute arguments.

The clean way to describe each strategy is as a deterministic small-step operational semantics: a relation $e \to e'$ that picks out exactly one redex to fire, together with a notion of evaluation context that says where in the syntax tree that redex is allowed to occur.

Call-by-value contexts. An evaluation context `E` marks the "hole" where the next reduction must happen. For CBV with left-to-right argument evaluation: ``` E ::= [ ] -- the hole itself | E a -- reduce the function position first | v E -- once function position is a value, reduce the argument ``` The rule `(λx.e) v → e[x := v]` applies only when both the operator has become a lambda and the operand has become a value `v`. This forces every subexpression passed as an argument to be fully reduced to a value before the call proceeds.

Call-by-name contexts. Only the function position is ever a reduction site at the top level; arguments are never touched until a substituted copy of them is itself in function position or is otherwise demanded structurally: ``` E ::= [ ] | E a -- only ever reduce the operator position ``` The single rule `(λx.e) a → e[x := a]` fires unconditionally — `a` is copied into the body verbatim, reduced only later, and only where actually used.

Call-by-need machinery. Call-by-need cannot be described with pure substitution alone, because substitution copies the argument expression, which would defeat sharing. Instead, implementations use a heap of thunks: a mutable store mapping variables (or addresses) to either an unevaluated expression plus its environment, or a already-computed value. This is the essence of Wadsworth/Launchbury's graph-reduction semantics that underlies the Spineless Tagless G-Machine used by GHC. ``` PSEUDOCODE — three evaluators for a small applicative language // Shared abstract syntax Expr = Var(name) | Lam(param, body) | App(fn, arg) | Lit(number) | Prim(op, e1, e2) // ---------- CALL BY VALUE ---------- function evalCBV(e, env): match e: case Lit(n): return n case Var(x): return env[x] // already a value case Lam(p, b): return Closure(p, b, env) case Prim(op, a, b): va = evalCBV(a, env) vb = evalCBV(b, env) return apply_prim(op, va, vb) case App(f, a): vf = evalCBV(f, env) // reduce operator va = evalCBV(a, env) // reduce operand EAGERLY (p, body, cenv) = vf return evalCBV(body, cenv.extend(p, va)) // substitute the VALUE // ---------- CALL BY NAME ---------- function evalCBN(e, env): match e: case Lit(n): return n case Var(x): return force(env[x]) // env holds unevaluated thunks case Lam(p, b): return Closure(p, b, env) case Prim(op, a, b): va = force(evalCBN_thunk(a, env)) vb = force(evalCBN_thunk(b, env)) return apply_prim(op, va, vb) case App(f, a): vf = evalCBN(f, env) (p, body, cenv) = vf thunk_a = Thunk(expr=a, env=env) // NOT evaluated yet return evalCBN(body, cenv.extend(p, thunk_a)) function force(thunk): if thunk.isValue: return thunk.value return evalCBN(thunk.expr, thunk.env) // re-evaluated EVERY force // ---------- CALL BY NEED (lazy, memoized) ---------- function evalNeed(e, env): match e: case Lit(n): return n case Var(x): return forceNeed(env[x]) // env holds mutable thunk cells case Lam(p, b): return Closure(p, b, env) case Prim(op, a, b): va = forceNeed(mkThunk(a, env)) vb = forceNeed(mkThunk(b, env)) return apply_prim(op, va, vb) case App(f, a): vf = evalNeed(f, env) (p, body, cenv) = vf cell = mkThunk(a, env) // shared mutable cell, UNEVALUATED return evalNeed(body, cenv.extend(p, cell)) function forceNeed(cell): if cell.state == EVALUATED: return cell.value // reuse cached result — no recompute v = evalNeed(cell.expr, cell.env) cell.state = EVALUATED cell.value = v // OVERWRITE cell: memoize return v ``` The pivotal difference is entirely in `App`: CBV computes `va` immediately and substitutes a value; CBN builds a `thunk_a` and substitutes an unevaluated expression, re-running `force` every time `x` is read; call-by-need builds a mutable shared cell, and the first `forceNeed` call permanently updates that cell so subsequent reads are $O(1)$ lookups rather than re-derivations.

Time complexity — the key asymmetry. Let a subexpression `a` passed as an argument have evaluation cost $T(a)$ and be referenced $k$ times in the function body.

• Under CBV, `a` is evaluated exactly once, cost $T(a)$, regardless of $k$, but this cost is paid even when $k = 0$.
• Under CBN, `a` is evaluated once per occurrence that is actually forced; in the worst case this is $k \cdot T(a)$, which can be exponential in the size of the source program when redexes nest (the classic example is $\lambda x.\, x\,x\,x \dots$ applied to something expensive, or Church-numeral-style duplication). If $k = 0$, cost is zero.
• Under call-by-need, `a` is evaluated at most once no matter how large $k$ is: cost is $T(a)$ if $k \ge 1$, and $0$ if $k = 0$. Call-by-need therefore dominates call-by-value on "wasted work" (unused arguments) and dominates call-by-name on "duplicated work" (repeated arguments) — it gets the better of both, at the price of needing a mutable heap (thunks) rather than a pure substitution model, plus the bookkeeping of forcing and updating cells.

Space complexity and space leaks. CBV's stack discipline is straightforward: values live on a call stack or are immediately consumable, and garbage collection can reclaim them once no longer referenced. Call-by-need's memoization is exactly what can go wrong: the thunk holding an unevaluated computation may be reachable long after it's needed, holding onto whatever data it closed over, and if never forced it silently retains a chain of un-evaluated expressions rather than the (smaller) value it would produce — the well-known Haskell space leak pattern (`foldl (+) 0 [1..n]` builds a chain of $n$ unevaluated thunks before forcing produces a stack overflow, whereas `foldl'`, a strict fold, is bounded in space).

Correctness — the central theorem. The deep reason call-by-name (and hence call-by-need, which computes the same values when it terminates) is theoretically preferred is a termination guarantee that call-by-value provably lacks: > Theorem (Standardization / normal-order theorem). If a lambda term $e$ has a normal form (i.e., some reduction sequence from $e$ terminates), then the normal-order reduction strategy — always reduce the leftmost-outermost redex first, which is precisely call-by-name — reaches that normal form. This is a consequence of the Church–Rosser theorem (confluence: if $e \to^* e_1$ and $e \to^* e_2$, there exists $e_3$ with $e_1 \to^* e_3$ and $e_2 \to^* e_3$) combined with a standardization argument showing outermost reduction cannot get "stuck" inside a subterm that is never demanded. Call-by-value, by contrast, insists on reducing the argument first, even when the argument is never used or is inside a branch that will discard it — so CBV can diverge on terms for which a normal form provably exists. The canonical witness:

where $\Omega = (\lambda z.\,z\,z)(\lambda z.\,z\,z)$ is the diverging term. Under call-by-name, `y` never occurs in the body `λy. x`, so `Ω` is discarded unevaluated and the whole expression reduces to `λy. 5` — wait, more precisely $(\lambda x.\lambda y.x)\,5\,\Omega \to (\lambda y.5)\,\Omega \to 5$, terminating cleanly since `Ω` is substituted for `y` but `y` never appears, so it's simply never forced. Under call-by-value, the reducer must first fully evaluate `Ω` to a value before it can even begin applying the outer function — and `Ω` has no normal form — so the CBV computation diverges on a term whose CBN evaluation is total and immediate.

Why call-by-need is safe to adopt in place of call-by-name. Call-by-need only ever performs a subset of the reductions call-by-name performs (it shares rather than duplicates), so any argument that call-by-name would evaluate to a value, call-by-need also evaluates to the same value (this is proved via a bisimulation between the substitution-based CBN semantics and the heap-based CBN-need semantics, originally due to Ariola–Felleisen and Launchbury). Consequently call-by-need inherits CBN's termination guarantee — if a normal form exists, call-by-need finds it — while matching CBV's "at most once per argument" work bound. This is why lazy functional languages can claim both properties simultaneously, at the engineering cost of a heap of updatable thunks instead of pure substitution.

Honest tradeoffs. Call-by-value is simpler to reason about operationally (the order of side effects is exactly the textual order of evaluation), is what hardware and most runtime stacks are built around, and avoids the space-leak failure mode entirely, since nothing is deferred. Call-by-need is more powerful semantically (more programs terminate, no work is wasted or duplicated) but harder to predict the timing of side effects and memory usage — which is precisely why Haskell segregates effects into a separate Monads and Effect Systems discipline (`IO`) rather than allowing arbitrary interleavings of unpredictable evaluation order with mutation.

Take the term (using `let` sugar for a top-level application, and a strict primitive `+`): ``` let twice = λf. λx. f (f x) in twice (λy. y + 1) (double(5)) ``` where `double(n) = n + n` and, crucially, evaluating `double(5)` prints a debug message `"evaluating!"` as a side effect before returning `10`. We trace how many times `"evaluating!"` prints, and the total reduction step count, under each strategy. `f` is applied twice inside `twice`, so the argument `x = double(5)` is referenced twice — this is exactly the scenario that separates the three strategies.

The bottom rows are the ones that matter: if the doubling substitution genuinely creates two syntactic copies of `double(5)` that each get demanded (which happens whenever a variable is used more than once and both uses are forced), call-by-name evaluates the side-effecting expression twice, printing `"evaluating!"` twice, while call-by-value and call-by-need both print it exactly once — CBV because it evaluates eagerly before any copies are made, call-by-need because it shares one memoized cell across all copies. This is the concrete sense in which call-by-need "gets CBV's sharing behavior with CBN's laziness." Now consider the companion case that shows the opposite asymmetry — an argument that is never used: ``` let const5 = λx. 5 in const5 (loop_forever()) ```

• Call-by-value: evaluates `loop_forever()` first — the program hangs, never reaching `5`.
• Call-by-name: substitutes the unevaluated call for `x`; since `x` never appears in the body `5`, it is never forced; the program returns `5` immediately.
• Call-by-need: identical to call-by-name here — the thunk is built but never forced, so it is simply garbage-collected; returns `5` immediately.

These two examples together are the complete story: CBV can do wasted work (or diverge) on unused arguments; CBN can do duplicated work on multiply-used arguments; call-by-need avoids both failure modes simultaneously by combining "evaluate on demand" with "cache the result."

Evaluation order was studied formally from the earliest days of the lambda calculus, well before "eager" and "lazy" became implementation vocabulary. Alonzo Church's original calculus made no commitment to a strategy at all — it was a system of terms and equalities — and it took later work by Curry, Church's students, and eventually the programming-languages community to turn "which redex do we reduce" into an operational, implementable discipline with a provable correctness story tied to the Church–Rosser property.

Every mainstream systems and application language — C, C++, Java, Python, JavaScript, OCaml, Scheme, Rust — is fundamentally call-by-value, which is why these languages evaluate function arguments eagerly, left to right (or in an unspecified but always-complete order), before a call proceeds; this makes cost and side-effect ordering predictable, which matters enormously for systems programming, debugging, and reasoning about performance. Haskell is the flagship call-by-need language, and its entire idiom — infinite data structures (`[1..]`), `takeWhile`, short-circuiting boolean combinators defined as ordinary functions rather than special forms, and guarded recursive definitions — depends on laziness with sharing; the runtime's Spineless Tagless G-Machine is a direct engineering realization of call-by-need graph reduction. Call-by-name survives largely as the theoretical idealization used in textbook proofs of the standardization theorem, in the semantics of C/C++ macros and Algol-style "thunked" parameters, and conceptually in default-argument or lazy-parameter features bolted onto otherwise-strict languages (Scala's `=> T` by-name parameters, C#'s `Lazy`, and default-argument thunks in some scripting languages). Compiler optimizations such as strictness analysis exist precisely to detect when a lazily-bound argument is guaranteed to be used, so the compiler can safely switch it to call-by-value at compile time and avoid the overhead of building a thunk — a concrete bridge between the theory in this article and production compiler engineering.

Ask the tutor: Can you show how the standardization theorem's proof sketch explains why leftmost-outermost reduction never gets "stuck" inside a discarded argument?