Trampolining Nix

How I nearly lost my mind fighting the evaluator

Mika Bohinen - NixCon 2026

Charlie Kelly tries to explain a wall of papers connected by red string.

The program asks for state; the handler supplies it.

An effect is a request whose meaning is supplied by a handler

Code

get

An operation and the handler that answers it

Program asksgetrequest the state

Handler replies21the current state

bind passes that reply to the rest of the program.

A continuation: the function to run after get replies

Code

s: put (s * 2)

The continuation turns the reply into the next request

get repliess = 21

continuation

Next requestput (s * 2)

Handler storesstate = 42

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

Read state, store twice the value, return the original

Code

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

Follow the requests and replies

get repliess = 21

put storesstate = 42

pure s returns21the original value

The state ends at 42; the program returns 21.

nix-effects / README.md

How far can these recursive calls nest?

Trace: recursive 3. Recorded run: n = 100000.

Code

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

recursive 3 nests four calls before any addition

Illustrative trace; spacing shows order, not elapsed time.

recursive n?

Explore code

The driver calls one step.

Every step gives control back to the driver

The driver has called the first step. It is the only call above the driver.

That call returns before the next one begins.

Every step gives control back to the driver

The first step has returned its reply. Its call is gone before the next one starts.

More steps. The same nesting depth.

Every step gives control back to the driver

Same scale as the recursive trace: more steps, but the depth stays at one.

A fold passes the running total to this function.

One addition per input

Code

total: _: total + 1

One call, starting from zero

Accumulatortotal = 0the initial value

total + 1

Next accumulator1

becomes total in the next call

Can a builtin fold run this counter?

scalarFold, with n = 100000

Code

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

scalarFold?

Explore code

The operator chooses a successor state or ends the traversal.

genericClosure owns the loop; operator chooses the next work

StartstartSetthe initial records

For each new recordoperator itemreturns a list

No successors[]this branch stops

Successors[ successor ]queued if the key is new

Queued records are passed to operator in turn

The result lists every visited record. Keys prevent revisiting the same identity.

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

genericClosure input; total stands in for the handler's state

Code

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

One state, two jobs

key = 0

Identity used by the worklist

total = 0

Payload used by our counter

Build the successor from the current record, item.

Inside the operator: the next total, then the successor record

Code

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

The first call to operator

Current itemkey = 0total = 0the seed

operator

Successorkey = item.key + 1inherit (next) totalno addition has run yet

Return no successors when the key reaches the limit.

Operator excerpt; the else branch returns the successor in a list

Code

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

The operator returns a list

Condition		operator returns	Effect
`item.key < n`		`[ successor ]`	one more state
`item.key >= n`		`[]`	this branch stops

n = 100000. The seed has key 0; the last visited record has key n.

naive names the returned list, including the initial state.

Combine the seed and operator we just built

Code

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

The returned list is named naive

First elementkey = 0the seed

Second elementkey = 1

…

Last elementkey = nselected by last naive

builtins.length naive and (last naive).total are the next two questions.

Surely the hard part is over.

A toddler clenches his fist with a triumphant expression. — Found a loop in Nix.

Did visiting every state compute the answer?

naive is the list of states returned by my first attempt at a counter.

How many states were visited?

builtins.length naive?

Explore code

What is the final total?

(last naive).total?

Explore code

I had a rather generous definition of finished.

KC Green's dog calmly sits in a burning room. — The loop has finished.

The key and the total have separate demand paths.

The two field expressions, extracted from the operator

Code

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

Empty source

Keys move forward; each total refers back

keytotal

successorrefers to

1total[0] + 1

2total[1] + 1

computed number
deferred expression
evaluated record

Three states shown; total[k] is the total of the state with key k.

Visiting evaluates each record and its key

keytotal

successorrefers to

1total[0] + 1

2total[1] + 1

computed number
deferred expression
evaluated record

Three states shown; total[k] is the total of the state with key k.

Reading the final total climbs through every deferred addition

Illustrative trace for n steps; the recorded run overflows at n = 100000.

seq next evaluates the record, not its total

keytotal

successorrefers to

1total[0] + 1

2total[1] + 1

computed number
deferred expression
evaluated record

Three states shown; total[k] is the total of the state with key k.

First transition: compute 1, then expose key 1

keytotal

successorrefers to

next?

computed number
deferred expression
evaluated record

Three states shown; total[k] is the total of the state with key k.

