Call-by-Need Evaluation and In-Place Thunk Update

Passing an argument to a function normally means evaluating it first. Call-by-name skips that step and substitutes the unevaluated expression for every use of the parameter, which duplicates work whenever the parameter appears more than once. Call-by-need keeps the delay but recovers the sharing: the first use evaluates the expression and every later use reads the stored result. The data structure that makes this work is a mutable cell holding either an unevaluated expression or its value, and the evaluation step destructively replaces the first with the second.

The cost of substituting an expression

Consider a function that uses its argument twice:

sq x = x * x

Under call-by-value, sq (1 + 2) evaluates 1 + 2 once, passes 3, and multiplies twice. Under call-by-name, the body becomes (1 + 2) * (1 + 2), and the addition runs twice. With a cheap argument the duplication is irrelevant; with an expensive one it compounds with the depth of nesting, because each level of a recursive call can double the work below it, so a chain of depth n can cost 2^n evaluations of the original expression.

The textbook example is the fib defined by the naive recurrence used as an argument to a function that uses it n times. Under call-by-name each use recomputes the whole tree. Under call-by-need the first use computes it, and the rest read the result. Sharing is what separates the two, and sharing requires a place to put the result.

A thunk is a closure with a writable slot

A thunk is a heap object with a code pointer, an environment, and a slot for its value. The code pointer identifies the expression to evaluate, and the environment holds the values of the free variables of that expression. Evaluating a thunk means entering the code with the environment, producing a value, and then storing that value in the thunk’s own slot so that later entries find it directly.

Three representations are in common use:

An overwritten thunk. The thunk and the value share one heap cell. The first word of the cell is an info-table pointer that distinguishes “unevaluated” from “evaluated”; for an evaluated value it points to the value’s own constructor info table. The update writes the value into the same cell and overwrites the info pointer. This is the representation the STG machine uses, and its advantage is that an update allocates nothing.

Two cells with an indirection. The thunk cell holds a pointer to a separate value cell after evaluation. This costs an extra allocation and an extra indirection on every subsequent access, but it allows the original closure to be freed.

A boxed mutable reference in the runtime’s own heap. In an interpreter written in a host language, a thunk is a record with a state field and a value field, and evaluation mutates the state. This is the slowest of the three and the easiest to get right.

The important invariant is the same in all three: after a thunk is forced, entering it again must not re-run the expression. A correct implementation therefore performs the update before returning the value, not after, so that a thunk reached from inside its own evaluation finds a defined state.

Blackholing and the single-threaded assumption

Updating before returning creates a window: between the start of evaluation and the update, the cell holds neither the expression nor a value. Implementations set it to a distinguished black hole state, written before the expression is evaluated. Entering a black hole means the program demanded a value that is currently being computed, which for a single-threaded evaluator can only happen if the expression depends on itself. The standard behaviour is to raise an error rather than loop, and the error names the binding involved.

This is also why the classic update-in-place scheme is not thread-safe. Two threads that force the same thunk can both run the expression, and the second update overwrites the first result. The usual fixes are a lock around the update, an atomic compare-and-swap on the thunk’s state word, or per-thread thunks with a merge step. Each adds cost to the common case where a thunk is forced exactly once, and each changes the semantics in a corner: a black hole entered by a second thread may block instead of raising.

Blackholing also explains why a self-referential definition such as ones = 1 : ones is fine while x = x + 1 is not. Constructing the cons cell does not force the tail; it stores a thunk for ones that is never entered during construction. The arithmetic definition forces x to compute x, which enters the black hole immediately.

Weak head normal form and where forcing stops

Forcing a thunk reduces it to weak head normal form: the outermost constructor is known, and the arguments are still thunks. Forcing 1 : map f xs yields the cons cell with an unevaluated tail. Forcing a function yields a lambda. Nothing inside is evaluated unless something pattern-matches on it.

This is what makes infinite structures usable. take 3 (repeat 1) forces the repeat thunk three times, each time producing one cons cell and a new tail thunk, and the fourth tail is never touched. A definition like let xs = 1 : 2 : 3 : xs in take 5 xs works for the same reason.

The cost is that a value in weak head normal form may hide a large unevaluated structure. A pair whose first component is a thunk is itself in weak head normal form, so matching on the pair does not evaluate the component. Only a seq, a bang pattern, or a strict field forces the nesting further, and seq alone is easy to misjudge: seq on a pair forces the pair to weak head normal form and leaves both components unevaluated, so forcing the components with seq takes two more seq calls, one per component.

Space leaks: retention, not evaluation

The characteristic failure of lazy evaluation is not that it computes too much but that it retains too much. Three shapes recur.

Accumulating chains. A left fold written with the non-strict fold builds a chain of thunks:

sumL :: [Integer] -> Integer
sumL = foldl (+) 0

-- sumL [1..n] evaluates to (((0 + 1) + 2) + 3) + ...
-- The accumulator is a thunk whose tree grows with the list.

foldl is defined so that the combining function’s second argument is the accumulator, and under laziness the accumulator is never forced until the end. Each step wraps the previous thunk in another application, so the chain has length n and the final force walks it. The strict variant foldl' forces the accumulator at each step, keeping the chain at constant size. Both traverse the list once and neither changes the asymptotic cost of the fold itself; the peak residency is what differs, because the lazy version holds all n pending applications alive at once.

Holding a head. A function that traverses a list while keeping a reference to its head prevents the garbage collector from reclaiming the front of the list. The usual symptom is a program whose live heap grows with the input even though the result is small, because the whole spine stays reachable through the retained reference. The fix is to avoid the reference, or to force the parts that are not needed, and no compiler can apply it without knowing which references the programmer considers dead.

A third shape is a thunk captured in a long-lived closure. A partially applied function holds its arguments’ thunks alive; if the closure outlives the computation, the thunks do too.

Strictness as an annotation

Because the evaluator cannot know which arguments a function will use, implementations add annotations. A strict field in a data declaration forces its contents when the constructor is built. A bang pattern on a function argument forces it on entry. seq forces its first argument to weak head normal form and returns the second. deepseq forces the whole structure, which is what a force-style helper needs.

The compiler can also infer strictness. Strictness analysis computes, for each function, which arguments are certain to be demanded, and a worker-wrapper transformation then passes those arguments unboxed. The analysis is conservative: an argument that is demanded on some paths but not others is treated as lazy, because the wrapper cannot assume the demand. This is one of the places where a small change in a function’s definition can change the optimized code substantially.

The design constraint behind all of this is that laziness is the default and strictness is the exception. A language that made strictness the default and laziness the annotation would need a different mechanism entirely: explicit thunks or a lazy type constructor, as in a strict language that offers a Lazy wrapper. Both designs exist, and the choice determines which failure mode is common. Under lazy-by-default, the common failure is retention. Under strict-by-default, the common failure is a computation that runs when the programmer wanted to defer it.

The connection to the rest of the cluster is direct. Laziness is what allows folds to be composed without intermediate lists, and it is what makes the recursive structure in recursion schemes usable on infinite trees. It is also what makes the substitution property of referential transparency non-trivial: an expression may denote a value it has not yet computed.