4 ms·
Please, for the sake of $DIETY, stop calling it "Tail Call Optimization". It is not an optimization, and the wrong term causes lots of useless discussions and m
by beagle3 14y ago
Please, for the sake of $DIETY, stop calling it "Tail Call Optimization". It is not an optimization, and the wrong term causes lots of useless discussions and misunderstanding. Call it "Tail Call Elimination", because that's what it is.
With finite memory (that is, in the real world), a program that relies on tail recursion will blow up if TCE is not implemented even though it can run forever with TCE. Thus, it changes actual program results (rather than just runtime speed or amount of memory required), and cannot be considered just an "optimization", since it is functionally required.
And to future-language designers: Please, for the sake of $DIETY2, make the syntax for guaranteed-eliminated-tail-call different than a regular call: It's really a bad idea that a function such as:
def f(x):
...
return 0+f(x-1)
cannot in general be TCEd (adding 0 to a floating point imporper denormal will make it proper), whereas
def f(x):
...
return f(x-1)
can. I suggest "chain y" instead of "return y" so that the compiler can verify that a TCE can indeed happen.
- gngeal 14y ago"Please, for the sake of $DIETY" If you worship food, that is. But you're right, people calling proper tail calls "an optimization" should be shot. Those who survive the subsequent generation scavenging should be shot again. :-)
- kibwen 14y agoAs a historical note, this was also the original plan for Rust, where the presence of the `be` keyword rather than the `return` keyword would indicate tail-calling.
- millstone 14y agocannot be considered just an "optimization", since it is functionally required Here is a C program: #include <stdio.h> int main(void) { while (1) malloc(64); } With clang, when compiled with -O0, this consumes all the memory on my system. When compiled with -O2, it runs forever in constant memory, because clang has optimized out the call to malloc. If I replace the call with, say, 'malloc((size_t)(-1) >> 1)', it even changes the output of the program. Here is another example: int factorial(long long x) { return x * factorial(x-1); } With gcc, when compiled with -O2, the factorial function can correctly compute the factorial of a very large number. When compiled with -O0, it cannot. I would call both of these optimizations, even though someone may rely on either for correctness. So I don't think tail calls are unique in this respect. make the syntax for guaranteed-eliminated-tail-call different than a regular call Agreed.
- kragen 14y agoThe reason people are so interested in TCO/TCE is not just that someone might rely on them for correctness, which as you point out is true of any optimization, but rather that they are so predictable that you can omit looping constructs from your core language if you have them.
- baddox 14y agoIn the finite world beagle3 talks about, don't all optimizations potentially qualify as "functionally required"? If the finite world you're operating in can only run a program that requires at most N steps ("steps" being deliberately vague "computing resources," like CPU cycles or memory usage), then any optimization that makes an (N+1)-step program complete in N steps qualifies as a "functional requirement."
- bcoates 14y agoBoth of those programs are playing with C's infamously broad undefined behavior rules, the first for a non-terminating loop and the second for using too much stack (when called with a sufficiently large number). -O2 being nice to you is a coincidence, not something you should rely on. In a language which prefers diagnosing programmer error over punting both should be errors.
- beagle3 14y ago> even though someone may rely on either for correctness. That someone is playing with fire. It's the kind of optimization that might be removed in a hotfix because it turns out to break something else. It's even worse than relying on things like byte order -- and if you rely on them, you are definitely outside the realm of "C language", and into the realm of "Specifically LLVM v.37x patchlevel 2, on an SSE4 architecture"
- ericbb 14y agoOr follow Alef (http://www.cs.bell-labs.com/who/rsc/thread/ug.pdf http://www.cs.bell-labs.com/who/rsc/thread/ug.pdf) and use "become". The Alef become statement is a kind of generalized tail-call form because you can use it to drop the current stack frame from anywhere, not just in tail-position.
- kragen 14y agoI suggest "chain y" instead of "return y" so that the compiler can verify that a TCE can indeed happen. I think the rust syntax for this was `be y` instead of `return y`.
- srean 14y agoIf I remember correctly the new version of TCL will have special syntax to enforce TCE. Unfortunately I did not book mark the relevant online discussion.