Trampolining Nix

Trampolining Nix

How I nearly lost my mind fighting the evaluator

Mika Bohinen - NixCon 2026

I wanted algebraic effects in Nix. Running those programs led from recursive calls to trampolining, strictness, defunctionalization, and an explicit machine, with another evaluator problem after each apparent repair. I assume you know the Nix language; I will introduce the compiler terminology as we encounter it.

The program asks for state; the handler supplies it.

get

bind passes that reply to the rest of the program.

s: put (s * 2)

The program changes the state, then returns the original value.

bind get (s:
  bind (put (s * 2)) (_:
    pure s))

Each recursive return still owes an addition.

recursive = count:
  if count == 0 then 0
  else 1 + recursive (count - 1);

The driver calls one step.

That call returns before the next one begins.

More steps. The same nesting depth.

A fold passes the running total to this function.

total: _: total + 1

A strict scalar fold already solves this fixed counter.

builtins.foldl'
  (total: _: total + 1)
  0
  (builtins.genList (i: i) n)

The operator chooses a successor state or ends the traversal.

Start with one record: an identity and a running total.

startSet = [{ key = 0; total = 0; }];

Build the successor from the current record, item.

next = { total = item.total + 1; };
{ key = item.key + 1; inherit (next) total; }

Return no successors when the key reaches the limit.

operator = item:
  if item.key >= n then [] else

naive names the returned list, including the initial state.

naive = builtins.genericClosure {
  inherit startSet operator;
};

Surely the hard part is over.

Time to ask it for a number.

We have a builtin to drive the traversal and a counter to put inside it. The next two experiments ask what this arrangement actually computes.

The same program succeeds or overflows depending on what I ask for.

I had a rather generous definition of finished.

I shall now make the mistake of asking for the answer.

I had taken the successful count to mean that the difficult part was over. The evaluator had been rather more precise about which part of the computation it had finished.

The key and the total have separate demand paths.

next.total = item.total + 1;
key = item.key + 1;

Each state is a record whose key identifies its place in the traversal. Its total can remain a thunk. Nix can make the record available before evaluating that field. The stop condition, omitted here, ends the traversal when the key reaches n.

Counting visited states does not demand their totals.

next.total = item.total + 1;
key = item.key + 1;

Starting from key = 0 and total = 0, the traversal visits n + 1 states, including the initial record. Taking the length of the returned list gets us through that traversal without asking for the total fields inside its records.

The final total depends on earlier deferred additions.

next.total = item.total + 1;
key = item.key + 1;

Visiting the states returns after every step without evaluating a total. Evaluating the last total requires the previous total, which in turn requires the one before it, so forcing climbs one level per step. Following those dependencies through 100000 steps overflows the stack in this run.

Forcing the record leaves its total field deferred.

next.total = item.total + 1;
key = builtins.seq next
  (item.key + 1);

seq next evaluates next only to weak head normal form: the outer record. Its total field stays untouched, so the chain of additions remains.

The next key becomes available after next.total has been computed.

next.total = item.total + 1;
key = builtins.seq next.total
  (item.key + 1);

Because the worklist needs the next key, placing seq next.total in that expression makes it compute the total first. The first transition starts from the number 0 and computes 1 before returning key 1.

The following step receives a total that has already been computed.

next.total = item.total + 1;
key = builtins.seq next.total
  (item.key + 1);

The preceding state already holds the number 1, so the following transition can compute 2 without following a chain of earlier additions. The same relationship holds between each pair of successive states.

Asking for the final total now succeeds with the same input and limits.

next.total = item.total + 1;
key = builtins.seq next.total
  (item.key + 1);

The input and evaluator limits are unchanged, but each step now computes the total it carries forward, one addition deep. Asking for the final total needs no chain and returns 100000. The handler has the same distinction to manage: making its next state record available does not establish that the fields inside it have been computed.

Is forcing next.stats enough?

next.stats.total = item.stats.total + 1;
key = item.key + 1;

The total now lives inside stats, so consider whether evaluating the containing record also computes the scalar needed by the next step.

The stats record can still contain a deferred total.

next.stats.total = item.stats.total + 1;
key = builtins.seq next.stats
  (item.key + 1);

Although the containing record is available, its total field still depends on the preceding state's scalar, leaving the same addition chain to evaluate later.

Computing next.stats.total at each step breaks the nested dependency chain.

next.stats.total = item.stats.total + 1;
key = builtins.seq next.stats.total
  (item.key + 1);

This repair reaches the nested scalar before returning the next key, allowing the following transition to begin with the number it needs already computed.

Why not force the whole state?

How much work can that be?

An interpreter can carry considerably more state than our counter, so forcing all of it may involve traversing a much larger structure at every step.

Each new history cell points to the old history.

history = {
  head = item.key;
  tail = item.history;
};

Forcing a record, a field, or the whole structure does different work.

next = {
  total = item.total + 1;
  history = { head = item.key; tail = item.history; };
};

Repeated deep traversal revisits the growing prefix.

This interpreter deliberately demands its next state.

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

The forcing policy should follow the state you carry.

This function remembers which function to call first.

f0 = x: x;
step = previous: x: previous x + 1;

Each new function remembers the one before it.

f1 = step f0;
f2 = step f1;
f3 = step f2;

A function value can be ready while its body still has work.

builtins.deepSeq closureChain true

deepSeq a function into doing its job

builtins.deepSeq closureChain truetrueRecorded result

EvaluateExplore code

deepSeq can make the function value available without applying it to an argument. The large construction succeeds in this run, but its body still contains the chain of calls. The next experiment asks for a number from it.

Applying the function enters the remembered calls.

closureChain 0

The recursion has moved inside the callback.

And then I called it.

Forcing the function value did not run its body. The driver cannot schedule the nested calls still hidden inside that body; the next repair makes their pending work explicit.

These pending additions can be represented as data.

The dispatcher reads one frame and performs its operation.

apply = value: frame:
  if frame.tag == "add"
  then value + frame.amount
  else throw "Unknown frame";

The dispatcher performs the same three additions.

builtins.foldl' apply 0 frames

A machine makes its pending operations inspectable.

This has become a disproportionate response to addition.

I'm the evaluator now.

We began with effect callbacks and now have explicit frames, a dispatcher and machine state. Those pieces expose the work to the driver. Next we return to the borrowed driver and ask what it keeps after that work is finished.

genericClosure keeps every visited state reachable from its result.

Counts states the driver references; references inside a state are not shown.

while holding every visited state

The three-frame example used a fold. Return now to genericClosure, the driver borrowed for our counter: its result list keeps every visited record reachable after the arithmetic has finished. This archive belongs to that driver; an abstract machine does not inherently need it. The garbage collector cannot reclaim objects while live references still reach them. The records' payloads can retain further data, so completing the calculation does not by itself release everything used to obtain the answer.

Keeping only the current state removes this history root.

A native loop can run our steps without worklist keys or history.

The step returns either another state or the final value.

step = s:
  if s.i == 100000
  then [ false s.total ]
  else [ true (nextState s) ];

Our step still decides when to compute the carried total.

nextState = s:
  let total = s.total + 1;
  in builtins.seq total {
    i = s.i + 1; inherit total;
  };

The builtin supplies the loop we kept borrowing.

builtins.trampoline step { i = 0; total = 0; }

Keep the loop small, stack-safe, and interruptible.

After all that, I would quite like a loop.