861d398 | plum | pyrossh

git clone https://git.pyrossh.dev/plum

A statically typed, imperative programming language inspired by rust, python

861d398 — Peter John 2026-11-03T16:08:41+05:30

tail calls: plan; default FnCall.tail at construction sites; run markTailCalls in typedSource

Files changed (8) hide show

docs/plans/2026-11-03-tail-calls.md +126 -0
docs/plans/2026-11-03-tail-calls.review.md +72 -0
plum-checker/src/lib.rs +9 -1
plum-core/src/ctors.rs +2 -0
plum-core/src/forms.rs +2 -0
plum-core/src/parser.rs +5 -0
plum-core/src/union_lower.rs +4 -0
plum-wasm-codegen/src/lib.rs +3 -0

docs/plans/2026-11-03-tail-calls.md ADDED Viewed

@@ -0,0 +1,126 @@
+# Tail calls
+**Review plan:** docs/plans/2026-11-03-tail-calls.review.md
+**Goal:** calls in tail position use no stack (self calls become loops, others `return_call`), tail recursion modulo cons for constructor-wrapped recursive calls, larger host stack, depth tests at 1,000,000.
+**Architecture:** plum-core `tail` pass marks tail calls on the AST → plum-core `trmc` pass rewrites `C(.., f: self(..))` tails into a hole-filling loop → codegen emits `loop`+`br` for self tail calls and `return_call`/`return_call_ref` for other tail calls → hosts enable wasm tail calls and an 8 MiB stack.
+**Tech stack:** Rust (plum-core, plum-wasm-codegen with wasm-encoder 0.220, wasmtime 47 in plum-cli/plum-runtime/plum-game), Plum.
+**Spec:** docs/plans/2026-11-03-tail-calls.review.md
+**Detail:** contracts
+**Target-min:** 30
+## Global constraints
+- Work only in /Users/pyrossh/Code/plum-pure-scene-values (branch pure-scene-values). Never touch /Users/pyrossh/Code/plum.
+- Plum file tests: `touch plum-cli/src/main.rs && cargo build --quiet -p plum-cli && ./target/debug/plum test <file>`. Rust: build `cargo build --tests -p <crate>` and run test binaries; `touch` edited .rs first. Whole Plum sweep: `./target/debug/plum test plum-std plum-examples` must stay green (594 tests).
+- Tail position: the value of a fn body; the last expr of a block in tail position; each `match`/`if`/ternary arm in tail position; `return e`. NOT tail: inside `try`/`?`/`!`/`??`, inside a `test`, under a `for`, as an argument, before `defer`-like cleanup, or in an export fn's boundary wrapper.
+- Defaults (review plan): automatic tail calls and TRMC, self calls as loops, wasm tail calls required, frames dropped from backtraces.
+- Known bug R5: same local name with different types across match arms gives invalid wasm; loop-converted params keep one fixed type.
+- Ownership (plum-checker/src/ownership.rs) must keep passing; do not edit it unless your task owns it.
+- Inline variant syntax: `enum Link[T] = Nil | Cons(head: T, tail: Link[T])`, `fun f(x) -> R = match x` (see plum-examples/functional.plum).
+```mermaid
+flowchart LR
+  AST["checked AST"] --> TP["tail pass (marks)"] --> TR["trmc rewrite"] --> CG["codegen: loop+br / return_call"] --> W[wasm]
+  H["hosts: wasm_tail_call + 8 MiB stack"] --> W
+```
+File structure: each task's Owns. Spec coverage: What you will get (T1-T5), What will be built (T1-T6; benchmark by coordinator), How it fits together (diagram), Decisions you can change (Global constraints), Risks (R1 T2, R2 T2/T5, R3 T2, R4 T4), Out of scope (not built), How we will know it works (T5, T6), Rough time and cost (schedule).
+## Task graph
+```mermaid
+flowchart LR
+  T1[tail pass]
+  T2[codegen tail calls]
+  T3[host config]
+  T4[trmc rewrite]
+  T5[depth tests]
+  T6[deep fixture]
+  %% taskgraph
+  T1 --> T2
+  T1 --> T4
+  T2 --> T5
+  T3 --> T5
+  T4 --> T5
+```
+## Analysis
+### T1 tail-position pass · Complexity 4 · Est. context 45k
+**Owns:** plum-core/src/tail.rs, plum-core/src/lib.rs, plum-core/src/ast.rs, plum-core/tests/tail_test.rs
+**Components:** 1
+**LOC owned:** 160
+**Tests:** fast
+**Model:** sonnet
+**Consumes:** none
+**Produces:** tail::markTailCalls(src: &mut ast::Source) · tail::tailCalls(f: &ast::Fn) -> Vec<TailSite> · ast call nodes gain `tail: TailKind` (`NotTail | SelfCall | Other | Closure`)
+e.g. `tailCalls(sumAcc)` -> `[TailSite(callee: "sumAcc", kind: SelfCall, line: 3)]`
+e.g. `tailCalls(length)` (`1 + length(t)`) -> `[]`
+**Review Focus:** deep: every rule in Global constraints' tail-position list, nested blocks, `= match` bodies, methods (`self.f(..)` on the same type is SelfCall), closures (a call inside a closure body is tail relative to the closure only).
+**Test code:** tail_test.rs: `self_tail_in_match_arm`, `self_tail_in_if_else`, `not_tail_under_binary_op`, `not_tail_as_argument`, `not_tail_inside_try`, `other_fn_tail`, `mutual_recursion_both_tail`, `method_self_tail`, `closure_value_call_tail` (kind Closure), `return_expr_tail`, `block_last_expr_tail`. Adding the AST field: default `NotTail` at every construction site (any crate; list them).
+**Steps:** pass runs after lowering and before codegen; wire the call in the shared pipeline entry that both `plum test` and `plum compile` use (find it; report where).
+### T4 tail recursion modulo cons · Complexity 6 · Est. context 55k
+**Owns:** plum-core/src/trmc.rs, plum-core/tests/trmc_test.rs
+**Components:** 1
+**LOC owned:** 170
+**Tests:** fast
+**Model:** sonnet
+**Consumes:** tail::tailCalls(f: &ast::Fn) -> Vec<TailSite>
+**Produces:** trmc::rewrite(src: &mut ast::Source) -> Vec<String>
+e.g. `rewrite` on functional.plum's `map` -> `["map"]` (names of rewritten fns)
+**Review Focus:** deep/state R4: only a single recursive call as one field of a constructor (record or inline variant) in tail position, other fields evaluated first in source order; results equal the original for every input; fields must be writable (if inline-variant hidden records are immutable, restrict to what is writable and report).
+**Test code:** trmc_test.rs (compile and run via plum-wasm-codegen's test helper or the CLI): `map_rewritten_same_result`, `filter_rewritten_same_result` (the `rest := filter(..)` then `if` form is NOT TRMC: assert not rewritten), `fromTo_rewritten`, `append_rewritten`, `two_recursive_fields_not_rewritten` (tree map), `side_effect_order_kept` (a field before the recursive one calls a counter closure: same order).
+**Steps:** rewrite into a loop that allocates each cell with a placeholder for the recursive field and writes it on the next iteration; run before T1's marking so the loop has no self call. Register the pass after `tail::markTailCalls`'s caller (same pipeline entry).
+## Codegen and hosts
+### T2 codegen tail calls · Complexity 6 · Est. context 70k
+**Owns:** plum-wasm-codegen/src/lib.rs, plum-wasm-codegen/tests/tail_calls_e2e_test.rs
+**Components:** 1
+**LOC owned:** 200
+**Tests:** fast
+**Model:** sonnet
+**Consumes:** tail::markTailCalls(src: &mut ast::Source)
+**Produces:** none
+**Review Focus:** state R1/R3: a fn with a SelfCall tail gets its body wrapped in `loop`; the tail call evaluates all args into temps, then `local.set`s params, then `br` to the loop (no param read after its set); a closure created in the body that captures a param copies it into a fresh local per iteration. Other/Closure tails emit `return_call` / `return_call_ref`. Error-union results and export wrappers never tail-call. R2: own params reassigned by the loop.
+**Test code:** tail_calls_e2e_test.rs (run wasm with tail calls enabled in the test engine): `self_tail_million` (sumAcc over build(1_000_000) = 500000500000), `self_tail_args_swap` (`gcd(b, a % b)`), `mutual_tail_million` (isEven/isOdd 1_000_001), `closure_tail_call_runs` (deep, through `fn` value), `method_self_tail` , `own_param_self_tail` (own record threaded through 100_000 iterations), `closure_captures_iteration_value`, `wasm_has_no_call_in_loop` (wasmparser: sumAcc contains `br`, no `call` to itself), `return_call_emitted` (isEven contains return_call). Existing codegen suite green.
+### T3 host config · Complexity 1 · Est. context 22k
+**Owns:** plum-cli/src/main.rs, plum-runtime/src/main.rs, plum-game/src/host.rs
+**Components:** 1
+**LOC owned:** 20
+**Tests:** fast
+**Kind:** mechanical
+**Model:** haiku
+**Consumes:** none
+**Produces:** none
+**Review Focus:** state: every `wasmtime::Config::new()` (plum-cli/src/main.rs:796 and :946, plum-runtime/src/main.rs:361, plum-game/src/host.rs:162) gets `.wasm_tail_call(true)` and `.max_wasm_stack(8 << 20)`.
+**Test code:** `cargo build --workspace` clean; `./target/debug/plum test plum-examples/functional.plum` passes; the probe `length(fromTo(0, 50000)) == 50000` in a scratch file under /private/tmp/claude-501/ passes (was "call stack exhausted" at 10,000).
+## Verification
+### T5 depth tests · Complexity 3 · Est. context 35k
+**Owns:** plum-examples/tail_calls.plum
+**Components:** 1
+**LOC owned:** 120
+**Tests:** fast
+**Model:** sonnet
+**Consumes:** none
+**Produces:** none
+**Review Focus:** deep: each test at 1,000,000 unless stated.
+**Test code:** module tail_calls with `enum Link[T] = Nil | Cons(head: T, tail: Link[T])`: `tail_sum_million`, `tail_build_million`, `fold_million`, `mutual_even_odd_million`, `trmc_map_million`, `trmc_fromTo_million`, `closure_tail_million`, `own_record_loop_100k`, `tree_recursion_depth_recorded` (a non-tail tree depth that passes at 8 MiB, documented in a comment with the measured limit). Update the "not tail call optimised" comment at the top of plum-examples/functional.plum? NO (not owned): report it.
+### T6 deep state/view fixture · Complexity 2 · Est. context 30k
+**Owns:** plum-game/web-test/fixtures/stress_state_view_deep.plum
+**Components:** 1
+**LOC owned:** 90
+**Tests:** fast
+**Model:** sonnet
+**Consumes:** none
+**Produces:** none
+**Review Focus:** numeric: same 5,750 actors and formulas as stress_state_view.plum, but the 5,000 dancers in ONE `Link` (5,000-deep recursion in step/view/draw).
+**Test code:** `plum test` on the fixture (2 tests mirroring stress_state_view.plum); `plum compile` succeeds. Expected to overflow before T2/T3/T4 and run after: report both.
+## Review Focus
+- compiler (library): deep, state. Risks: wrong tail-position classification; param clobbering in loops; TRMC changing evaluation order; ownership interplay.
+- hosts: state. Risk: a missed Config.
+**Probe entry:** run=./target/debug/plum test

docs/plans/2026-11-03-tail-calls.review.md ADDED Viewed

@@ -0,0 +1,72 @@
+# Tail calls: review plan
+**Builds on:** branch `pure-scene-values` (phase B, commit 64aab59). The recursive state/view and `std/game/Picture` are the motivating code. The supercompiler is a later, separate plan.
+## Summary
+Plum recursion currently runs out of stack between 5,000 and 10,000 frames, measured on 2026-11-03 under `plum test` (wasmtime 47). Tail-shaped functions overflow just the same:
+| probe | depth | result |
+|---|---|---|
+| `length(fromTo(0, n))` (not tail) | 5,000 | ok |
+| same | 10,000 | `wasm trap: call stack exhausted` |
+| `sumAcc(build(n, Nil), 0)` (tail) | 5,000 | ok |
+| same | 20,000 / 1,000,000 | stack exhausted |
+This plan makes calls in tail position free, so tail-recursive functions run at any depth. It also turns the most common non-tail shape, building a list as you go (`Cons(head: f(h), tail: map(t, f))`), into a tail call. After that, `map`, `filter`, `fromTo`, `view` and `step` over long `Link`s no longer overflow either.
+## What you will get
+- **Self tail calls become loops.** A function that calls itself in tail position (the last thing a `match` arm, `if` branch or block does) compiles to a jump back to its start with the parameters reassigned. No new stack frame is used, and it runs at loop speed. Examples: `sumAcc`, `build`, `fold`, `drawNodes(tail)`.
+- **Other tail calls use wasm `return_call`.** A call to a different function in tail position, mutual recursion (`isEven` / `isOdd`), and calls through a closure value use `return_call` / `return_call_ref`. They also stop growing the stack.
+- **Tail recursion modulo cons.** A function whose tail is a constructor around one recursive call, such as `Cons(head: x, tail: f(rest))`, is rewritten to fill a hole in the result as it goes. That makes it a loop. This covers `map`, `filter`, `fromTo`, `append` and Picture/state-view `view` builders. Opt-in rules are listed under Decisions.
+- **`plum test` and the host stack.** Raise wasmtime's stack limit to a stated size for deep non-tail recursion that remains (tree recursion such as `bounds` over a deep Group). Report the new limit.
+- **Diagnostics.** `plum build --explain-tail fn` (or a test helper) lists which calls were made tail calls. Tests can then assert on a function's tail calls without inspecting the wasm.
+## What will be built
+| Part | What it does | Size |
+|---|---|---|
+| Tail-position analysis | Marks calls in tail position through `match`/`if`/blocks/`= match` bodies, early `return`, and error-union `try` (not tail) | S |
+| Self-tail loop | Codegen wraps the body in a `loop`, and a self tail call becomes param `local.set` + `br` | M |
+| `return_call` | Codegen emits `return_call` / `return_call_ref` for other tail calls; wasmtime `Config::wasm_tail_call(true)` in plum-cli, plum-runtime and plum-game | S |
+| Tail modulo cons | Pass: `C(.., field: f(..), ..)` in tail position, with `f` the enclosing fn and one recursive field → destination-passing loop (allocate the node with a hole, write the hole next iteration) | M |
+| Stack limit | `max_wasm_stack` set in all three hosts; depth probe recorded | S |
+| Tests and probes | Depth tests at 1,000,000 for tail and TRMC functions, mutual recursion, closures in tail position, and every existing suite green | M |
+| Benchmark | Recursive state/view stress fixture re-measured; a 5,000-deep single-list variant added to show the recursion depth limit is gone | S |
+## How it fits together
+```mermaid
+flowchart LR
+  AST["checked AST"] --> TP["tail-position analysis"]
+  TP --> TRMC["tail modulo cons rewrite"]
+  TRMC --> CG["codegen"]
+  CG --> L["self tail call: loop + br"]
+  CG --> RC["other tail call: return_call / return_call_ref"]
+  L --> W[wasm-gc]
+  RC --> W
+```
+## Decisions you can change
+- **Which calls.** Default: every call in tail position is a tail call, automatically. Alternative: an explicit marker (for example `return tail f(x)`, or an `@tailrec` annotation that errors when the call isn't in tail position).
+- **Tail modulo cons.** Default: automatic for a single recursive field in a constructor at tail position. Alternative: opt-in per function (OCaml's `[@tail_mod_cons]`).
+- **Self calls.** Default: a loop, not `return_call`, because it's faster and needs no engine support. Alternative: `return_call` everywhere (simpler, slower).
+- **Browser support.** Default: require wasm tail calls (Chrome 112+, Firefox 121+, Safari 18.2+). Alternative: loops only, no `return_call`, for older engines; mutual recursion would then still grow the stack.
+- **Stack traces.** Tail calls drop frames from wasm backtraces. Default: accept that. Alternative: a debug flag that turns tail calls off.
+## Risks
+- **R1: R5 match-arm local bug.** Reassigning params in a loop meets the known invalid-wasm bug where the same name gets different types. The analysis gives every loop param one fixed type, and a regression test covers it.
+- **R2: owned values.** Tail-call reassignment counts as a move under the ownership checker. Self tail calls with `own` params must not trip "used after it was moved". Tests cover it.
+- **R3: closures capturing params.** A closure created in an iteration that captures a param must see that iteration's value. Loop-converted params are reassigned, so captured params are copied into a fresh local per iteration.
+- **R4: TRMC and wasm-gc.** Filling a hole needs a mutable field. Plum records are mutable today, so this holds; immutable struct/inline-variant layouts would need a builder type. If hidden inline-variant records turn out to be immutable, TRMC covers records only, or is deferred.
+## Out of scope
+- The supercompiler (driving/folding, deforestation, fusing `view` into `draw`): the next plan, once this lands.
+- General CPS, or any non-tail recursion beyond tail modulo cons (tree recursion keeps using the stack).
+- Changing the existing for-loop forms.
+## How we will know it works
+- **Depth tests:** the probes above all pass at 1,000,000 for tail-recursive functions (`sumAcc`, `build`, `fold`), for mutual recursion, for TRMC functions (`map`, `filter`, `fromTo`), and for a closure called in tail position. Non-tail tree recursion still fails at a stated depth, which is recorded.
+- **Explain output:** a test asserts which calls are tail calls for a small set of functions (tail, not tail, inside `try`, inside a closure).
+- **Existing suites:** the whole suite stays green (1,765 tests today), and so do the host parity test and both browser checks.
+- **Benchmark:** the recursive state/view row is re-measured, plus a 5,000-deep single-list fixture that overflows before this change and runs after it.
+## Rough time and cost
+About 7 parts. The analysis comes first, then the self-loop and `return_call` in parallel, then TRMC, then tests and the benchmark. Rough agent time is 45–70 minutes.

plum-checker/src/lib.rs CHANGED Viewed

@@ -1179,7 +1179,14 @@ pub fn checkSource(source: &ast::Source) -> CheckResult<()> {
 /// instantiated type of every expression (keyed by expression address) and the
 /// set of generic instantiations (see `TypedInfo`) for codegen.
 pub fn typedSource(source: &ast::Source) -> CheckResult<TypedInfo> {
-    let (result, info) = checkSourceFull(source);
+    let (result, mut info) = checkSourceFull(source);
+    // TODO(tail-calls): the tail-recursion-modulo-cons AST rewrite pass goes HERE,
+    // on the fully lowered program, immediately before `markTailCalls`.
+    // Mark tail calls on the final lowered program codegen compiles. Flags are set
+    // in place, so the address-keyed type info stays valid.
+    if let Some(lowered) = info.lowered.as_mut().and_then(std::rc::Rc::get_mut) {
+        plum_core::tail::markTailCalls(lowered);
+    }
     result.map(|()| info)
 }
@@ -4428,6 +4435,7 @@ fn inferOperatorCall(
                         .collect(),
                     line: 0,
                     column: 0,
+                    tail: ast::TailKind::NotTail,
                 })
             })
             .clone()

plum-core/src/ctors.rs CHANGED Viewed

@@ -374,6 +374,7 @@ pub fn lowerCtors(source: &mut Source) -> Vec<String> {
                         args: vec![],
                         line: line,
                         column: column,
+                        tail: TailKind::NotTail,
                     }),
                 })),
                 0,
