Why Object-Oriented Languages Need Tail Calls

Why is there even an argument about this? Not being able to make a recursive call without potentially blowing the stack is a major drawback in any language. I'd venture to say it's a "bug.”

You aren’t going to like Python:

  I don't believe in recursion as the basis of all
  programming. This is a fundamental belief of certain
  computer scientists, especially those who love Scheme
  and like to teach programming by starting with a "cons"
  cell and recursion. But to me, seeing recursion as the
  basis of everything else is just a nice theoretical
  approach to fundamental mathematics (turtles all the
  way down), not a day-to-day tool.

http://neopythonic.blogspot.com/2009/04/tail-recursion-elimi...

(I’m not advocating this view, just pointing out that there are programmers who appear in all other respects to be reasonable, intelligent, contributing members of computing society who actually feel that TCO is a bug, that 1000 calls ought to be enough for anybody, and so forth.)

> Not being able to make a recursive call without potentially blowing the stack is a major drawback in any language. I'd venture to say it's a "bug."

Recursive calls can blow the stack even with TCO....

I like TCO, but it lends itself to "infinite loops" that aren't as easy to figure out because they're not "local".

> And TCO is so handy in so many instances that it's silly not to have it.

"So handy" is even more true of lisp macros but ....

> And you gain performance.

It depends. If you're not doing a lot of interprocedural analysis, you can easily lose performance by writing "TCO-style".

That is a bit misleading. Not every recursive function is tail-recursive, and making it tail-recursive will often throw away the benefits of recursion. Take, for example, a simple factorial implementation in OCaml (ignore for the sake of this example that int will overflow for reasonably large values of x, I don't want to complicate the example by using big_int):

  let rec fact x =
    if x <= 1 then 1
              else x * fact (x-1);;

This implementation is not tail-recursive, so tail-call optimization will not help. Now, you can make the function tail-recursive by rewriting it to use a helper function with an accumulator:

  let fact x =
    let rec f x a =
      if x <= 1 then a
                else f (x-1) * (x-a)
    in
      f x 1;;

This implementation is tail-recursive; however, this happens at the loss of readability. Furthermore, any such accumulator-based implementation can trivially be converted into a (non-recursive) loop, which is in fact exactly what the compiler will do.

Now, if you look at the Hamster library code that inspired the post, you will see the following in hamster/list.rb:

  def map(&block)
    return self unless block_given?
    Stream.new do
      next self if empty?
      Sequence.new(yield(head), tail.map(&block))
    end
  end
  

That's not tail-recursive, either, and the author would experience the self-same problems if ruby actually optimized tail calls. He'd have to rewrite his implementation for that.

(If you look at OCaml's List.map, you will notice that it is not tail-recursive, either, and you will have to chain List.rev_map and List.rev to get a tail-recursive map.)

In short: tail-call optimization is no silver bullet that protects against stack overflow. It's not uncommon for programmers to assume that code is tail-recursive when it, in fact, isn't (which is one reason why Scala, for example, has the @tailrec annotation to let the programmer verify that a function is actually tail-recursive).

That does not mean that tail-call optimization is useless even in a procedural or object-oriented language. For example, if you have a language with formal function/procedure/method arguments that cannot be assigned to (that includes not only functional languages, but also Eiffel or Scala, and affects also the implicit self/this argument in any object-oriented language), then the only way to let the garbage collector free objects referenced by these arguments is to drop references to them via a tail call.

Relevant LtU thread: http://lambda-the-ultimate.org/node/3702