Design: constant-space tail calls on the explicit-frame VM (closures, multi-arity, apply)

[nnunley]

Summary

#645 changes the starting point for #620.

The compiler already emits OP_TAIL_CALL for ordinary calls in tail position. Before #645, a tail call to a *Closure or *MultiArityFn fell through ExecContext.Invoke into a nested Frame.Run, so deep recursion grew the Go stack. #645 makes those direct bytecode spans Go-stack-safe by descending through an explicit parent-linked frame chain.

That is not yet general tail-call elimination. A closure or multi-arity tail call still allocates and retains one child Frame per call. The remaining #620 goal is therefore:

Reuse the current VM frame for every resolvable bytecode tail call, including closures and multi-arity functions, and make apply* capable of handing its target back to the VM tail loop without exposing a continuation as a let-go Value.

The implementation should be stacked on #645. It must not introduce a second callee resolver or a second frame-acquisition path.

State after #645

Call path	#645 behavior	Remaining #620 work
Non-tail direct bytecode call	Descend to a child heap frame; flat Go stack	None for Go-stack safety; non-tail depth remains linear heap growth
Tail *Func	Existing same-frame reuse	Move onto the shared resolver/transition path
Tail *Closure	Descend to a child frame	Reuse the current frame while installing captures
Tail *MultiArityFn	Resolve the variant, then descend	Reuse the current frame after variant selection
Tail metadata-wrapped bytecode fn	Unwrap, then descend	Reuse through the same target preparation path
Tail native leaf	Invoke and return its value	Preserve terminal behavior and error attribution
Tail apply*	Native calls public ExecContext.Invoke, hiding the target behind a new invocation segment	Return a private pending-call outcome to the tail loop
Tail ProtocolFn	Protocol dispatch calls public ExecContext.Invoke	Resolve the implementation into the shared raw path, if included in v1
Tail MultiFn	Dispatch function and selected method are nested invocations	Requires a resumable dispatcher; explicitly include or defer

Goals and non-goals

Goals for v1

• Constant Go and VM-frame space for tail calls to *Func, *Closure, and *MultiArityFn, including metadata wrappers and closures over multi-arity functions.
• Tail-transparent apply* without allowing an internal continuation to escape through Value, variables, collections, or public host APIs.
• One shared path for callee unwrapping, multi-arity selection, closure captures, fixed/variadic arity validation, argument preparation, and frame transition.
• Preserve current OP_TAIL_CALL semantics for protected regions, dynamic bindings, errors, tracing, profiling, and host entry points.

Non-goals for v1

• Eliminating the necessary heap frame chain for non-tail calls. vm: make direct bytecode calls non-recursive with an explicit frame chain #645/vm: Frame.Run is Go-recursive — deep lg→lg recursion aborts the process #644 own that path and its resource budget.
• Making every native builtin resumable. reduce, map, and other natives that synchronously call back into let-go remain a broader native-continuation boundary unless they explicitly adopt the raw protocol.
• CPS conversion or replacement of the compiler IR.
• The deferred static self-call opcode from closed PR feat(vm): OP_CALL_SELF for non-tail self-recursive defn calls #618. That hypothesis is preserved in perf(vm): re-evaluate static self-call shortcut after shared frame transitions #646 and must use this shared transition seam if revisited.
• Claiming arbitrary custom IFn, callable Var, or ifnAdapter values are constant-space unless they are explicitly covered by the resolver and tests.

Architecture

1. Separate call preparation from frame allocation

#645's childFrameFor currently combines two responsibilities:

1. resolve MetaFn / MultiArityFn / Closure to a concrete bytecode *Func, preserving captures and validating/packing arguments;
2. allocate and initialize a child Frame.

Extract the first responsibility into a behavior-preserving resolver. The exact names are not prescribed, but the shape is:

type bytecodeCallTarget struct {
    fn          *Func
    args        []Value
    closedOvers []Value
}

func resolveBytecodeCall(fn Fn, args []Value) (bytecodeCallTarget, bool, error)