@@ -502,5 +503,6 @@ fn rewriteCall(e: &mut Expr, plans: &HashMap<String, Plan>, errors: &mut Vec<Str
         args,
         line: 0,
         column: 0,
+        tail: TailKind::NotTail,
     });
 }

plum-core/src/forms.rs CHANGED Viewed

@@ -301,6 +301,7 @@ fn method(obj: &str, name: &str, args: Vec<Expr>) -> Expr {
             args: args.into_iter().map(Arg::Positional).collect(),
             line: 0,
             column: 0,
+            tail: TailKind::NotTail,
         }),
     }))
 }
@@ -1867,6 +1868,7 @@ fn yieldCall(args: Vec<Expr>) -> Expr {
         args: args.into_iter().map(Arg::Positional).collect(),
         line: 0,
         column: 0,
+        tail: TailKind::NotTail,
     })
 }

plum-core/src/parser.rs CHANGED Viewed

@@ -1607,6 +1607,7 @@ impl<'a> AstParser<'a> {
                     args,
                     line: pos.row + 1,
                     column: pos.column + 1,
+                    tail: TailKind::NotTail,
                 })
             }
             None => AttrKind::Field(member),
@@ -1666,6 +1667,7 @@ impl<'a> AstParser<'a> {
                     args,
                     line: pos.row + 1,
                     column: pos.column + 1,
+                    tail: TailKind::NotTail,
                 })
             }
             None => AttrKind::Field(member),
