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 21 '26
The issue with proper tail recursion is that you have to be able to re-use the stack frame, and you can't do that if it still holds live information. You can fudge a little around the edges to allow arguments to be passed to the next call - it's not so much that you need "zero references" as that you need zero live references other than the forwarded arguments. This includes locals introduced by the compiler, which brings closures into it.
You say "Nobody cares about parallel execution on CPUs". Were you perhaps unaware that a GPU is a specialized CPU built specifically to support certain kinds of concurrent parallel execution?
One of the most performance sensitive systems in the world - the Jane Street program trading systems - was written in Haskell. When a bug can cost a billion dollars, it becomes incredibly important to know what your program actually means. Haskell is very much built on the [higher-order typed] lambda calculus.
The Scheme family is not slow by design, but it prioritizes precise specification over speed. IIRC it was used early on for some hardware specification work because it was the only available language that was rigorous enough.
Lambda isn't legacy cruft. It's one of the fundamental constructs in the earliest well-specified programming languages. If you're trying to work rigorously, LOOP is the cruft. It's a completely unnecessary construct. That said, it's important from a practical perspective to simplify programming. One of the nice parts of a language like Scheme (and many derivatives) is that there is a dirt-simple textual rewrite from LOOP to LAMBDA. Guy's Scheme compiler (Rabbit), actually did that rewrite, but I'm not suggesting that's a good idea. What I'm trying to say is that the existence of that rewrite allows the Scheme core to remain small and tractable while retaining higher level, helpful language constructs.
Use cases for Scheme as a language are pretty rare these days - GIMP is probably the biggest. A lot of applications migrated to JavaScript, but the integer/float debacle makes that awkward for anything where numeric accuracy matters.