μ

internals — expression to result

Pipeline

Every expression travels through four stages before producing a value. The optimizer is a pure AST→AST transform — it sees no runtime state and changes no semantics, only structure.

parse parse_expr() · parser.c
right-to-left recursive descent
→ expr_t * (pool-allocated AST)

→

optimize opt_normalize() · const-fold, substitute
opt_expr() · structural rewrites
pure AST → AST, no runtime state

→

eval eval_expr() · eval.c
recursive tree-walk interpreter
→ value_t * (typed tagged union)

AST node types

Every node in the tree is an expr_t tagged with an expr_kind_t. The optimizer rewrites nodes by returning new pointers from the same pool — no mutation of shared nodes.

kind	payload	example μ source
`EXPR_CONSTANT`	boxed `value_t*` literal	`42`, `3.14`, `foo
`EXPR_NAME`	interned `stringview_t`	`x`, `vol_dt`
`EXPR_GLOBAL_NAME`	interned `stringview_t` — dot-prefix global reference	`.vol`, `.base`
`EXPR_ASSIGN`	name + rhs `expr_t*` + `is_global` flag	`x: 42`, `.x: 42`
`EXPR_MONADIC`	verb char + operand	`-x`, `?n`, `#v`
`EXPR_DYADIC`	verb char + left + right	`a + b`, `x * y`
`EXPR_ADVERB`	verb + adverb char + left? + right	`+/v`, `+\v`, `f' list`
`EXPR_APPLY`	func `expr_t` + arg `expr_t`	`sqrt x`, `f 1 2 3`
`EXPR_FUNC_LITERAL`	verb, adverb, body, nargs, arg names	`{x+1}`, `{[n] ?n}`, `+/`
`EXPR_COMPOSE`	left + right function nodes	`sqrt . sq`
`EXPR_VECTOR`	array of `expr_t*` children	`1 2 3`, `[a; b]`
`EXPR_SEQ`	array of statement nodes	`a:1; b:2; a+b`
`EXPR_WHILE`	test `expr_t` + body `expr_t[]`	`while[x<10; x:x+1]`

Evaluation

eval_expr(expr_t *e, env_t *env) is a recursive tree-walk in eval.c. It switches on e→kind:

EXPR_CONSTANT     → return e->constant.val
EXPR_NAME         → env_get_iname(env, name)           // O(n) linear scan, interned pointer ==
EXPR_GLOBAL_NAME  → env_get_global(env, name)          // shared global namespace, never captured
EXPR_ASSIGN       → eval rhs; env_set_iname (or env_set_global if is_global); return val
EXPR_MONADIC      → eval operand; apply_verb_monadic(verb, val)
EXPR_DYADIC       → eval left; eval right; apply_verb_dyadic(verb, l, r)
EXPR_ADVERB       → fold/scan/each/each-right/each-left/ternary-fold/ternary-scan dispatch
EXPR_APPLY        → eval func → VAL_FUNC; eval arg; apply_func_once(fn, arg)
EXPR_FUNC_LITERAL → val_func(body, verb, adverb, nargs, args)  // capture env frame
EXPR_COMPOSE      → eval both; build composed VAL_FUNC
EXPR_SEQ          → eval each stmt; return last (or cond-chain inside lambda)
EXPR_VECTOR       → eval each element; pack into list or FLOAT[]/LONG[] if homogeneous
EXPR_WHILE        → while eval(test) is truthy: eval each body stmt; return last val or nil

apply_func_once builds a local env seeded from the captured env_frame_t, binds the argument, then calls eval_expr(body, local_env). Fused kernels short-circuit this via the verb sentinel character — no body evaluation at all.

Optimization passes

Two passes run sequentially on every expr_t* before eval_expr. Both are pure functions: input node in, (possibly different) node out, no side effects.

