Compiler: tail recursion modulo cons (TRMC) for (cons H (self ...)) list builders

[pyrex41]

Split out of #46, which is now closed on the start-up side. This is the remaining compute-side lever named there, stated precisely enough to be picked up cold.

What it is

compiler.lua already lowers direct self-tail-calls to a loop (SELF / pure_tail_self / try_self_tail, compiler.lua:65-270). Eligibility is deliberately strict: every occurrence of the function's own name must be the head of a direct call in tail position with exact arity and self-free arguments. Anything else keeps proper-tail-call codegen for the whole function.

That rules out the single most common list-building shape in Shen and in the kernel:

(defun f (X) (cond (... ()) (true (cons (g (hd X)) (f (tl X))))))

The self-call sits in an argument of cons, so pure_tail_self sees a non-tail occurrence and refuses. The compiled result is one Lua stack frame per output element.

TRMC lowers exactly that shape: build the spine iteratively with a mutable tail pointer, filling in each cons cell's cdr on the next iteration, then close it. The port already does this by hand, natively, in three places — prims.lua's append, shen.assoc-> and shen.reverse-help are all hand-written versions of the transformation, with the same "fresh cells are unshared until we return, so in-place tail assignment is unobservable" argument. TRMC generalises that to compiled KL.

Why it is worth doing

The residual gap to shen-cl on urdr's suites is 1.6-3.5x (doc/PERF-URDR-RESULTS.md), and urdr represents machine words as 32-element bit lists, so list.take, bits.xor and byte.bits.weights — all (cons H (self …)) recursions — dominate. Each is currently one frame per bit.

Scope

• Extend pure_tail_self (or add a sibling scan) to accept an occurrence that is the self-call in the last argument of a cons whose other argument is self-free, in what would otherwise be tail position — this is a modulo-cons tail position, not a plain one.
• Extend the SELF lowering in ctail to maintain a head/last pair for such calls and to goto tco after linking the new cell, with the function returning head at the end.
• Nested/mixed shapes must stay refused. The existing scan's conservatism is load-bearing.
• HAS_GOTO gating already exists (PUC 5.1 cannot parse goto); TRMC must degrade the same way.

The measurement bar — please read before starting

This is where the previous attempt in #46 stopped, and it is the actual difficulty. From that work:

the pure_tail_self relaxation was correct and still regressed short-list SHA ~14%, so it was left unmerged

LuaJIT traces a self-tail-call chain well. Turning one into a loop is not automatically a win, and for short lists it can lose. So:

• A/B interleaved, min-of-N CPU, on a quiet machine — the dev box for Performance: cold start ~1.5s for a trivial script (~100x shen-cl); urdr SHA suites ~12x CL; -q unusable for golden runners #46 ran at load average 13-14 and inflated every absolute number ~2x.
• Workloads must include short lists (urdr prng, the 32-element bit lists) and not only long ones, because that is where the previous relaxation regressed.
• Suites to hold: luajit run-kernel-tests.lua (134/134), make test, the three examples/*/selftest.lua, bifrost.py --impls shen-lua (0 FAIL), and urdr shen/tests/{prng,search,world} ALL PASS with unchanged golden output — the digests cannot move.
• If it does not win measurably on a workload that matters, it should not land. doc/PERF-URDR-RESULTS.md already records several levers that were tried and rejected for measured regressions; that is the standard here.