bool == false means the callable is not a directly executable bytecode target and must proceed through raw/public invocation. The resolver owns:

• metadata unwrapping;
• multi-arity fixed/rest selection;
• closure capture preservation, including closure-over-multi-arity;
• exact and variadic arity errors;
• rest-list packing semantics.

It does not allocate a frame or decide whether the call is tail-positioned.

2. Give one prepared target two transitions

The caller chooses the transition, not the resolver:

• Non-tail OP_INVOKE: allocate a child frame, link it to the suspended parent, and descend as vm: make direct bytecode calls non-recursive with an explicit frame chain #645 already does.
• Tail OP_TAIL_CALL: replace the current frame's executable state with the prepared target and continue the same dispatch loop.

The tail replacement must install, at minimum:

• code, consts, and constsc;
• closedOvers (clear for plain functions, install for closures);
• owned arguments and argc;
• ip = 0 and sp = 0;
• sufficient operand-stack capacity.

The existing separate zero/nonzero-arity OP_TAIL_CALL branches should converge on this path.

3. Make argument ownership explicit

Arguments read by OP_TAIL_CALL are slices into the current operand stack. They cannot remain borrowed while that stack is reset and reused.

The transition must copy/reposition them into storage owned by the reused frame before overwriting the source. Variadic packing must also be fresh or frame-owned; the current append(sargs, restlist) tail path can reuse and mutate an input backing array.

A reusable frame-owned argument buffer is preferable to allocating a new slice on every tail hop. Correctness comes first; allocation behavior is measured and optimized after the ownership invariant is explicit.

4. Split raw invocation from public invocation

Fn.Invoke, NativeFn.proxy, and public ExecContext.Invoke return (Value, error). A pending call must not implement Value merely to fit those interfaces.

Introduce a private/raw outcome with two states:

• final Value;
• pending (Fn, []Value).

Then enforce these boundaries:

• raw invocation performs one dispatch step and may return a pending call;
• public ExecContext.Invoke iteratively drains pending calls and returns only a final Value;
• non-tail OP_INVOKE uses the draining/public behavior when a callable cannot become a direct bytecode child;
• OP_TAIL_CALL consumes the raw outcome, so a pending bytecode target can replace the current frame;
• direct Fn.Invoke entry points remain continuation-proof.

Because apply* is defined in pkg/rt, the opt-in API may need a small exported constructor or opaque outcome type. It must remain impossible to store the pending-call object as a let-go value.

5. Make apply* the first raw continuation producer

apply* already normalizes its final sequence into (fn, args). Instead of recursively calling public ec.Invoke, its raw form returns that pending call. Public/non-tail callers drain it immediately; a tail opcode can reuse its frame for the target.

This does not imply that every callback-taking native becomes resumable in v1.

6. Define dispatcher scope explicitly

ProtocolFn can resolve its implementation without first invoking another function, so it is a reasonable v1 candidate for returning the implementation as a pending call.

MultiFn is different: it must invoke the dispatch function, await its value, select a method, and then invoke the method. Constant-space recursion through a multimethod therefore needs resumable dispatcher state, not only a (fn, args) redirect. Either implement that state machine deliberately or mark MultiFn out of scope for v1. Do not call it bounded while it still nests one dispatch continuation per recursive call.

Correctness invariants

• Public APIs never return a pending-call outcome.
• A prepared call has exactly one owner for argument storage before frame replacement begins.
• Closure captures survive metadata and multi-arity unwrapping.
• Same-frame replacement is legal only when no handler or cleanup continuation must return to the current body. The compiler already clears tail position inside try/catch/finally; retain runtime assertions or a safe fallback and add regressions.
• binding and with-redefs cleanup remains intact.
• Eliminated tail frames may disappear from traces, but errors from arity resolution, native leaves, apply*, and dispatcher selection receive a defined nearest-call-site source.
• Preserve the current tracing/profile/allocation-attribution semantics of the existing *Func tail-reuse path unless a separate change intentionally revises them.
• OP_RECUR and OP_RECUR_FN remain in-frame recursion mechanisms; do not route them through the general resolver merely for symmetry.

