Laziness and Evaluation Strategies
Consider a function that takes two arguments, ignores the second, and returns the first: `first(x, y) = x`. If you call `first(5, 1/0)`, should the program crash? A beta-reducing interpreter that eagerly evaluates arguments before substitution says yes. Division by zero fires before `first` ever runs. An interpreter that substitutes the unevaluated expression `1/0` for `y` says no. It only forces `y` if it is actually used. In that case the program returns `5` cleanly. Both interpreters implement the same beta rule. They differ only in when they choose to reduce. That single design decision — the evaluation strategy — is one of the most consequential choices a language designer makes. Evaluation strategy governs far more than error behavior. It determines whether you can write an infinite list of primes and just ask for the first ten. It determines whether a function argument is computed once or a thousand times. It determines whether a program terminates at all. It also determines how much memory a running computation retains. Call-by-value languages (C, Python, Java, ML, Scheme) evaluate arguments before a function body ever sees them. Call-by-need languages (Haskell, and, with effort, any language exposing suspended computations) defer evaluation until a value is demanded. They then cache the result, so repeated demands are free. Between these two poles sits call-by-name, the "pay every time" cousin of call-by-need. It is useful mainly as a stepping stone for understanding the tradeoffs. This matters in real systems because it changes what programs are expressible and safe to write. Streaming pipelines, self-referential definitions like the Fibonacci stream, short-circuiting logical operators, and default-argument idioms all lean on some notion of delayed evaluation. Conversely, careless laziness can turn a simple accumulator loop into trouble. It can build a chain of unevaluated additions that blows the stack — the notorious "space leak." Understanding thunks (the machinery that implements suspension) helps here. So does understanding the tradeoffs between strategies. Together they let you predict when a program will loop forever. You can also predict when it will leak memory, and when it will do the least possible work. This article builds the operational semantics of call-by-value, call-by-name, and call-by-need from the ground up. It uses the closure machinery you already know as the substrate. It gives you a working mental model of a thunk, and traces a real evaluation step by step. It is honest about the performance and predictability tradeoffs each strategy makes. It closes by pointing toward how Haskell tames the unpredictability of laziness. Haskell does this using monads to sequence effects explicitly.
- Evaluation strategy decides when an argument or expression is reduced relative to when it's bound.
- Call-by-value evaluates arguments eagerly, before substitution; simple and predictable, but wasteful or unsafe when arguments are expensive or non-terminating.
- Call-by-name substitutes the unevaluated expression and re-evaluates it every time it's used; call-by-need does the same but caches the result in a thunk after the first forcing.
- Thunks are just closures over an expression plus its environment, with a mutable cell to memoize the eventual value.
- Laziness enables infinite data structures (streams, generators) and short-circuiting, but complicates reasoning about space and the order of side effects.
- Haskell's purity is what makes pervasive laziness tractable; effectful lazy languages need explicit sequencing, which is one motivation for monads.
An evaluation strategy is a policy for when to reduce an expression — eagerly at binding time, or lazily (once, with caching) at first use — and that single policy choice governs termination, sharing, and side-effect order for an entire language.
The idea
An evaluation strategy is a precise rule specifying, for a given reducible expression (a redex, in the language of Beta Reduction), which sub-expression gets reduced next and under what conditions. In the lambda calculus, applying a function `(λx. body) arg` can proceed in at least two disciplined orders. Applicative order reduces `arg` to a value first, then substitutes that value for `x` in `body`. Normal order substitutes the unevaluated `arg` expression directly for every occurrence of `x` in `body`, deferring reduction of `arg` until (and unless) the substituted copies are themselves used in a context that forces them. Real languages refine these two orders into three named strategies. Call-by-value (CBV) is applicative order restricted to function application: evaluate the argument to a value, bind it, then evaluate the body. Call-by-name (CBN) is normal order at the call boundary: substitute the argument expression unevaluated, and every time the parameter is referenced inside the body, re-evaluate that expression from scratch. Call-by-need is call-by-name plus memoization: the first time the parameter is forced, the result is computed and the original binding site is overwritten with that value, so every subsequent reference is a cheap cache lookup rather than a fresh computation. Call-by-need is what people mean by "laziness" in practice; call-by-name is a useful theoretical simplification of it. The mechanism that makes call-by-name and call-by-need implementable — rather than just a rewriting rule on paper — is the thunk. A thunk packages an unevaluated expression together with the environment needed to evaluate it later, exactly like a closure packages a function body with its environment. The only addition is a mutable memoization cell: once the thunk is forced (evaluated), the cell is overwritten with the resulting value (or, for call-by-name, the thunk is simply re-run and no cell is kept). "Forcing" a thunk means: if already evaluated, return the cached value; otherwise, evaluate the wrapped expression in its stored environment, store the result, and return it. This turns "laziness" from a vague slogan into a concrete, three-field data structure.
How it works
The cleanest way to see the mechanism is to build a small interpreter core for each strategy and watch how argument passing differs. Assume the standard lambda-calculus grammar of variables, abstractions, and applications, plus literals and primitive operations for concreteness.
Call-by-value. The evaluator recursively reduces the argument to a value before calling the function. ``` eval_CBV(expr, env): match expr: case Literal(v): return v case Var(x): return env.lookup(x) case Lambda(param, body): return Closure(param, body, env) # capture env now case App(f, argExpr): fnVal = eval_CBV(f, env) argVal = eval_CBV(argExpr, env) # <-- eager: reduce now (param, body, closureEnv) = fnVal newEnv = closureEnv.extend(param, argVal) return eval_CBV(body, newEnv) case Prim(op, e1, e2): return apply_op(op, eval_CBV(e1, env), eval_CBV(e2, env)) ```
Call-by-name. No thunk cache is needed conceptually — a thunk here is just a zero-argument closure re-run every time it's referenced. ``` eval_CBN(expr, env): match expr: case Literal(v): return v case Var(x): thunk = env.lookup(x) # a suspended computation return force_CBN(thunk) # re-run every time case Lambda(param, body): return Closure(param, body, env) case App(f, argExpr): fnVal = eval_CBN(f, env) thunk = Thunk(argExpr, env) # DO NOT evaluate argExpr (param, body, closureEnv) = fnVal newEnv = closureEnv.extend(param, thunk) return eval_CBN(body, newEnv) case Prim(op, e1, e2): return apply_op(op, force_CBN(Thunk(e1, env)), force_CBN(Thunk(e2, env))) force_CBN(thunk): return eval_CBN(thunk.expr, thunk.env) # always recompute ```
Call-by-need. Identical structure, but the thunk gains a mutable cell, and forcing checks/updates it — this is the memoization that distinguishes laziness from mere call-by-name. ``` struct Thunk: expr # unevaluated expression env # captured environment evaluated: bool = false value = None force(thunk): if thunk.evaluated: return thunk.value # cache hit: O(1), no recomputation v = eval_lazy(thunk.expr, thunk.env) # recursive evaluation, may itself force other thunks thunk.value = v thunk.evaluated = true thunk.expr = None # allow GC of the expr/env closure return v eval_lazy(expr, env): match expr: case Literal(v): return v case Var(x): return force(env.lookup(x)) # forcing happens only on demand case Lambda(param, body): return Closure(param, body, env) case App(f, argExpr): fnVal = eval_lazy(f, env) thunk = Thunk(argExpr, env, evaluated=false) # build, don't run (param, body, closureEnv) = fnVal newEnv = closureEnv.extend(param, thunk) return eval_lazy(body, newEnv) case Prim(op, e1, e2): t1 = Thunk(e1, env) t2 = Thunk(e2, env) return apply_op(op, force(t1), force(t2)) # primitives are strict: they must force ``` The crucial design points, easy to miss on a first read: 1. Environments bind thunks, not values, under call-by-name/need. A variable lookup returns a thunk; only `force` produces an actual value. 2. Primitive operations are strict in essentially every language — you cannot add two numbers without knowing what they are — so `force` is unavoidable at that boundary even in a "lazy" language. 3. Sharing is what makes call-by-need efficient. If the same thunk object (not a re-built copy) is referenced from two places — e.g., because it was bound once and used twice in the body — forcing it once benefits both uses. This requires the interpreter to substitute the thunk itself, by reference, not re-parse or re-copy the expression. 4. Laziness must extend to data constructors, not just function arguments, to support infinite structures: `Cons(x, xs)` must not force `xs`, only store a thunk for it. The following diagram traces `let ones = 1 : ones in first(2, second) where second = head(tail(ones))`-style sharing: two references to one thunk, forced once.
Complexity & correctness
Termination. The central theoretical result, due to the standardization/normalization theory of the lambda calculus, is: if any reduction order terminates on an expression, normal order terminates on it too. Call-by-name (and by extension call-by-need, which reduces at least as few times) is normal-order at the call boundary, so it is weakly normalizing whenever a normal form exists — it finds termination whenever termination is findable. Call-by-value has no such guarantee: it can diverge on `first(5, loop())` even though the result `5` never needed `loop()`'s value at all, because CBV insists on reducing the argument regardless of whether the body uses it. This is not a performance quirk; it is a difference in which programs terminate at all under the two strategies.
Work duplication versus re-evaluation. Call-by-name's weakness is the mirror image: if a bound variable is used `k` times in the body, call-by-name re-evaluates its argument expression `k` separate times. For an argument expression costing `T` steps to reduce, naive call-by-name pays `Θ(k·T)` where call-by-value and call-by-need both pay `Θ(T)` (value computed once, then just copied or cached). This is exactly why real lazy languages use call-by-need, not call-by-name: the thunk's memoization cell converts the re-evaluation cost from `Θ(k·T)` to `Θ(T + k)` — one real computation plus `k` cheap cache reads.
Space. Here is the least intuitive part, and the honest tradeoff. Call-by-value forces evaluation eagerly, so an accumulator like ``` sum(n, acc): if n == 0: return acc return sum(n - 1, acc + n) ``` under CBV keeps `acc` as a fully-reduced integer at every call — constant space per frame (with tail-call optimization, constant space overall). Under call-by-need, `acc + n` is not reduced; it is wrapped in a new thunk pointing to the previous (also unevaluated) thunk. After `n` recursive calls, `acc` is a thunk chain `((((0+n)+n-1)+n-2)+...)` of depth `n` — nothing has actually been added yet. Forcing this chain at the end requires unwinding `n` nested suspended additions, which, depending on the runtime's stack discipline, can overflow the stack or simply allocate `Θ(n)` heap objects that a strict version never would. This is the canonical space leak: laziness traded eager, bounded space for lazy, unbounded thunk buildup. The fix — forcing accumulators strictly with an explicit "seq" or strictness annotation — is a direct, practical consequence of the semantics just described, not an incidental implementation bug.
A correctness argument for call-by-need's memoization. We must check that caching a thunk's value is observationally safe — that it never changes what a pure program computes, only how many times it recomputes. This is essentially confluence (the Church–Rosser property) specialized to sharing: if an expression `e` reduces to value `v` under any terminating reduction sequence, then it reduces to the same `v` under any other terminating sequence, because beta reduction is confluent. Consequently, forcing a shared thunk once and reusing the cached `v` for all subsequent references yields the same value as re-deriving `v` from `e` at each reference — the only difference is work, not result. This argument depends critically on purity: if evaluating `e` can perform an observable side effect (print, mutate a ref cell, raise an exception), then how many times and when `e` is evaluated becomes observable, and CBV, CBN, and call-by-need can produce genuinely different program behavior, not just different speeds. That fact — that laziness and effects don't mix safely without extra discipline — is exactly the gap that monads are designed to close in a lazy, pure language like Haskell.
Worked example
Trace the expression below under all three strategies, where `boom` is a diverging computation (`boom = boom`, an infinite loop) and `dbl(x) = x + x`. ``` dbl(boom) -- never uses x's value at all! Wait, dbl DOES use x twice. ``` To show the sharing behavior cleanly, use a function that uses its argument twice but where the argument is cheap-but-not-free, `cube(x) = xxx` applied to `2+3`: ``` cube(2 + 3) ```
| Step | Call-by-value | Call-by-name | Call-by-need |
|---|---|---|---|
| 1. Application | Evaluate arg first: `2+3 → 5`. Bind `x = 5`. | Substitute unevaluated `2+3` for `x`. Bind `x = Thunk("2+3")`. | Bind `x = Thunk("2+3", evaluated=false)`. |
| 2. Enter body `xxx` | Body becomes `555`. | Body is `(2+3)(2+3)(2+3)` conceptually — each `x` forces its own copy. | Body forces `x` on first `*`: `force(x)`. |
| 3. First multiply | `5*5 = 25` | Evaluate `2+3 → 5` (first time). | `x` not yet evaluated → compute `2+3=5`, store 5 in the thunk, `evaluated=true`. |
| 4. Second use of `x` | reuse `25` (already a plain value) | Evaluate `2+3 → 5` again (second time, from scratch). | `force(x)` sees `evaluated=true`, returns cached `5` — no recomputation. |
| 5. Final multiply | `25*5 = 125` | `555 = 125` | `555 = 125` |
| Result | `125` | `125` | `125` |
| Times `2+3` is evaluated | 1 | 3 (once per occurrence of `x` in the fully substituted body) | 1 (computed once, cached, reused twice) |
All three strategies agree on the answer — as confluence guarantees for a pure, terminating expression — but they disagree sharply on work done. Call-by-name pays for its simplicity with repeated recomputation; call-by-need gets call-by-name's termination behavior and call-by-value's single-evaluation efficiency, at the cost of maintaining the mutable thunk cell. Now the case that distinguishes CBV from the lazy strategies in outcome, not just cost — using `first(x, y) = x` and `y = loop` where `loop = loop` diverges:
| Strategy | What happens to `first(5, loop)` |
|---|---|
| Call-by-value | Evaluates `loop` first (arguments evaluated before call) → diverges, never returns |
| Call-by-name | Substitutes unevaluated `loop` for `y`; body is just `x`, never references `y` → returns 5 |
| Call-by-need | Same as call-by-name here: `y`'s thunk is built but never forced → returns 5 |
This is the sharpest illustration of the termination theorem: the same function, the same arguments, and one strategy hangs forever while the other two terminate immediately, because only the lazy strategies avoid computing an argument that the body throws away.
Common pitfalls & traps
| Pitfall | Why it happens | Fix | |
|---|---|---|---|
| Space leak from thunk buildup in accumulators | Lazy `acc + n` builds a chain of unevaluated additions instead of a number | Force strictly at each step (strict `foldl'`, explicit `seq`/bang patterns) | |
| Assuming call-by-name and call-by-need have the same cost | They agree on results (by confluence) but call-by-name recomputes on every use | Remember: call-by-need = call-by-name + memoization; only call-by-need is used in practice | |
| Mixing side effects with lazy evaluation | Order and number of evaluations become unpredictable when evaluation is demand-driven | Sequence effects explicitly (e.g., via [[Monads: An Introduction | monads]]) rather than relying on evaluation order |
| Forgetting primitives are strict | Beginners expect `+` to be lazy in a "lazy language" | Only user-level bindings/constructors are lazy by default; arithmetic and comparisons must force their operands | |
| Confusing call-by-reference with call-by-name/need | Both defer something, but call-by-reference passes a mutable location, not a suspended pure computation | Keep the vocabulary separate: call-by-reference is about aliasing/mutation, call-by-name/need is about when pure reduction happens | |
| Building infinite structures without a lazy `cons` | Eagerly evaluating a constructor's fields forces the "infinite" list immediately, looping forever | Ensure data constructors store thunks for their fields, not forced values |
Pioneers & history
The theory underlying evaluation strategy traces back to the confluence and standardization results for the untyped lambda calculus, later sharpened into concrete language designs by researchers building the first non-strict functional languages. Peter Landin's SECD machine (1964) gave the first operational account of call-by-value evaluation as an abstract machine, while later work by Christopher Wadsworth and others on graph reduction supplied the mechanism — sharing mutable graph nodes — that call-by-need relies on. The Haskell committee of the late 1980s deliberately chose non-strict (lazy, call-by-need) semantics as the language's defining feature, betting that purity would make pervasive laziness tractable rather than chaotic.
Origins · 1 minPeter J. Landin and how this was discovered
Where this matters
Haskell is the flagship example of call-by-need as a load-bearing language feature: its list type is lazy by default, so idioms like `take 10 primes` over an infinite list of primes are ordinary code, not special syntax. Scala, Kotlin, and Swift expose opt-in laziness via `lazy val` / lazy properties and lazy sequence combinators, letting programmers choose call-by-need locally without committing an entire language to it. Python and JavaScript generators (`yield`) are a controlled, explicit form of the same idea: a suspended computation that produces values on demand rather than all at once, useful for streaming large or infinite data without materializing it in memory. Short-circuit boolean operators (`&&`, `||`) in almost every mainstream language are a small, universally accepted island of call-by-name-style behavior inside otherwise strict languages. Build systems and reactive/dataflow frameworks use demand-driven ("only recompute what's needed") evaluation, a spiritual cousin of laziness, to avoid redundant work in large dependency graphs. Compiler writers care about evaluation strategy when choosing default argument-passing conventions, when deciding whether to inline expressions safely (inlining a call-by-value argument can duplicate its side effects), and when designing intermediate representations — this is one reason the lambda calculus and its evaluation orders remain foundational to how real compilers reason about program transformations.
Ask the tutor: How do monads let a lazy, pure language like Haskell sequence side effects predictably despite demand-driven evaluation?
What exactly is a thunk, structurally?
A thunk is a small record with three parts: an unevaluated expression, the environment (variable bindings) needed to evaluate that expression, and a mutable slot recording whether it has been forced yet and, if so, the cached value. It is structurally identical to a closure — code plus captured environment — with one addition: the memoization cell. "Forcing" a thunk means checking the cell; if empty, evaluating the expression in its environment, writing the result into the cell, and returning it; if already filled, returning the cached value immediately. This is the entire mechanism behind call-by-need; nothing more exotic is required.
Is call-by-name ever used in real languages, or is it purely theoretical?
Call-by-name is mostly a theoretical stepping stone, but it does appear directly in a few places: Algol 60's parameter passing was call-by-name, macro-expansion-style systems and some C preprocessor patterns behave like it, and short-circuit boolean operators (`&&`, `||`) in mainstream strict languages are effectively call-by-name special cases baked into the syntax. In practice, whenever a language wants "evaluate the argument lazily," it almost always implements call-by-need (with caching) rather than pure call-by-name, because paying for recomputation on every use is rarely worth the memory savings of not caching.
Does laziness change what a program computes, or only how fast it runs?
For pure, terminating expressions, confluence guarantees that different evaluation orders reach the same final value — laziness changes cost, not correctness, in that setting. But laziness can change whether a program terminates at all (a lazy strategy can return a result where an eager one diverges on an unused argument), and once side effects are involved, laziness changes the number and order of those effects, which is observable behavior, not just performance. This is why purely functional lazy languages need a disciplined mechanism, ultimately explained through monads, to keep effect ordering predictable despite demand-driven evaluation.
How do infinite data structures actually work under the hood?
An infinite list like `ones = 1 : ones` type-checks and "exists" as a value immediately because the constructor `:` (cons) does not force its second argument — it stores a thunk for the tail rather than evaluating it. Each time you ask for more of the list (e.g., via `take n`), the consumer forces one more layer of the thunk chain, which computes exactly one more cons cell and leaves the rest suspended. Nothing about this requires infinite memory or infinite time up front; the list is a potentially infinite, incrementally-unfolding structure, and only a finite prefix is ever actually materialized if the consumer only asks for a finite prefix.
Why doesn't call-by-value support infinite lists the same way?
Under call-by-value, evaluating `ones = 1 : ones` would require fully evaluating the second argument to `:` before the cons cell can even be constructed, and that argument is `ones` itself — an infinite regress that never produces a first value. There is no way to "pause partway" under strict evaluation of constructor arguments; either you eagerly build the whole structure (impossible if infinite) or you don't build it at all. Strict languages instead simulate infinite sequences using explicit suspension (closures/generators) so that constructing the next element is deferred behind a function call rather than a data constructor.
What's the actual space/time tradeoff summary between the three strategies?
Call-by-value: each argument evaluated exactly once, at call time; cheapest and most predictable, but can force unnecessary or divergent computations. Call-by-name: correctness matches normal-order (terminates whenever any order does), but an argument used `k` times costs `k` full re-evaluations — potentially exponential blowup in pathological cases. Call-by-need: same termination guarantee as call-by-name, but memoization caps the cost of a `k`-times-used argument at one real evaluation plus `k` cache lookups — however, it pays with unevaluated thunk chains that can silently accumulate unbounded heap space if not periodically forced.
How does this connect to what comes after — monads?
Laziness cleanly separates building a computation from running it, which is exactly the conceptual move monads formalize for effects: a monadic value like an `IO` action describes a computation without performing it, and only an explicit "run" step (analogous to forcing a thunk) actually executes it. In a call-by-need language, this separation is not optional — it's necessary, because you cannot rely on textual order to sequence side effects when evaluation order is demand-driven. Monads give a principled, composable way to say "do this, then that" explicitly, restoring predictable sequencing on top of a language that otherwise evaluates lazily.