# What a native trampoline should promise

A simple native loop that does not grow the call stack could have spared much of the improvised driver machinery. The native proposal removes the need to borrow a worklist from `genericClosure`. It does not remove the need to choose which parts of the carried state to evaluate. That distinction is the useful ending to the talk: every failed repair supplies a requirement or a limit for the proposed builtin.

## Reviewed source

[NixOS/nix PR #14553](https://github.com/NixOS/nix/pull/14553), by hsjobeki, was open and unmerged in the GitHub API capture on 22 September 2026. The reviewed head is `85bf7b5790da5ca182a6f82979d99aa10fc058a2`. The patch changes one file, `src/libexpr/primops.cc`; it contains a proof of concept without accompanying tests. Review records, comments, the patch and evaluator source are under `../evidence/trampoline/`.

The [original request, #8430](https://github.com/NixOS/nix/issues/8430), includes a different value/thunk protocol. Do not present that protocol as the API implemented by this PR. The native proposal is also distinct from the [nixpkgs polyfill proposal, #452088](https://github.com/NixOS/nixpkgs/pull/452088), linked in the review discussion. Its reviewed head is `8ce7b25` (the full identity is in the captured API response).

## What the native patch does

```nix
builtins.trampoline step initial
```

`step` returns a two-element list. `[ true next ]` continues with `next`; `[ false result ]` terminates with `result`. The terminating callback is the final callback. The result can have a different type from the carried state.

The implementation forces the function argument, copies the initial value, and enters a C++ loop. Before each callback it forces the carried value to weak head normal form. It forces the callback result to a list, checks its length, and forces the first element to a Boolean. On termination it forces the second element to weak head normal form before returning it.

| Boundary | Demand in the reviewed patch |
|---|---|
| Function argument | Must evaluate to a function |
| Initial state | WHNF, even if the callback ignores it |
| Intermediate state | WHNF before the next callback |
| Callback reply | List shape, exactly two elements |
| Continue flag | Boolean |
| Final result | WHNF, including when the caller would otherwise discard it |
| Record fields | Remain lazy unless the callback or later consumer demands them |
| Function body | Remains unexecuted until application |

The loop owns no visited-state collection and applies no key deduplication. It still allocates values for applications and replies. The current state, callback closure and result may retain earlier objects. Absence of a history collection is a source-level property; these experiments do not establish constant heap use.

For a record counter, the field dependency survives the move into C++:

```nix
builtins.trampoline (s:
  if s.i == 100000 then [ false s.total ]
  else let next = {
    i = s.i + 1;
    total = s.total + 1;
  }; in [ true (builtins.seq next.total next) ]
) { i = 0; total = 0; }
```

`seq next.total` is still necessary for this example. Merely forcing `next` exposes a record whose total can refer to the preceding total. A function-valued state has the corresponding limit: making its closure available does not turn recursive work inside its body into trampoline steps.

## Local probe and its limits

`prim-trampoline.cc` in the research harness copies the patch's function body. The surrounding plugin registration uses the installed Nix API's `.impl` member instead of the PR's `.fun`; its documentation identifies the experiment. The interrupt-control build injects one `checkInterrupt()` call and includes its declaration header. The full upstream checkout was **not** built. This tests the copied primitive against `nix (Nix) 2.35pre20260504_53ab7375`, not an upstream build at the proposed merge revision.

The harness uses an 8 MiB process stack and maximum call depth 10000. Normal cases have a 12-second timeout. Interruption cases receive SIGINT after one second, with SIGKILL available one second later. Nix warns that the stack hard limit is below its preferred size; the limit is intentional and appears in the captured diagnostics.

The final 22-case run passed 20 checks. Two interruption cases required SIGKILL; the explicit-check control stopped as expected:

- Scalar and targeted-record counters reach 100000. The slide's exact program also returns 100000.
- An unforced record can expose its field names; asking for its final total overflows.
- Deep forcing also repairs this small counter. An unrelated throwing field stays lazy with targeted demand and throws with deep demand.
- Constructing a function chain succeeds; applying the chain overflows.
- A terminal first callback returns immediately; the terminal result can change type. Throwing initial and terminal values establish their demand boundaries.
- Duplicate `key` fields are ordinary payload data. Malformed list shape, length and Boolean fail.
- The infinite constant-state loop does **not** exit after SIGINT in this experiment. It requires SIGKILL and returns status 137.

The interruption failure is material. The copied loop has no explicit `checkInterrupt()` call; the captured `forceValue` implementation also has its interrupt check commented out. A constant reply can therefore keep cycling without an effective check. This is a local reproduction against the installed evaluator, not a claim that every infinite callback ignores interruption. The unbounded `genericClosure` comparison also required SIGKILL. It does not establish a prototype-specific regression. A separate copy of the native primitive with `checkInterrupt()` added inside its loop did stop on SIGINT, returning the expected timeout status 124 and Nix's interrupted diagnostic. That control confirms signal delivery and supports the need for an effective interrupt check in this loop. The unchanged primitive and the control are separately built plugins; the control is not presented as upstream code.

Malformed reply tests establish rejection, not diagnostic quality. The patch's wrong-length message is `Wrong size :(`, and its builtin documentation still describes `removeAttrs`. Those need replacement before release. The patch contains no acceptance tests for these boundaries.

## Contract to discuss

1. **Keep the driver stack independent of the transition count.** The callback must return before the driver invokes the next step. Recursive work hidden inside a callback remains the callback's responsibility.
2. **State every demand boundary.** Initial, intermediate and terminal demand are observable. Preserve lazy unrelated fields; do not silently deep-force arbitrary state. Decide deliberately whether forcing an otherwise unused initial value is part of the API.
3. **Return a result without a driver-owned history.** Do not impose keys, deduplication or a returned list of visited states. Do not promise bounded heap use when user state can retain old objects.
4. **Specify termination precisely.** A stop reply prevents any further callback. Permit a final value of a different type, including a function value.
5. **Make interruption and errors part of correctness.** Check for interruption on the native loop path. Explain malformed replies with the builtin name and expected protocol. Test this alongside the large scalar benchmark.

The two-element Boolean protocol is small and sufficient to discuss semantics. An attribute-based continue/finish result could make call sites clearer; that is an API design question, not a property of the current patch. The important decisions are demand, termination, retention and interruption.

## Relation to earlier work

[sternenseemann's 2022 discussion](https://discourse.nixos.org/t/tail-call-optimization-in-nix-today/17763) explains the `genericClosure` approach. The [nixpkgs polyfill PR](https://github.com/NixOS/nixpkgs/pull/452088) takes another route through linked continuation data and an exponentially tiered binary reduction. Its logarithmic nesting strategy should not be described as the same implementation or a measured performance equivalent to the native loop. No comparative benchmark was run here.

The talk's arc is a set of escalating requirements: effect requests need a driver; the driver exposes lazy state; deep traversal exposes cost and function boundaries; explicit frames expose retention. The native builtin would remove the improvised driver machinery while leaving those semantics visible. That earns the final line: “After all that, I would quite like a loop.”