Each transition carries a computed number

keytotal

successorrefers to

computed number
deferred expression
evaluated record

Three states shown; total[k] is the total of the state with key k.

Each step computes its total before the next begins

Illustrative trace for n steps; the recorded run returns 100000.

?

Explore code

Is forcing next.stats enough?

The two field expressions, extracted from the operator

Code

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

Empty source

Keys move forward; each total refers back

keystats.total

successorrefers to

1stats.total[0] + 1

2stats.total[1] + 1

computed number
deferred expression
evaluated record

Three states shown; stats.total[k] is the stats.total of the state with key k.

seq next.stats evaluates stats, not stats.total

keystats.total

successorrefers to

1stats.total[0] + 1

2stats.total[1] + 1

computed number
deferred expression
evaluated record

Three states shown; stats.total[k] is the stats.total of the state with key k.

Each transition carries a computed number

keystats.total

successorrefers to

computed number
deferred expression
evaluated record

Three states shown; stats.total[k] is the stats.total of the state with key k.

?

Explore code

Why not force the whole state?

A girl smiles at the camera while a house burns behind her. — I'll force the whole state.

Each new history cell points to the old history.

The new history field inside next

Code

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

The new cell retains the existing chain

New cellhead = item.keytail = item.history

tail

Previous cellitem.historyshared, not copied

tail

Earlier cells…

Extending adds one cell. Deep traversal walks every link again.

How much of this state does each demand evaluate?

next now carries a history

Code

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

The same state, three demand boundaries

Demand	Evaluates	Still deferred
`seq next`	the record	total, history
`seq next.total`	total	history
`deepSeq next`	total and every history cell	nothing

Forcing a function value does not execute its body.

Repeated deep traversal revisits the growing prefix.

A traversal of the whole retained chain after every extension

Step 1

cell 1

1 visit

Step 2

cell 1cell 2

2 visits

Step 3

cell 1cell 2cell 3

3 visits

1 + 2 + 3 = 6 visits

n steps cost n(n + 1) / 2 visits: about 5 billion at n = 100000.

This interpreter deliberately demands its next state.

nix-effects interpreter

Code

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

nix-effects / src/trampoline.nix

The forcing policy should follow the state you carry.

Handler state

deepSeq newState

A deliberately broad policy for carried state.

Concrete syntax walk

key = item.key + 1;

A different workload avoids unnecessary traversal.

nix-effects / src/tc/eval/core.nix

This function remembers which function to call first.

step wraps previous in a closure

Code

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

Constructing a function that remembers previous

Callstep f0

returns

A new functionx: previous x + 1remembers previous = f0

Each new function remembers the one before it.

Three wrappers; no argument has been supplied to f3

Code

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

Arrows are captured references, not calls

Wrapperf3adds 1 after previous

previous

Wrapperf2adds 1 after previous

previous

Wrapperf1adds 1 after previous

previous

Base functionf0returns x

What does deepSeq do with this larger function?

closureChain: the same construction, repeated 100000 times

Code

builtins.deepSeq closureChain true

builtins.deepSeq closureChain true?

Explore code

What happens when we apply the larger function?

Run the larger construction

Code

closureChain 0

f3 0 nests four calls before any addition

Illustrative trace; spacing shows order, not elapsed time.

closureChain 0?

Explore code

The recursion has moved inside the callback.

Pikachu stares in open-mouthed surprise. — I forced the function.

These pending additions can be represented as data.

Preserve the pending operation and its order

Function bodyx: previous x + 1

previous is the remembered function. The pending operation is + 1.

Explicit pending operation{ tag = "add"; amount = 1; }

Store the operation for the dispatcher to perform. Written add 1 below.

Where did previous go? Its links become the order of the frame list.

First: f1's additionadd 1

Then: f2's additionadd 1

Last: f3's additionadd 1

Defunctionalization

The dispatcher reads one frame and performs its operation.

apply: the dispatcher for add frames

Code

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

Hand trace: one frame

Current value0

apply reads the frametag = "add"amount = 1

New value1value + frame.amount

Do the frames produce the same result?

frames holds the three add records

Code

builtins.foldl' apply 0 frames

f3 0?

Explore code

builtins.foldl' apply 0 frames?

Explore code

A machine makes its pending operations inspectable.

Each transition consumes one frame and carries the rest forward

Each transition consumes the top frame; the remaining frames keep their order.

nix-effects / src/tc/eval/machine.nix