@@ -1689,6 +1691,7 @@ impl<'a> AstParser<'a> {
                 args: vec![Arg::Positional(Expr::Closure(Box::new(closure)))],
                 line: pos.row + 1,
                 column: pos.column + 1,
+                tail: TailKind::NotTail,
             }),
         }))
     }
@@ -1716,6 +1719,7 @@ impl<'a> AstParser<'a> {
             args,
             line: pos.row + 1,
             column: pos.column + 1,
+            tail: TailKind::NotTail,
         }
     }
@@ -1752,6 +1756,7 @@ impl<'a> AstParser<'a> {
                     args: vec![part(0), part(1)],
                     line: pos.row + 1,
                     column: pos.column + 1,
+                    tail: TailKind::NotTail,
                 }))
             }
             _ => {

plum-core/src/union_lower.rs CHANGED Viewed

@@ -168,6 +168,7 @@ impl<'a> Lowerer<'a> {
                     args: vec![Arg::Positional(value)],
                     line: 0,
                     column: 0,
+                    tail: TailKind::NotTail,
                 }),
             })),
             0,
@@ -345,6 +346,7 @@ impl<'a> Lowerer<'a> {
                         args: vec![],
                         line: 0,
                         column: 0,
+                        tail: TailKind::NotTail,
                     });
                 }
             }
