8 ms·
Why don't languages give tail calls their own syntax rather than making it an optimization? It seems like a lot of the arguments against tail calls boil down ei
by mikeash 9y ago
Why don't languages give tail calls their own syntax rather than making it an optimization? It seems like a lot of the arguments against tail calls boil down either 1) it's confusing when things go wrong and you weren't expecting stack frames to be optimized out or 2) it's hard to safely write tail-recursive code because a small change to the code or, worse, the compiler settings can make it stop being tail-recursive.
If you had to explicitly request it, say by doing `tailcall f()` instead of just `f()`, that would mostly fix these problems. Control flow will be a lot less confusing since it'll be explicit in the code (but you still lose information from the optimized-out stack frames, no way around that) and you'll get an explicit error if someone tries to add something that can no longer be tail call optimized, like `tailcall f() + 1`.
- catnaroek 9y agoI understand the case for adding O(1) overhead for the sake of debuggability, but not having proper tail calls (it's not an optimization, goddammit) is way more than O(1) overhead.
- cr__ 9y agoThis is how Clojure does it. https://clojuredocs.org/clojure.core/recur https://clojuredocs.org/clojure.core/recur https://clojuredocs.org/clojure.core/trampoline https://clojuredocs.org/clojure.core/trampoline
- mikeash 9y agoNice. When I wrote that, I was sure there would be some language that had already done it, and I was about 90% sure it would be some sort of Lisp.
- andreasgonewild 9y agoThat, or some sort of Forth; the separate keyword also enables calling anonymous functions recursively: https://github.com/andreas-gone-wild/snackis/blob/master/snabel.md#lambdas https://github.com/andreas-gone-wild/snackis/blob/master/sna...
- to3m 9y agoWe even already have a common keyword suitable for this: 'goto'.
- javajosh 9y agoheck you don't even need goto, just a labelled break, which is extremely well supported across languages (great comment btw i lol'd)
- sevensor 9y agoThis is an interesting point -- structured programming has made source code vastly easier to reason about, but at the cost of turning some obvious control structures into optimizations. The upshot is that we don't have some of the really terrible control structures that were enabled by goto. I once had the pleasure of reading through some old Fortran code that freely jumped into various points in the middle of a loop, from outside the loop. Took me ages to figure out what it was doing.
- jcdavis 9y agoScala sort of has this with the @tailrec annotation. The compiler will always attempt TCO, but the annotation makes failure to do so a compilation error. (Its not a perfect situation though, since there can still be functions assumed to be tail recursive without @tailrec, and whose behavior can change without warning)
- stormbrew 9y agoDefinitely. I think, especially, in the case of retrofitting it into an existing language this is the way to go.
- ajross 9y ago> Why don't languages give tail calls their own syntax rather than making it an optimization? Grumpy old man answer: because if you need "special syntax" to express the fact that your recursively defined function can technically be evaluated in constant stack space, you probably should be writing it as an iterative function to begin with. The whole point about recursion as a software engineering paradigm is that it's a clearer way to express the problem and thus less likely to be mistakenly implemented. Special syntax is the opposite of clear. Iteration ain't that hard either folks, and it has the notable advantage of mapping more obviously to the behavior of actual machines we use to execute our code.
- catnaroek 9y agoStructured looping constructs are rather removed from how a machine works - not that this is inherently a bad thing. The way it actually works in a physical machine is via jumps into code that has already run, i.e. self-reference, i.e. recursion.
- adrianratnapala 9y agoMy way of saying the same thing is that there is surprisingly little difference between the recursive and iterative models when you start breaking things down. Indeed, if I were to add an explicit tail syntax to some language, it would probably involve the "goto" keyword.
- ajross 9y agoA loop can be turned into branch-based code with an absolutely trivial transformation (e.g. evaluate the test, branch to the end if false, branch back to the start at the end), I don't quite know what you mean by that. 3GL compilers were available with working looping syntax within years of the first programmable computers. FIVE decades later, and as this thread proves, we still don't have general algorithms to turn recursive solutions into iterative ones at the compiler level. It's true that it's more abstracted than machine code. It's absoultely not true that it's equivalently complicated to tail recursion detection.
- dghf 9y ago> Why don't languages give tail calls their own syntax rather than making it an optimization? Clojure does exactly that: (defn gcd [x y] (if (zero? y) x (recur y (quot x y))) You can also recur with TCO to an explicitly labelled point within the function (effectively creating an inner, anonymous function): (defn factorial [n] (loop [n n, fac 1] (if (zero? n) fac (recur (dec n) (* fac n))))) As I understand it, this syntax was developed because of limitations of the JVM w/r/t TCO.
- catnaroek 9y ago> As I understand it, this syntax was developed because of limitations of the JVM w/r/t TCO. This doesn't make sense. Tail calls don't need any virtual machine support whatsoever: they're translated into jumps by the compiler. The real problem is a lack of willingness to translate functions into anything other than JVM methods, because “compatibility“, but that is a political issue, not a technical one.
- _pmf_ 9y agoI don't think it's that easy. Clojure code calls into Java libraries, and these are regular Java functions so you cannot reuse the same stack frame for these. Pure Clojure code, on which you could perform arbitrary transformations, is quite rare (does not exist at the moment, since the core datastructures are written in Java).
- catnaroek 9y ago> Clojure code calls into Java libraries, and these are regular Java functions so you cannot reuse the same stack frame for these. Somehow, programs written in <insert language that provides correctly implemented tail calls> can call routines written in C (of all languages!) without any problems. So I stand by what I previously said: the problem is political, not technical.
- pjmlp 9y ago
- Jach 9y agoProbably because people have concluded that programmers suck at explicitly specifying optimizations, so much so that things like "inline" don't guarantee inlining in certain languages. Furthermore tail recursion elimination can happen as an optimization even when the source isn't clearly tail recursive. For example, GCC can optimize this: int factorial(int x) { if (x > 1) return x * factorial(x-1); else return 1; } to this: int factorial(int x) { int result = 1; while (x > 1) result *= x--; return result; } (See http://ridiculousfish.com/blog/posts/will-it-optimize.html http://ridiculousfish.com/blog/posts/will-it-optimize.html for other fun optimizations.)
- adrianratnapala 9y agoI think mikeash's point is that sometimes tail-recursion is not just an optimisation. For example it means I won't overflow my stack even if this thing recurses 10^7 times. Right now, a programmer needing such guarantee must write explictly iterative code. But with explicit tail calls, she can write it recursively if she wants and get a compiler error if something makes it impossible to do the tail-call transformation.
- Jach 9y agoThere's an interesting idea here that I wonder if any non-academic language has tried: annotating your expected big-O time and space complexities for a function. I wouldn't expect much compiler support except for trivial cases though due to the halting problem... AFAIK academic attempts at automated program analysis go back to Knuth and his students in the 70s, no idea what the state of the art looks like.
- adrianratnapala 9y agoI expect the trivial cases are the common ones for big-O.
- sitkack 9y agoEverytime I have used a tail call, it was because I wanted the control flow, not the optimization. Optimization is a misnomer for such a powerful construct. I think having an explicit `tailcall f(args)` would go a long way towards assuaging the non-tailers fears.
- pjmlp 9y agoIn Scheme it isn't just an optimization, it is an actual semantic requirement.