THE FOLD / RESPAWN / SECOND WIND / THE TAIL CALL
THE TAIL CALL
a record of the past traded for a future
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
If the very last thing a function does is call another one, the caller’s frame has nothing left to do. Reuse it instead of stacking a new one, and recursion stops being bounded by memory.
LIT verified live. A stack limited to 10,000 frames. Without the transformation, 100 calls use 100 frames and 1,000 use 1,000; the first overflow is at 10,000 calls, and 3 of the 5 sizes tested fail. With it, every size completes and the frame count is 1 — at a hundred calls or a million. It is a jump, not a call.
LIT verified live. A stack limited to 10,000 frames. Without the transformation, 100 calls use 100 frames and 1,000 use 1,000; the first overflow is at 10,000 calls, and 3 of the 5 sizes tested fail. With it, every size completes and the frame count is 1 — at a hundred calls or a million. It is a jump, not a call.
2 HOW IT WAS WEAVED · AI + HUMAN
Proper tail calls are required by the Scheme standard and are the reason recursion is the ordinary loop there; most mainstream languages do not guarantee them.
AVAN (AI) reports the frame count as flat rather than as a reduction, because a reduction implies a smaller version of the same quantity. It is not smaller — it stops being a function of the input at all, and that change in kind is what makes a recursive algorithm safe to write.
AVAN (AI) reports the frame count as flat rather than as a reduction, because a reduction implies a smaller version of the same quantity. It is not smaller — it stops being a function of the input at all, and that change in kind is what makes a recursive algorithm safe to write.
3 ONE DIMENSION
Calls against frames, with and without.
4 TWO DIMENSIONS · INTERACTIVE
Add calls until the stack gives out.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a frame reused forever.
AVAN’s addition (the inverse-companion): the forward reading is that tail calls make deep recursion safe. The inverse is that they do it by destroying the evidence. Each reused frame overwrites the one before, so the stack trace that would have told you how you got here no longer exists — the crash reports the last frame and nothing about the million that led to it. Read backwards, the optimisation trades a record of the past for the ability to have a future, and every language that guarantees tail calls has quietly decided which of those two the programmer needs more.
LIT with a stack limited to 10,000 frames, 100 calls use 100 frames and 1,000 use 1,000 without the transformation, the first overflow lands at 10,000 calls and 3 of the 5 sizes tested fail - while with it every size completes and the frame count is 1, at a hundred calls or a million
FIG Proper tail calls are required by the Scheme standard and are the reason recursion is the ordinary loop there; most mainstream languages do not guarantee them. AVAN reports the frame count as flat rather than as a reduction, because a reduction implies a smaller version of the same quantity. It is not smaller - it stops being a function of the input at all, and that change in kind is what makes a recursive algorithm safe to write.
FIG Proper tail calls are required by the Scheme standard and are the reason recursion is the ordinary loop there; most mainstream languages do not guarantee them. AVAN reports the frame count as flat rather than as a reduction, because a reduction implies a smaller version of the same quantity. It is not smaller - it stops being a function of the input at all, and that change in kind is what makes a recursive algorithm safe to write.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of SECOND WIND · David Lee Wise (ROOT0), with AVAN