The Boston Diaries

The ongoing saga of a programmer who doesn't live in Boston, nor does he even like Boston, but yet named his weblog/journal “The Boston Diaries.”

Go figure.

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.

Tail Call Optimization

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.

Obligatory Picture

[Here I am, enjoying my vacaton in a rain forest.]

Obligatory Links

Obligatory Miscellaneous

You have my permission to link freely to any entry here. Go ahead, I won't bite. I promise.

The dates are the permanent links to that day's entries (or entry, if there is only one entry). The titles are the permanent links to that entry only. The format for the links are simple: Start with the base link for this site: http://boston.conman.org/, then add the date you are interested in, say 2000/08/01, so that would make the final URL:

http://boston.conman.org/2000/08/01

You can also specify the entire month by leaving off the day portion. You can even select an arbitrary portion of time.

You may also note subtle shading of the links and that's intentional: the “closer” the link is (relative to the page) the “brighter” it appears. It's an experiment in using color shading to denote the distance a link is from here. If you don't notice it, don't worry; it's not all that important.

It is assumed that every brand name, slogan, corporate name, symbol, design element, et cetera mentioned in these pages is a protected and/or trademarked entity, the sole property of its owner(s), and acknowledgement of this status is implied.

Copyright © 1999-2017 by Sean Conner. All Rights Reserved.