Trampoline

The trampoline is how nix-effects interprets freer monad computations with O(1) stack depth in a language with no iteration primitives and no tail-call optimization.

The problem

Nix is a pure, lazy, functional language. It has no loops. Every "iteration" is recursion. A naïve free monad interpreter using mutual recursion would build a call stack proportional to the computation length:

run (bind (bind (bind ... (send "get" null) ...) ...) ...)
  → run step1
    → run step2
      → run step3
        → ...  (N frames deep)

For validation of a large DSL value — say, an aspect graph with hundreds of declarations — this would blow the stack.

The solution: builtins.genericClosure

Nix's builtins.genericClosure is the only built-in iterative primitive. It implements a worklist algorithm:

genericClosure {
  startSet = [ initialNode ];
  operator = node -> [ ...nextNodes ];
}

operator is called on each node. New nodes returned by operator are added to the worklist if their key hasn't been seen before. The result is the set of all reachable nodes.

nix-effects repurposes this as a trampoline: each step of computation is a node. The operator function handles one effect and produces the next step as a singleton list. The computation terminates when operator returns [] (i.e., when we reach a Pure node).

steps = builtins.genericClosure {
  startSet = [{ key = 0; _comp = comp; _state = initialState; }];
  operator = step:
    if isPure step._comp
    then []          # halt
    else [ nextStep ]; # one more step
};

Stack depth: O(1). genericClosure handles its own iteration internally; the operator function is never deeply nested.

The thunk problem and deepSeq

genericClosure only forces the key field of each node (for deduplication). All other fields — including _state and _comp — are lazy thunks.

Without intervention, after N steps the _state field would be:

f(f(f(... f(initialState) ...)))  # N thunks deep

Forcing the final _state would then rebuild the entire call stack in thunk evaluation, defeating the purpose.

The fix: make key depend on builtins.deepSeq newState:

key = builtins.deepSeq newState (step.key + 1)

Since genericClosure forces key, it also forces deepSeq newState, which eagerly evaluates the state at each step. No thunk chain builds up.

The test suite validates deep effect chains and pure bind chains so the stack-safety contract stays covered by automated checks.

State-shape contract

builtins.deepSeq newState imposes a contract on handler-state shape: every value reachable through state must be deepSeq-tolerant. Scalars, finite records, and lists of scalars satisfy this trivially. Functions are also safe — deepSeq on a closure forces it to WHNF and stops, never recursing into the captured environment.

The contract breaks on values with cyclic structure. Nix derivations are the canonical example: drv.passthru.foo.drv cycles back through the same drv, and deepSeq has no cycle detection. A raw drv in handler state hangs the evaluator, and tryEval cannot recover — only throw and assert false are catchable.

For this case the library ships fx.state.mkThunk / forceThunk (src/state/thunk.nix). The carrier wraps any value as { _tag = "Thunk"; _force = _: value; } — a closure shields the value from deepSeq. The companion kernel type former H.thunk : Hoas → Hoas is decided by a lazy structural walker: it verifies is attrset ∧ has _force closure and does NOT recurse into _force. Inner-type validation runs at forget time, post-forced. Forcing in the validator would defeat the deepSeq-shielding the whole construct exists for.

Effect descriptions that carry derivations through state type their payload fields as H.thunk H.derivation, not H.derivation, so fx.send-time validation rejects unwrapped drvs before they reach the trampoline. The inner type is parametric: any value category that needs trampoline transit can ride through H.thunk a with no bespoke primitive.

Defunctionalization

The interpreter defunctionalizes (Reynolds 1972) the recursive handler: the continuation moves from the call stack into an explicit data structure (the FTCQueue). The worklist loop processes these continuations iteratively rather than recursively — the same pattern identified by Van Horn & Might (2010) in Abstracting Abstract Machines.

Gibbons (2022) Continuation-Passing Style, Defunctionalization, Accumulations, and Associativity shows the hidden precondition: this transformation is valid when the accumulated operation is associative. For nix-effects, the handler state transformations compose associatively because function composition is associative.

References

• Reynolds, J. C. (1972). Definitional Interpreters for Higher-Order Programming Languages. ACM Annual Conference.
• Van Horn, D., & Might, M. (2010). Abstracting Abstract Machines. ICFP 2010.
• Gibbons, J. (2022). Continuation-Passing Style, Defunctionalization, Accumulations, and Associativity. The Art, Science, and Engineering of Programming, 6(2). [doi]
• Kiselyov, O., & Ishii, H. (2015). Freer Monads, More Extensible Effects.