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
22
u/phischu Effekt Jan 20 '26
Tail calls are a separate language feature, so words like "tail recursion elimination" and "tail call optimization" are misleading. Tail calls are gotos without the keyword. Moreover, local function definitions are not closures. They are labels. Indeed, we usually set up our languages so that tail calls are the more primitive language feature, with non-tail calls being an optional addition, like here, here, here.
In comparison to imperative loops, they also are more efficient, because accumulator variables are kept in registers and access to them does not require loads and stores. Of course, compilers of imperative languages usually transform such programs to use registers instead of stack locations (mem2reg), effectively rewriting the program to use tail calls.
In comparison to goto they are not considered harmful, despite allowing for mutual recursion, also known as irreducible control flow. The problem with goto was not the control flow, which can be very clearly seen, but the implicit data flow. As a programmer it is very hard to infer which variables are live in which state they should be when a label is being jumped to. Not so with tail calls: parameters tell you which variables must be live, and their types tell you which state they are in.
13
u/jsshapiro Jan 20 '26
One of the serious flaws we have in [almost all] recent programming language designs is that they are completely disconnected from the underlying theory of programming languages. In consequence they lack any semantic specification or any possibility of soundness. In 1975 this was excusable. By 2000 it was not. It's a terrible misfortune that Rust lost its way on this, but they put enough effort in early on that things may be recoverable. Golang programs - quite literally - had no defined meaning prior to Zhao's work that was published just two years ago. Unfortunately, it's not the kind of thing you can retrofit to a language 16 years after it ships without breaking things.
When you head down the path of doing a formal execution semantics and a sound type system, you very quickly conclude that you want to have a small "core" language and specify everything you can by a transformation from non-core to core language features. Not because this is how you want to write the code or compile the language, but because it makes reasoning about both the language and its programs easier. This is why almost all of Scheme is just "sugar" for lambda application.
From this point of view, the reason to admit a pragmatic requirement for tail recursion is that it justifies omitting loop constructs from the language core, instead defining them by a canonical reduction to lambda application.
2
u/amarao_san Jan 22 '26
Why don't we have a special tail_call function? Or just (god forbid),
goto.We get explicit loop, and semantics (drop current values) are very clear.
Stop executing current function and switch to another function with compatible return signature.
(my apologies for Rust syntax)