* * * * *
“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.
>
“ Tail Call Optimization [1]”
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.
[1]
http://tratt.net/laurie/tech_articles/articles/tail_call_optimization
Email author at
[email protected]
