Why Object-Oriented Languages Need Tail Calls (2011)
eighty-twenty.org
eighty-twenty.org
The primes example effectively constructs a linked list with 78,498 elements; any unsuccessful search will iterate over all those elements, and successful searches will (depending on how the search arguments are distributed) also easily traverse tens of thousands of elements. Handwaving performance issues away with "we know lots of ways this code can be optimized, but let us please focus on the behavior of the constructed set" is wrong, simply because efficient and actually usable implementations may exhibit totally different requirements w.r.t. tail recursion and what should be in an interface.
Thank you so much for that!
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`.
https://github.com/andreas-gone-wild/snackis/blob/master/sna...
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.
Indeed, if I were to add an explicit tail syntax to some language, it would probably involve the "goto" keyword.
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.
Tail recursion doesn't need to be “detected”. The correct implementation of all tail calls, recursive or otherwise, is to overwrite the current activation record, rather than save it.
> mapping more obviously to the behavior of actual machines we use to execute our code.
There's a reason we usually don't write in assembly.
Because we want programming languages to hide the hardware complexity behind elaborated semantics. Programming languages are for humans, not for machines.
Why? I find recursive functions are often simpler to understand and write than iteration. Why does the compiler need to stop me from doing so? You write "technically" as though it were just an obscure technicality that it's possible to implement a function call without taking up excessive stack space, but to my mind it's a fundamental fact.
> 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.
In what sense is this true? Recursive function: update these variables (in registers or memory) and jump back up to this instruction. Iteration: update this variable and jump back up to this instruction.
I'm in favor of having special syntax because compilers shouldn't really be in the business of 'do what I mean not what I say'.
The Scheme approach of mandating the use of tail calls for every call which occurs in "tail position" is the correct one, in my opinion.
But it's not though. By this token failing to optimize anything could be considered incorrect behavior. Obviously not turning on optimizations makes your program take longer and use more memory. When a function call is made its variables are pushed onto the stack and popped when the function returns. Doing something different when the compiler detects certain properties of your code is the definition of an optimization that at least in theory shouldn't be relied on to produce correct code.
A more correct design, I think, would be having a 'replace' keyword for function calls instead of return that causes it to replace the stack of the caller. Then the behavior is no longer an optimization but behavior. Now you have the best of both worlds. The compiler can even warn you about when you might want to use replace rather than return.
Yes, but it shouldn't take an algorithm which only requires constant space as written and turn it into object code which requires linear space.
Update: Elaborating on this point somewhat—Consider the case of a simple loop with a local variable. The variable is specific to the body of the loop; each iteration, in effect, has its own copy of the variable. What if a compiler implementer decided, for the sake of simplicity, to allocate block-local variables with alloca(), so that new memory is reserved from the stack for each loop iteration, and only freed when the enclosing function returns? Perhaps an optional optimization is provided -floop-variable-space-optimization which "lifts" the variable out of the loop, allowing the memory to be reused and restoring constant space complexity. Would you still consider this an acceptable implementation on the grounds that "obviously not turning on optimizations makes your program ... use more memory"? I think not.
> When a function call is made its variables are pushed onto the stack and popped when the function returns.
That is nothing more than an unfortunate, naïve implementation choice common among compilers which do not implement tail calls properly. Nothing in the definition of a function or a function call requires the use of a stack. What is required is only a continuation—a reference to the code to be executed when the function is finished. When there is a chain of calls F -> G -> H, and the G -> H call is in tail position, the natural continuation for that call is the same continuation which was provided to G. A compiler which does not implement tail calls properly, however, interposes an extra, unnecessary continuation for the call to H, turning a (potentially) constant-space function into a linear one.
> A more correct design, I think, would be having a 'replace' keyword for function calls instead of return that causes it to replace the stack of the caller.
Most modern languages make it simple to determine when a function call is in tail position, and in such cases I feel that a special calling syntax would be an unnecessary distraction. In Scheme, for example, the cases where a tail call is required are obvious from the structure of the code and are, moreover, spelled out in the language standard. However, I will grant that languages like C and C++ which occasionally depend on the compiler adding hidden code at the end of some functions to run destructors or implicitly transform the result type might benefit from such a keyword. It would, at any rate, be an improvement over the current situation where proper tail calls are deemed an optional optimization.
But it's completely arbitrary that you consider this "a compiler optimization" as opposed to "the way the language behaves." The languages you're used to work the way you describe: if the stars are aligned, a particular compiler may do TCO as an extra optimization.
But there is absolutely no reason it has to be this way. It is perfectly possible for a language standard to mandate that TCO must happen and to specify in an easily understood way when it must happen. As Scheme did over 40 years ago.
For simple recursive algorithms, that's true. And those tend to overlap well with ones which don't require assisted tail call tagging or whatever.
Those that do, however, tend to be pretty complicated. And the set of programmers who can understand an interative implementation of them is IMHO rather larger than that which can get their heads around the tail call analysis to know how (and when!) to make it work.
Clojure does exactly that:
(defn gcd [x y]
(if (zero? y)
x
(recur y (quot x y)))
(defn factorial [n]
(loop [n n, fac 1]
(if (zero? n)
fac
(recur (dec n) (* fac n)))))
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.
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.
Eventually one could do some tricks with invokedynamic, but I doubt the performance impact would be worthwhile.
Nor does there need to be one, because translating function calls to jumps is the (AOT) compiler's business, not the VM's.
int factorial(int x) {
if (x > 1) return x * factorial(x-1);
else return 1;
}
int factorial(int x) {
int result = 1;
while (x > 1) result *= x--;
return result;
}
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.
5 * (4 * (3 * (2 * 1)))
to:
(((1 * 5) * 4) * 3) * 2
It relies on the commutative and associative nature of integer multiplication.
This means it's quite a brittle optimization -- it shouldn't really work for floats, for example, which aren't associative at multiplication. And it wouldn't work on any operation for which the compiler does not know the associativity.
So while it seems general -- it's quite specific and not widely applicable.
Even in jq we found that adding TCO enabled a number of interesting possibilities. For example, the range() builtin in jq can be implemented as a tail-recursive function (and the version that takes two or three arguments is). There are a number of builtins in jq 1.5 which are made possible and practical only by having TCO. Before we added TCO it just didn't seem that interesting, but it's proven to be quite an enabler.
I can't think of a language that shouldn't have TCO. C/C++ absolutely should have it (and many compilers do). Java should have it (but doesn't). Lisps badly need it and generally have it -- the same goes for all functional (or mostly functional) languages. Python needs it but apparently lacks it[0]. And so on.
Yes, tail calls obscure stack traces by eliding reused frames. This could be ameliorated by leaving a flag in reused frames that could be shown on stack traces to indicate that there are missing frames. Or perhaps syntactic sugar could be used to control which tail calls are to get optimized (since often it does not matter).
[0] https://stackoverflow.com/questions/13591970/does-python-opt...
On the one hand with tail calls you can write recursive code and find that it runs fast without excessive memory.
On the other hand when things blow up, it is really nice to have a stack backtrace to help debug why it blew up. But a stack backtrace can't include stack frames that were optimized away. Which makes it far harder to figure out why this call on this object turned into that call on that object.
Is that really a concern?
If you're writing a loop, do you expect your tools to show you a trace of every iteration in the loop? Of course not, because that would be silly. If you really want to trace each iteration, you can add your own tracing.
I think of tail-recursion as parameterized gotos that are wonderfully constrained and are useful for describing state transformations in a predictable way. It's not a regular function call, so the stack trace is probably a very bad idea.
Everyone readily thinks of loops, in the abstract, as "GOTO line X and do everything over again, but using all the state that has changed since the last time we were at line X."
Ideally, you can think of recursion as nearly the same thing: "GOTO line X and do this stuff again, but using these very clearly stated changes to the data."
If you think of recursion that way, then it's fairly self-evidently easier to reason about. In practice, though, I've met few developers who think that way and haven't spent significant time doing functional programming.
I'm guessing it's because you need to spend a fair bit of time with both abstractions before you can really grok either of them. Without that, they're just kind of intimidating. Recursion more so, because everyone's taught from a young age to think imperatively.
At least you can know at which iteration you are. If iterate over 12 elements and my loop counter is at 134753745, I can pinpoint what went wrong much more easily.
I wouldn't expect the same from an OO language, but I'm not sure that it's impossible either.
That paper is about implementing security models based on what is supposed to be in the stack. My concern is about emitting a debugging stack backtrace on error.
If you are concerned with a security model, it is nice to know that you can remove the stack and prove that the security model is satisfied. But you can't provide a programmer with a record of stack frames that you do not have.
[1] http://rpanachi.com/2016/05/30/ruby-recursion-stack-size-tai...