Friday, October 19, 2007
“You're programming it wrong.”
This function essentially sums all even integers from 0 to i inclusive. However, this function contains two tail calls, and what's worse as the function recurses those two tail calls are interleaved (in this case, the pattern of that interleaving is simple and easily determined in advance, but there is no reason why that would be the case in general). As far as I can see, this means that it is now impossible to record, or calculate, a full error report in the presence of tail calls in a static amount of stack space. The previous trick of recording a pointer is of little use, since every time tail recursion occurs via a different line of code than the previous call, then a new counter needs to be created pointing to the new tail call location: in the worst case, this will lead to exactly the same number of stack levels being recorded as in the unoptimized tail calling case.
The lack of a stack trace in tail calls is one reason to dislike them. But I dislike them for an entirely different reason.
Now, just to refresh your memory, a recursive function is a function that calls itself:
fib(i)
if i = 0
return 0
else
if i = 1
return 1
else
return fib(i - 1) + fib(i - 2)
end
end
result = fib(10);
But recursion is expensive, as it requires aditional stack frames to handle (but it's the stack frames that make debugging easier if it's required). If the last thing a function does is call itself:
mult(a,b)
if a = 1
return b
else
return(a - 1,b+b)
end
the compiler can turn this into a loop. And this space optimization (and
that's what it is) is called `tail call optimization.” But it has to
be of that form, where the last thing the routine does is call itself (and
yes, the example mult() function above doesn't work for values
of 0 or less, but this is an example).
fib2(i,current,next)
if i = 0
return current
else
return fib (i - 1,next,current + next)
end
result = fib2(10,0,1);
But at that point, can you really consider it recursion? If the only way you get the benefit is to construct non-intuitive recursive functions that you can't even get a proper trace out of, isn't calling such an optimization “elegant” a polite fiction? Isn't the compiler there to take care of such details for me? Why should I be forced to write convoluted code to get decent performance? If I want that, I can code in C.
And that's my problem with tail call optimization.
