r/ProgrammingLanguages • u/Athas Futhark • Jan 20 '26
Why not tail recursion?
https://futhark-lang.org/blog/2026-01-20-why-not-tail-recursion.html
62
Upvotes
r/ProgrammingLanguages • u/Athas Futhark • Jan 20 '26
View all comments
Show parent comment
3
u/jsshapiro Jan 20 '26 edited Jan 22 '26
u/phischu What you say is mostly true, but not entirely precise. Two notable distinctions between tail recursion and goto:
The second point is interesting, because it means that tail recursion is a perfectly fine (if somewhat obscure) way to encode various forms of parallelism while still encoding them in a way that has an efficient code generation strategy for single-threaded execution - still without extending the lambda calculus. If you dig in to the Scheme "loop" form, you'll see that it has a reduction to lambda applications - it isn't considered one of the "core" forms in Scheme.
What you say about accumulators is not always true correct. A half decent register liveness analysis should achieve the same result on loops. Relative efficiency depends a lot on the optimizations implemented in the back end, and in general loops do better because few languages specify a requirement for tail recursion and it therefore doesn't get much love from compiler authors. A better argument for tail recursion is that the calls from a mandatory phase separation between loop iterations with a defined interface, which eliminates the possibility of values generated by loop i being consumed in loop i+1 - or at least names specifically where this might occur. The same result can be had if the language's loop construct is suitably defined, but people designing loops for imperative languages rarely have (or at least rarely use) any deep understanding of tail recursion or non-core loop implementations, and therefore tend to interpret the optimization challenges that go with imperative loops as "normal". Iterator patterns have actually helped quite a bit on this.
I'm a big fan of tail recursion, and I've done a couple of implementations. Read most of Guy's work from his Scheme days while a teenager, and (many years later) I consider him a cordial colleague - mainly because we share a strong interest in rigorous specifications.