TAIL CALL OPTIMIZATION a call in tail position is a GOTO; reuse the frame
When a function’s last act is to call another and return whatever it returns, there is nothing left to do in the current frame — so reuse it instead of stacking a new one. Deep tail recursion then runs in constant stack. This is the optimisation aimed squarely at I-13’s hard wall: recursion is capped at 4096 frames, and a tail-recursive loop hits it — measured here.
THE TECHNIQUE the operand stack is empty at the call: measured
A tail-recursive sumto(acc, n) leaves the operand stack empty at each recursive call — so a TCO pass could reuse the frame. On the canonical compiler it does not: frames grow with n and overflow at 4096. Slide n and watch the real cliff: live demo, measured
HISTORY & CREDIT Steele, 1977: not an optimisation, a semantics
“Tail-call optimisation is a nice-to-have compiler optimisation.” — Steele’s point in 1977 is the opposite: a tail call is a GOTO, and treating it as an expensive stack-pushing call is the mistake. In Scheme, proper tail calls are required by the standard, not optional. cited
1977 · Guy L. Steele Jr. — “Debunking the ‘Expensive Procedure Call’ Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO” (AI Memo 443): a tail call compiles to a jump. 1975–79 · Steele & Sussman — the Lambda Papers; Scheme is designed so recursion in tail position is iteration. 1998 · R5RS and successors mandate proper tail recursion — an implementation that grows the stack on tail calls is non-conforming.
“Tail position” is syntactic: the call whose result is the caller’s result, with no pending operation after it. That is exactly when the frame carries nothing worth keeping. Steele, 1977 (AI Memo 443)
RECOMMEND FOR I-13 the wall this dart is built for
The canonical compiler does not yet eliminate tail calls — measured directly (peak operand stack stays flat while frames grow, then overflow):
$ i13 run tco.i13 # sumto(0,4000): tail-recursive accumulator sum
RUN OK 57423 steps peak stack 4call depth 4001
s4000 = 8002000 -- correct, but 4001 frames deep
$ i13 run tco2.i13 # sumto(0,9000): past the cap
error[E0503] runtime/resource: I13 execution exceeded 4096 frames
Recommend: tail-call elimination is the highest-value OPEN pass for I-13, and this dart carries the measurement to prove it: sumto(0,4000) runs correctly with peak operand stack 4 (nothing pending — every recursive call is genuinely in tail position) yet call depth 4001, and sumto(0,9000) hits error E0503: exceeded 4096 frames. The flat operand stack is the proof that a TCO pass could reuse the frame and lift the recursion wall for the entire class of accumulator loops. The studio’s rev5 already carries a tail-call form; the canonical H1.1 compiler does not — a clean, motivated target. OPEN on canonical i13