pass	function	what it does
normalize	opt_normalize()	A. Fold pure constant subtrees bottom-up (e.g. `2*acos(-1.0)` → `6.2831…`). B. Substitute scalar env names with their current `EXPR_CONSTANT` values everywhere in the tree. C. For `EXPR_FUNC_LITERAL` bodies, snapshot captured scalar env values as embedded constants — eliminating runtime name lookups inside loops.
structural rewrite	opt_expr()	Pattern-match structural idioms in function bodies and replace them with pre-resolved fused AST nodes. Each rewrite rule is a structural predicate over the AST shape — no value computation, no env access. Matched subtrees are replaced by `EXPR_APPLY(EXPR_CONSTANT(fused_fn), args)`. Unmatched nodes are returned unchanged.

Fused functions carry a sentinel verb character (uppercase, outside the μ verb alphabet) in their val_func_data_t. apply_func_once dispatches on this character directly — no body evaluation, no env frame construction, no per-element allocation beyond one float_alloc(n).

Rewrite rules

Each rule is written in the S-expression notation used by opt_expr_str() — the same format visible in --opt-trace output and .mtest expected values. Red nodes are replaced; green nodes are introduced.

__sq_fused__ eliminate duplicate subexpression in x·x

DYADIC('*', e, e) → APPLY(__sq_fused__, e) // requires e pure (no side effects)

before

after

Runtime: computes x*x in a single pass — argument evaluated once.

__hypot2_fused__ Euclidean 2-norm: sqrt(a²+b²)

APPLY("sqrt", DYADIC('+', DYADIC('*',a,a), DYADIC('*',b,b))) → APPLY(__hypot2_fused__, VECTOR[a, b]) // also accepts post-R1 __sq_fused__ forms

before

after

Runtime: hypot(a, b) using the C standard library — numerically stable, single call.

