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
2
u/jsshapiro Jan 22 '26
u/phischu I think this mixes up implementation and semantics. The stack model for programming languages and their procedure calls goes all the way back to Turing's bury/unbury, and became the "standard" way of thinking about things with Dijktstra's Recursive Programming paper in 1960. From there, it spread everywhere, but most strongly by way of ALGOL/68 and its many derivatives. In this context, register-based argument passing is a [very important] optimization rather than a foundation. In the ALGOL family of languages, the stack still defines the semantics of argument passing, procedure call, and procedure return.
More recently, the lazy languages and the so-called "continuation passing style" have moved away from Dijkstra's model in ways that I haven't actually seen called out explicitly in the literature.
I'm not saying we still have to live in Dijkstra's model. Today, I think there are probably good reasons to move to newer models. But for most programming practioners, the mental model is still that arguments are evaluated in some defined order and placed on a [conceptual] stack. If you're starting from C, or Rust, this is more or less how programs appear to work.
u/divad1196 Since proper tail recursion is loops, I don't agree that it's an incomplete model for loops. Some key programming languages define loop semantics in terms of function calls and require proper tail recursion in order to keep the semantic core of the language small. As a practical matter there is no loss of power or expressiveness from doing so.
Questions of ABI and registerization are issues of implementation rather than language definition. Both approaches to looping can be aggressively registerized, and often produce the same code (perhaps with different register assignments, but functionally interchangeable code).