This has become a disproportionate response to addition.

The hijacker in Captain Phillips points to his eyes while taking command. — Look at me.

genericClosure keeps every visited state reachable from its result.

The visited list holds every state until return

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

A skeleton waits at a computer. — Me waiting for the garbage collector

Keeping only the current state removes this history root.

The driver holds one state at a time

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

nix-effects / src/tc/eval/machine.nix

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

The borrowed machinery	What the loop needs
Nested driver calls	Return from one step before calling the next
A fold needs a list of inputs	Let each step choose whether to continue
Worklist keys and visited history	Carry the current state; return the final result

The step still chooses which fields to compute and which calls to make.

The step returns either another state or the final value.

Proposed step protocol; nextState constructs one successor

Code

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

Each reply gives control back to the native driver

step returns		The native driver
`[ true nextState ]`		calls step with nextState
`[ false value ]`		returns value as the result

hsjobeki / NixOS/nix #14553 - open, unmerged - checked 22 September 2026

Our step still decides when to compute the carried total.

The same targeted forcing policy, now inside nextState

Code

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

The payload policy stays in our program

Current statei = 0total = 0

seq computes firsttotal = s.total + 1before the record is returned

Next statei = 1total = 1total is already a number

hsjobeki / NixOS/nix #14553 - open, unmerged - checked 22 September 2026

The builtin supplies the loop we kept borrowing.

The step and payload policy have already been defined

Code

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

The native driver replaces our borrowed worklist

Initial statei = 0total = 0

Native driverstep currenteach call returns a reply

Finish reply[ false value ]the driver returns value

[ true nextState ]: nextState becomes current

No driver-owned list of every state. No keys for deduplication.

hsjobeki / NixOS/nix #14553 - open, unmerged - checked 22 September 2026

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

Case	What I want the contract to say
The step says finish	No further step is called
A million steps	The driver stack does not grow with them
Only the final state is needed	No driver-owned collection of every state
The loop never says finish	An interrupt still stops it

The step chooses which fields to force. Recursive callbacks still need explicit steps.

After all that, I would quite like a loop.

Run the next step without growing the call stack.

nixcon2026.bohinen.no

Examples - captured evidence - reading - PDFs

Discuss builtins.trampoline: NixOS/nix #14553 / Prototype review / Probe results

sternenseemann: trampolining Nix (2022)

Overview

Trampolining Nix
The program asks for state; the handler supplies it.
bind passes that reply to the rest of the program.
The program changes the state, then returns the original value.
How far can these recursive calls nest?
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.
Can a builtin fold run this counter?
The operator chooses a successor state or ends the traversal.
Start with one record: an identity and a running total.
Build the successor from the current record, item.
Return no successors when the key reaches the limit.
naive names the returned list, including the initial state.
Surely the hard part is over.
Did visiting every state compute the answer?
I had a rather generous definition of finished.
The key and the total have separate demand paths.
Did the worklist visit every step?
What work remains in the final total?
Does forcing next also compute total?
The next key becomes available after next.total has been computed.
The following step receives a total that has already been computed.
Does forcing next.total finish the counter?
Is forcing next.stats enough?
Does forcing stats compute its total?
Does reaching stats.total repair the counter?
Why not force the whole state?
Each new history cell points to the old history.
How much of this state does each demand evaluate?
Repeated deep traversal revisits the growing prefix.
This interpreter deliberately demands its next state.
The forcing policy should follow the state you carry.
This function remembers which function to call first.
Each new function remembers the one before it.
What does deepSeq do with this larger function?
What happens when we apply the larger function?
The recursion has moved inside the callback.
These pending additions can be represented as data.
The dispatcher reads one frame and performs its operation.
Do the frames produce the same result?
A machine makes its pending operations inspectable.
This has become a disproportionate response to addition.
genericClosure keeps every visited state reachable from its result.
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.
Our step still decides when to compute the carried total.
The builtin supplies the loop we kept borrowing.
Keep the loop small, stack-safe, and interruptible.
After all that, I would quite like a loop.

Worked example

The fold returns an attribute set. Ask for its names without demanding the value of total.

Definitions · example.nix

n = 100000;
ticks = builtins.genList (i: i) n;
result = builtins.foldl'
  (acc: _: { total = acc.total + 1; })
  { total = 0; } ticks;

Empty source

Expression

Inspect the code, then run the expression.

Result

Not run

Reference