@@ -371,6 +373,7 @@ impl<'a> Lowerer<'a> {
                 args: vec![Arg::Positional(inner)],
                 line: 0,
                 column: 0,
+                tail: TailKind::NotTail,
             });
         }
     }
@@ -696,6 +699,7 @@ isOwn: false,
                     args,
                     line: 0,
                     column: 0,
+                    tail: TailKind::NotTail,
                 }),
             }));
             Case {

plum-wasm-codegen/src/lib.rs CHANGED Viewed

@@ -7586,6 +7586,7 @@ fn compileExprCore(
                             .collect(),
                         line: 0,
                         column: 0,
+                        tail: ast::TailKind::NotTail,
                     };
                     compileVariantConstruction(info, &synthetic_call, expr, body, ctx, state)?;
                 }
@@ -7645,6 +7646,7 @@ fn compileExprCore(
                 args: vec![],
                 line: 0,
                 column: 0,
+                tail: ast::TailKind::NotTail,
             };
             compileMethodCall(
                 &object,
@@ -8414,6 +8416,7 @@ fn compileInterpolatedString(
                             args: vec![],
                             line: 0,
                             column: 0,
+                            tail: ast::TailKind::NotTail,
                         };
                         if plum_checker::nominalName(&other)
                             .is_some_and(|n| ctx.func_ids.contains_key(&format!("{}::toStr", n)))