plum
git clone https://git.pyrossh.dev/plum
A statically typed, imperative programming language inspired by rust, python
8d9b551
— Peter John
2026-11-03T20:22:49+05:30
docs(plans): supercompiler review plan
docs/plans/2026-11-03-supercompiler.review.md
ADDED
|
@@ -0,0 +1,77 @@
|
|
|
1
|
+
# Supercompiler: fusing List chains and view-into-draw: review plan
|
|
2
|
+
|
|
3
|
+
**Builds on:** branch `pure-scene-values` at 651acd8 (on top of master 59d923d): closure specialisation, tail calls and TRMC, unboxed variants, std cons `List`, recursive `Picture` and the state/view Orb Run.
|
|
4
|
+
|
|
5
|
+
## Summary
|
|
6
|
+
Two kinds of code still build data only to take it apart straight away:
|
|
7
|
+
|
|
8
|
+
1. **List pipelines.** `xs.map(f).filter(g).fold(0, h)` builds a whole new list for `map`, another for `filter` (plus a reversed copy), and only then folds. Closure specialisation (last plan) made the calls direct, but every intermediate list is still allocated.
|
|
9
|
+
2. **State/view games.** Every frame, `draw(w)` calls `Picture.draw(view(state))`. `view` allocates a full `SceneNode` tree (groups, sprites, text, the `Cons` cells of every child list), and `Picture.draw` immediately walks it and throws it away. The recursive state/view Orb Run averages 1.91 ms against 1.73 ms for the mutable scene, and that tree is most of the difference.
|
|
10
|
+
|
|
11
|
+
A small **supercompiler** removes both. It is a compiler pass that, when one function's result is consumed straight away by another, runs the consumer symbolically over the producer's body. A `match` on a constructor the producer just built is then decided at compile time, so the constructor is never allocated. Recursive pairs (a consumer walking a list that a recursive producer builds) become one new recursive function that does both jobs in a single pass.
|
|
12
|
+
|
|
13
|
+
## What you will get
|
|
14
|
+
- **Fused List chains.** `xs.map(f).filter(g).fold(acc, h)`, `xs.map(f).length()`, `xs.filter(g).map(f)` and similar chains of std `List` methods compile to one loop with no intermediate lists. This is not a special case for `List`: the same pass fuses any user functions with the same shape, for example a user-written `sumSquares(squares(xs))`.
|
|
15
|
+
- **View-into-draw fusion.** `Picture.draw(view(s))` compiles to a function that draws straight from `State`, with no `SceneNode`, `Transform` or child-list allocation on any path the pass can see through. The same goes for `Picture.bounds(view(s))` and `Picture.hitPath(view(s), x, y)`. `view` itself remains available for tests and hit-testing.
|
|
16
|
+
- **Pure code only.** The pass fuses only when every function and closure involved is pure (no `extern` calls, no field or variable writes outside its own locals, no `print`). Fusing changes the order in which steps run (`f`, `g` and `h` interleave per element instead of running stage by stage), and pure code can't tell the difference. Anything else is left exactly as it is today.
|
|
17
|
+
- **Visible results.** A `plum build --explain-fusion` flag (or an env var, whichever fits the CLI better) lists each fused site and each place where the pass gave up, and why.
|
|
18
|
+
|
|
19
|
+
## What will be built
|
|
20
|
+
| Part | What it does | Size |
|
|
21
|
+
|---|---|---|
|
|
22
|
+
| Purity check | Marks each function and closure as pure or not (transitively; externs and writes are impure). Conservative: anything unclear counts as impure | S–M |
|
|
23
|
+
| Inline and simplify | Inline small non-recursive producers; a `match` on a known constructor picks its arm; a `match` on a `match` pushes the outer one into each arm; field reads on a just-built record become the value | M |
|
|
24
|
+
| Driving with folding | When a pure recursive consumer is applied to a pure recursive producer call, build a new function for the pair and drive the consumer through the producer's body. A repeat of the same (consumer, producer) shape becomes a recursive call to the new function, so recursion ties off | L |
|
|
25
|
+
| Stop rule | A growth check (homeomorphic embedding plus a size budget per site) stops driving that would never end or would blow up code size; the site is left unfused. No generalisation in this round | M |
|
|
26
|
+
| Std reshaping | `List.filter` written in direct recursive style (TRMC still makes it constant-stack) so it fuses; `Picture`'s draw, bounds and hit walks checked to be pure; `toNodes`-style helpers in the example kept fusable | S |
|
|
27
|
+
| Pipeline placement | Runs after closure specialisation (so closures are already inlined) and before TRMC and tail-call marking (so the fused functions still get loops and `return_call`) | S |
|
|
28
|
+
| Benchmarks and docs | 1M List pipeline table, state/view vs mutable vs pure scene table, README "how fusion works" section | S |
|
|
29
|
+
|
|
30
|
+
## How it fits together
|
|
31
|
+
```mermaid
|
|
32
|
+
flowchart LR
|
|
33
|
+
P["parse + check"] --> CS["closure specialisation"]
|
|
34
|
+
CS --> PU["purity check"]
|
|
35
|
+
PU --> SC["supercompile: inline, known-constructor match, drive + fold, stop rule"]
|
|
36
|
+
SC --> TR["TRMC + tail calls"]
|
|
37
|
+
TR --> CG["wasm codegen"]
|
|
38
|
+
```
|
|
39
|
+
|
|
40
|
+
## Decisions you can change
|
|
41
|
+
- **Effects.**
|
|
42
|
+
- Default: fuse only pure code, as above.
|
|
43
|
+
- Alternative: fuse everything and document that a pipeline's closures run interleaved per element (as in Rust iterators and Java streams).
|
|
44
|
+
- **Stopping.**
|
|
45
|
+
- Default: give up on a site when growth is detected (no generalisation). Simpler and predictable; some deep recursive pairs stay unfused.
|
|
46
|
+
- Alternative: full positive supercompilation with generalisation, which fuses more but is a research-sized job with harder-to-predict code size.
|
|
47
|
+
- **Scope of the pass.**
|
|
48
|
+
- Default: the whole program, std included, automatically.
|
|
49
|
+
- Alternative: only where a function is marked (e.g. `fuse fun view`), as an opt-in.
|
|
50
|
+
- **Host GC heap for `plum test` / `plum run`** (still open from the last plan): default a 64 MiB initial wasmtime GC heap, lazily committed. Alternative: leave wasmtime's default and rely on fusion to cut garbage. Browser games are unaffected either way (V8's GC).
|
|
51
|
+
|
|
52
|
+
## Risks
|
|
53
|
+
- **R1: termination and code size.** Driving can loop or blow up. Mitigated by the stop rule, a per-site size budget and a whole-program cap on new functions; past the cap the pass stops and code is unchanged.
|
|
54
|
+
- **R2: purity analysis too weak.** If it is too conservative, `view` or `Picture.draw` may be marked impure (for example through a shared helper that calls an extern). The draw extern calls themselves are the consumer's effects, which is fine: the rule is that the *producer* must be pure and its constructors must not escape anywhere else. The plan checks this on `game_state_view` first and reports if it falls short.
|
|
55
|
+
- **R3: sharing.** If a producer's result is used twice (`p := view(s)` then `draw(p)` and `bounds(p)`), fusing would duplicate the work. Only single-use results are fused.
|
|
56
|
+
- **R4: generics and unboxed variants.** The fused functions must type-check and emit through the same paths as hand-written code. All fused output goes back through the checker, so a mistake is a compile error, not a wrong answer.
|
|
57
|
+
- **R5: gain smaller than hoped.** If the state/view gap turns out to be draw-call cost rather than allocation, the benchmark shows it and the plan reports it instead of chasing it.
|
|
58
|
+
|
|
59
|
+
## Out of scope
|
|
60
|
+
- Changing `Slice` for-chains (already fused).
|
|
61
|
+
- Fusing through trait dispatch (`Actor.act` on the pure scene graph) or across escaping closures.
|
|
62
|
+
- Generalisation (see Decisions).
|
|
63
|
+
- The smaller follow-ups: move-error columns, record `==`, `Json.decode` on unions, `Slice[fn(..)]` parsing, TRMC on methods.
|
|
64
|
+
|
|
65
|
+
## How we will know it works
|
|
66
|
+
- **Correctness:**
|
|
67
|
+
- every existing suite stays green (Plum std/examples, Rust crates), with fusion on;
|
|
68
|
+
- the same suites also pass with fusion turned off (one switch), and results match exactly;
|
|
69
|
+
- fusion tests for map/filter/fold/length chains, a user-written producer/consumer pair, a shared result (not fused), an impure closure (not fused), and a growing pair that the stop rule must refuse.
|
|
70
|
+
- **No allocation where promised:** a wasmparser test counts `struct.new` in the fused 1M List pipeline loop (none for list cells) and in the fused `draw` of `game_state_view` (none for `SceneNode`, `Transform` or child-list cells).
|
|
71
|
+
- **Speed:**
|
|
72
|
+
- 1M `map → filter → fold` on `List` within 2x of the `Slice` for-chain (19 ms), from about 600 ms today;
|
|
73
|
+
- headed Chromium, same session: state/view Orb Run average within 5% of the mutable scene (1.73 ms) and no worse p95.
|
|
74
|
+
- **Host parity and browser checks green** for `game_state_view`, `game_pure_scene` and `game`.
|
|
75
|
+
|
|
76
|
+
## Rough time and cost
|
|
77
|
+
About 7 parts, mostly sequential because they share `plum-core` and the checker pipeline. Driving with folding is the largest and riskiest. Rough agent time is 100–150 minutes, plus one headed benchmark run.
|