Execution plan

Phase 1 — resolver extraction, no behavior change

• Stack a branch on vm: make direct bytecode calls non-recursive with an explicit frame chain #645.
• Replace childFrameFor with a pure prepared-target resolver plus a separate child-frame constructor.
• Route vm: make direct bytecode calls non-recursive with an explicit frame chain #645's non-tail descent through the new split.
• Add table-driven tests for metadata, fixed/rest multi-arity, closure captures, variadic packing, arity failures, and unsupported/native fallthrough.
• Run the full suite, race tests for pkg/vm, allocation ratchets, and the existing vm: make direct bytecode calls non-recursive with an explicit frame chain #645 benchmark matrix.

Exit gate: bytecode and observable behavior are unchanged; no tail-reuse behavior is added.

Phase 2 — constant-space bytecode tail replacement

• Route all OP_TAIL_CALL arities through the prepared target.
• Replace the current frame for Func, Closure, and MultiArityFn targets.
• Add frame-owned argument storage or an equivalent ownership-safe transition.
• Preserve captures, arity errors, variadic semantics, source attribution, and protected-region behavior.

Exit gate: deep capturing-closure and multi-arity tail recursion use one live VM frame rather than a linear parent chain.

Phase 3 — raw invocation and apply*

• Introduce raw outcome and public draining layers.
• Make apply* return a pending call through the raw-only API.
• Ensure tail apply* can replace the current frame; non-tail and host callers still receive ordinary values.
• Prove that no outcome escapes through direct Invoke, Vars, collections, macros, callbacks, or host APIs.

Exit gate: deep recursion through tail-position apply* is constant-space, and non-tail apply* is semantically unchanged.

Phase 4 — dispatchers

• Route ProtocolFn resolution through the raw path if included in v1.
• Decide whether MultiFn gets a resumable dispatcher in this issue or a dedicated follow-up.
• Narrow the issue's “arbitrary callee” wording to exactly the implemented/tested set.

Phase 5 — validation and performance disposition

• Full tests and race tests.
• Generated-bundle checks and supported target builds.
• Deep tests under a live-frame counter/budget so vm: make direct bytecode calls non-recursive with an explicit frame chain #645's heap-linear descent cannot accidentally satisfy a tail-space assertion.
• Interleaved benchmarks through both Frame.Run and Func.Invoke.
• Controls for ordinary direct calls, closures, collections, and loop/recur.
• Allocation measurements for fixed, variadic, closure, multi-arity, and apply* tail loops.

Required tests

• Multi-million top-level mutual tail recursion.
• Multi-million mutual recursion through closures with a real capture.
• Multi-arity fixed and rest variants, including a closure over the multi-arity function.
• Metadata-wrapped functions and closures.
• Tail-position arity mismatch parity with ordinary invocation.
• Variadic argument immutability for vector-backed apply*.
• Tail and non-tail apply*.
• Direct/public Invoke containment: only final Value escapes.
• try/catch/finally, binding, and with-redefs cleanup.
• Error source attribution across eliminated tail calls.
• Protocol recursion if ProtocolFn is in v1.
• Multimethod recursion only if MultiFn is claimed in scope.

Relationships

• vm: make direct bytecode calls non-recursive with an explicit frame chain #645 is the required base: explicit non-tail child descent and the initial bytecode-target resolver.
• vm: Frame.Run is Go-recursive — deep lg→lg recursion aborts the process #644 owns non-tail frame growth, execution budgeting, and the remaining general native-callback boundary.
• feat(vm): OP_CALL_SELF for non-tail self-recursive defn calls #618 is closed; its separate OP_CALL_SELF path must not be revived unchanged.
• perf(vm): reuse frames per bytecode call tree #619 is closed; there is no arena path to coordinate.
• perf(vm): re-evaluate static self-call shortcut after shared frame transitions #646 preserves the possible static self-call shortcut after the shared transition machinery is stable.

