3 ms·
Probably because people have concluded that programmers suck at explicitly specifying optimizations, so much so that things like "inline" don't guarantee inlini
by Jach 9y ago
Probably 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.
- Peaker 9y agoThis optimization changes factorial from: 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.