__mean_fused__ replace two-pass (+/v)÷(#v) with single-pass accumulator

DYADIC('%', ADVERB('+','/', NAME(v)), MONADIC('#', NAME(v))) → APPLY(__mean_fused__, NAME(v)) // also matches APPLY("mean",v) and APPLY("avg",v)

before

after

Runtime: single loop — sum and count accumulated together, one float_alloc skipped entirely.

__variance_fused__ two-pass variance → single-pass Welford

{[x] DYADIC('%', ADVERB('+','/', DYADIC('*', DYADIC('-',x,mean(x)), DYADIC('-',x,mean(x)))), MONADIC('#', x))} → {[x] APPLY(__variance_fused__, NAME(x))}

before — body (simplified)

after — body

Runtime: Welford online algorithm — single pass, numerically stable, no intermediate FLOAT[] for squared deviations.

__stddev_fused__ chains on R4 — sqrt(variance(x)) in one pass

{[x] APPLY("sqrt", <variance_body OR __variance_fused__(x)>)} → {[x] APPLY(__stddev_fused__, NAME(x))}

before — body

after — body

Runtime: single Welford pass returns sqrt(variance) directly — no intermediate scalar allocation.

__bm_fused__ Box-Muller transform — two RNG draws, one loop

{[n] DYADIC('*', APPLY("sqrt", DYADIC('*', CONST(-2), APPLY("log", DYADIC('-', CONST(1), MONADIC('?',n))))), APPLY("cos", DYADIC('*', CONST(2π), MONADIC('?', n)))) } → {[n] APPLY(__bm_fused__, VECTOR[NAME(n), CONST(2π)])} // 2π is extracted from the normalisation pass: 2*acos(-1) → 6.2831…

before — body

after — body

Runtime: single C loop — 2 xoshiro256+ draws per element, 1 float_alloc(n), no intermediate arrays for log/cos/sqrt results.

__gbm_path_fused__ GBM price path — entire inner loop fused to one C pass

{[w] DYADIC('*', CONST(S0), APPLY("exp", ADVERB('+','\\', DYADIC('+', DYADIC('*', NAME(w), CONST(vol_dt)), CONST(drift))))) } → {[w] APPLY(__gbm_path_fused__, VECTOR[NAME(w), CONST(S0), CONST(vol_dt), CONST(drift)])} // S0, vol_dt, drift are folded to constants by opt_normalize before this rule fires

before — body

after — body

Runtime: single C loop — prefix-sum log-price, exp, scale by S0. 1 float_alloc(steps), zero intermediate arrays for scan/exp results.

__ewise_chain__ any pure element-wise math lambda compiled to RPN bytecode

EXPR_FUNC_LITERAL {[x] <pure ewise body: ±*/% + whitelisted math fns>} → EXPR_FUNC_LITERAL {[x] APPLY(__ewise_chain__, x)} // fused_data = ewc_program_t (RPN bytecode compiled at opt time) // Fires only when body contains ≥1 math function call (sqrt/log/exp/cos/…) // and no ADVERB nodes (no scan/fold inside). Pure arithmetic skips this rule.

before — body e.g. {[x] cos(sqrt(x*2.0))}

after — body (bytecode stored in fused_data)

          ewc_program_t bytecode:

          PUSH_X · PUSH_CONST(2.0) · MUL · SQRT · COS

Runtime: single loop over the input FLOAT[] — stack machine executes RPN bytecode per element, 1 float_alloc(n), no intermediate arrays.

wrapper inlining + pre-resolved constants collapse {(f c)}' wrappers; eliminate env scan per each' iteration

// Two-part optimization applied together at definition time: // Part 1 — wrapper inlining: ADVERB('E', FUNC_LITERAL { body = APPLY(NAME("bm"), CONST(252)) }) → ADVERB('E', FUNC_LITERAL { body = APPLY(CONST(__bm_fused__), VECTOR[252, 12.5664]) }) // Part 2 — pre-resolved EXPR_CONSTANT (all make_*_fused_call builders): APPLY(NAME("__bm_fused__"), …) // env lookup on every iteration → APPLY(EXPR_CONSTANT(fused_fn), …) // zero env scan; eval returns embedded val

before — each call

after — each call

Runtime: eval_expr(EXPR_CONSTANT) returns the embedded value_t* in O(1) — zero env scan on every each' iteration. Phase A: ~44 ms → ~18 ms; Phase B: ~19 ms → ~8 ms.

Runtime fast paths

The rewrite rules eliminate redundant AST nodes. These runtime changes eliminate redundant memory operations in the evaluator itself.

mechanism	where	effect
Packed arrays `LIST_STORAGE_FLOAT` `LIST_STORAGE_LONG`	`eval.c` · `ewise`, `scan`, math keywords	Homogeneous numeric lists store a bare `double[]` or `long[]` instead of `value_t*[]`. All arithmetic operates directly on the packed buffer — no per-element `val_alloc` boxing, no `LIST_GET` ring-buffer indirection.
Interned env keys `env_get_iname` `env_set_iname`	`eval.c` · every name lookup	All argument names (`[n]`, `[w]`, implicit `x/y/z`) are stored as `const char*` pointers into the interned symbol table. Lookup compares pointers with `==` — eliminates `strlen` + `memcmp` on every hot-path env access.
Fast-path `each'`	`eval.c` · `ADVERB each` handler	For single-arg lambdas the local env is built once (caller env + captured frame), then per-iteration only `local.len` is reset and the argument rebound via a single `env_set_iname`. Replaces per-call `memcpy(16 KB)` with one pointer store.
Scratch-reset	`eval.c` · `each'` fast path	The bump-pointer float/val pools are treated as a call stack per iteration. For bodies returning a packed `FLOAT[]`, an output slab is pre-allocated before `eval_expr`; all intermediate results land above it. After the call, pool tops reset to just above the output slab — discarding all intermediates at zero cost. Working set: ~19 MB → ~4 MB for 1 000 paths.
Scalar accumulation	`eval.c` · `each'` fast path	When the body returns a `VAL_FLOAT` scalar, results are written directly into a pre-allocated `float_alloc(n)` slab and returned as a packed `FLOAT[]`. Eliminates n individual `val_alloc` calls and makes downstream `+/`, `-`, `*` all hit the packed-array fast path.

See the field notes for a narrative account of how these optimizations were discovered and measured, and the grammar reference for the μ syntax they operate on.