Open decisions before Phase 3

1. Is ProtocolFn required for v1? Recommendation: yes; its lookup can redirect without a resumable intermediate computation.
2. Is MultiFn required for v1? Recommendation: no; track the resumable dispatch state separately unless implementation work shows it is small and reviewable.
3. What raw continuation API should pkg/rt receive? It must be opaque to let-go values and impossible to leak through public Invoke.
4. Should tail replacement preserve today's trace/profile behavior exactly, or should logical callee transitions become visible? Recommendation: preserve current behavior in Design: constant-space tail calls on the explicit-frame VM (closures, multi-arity, apply) #620 and make observability changes separately.

[mparrett]

@nnunley Thanks for tagging me here re: 618/619. I'll take a look.

[mparrett]

Preliminary look confirms #619 is complementary, and #618 is checking out as not actually redundant:

#620 explicitly excludes non-tail recursion; #618 specifically optimizes non-tail self-calls. Naive Fibonacci remains a #618/#619 workload and receives no help from general TCE. The real question is whether #618’s narrower gain justifies another opcode and dispatch path—not whether #620 replaces it.

More detailed analysis to come.

[mparrett]

Thanks for writing this down. I agree with the goal, and with #619 being complementary. I do not think #618 is redundant: #620 explicitly leaves non-tail recursion alone, while #618 specifically optimizes non-tail self-calls. Naive Fibonacci remains a #618/#619 workload.

After checking the proposal against current origin/main and the #618/#619 heads, I don't think the continuation mechanism is implementable safely as currently specified. I would resolve these points before turning it into code:

1. The proposed continuation does not fit the current interfaces. Fn.Invoke, NativeFn.proxy, and NativeFn.ctxProxy all return (Value, error), while tailCall is explicitly non-Value. Therefore apply* cannot return it. Making it implement Value would weaken the containment invariant rather than solve it.

   I suggest a private outcome type behind a raw invocation layer, e.g. “final Value or pending call,” while every public Invoke continues to return only Value.

2. Raw and public invocation need to be separate. A loop in public ec.Invoke cannot call public ec.Invoke again and expect to observe an unresolved continuation: the inner call either drains it or recreates recursive Go calls. The shape needs to be:

   • invokeRaw: performs one dispatch step and may return a continuation
   • Invoke: iteratively drains invokeRaw outcomes and returns only Value
   • OP_INVOKE: uses the public/draining layer
   • OP_TAIL_CALL: consumes the raw outcome so it can reuse its frame

3. MultiFn and ProtocolFn are not bounded as written. Both currently call public ec.Invoke for the selected implementation. Calling them through public ec.Invoke and then looking for a tailCall cannot work, because public invocation must have already drained it. For constant-stack dispatch, MultiFn should fully evaluate its dispatch function, then return the selected method as a raw continuation; ProtocolFn should return its resolved implementation the same way. Otherwise recursion through either dispatcher still nests Frame.Run/Go calls.

4. Closure state has to survive multi-arity selection. Closure.fn is an Fn, not necessarily a *Func; it can be a *MultiArityFn. The proposed fn.fn.(*Func) unwrap can therefore panic, and selecting a multi-arity variant before reconstructing the closure loses closedOvers. The pending-call/resolver state needs to carry captures, or variant selection must explicitly preserve the enclosing closure.

5. Argument ownership and arity validation need one shared preparation path. Arguments from OP_TAIL_CALL are slices into the current frame stack; feat(vm): OP_CALL_SELF for non-tail self-recursive defn calls #618 also deliberately borrows caller-stack slices. They must be copied/repositioned before resetting or overwriting that storage.

   Also, boxRest does not make the packed argument slice fresh: the current append(sargs, restlist) can reuse and mutate the input backing array. This is observable today:

   (let [v [1 2 3]]
     [(apply* (fn [x & xs] xs) v) v])
   ;; => [(2 3) [1 (2 3) 3]]

   Direct frame reuse must also perform ordinary exact-arity checks. Today a tail-position zero-arg call of a one-arg *Func reports argument lookup out of bounds, while the ordinary path correctly reports “expected 1 args, got 0.” A shared helper for fixed arity, variadic packing, multi-arity selection, ownership, and captures would prevent the resolver from duplicating these semantics.

