Call-by-Need Evaluator¶

Evaluation method — instantiates Demand-Triggered Deferred Evaluation

Evaluates an expression only when its value is demanded, propagates that demand through everything the value depends on, and evaluates each suspended piece at most once.

Call-by-Need Evaluation is the reduction strategy that makes an entire language lazy. An argument is not evaluated when a function is called; it is passed as a suspension and forced only if and when the function actually inspects it. Forcing one value pulls on whatever it depends on, so demand threads backwards through the dependency closure, realizing exactly the sub-expressions the final answer requires and no others. Its distinguishing commitment is demand propagation combined with sharing: call-by-need is call-by-name that also memoizes each forced result in place, so a value referenced ten times is computed once. Where the Thunk or Lazy Promise is the unit that holds a single suspension, the evaluator is the discipline that decides when to force, how far the pull travels, and how to opt back into strictness when laziness would cost more than it saves.

Example¶

In a lazy functional language, a pipeline builds a record report whose fields include a cheap title and an expensive full_breakdown that reruns a large simulation. A caller prints only report.title. Under call-by-need, constructing report forces nothing; printing title pulls only on the title's closure; full_breakdown is never demanded, so the simulation never runs — its cost is simply never paid.

The same strategy underwrites an infinite structure: primes = sieve [2..] denotes all primes, but take 5 primes forces only the first five, because demand stops the moment the caller's need is satisfied. The catch appears when timing matters: if a field's closure performs a log write, that write happens whenever the field is first forced — which may be much later than where it was written, or never. The evaluator's answer is a seq/strictness annotation that forces the value at a chosen point, pulling side effects back onto a predictable boundary.

How it works¶

Suspend, then force on demand. Expressions are held as suspensions; a value is reduced only when a consumer inspects it, and only to the depth demanded (weak head normal form, not necessarily all the way down).
Propagate demand through the closure. Forcing a value forces its free dependencies transitively, so the realized set is exactly the demanded closure — the mechanism's realization path.
Update in place (sharing). Once forced, a suspension is overwritten with its result, so repeated references pay once. This is what separates call-by-need from call-by-name.
Escape to strictness deliberately. Annotations (seq, bang patterns, strict fields) force selected values eagerly where laziness would leak space or scramble effect timing.

Tuning parameters¶

Strictness annotations — where to force eagerly. More strictness recovers predictable timing and bounded memory at the cost of doing work that might not be needed.
Forcing depth — shallow (head) vs. deep (fully evaluate). Deeper forcing flushes out hidden thunks now instead of stranding them for later, trading eagerness for control.
Sharing granularity — what gets its own updatable suspension. Finer sharing reuses more but retains more references, which is exactly where space leaks breed.
Effect confinement — how strictly side-effecting work is kept out of lazy positions (e.g. via an effect type or an IO boundary), so deferral never silently reorders effects.

When it helps, and when it misleads¶

Call-by-need lets you write in terms of what a value is and pay only for what is observed — unused branches, unused record fields, and the tails of infinite structures cost nothing. It composes producers and consumers without a manual "compute only up to here," and it makes short-circuiting and infinite data natural rather than special cases.

Its two signature hazards are both about things moving in time. Retained suspensions accumulate into a space leak — memory held by unforced closures that a strict evaluator would have freed — often surfacing far from its cause.^[1] And deferring a computation defers its side effects, so a log line, an exception, or an external write can fire at a surprising point or not at all, breaking any code that assumed effects happen where they are written. The classic misuse is reaching for laziness where you actually needed strict, ordered effects — deferring work whose timing was the point. The discipline: keep effects out of lazy positions behind an explicit boundary, and reach for the strictness escape hatch the moment predictable timing or bounded memory matters more than skipping work.

How it implements the components¶

realization_path — forcing a value propagates demand through its dependency closure, realizing exactly the sub-expressions the answer requires; the evaluator is that path.
side_effect_boundary — because deferral moves effects in time, the strategy defines where effecting work may live so that laziness never silently reorders it.
strictness_escape_hatch — seq / bang patterns / strict fields, the deliberate opt-out that forces a value eagerly when laziness would leak or mistime.

It does NOT hold the suspended unit as a data structure (deferred_work_unit, suspended_evaluation_state — that's the Thunk or Lazy Promise it forces) and it does NOT cache results across separate top-level calls (memoized_result_store — that's Memoization); the evaluator decides *when to force and how far demand travels.*

Instantiates: Demand-Triggered Deferred Evaluation — call-by-need is the evaluation strategy that realizes deferred work exactly at the point of demand.
Consumes: Thunk or Lazy Promise — the suspended units the evaluator forces and updates in place.
Sibling mechanisms: Thunk or Lazy Promise · Short-Circuit Evaluation · Lazy Sequence Generator · Memoization · Just-in-Time Compilation

Notes¶

The in-place update that gives call-by-need its sharing is also the source of its worst surprises: a suspension that captures a large structure keeps that structure alive until it is forced, so a value you thought was cheap can pin megabytes. Space leaks of this kind are diagnosed by adding strictness, not by adding memory.

References¶

[1] A space leak is memory retained by unevaluated closures (thunks) that a strict evaluation would have released — a hazard specific to lazy evaluation. The standard cure is selective strictness (forcing accumulators and hot fields), which is why the strictness escape hatch is part of the strategy rather than an afterthought. ↩