Evaluate dropping subroutine hopper — `call('foo')` could wrap `foo::1` directly

[mellonis]

Background

PostMachine constructs a separate hopper State for each subroutine, named after the subroutine itself (e.g., rightToBlank). The hopper's only transition forwards to the first instruction ([ifOtherSymbol]: { nextState: rightToBlank::1 }). call('foo') wraps the hopper:

// commands.ts ~107
const state = subroutineInitialStates[subroutineName]  // ← the hopper
  .withOverriddenHaltState(new State({
    [ifOtherSymbol]: { nextState: nextInstruction },
  }, continuationName));

This dates from v6.1.0's instruction-derived naming work (per packages/machine/CLAUDE.md).

The asymmetry

Level	Entry-point structure
Top-level program	idle -. enter .-> 1 — idle sentinel points directly at the first numbered instruction. No hopper.
Subroutine foo	caller → wrapper → call ==> foo (hopper) → "[*]" → foo::1 — extra hopper hop before the first instruction.

Surfaced while writing the callable-subtree visualization spec for turing#174 — the new diagram model makes the asymmetry visually obvious (the hopper appears as a bare inside the subtree, adding an extra node between the wrapper's call arrow and the first body instruction).

Proposed change

Drop the hopper. call('foo') directly wraps foo::1:

const state = subroutineFirstInstruction[subroutineName]  // foo::1
  .withOverriddenHaltState(continuation);

subroutineInitialStates[name] either renamed (to subroutineFirstInstruction) or eliminated as redundant with the existing instruction-state cache.

What changes

Composite wrapper name: foo(continuation) → foo::1(continuation). Slightly less readable but accurately reflects the bare's identity.

Per-subroutine state count: -1 State per subroutine (the hopper). Small memory + GraphNode count win, especially for libraries with many subroutines.

Symmetry: top-level and subroutine both have a "first numbered instruction is the entry" model. Reads consistently across nesting depths.

Engine emit (under turing#174's callable-subtree model): subtree_foo::1 contains foo::1, foo::2, halt marker. Wrapper [[foo::1(1~2)]] calls into the subtree's foo::1 bare directly. One less node per subroutine in the diagram.

Trade-offs / concerns

1. Composite-name readability. foo(continuation) is more "subroutine-call-like" than foo::1(continuation). The latter accurately names the bare but obscures the subroutine name. Mitigation: PostMachine could still expose subroutineName as a separate field on the wrapper for display purposes (e.g., in summarizePostMachine).

2. Breakpoint registry / instruction-derived paths. PostMachine's debug lockdown registers each per-instruction State separately. The hopper had its own registry entry under the subroutine's name. Dropping it removes that registry entry — paths that referenced the hopper (pm.setBreakpoint("foo"), etc.) would need to target "foo::1" instead. Documented migration needed.

3. Backward compat. Diagram emit shape changes (one less node per subroutine, different composite-name). Tests that pin state names would need updates. summarize* output may differ. The states.md artifacts for library-binary-numbers would regenerate.

4. stateAt(path) lookup. Currently pm.stateAt('foo') returns the hopper. Post-change, what does it return? The first instruction (foo::1)? Or throw? Spec a clear migration.

Alternative (briefly considered)

Render the hopper as a visualization-only sentinel (stadium shape s([…]) like idle) without dropping it. Preserves the runtime State but makes the asymmetry meaningful (different shape = different role). Rejected as a separate engine-spec change; the symmetry argument here is structural, not just visual.

Scope

• Single-package change in @post-machine-js/machine.
• v6.x major or v7.x — likely needs a major version bump (breaking change to wrapper composite names + breakpoint paths + diagram shape).
• Coordinate with turing#174 — once both ship, the PostMachine subroutine diagram becomes clean and symmetric with top-level.

Related

• turing-machine-js#174 — callable-subtree visualization (where this asymmetry first surfaced visibly).
• post-machine-js v6.1.0 work that introduced instruction-derived names.

[mellonis]

Probe: mutual subroutine recursion currently works

Before sketching the implementation, I ran a probe:

new PostMachine({
  foo: { 1: call('bar'), 2: stop },
  bar: { 1: call('foo'), 2: stop },
  1: call('foo'),
  2: stop,
});
// → constructs cleanly. initialState.name === "foo(1~2)"

So mutual recursion (foo calls bar, bar calls foo) is supported today. The hopper is the forward-declaration anchor that makes this work, not just visual padding.

What breaks under the issue's proposal as written

The proposal says call('foo') should wrap foo::1 directly. But during foo's body construction, the producer for foo::1 may invoke call('bar') — which would need bar::1 to exist as a State. If bar hasn't been recursively built yet (mutual cycle, or just iteration order), bar::1 doesn't exist.

The current hopper sidesteps this: subroutineInitialStates['bar'] is a hopper State whose single transition uses a Reference to bar::1. The reference resolves at runtime, not at construction. So call('bar') can wrap the hopper before bar is built.

A direct subroutineFirstInstruction['bar'].withOverriddenHaltState(...) requires subroutineFirstInstruction['bar'] to already be a real State — which we can't guarantee under mutual recursion.

Options I see

(A) Drop the hopper unconditionally; remove mutual-recursion support. Document it as no longer supported in the migration notes. Cleanest implementation; loses a feature. Worth asking: is anyone using mutual subroutine recursion? Looking at library-binary-numbers (the only large real consumer), I don't see any mutual-recursion patterns — but external users may.

(B) Keep the hopper; tackle the visual asymmetry engine-side. Engine could render the hopper transparently (e.g., as part of the wrapper's [[…]] label rather than as a separate node inside the subtree). Smaller win — still one less node visually, but structurally unchanged.

(C) Hybrid: hopper only for subs that participate in cycles. Static call-graph analysis at construction time. Eliminate hoppers for acyclic subs (the common case); keep them for cyclic. Captures most of the win. Bigger implementation: 2 code paths for subroutineInitialStates, call-graph builder, cycle detection.

(D) Deferred wrapper construction. call('foo') returns a sentinel; a final pass after all subroutines are built materializes the actual wrapper = foo::1.withOverriddenHaltState(continuation). Bigger refactor of the state-producer pipeline.

Recommendation

(A) if mutual recursion is genuinely unused — simplest, fixes the asymmetry the issue is actually about. The "evaluate" verb in the issue title is now answered: the proposal as documented breaks a working feature, so it needs scope clarification.

(C) if mutual recursion must stay supported — moderate complexity but preserves backward compat.

(B) is a non-fix per the issue ("Rejected as a separate engine-spec change").

(D) is the most principled but I'd want a separate spec doc before implementing.

Which way? Or is there a use case for mutual recursion you know about that I'm missing?

[mellonis]

Shipped in v7.0.0-alpha.3 via #88. Closing for v7 milestone bookkeeping. (Release PR #92 still references this issue for historical trace.)