6. The “arbitrary callee” claim needs either broader coverage or narrower wording. The listed switch does not cover callable Var values, ifnAdapter/custom IFn values, or other wrappers whose Invoke method internally dispatches to another function. There are also many legitimate direct Fn.Invoke entry points outside ExecContext.Invoke (Vars, Atom callbacks, LazySeq/Delay, host callbacks, compiler macro execution, etc.). Containment should be enforced by the type/API boundary—not by assuming all calls already pass through ec.Invoke.

7. Protected-region behavior is mostly guarded already. tryCompiler sets tailPosition = false for the protected body, catch, and finally code. binding expands through try/finally, and the with-redefs body call is inside a try/catch. I would retain explicit regressions, but this is not currently the latent bug described above.

   I would also change “preserve f.handlers” to a stronger invariant: same-frame reuse is only legal when there is no pending handler/cleanup continuation. A protected non-tail call must drain its continuation in a child invocation and return to the protected caller.

8. Error and trace attribution needs an explicit policy. The resolver swaps f.code/f.ip, so it must capture the relevant call-site source before the swap. Eliminated tail frames can intentionally disappear, but errors from native leaves, apply, arity resolution, and dispatcher selection should have a defined nearest-call-site rule.

Architecturally, if #619 lands first, its invokeWithArena is the natural seam to refactor into the raw dispatcher. I would avoid maintaining separate overlapping type switches in ExecContext.Invoke, invokeWithArena, and the tail resolver.

A compact implementation shape would be: one private raw dispatcher producing an outcome; public Invoke loops until that outcome is a value; the tail opcode can turn a reusable-bytecode outcome into a frame reset; and all public/direct Invoke methods remain continuation-proof. That also leaves a clean opt-in seam for generated/AOT functions later.

Tests I would add beyond the issue list: tail-position arity mismatches, closure-over-multi-arity with captures, meta-wrapped closures/natives, deep recursion through MultiFn and protocol/IFn dispatch, direct-Invoke containment, and argument immutability for vector-backed apply*.

So: strong +1 on pursuing general TCE, but I would not endorse the current sentinel design without the raw-result API and ownership/dispatch details above.

[mparrett]

Follow-up data relevant to the coordination section. I re-measured the #618/#619 stack end-to-end — through lg -b bundled binaries (what embedders ship) and through direct Func.Invoke entry — and cross-checked with the #621 in-process entry-mode harness. Three results changed my disposition recommendation:

1. #618 and #619 as published do not compose. A plain merge of the two heads is slower than #618 alone on the workload both PRs target (in-process fib(20): #618 runs 13-16% faster than main; the merge gives most of that back; end-to-end fib(32) shows the same ordering). Root cause: OP_CALL_SELF acquires child frames through NewFrame, the global mutex pool, while #618 replaces exactly the recursive-arm OP_INVOKEs that #619's arena accelerates. Combined, the hot recursive path pays #619's per-frame bookkeeping and receives none of its mutex-free reuse. A plain merge does not reproduce the +15% combined figure in the #618 PR body; that number evidently required CALL_SELF children to come from the arena, and neither head includes that glue. The fix is one line (child := newFrameIn(f.arena, f.code, rawArgs)), and with it the combination restores parity with #618 alone on my measurements; host noise is currently too high to establish whether it does better than parity.

2. Entry path is not a differentiator. The arena attaches at the first Func.Invoke boundary (for a bundled binary, the program's -main invocation), so lg -b binaries and API callers behave the same. #619's standalone value therefore reduces to its measured 2-3% on deep non-tail recursion, plus its still-unresolved shallow-call regression on standalone NewFrame.Run entry.

3. Disposition update. I'm closing #619 (details in a comment there); its branch stays for reference. #618 remains the one measurable non-tail win (reproduced at 8-16% depending on harness and workload). For this design, the composition failure is an instance of the hazard in point 2 of my earlier comment: the resolver should own frame acquisition end-to-end, so that specialized call paths (CALL_SELF today, any future generated/AOT entry) cannot silently diverge from it. A combined-tree benchmark assertion would have caught this before either PR merged; the eventual TCE implementation should include one.

Methodology: interleaved ABBA blocks, medians of paired per-round deltas, three independent instruments (bundled binary, Go-driver Func.Invoke entry, #621 in-process harness), and verified identical CALL_SELF emission across variants before attributing the difference to runtime behavior.

[mparrett]

The design section defers non-tail recursion to "#464", but #464 is Epic: Runtime performance & concurrency (Var.Deref, #459/#462/#463) and says nothing about a trampoline or a non-recursive Frame.Run. Nothing was tracking that work, so I've filed #644 for it.

It's the case this issue puts out of scope, and it fails hard: every non-tail let-go call consumes a Go stack frame, so at roughly 350k levels the process dies with fatal error: stack overflow. That's an uncatchable Go runtime abort, not an ExecutionError — no try sees it and an embedding host loses the process.

Two findings there bear on this issue directly.

The closure gap is real, but the obvious test passes vacuously. A (fn ...) that closes over nothing compiles to a plain *Func and gets OP_TAIL_CALL's frame reuse. My first run at the ev?/od? shape in the Testing section went a million deep and passed, because the mutual references resolve through vars rather than captures. Binding something in the enclosing let is what forces a *Closure; with a real capture it dies between 100k and 500k. Worth pinning explicitly in the test, or it will look green while covering nothing.

The non-tail fix may be a throughput win rather than a cost. I prototyped the explicit chain (branch, measurements in #644). Descending inside the dispatch loop instead of recursing into Go runs 7.9% faster than main on fib(32) — the nested Go call and its ~2.9 KB frame prologue per let-go call go away. Interleaved ABBA, medians of paired per-round deltas, against an A/A noise floor centered on zero; fib's per-round deltas are entirely negative, reduce/map is a smaller win whose range still spans zero. Caveat that this is a prototype with known residuals, and given how #618 and #619 failed to compose I'd expect it re-measured before anyone leans on it.

That second point is the one I'd weigh here. It lands on the frame-acquisition ownership question from my earlier comment: if the non-tail path also wants to own frame acquisition end to end, #644 and this issue are reshaping the same seam, and their order matters. My inclination is that the explicit chain goes first, since it changes what "reuse the frame" costs relative to descending. I don't hold that strongly though, and if you'd rather take general TCE first I'd want the combined-tree benchmark in place before either.

[mparrett]

The promised post-fix #644 measurement is now available. The three prototype findings are fixed on 196e03e7: multi-arity/metadata/capture-aware descent, balanced trace/profile/allocation lifecycle, and release of error-path frames via cleared parent links. Full suite and go test -race ./pkg/vm are green.

Fresh dc316a0c baseline vs corrected prototype, preserved interleaved ABBA harness:

• fib(32), 25 rounds: 4.25% faster (23/25 paired rounds faster; original provisional result was 7.9%).
• reduce/map, 25 rounds: 4.22% slower (24/25 paired rounds slower).
• call-free loop/recur, 12 rounds: nominally 5.08% faster but with a -18.22% to +7.89% range, so inconclusive.

That makes the throughput answer workload-dependent, not a blanket justification for the explicit chain. The architectural result is clearer: #620 tail reuse and #644 non-tail descent need the same callee-preparation/frame-transition seam, including multi-arity selection, captures, lifecycle, and frame acquisition. The prototype duplicated that seam and failed in exactly the ways discussed earlier; the corrective commit is evidence that those responsibilities must be centralized in a production design.