When there's no TCO, when to worry about blowing the stack?

Question

Every single time there's a discussion about a new programming language targetting the JVM, there are inevitably people saying things like:

"The JVM doesn't support tail-call optimization, so I predict lots of exploding stacks"

There are thousands of variations on that theme.

Now I know that some language, like Clojure for example, have a special recur construct that you can use.

What I don't understand is: how serious is the lack of tail-call optimization? When should I worry about it?

My main source of confusion probably comes from the fact that Java is one of the most succesful languages ever and quite a few of the JVM languages seems to be doing fairly well. How is that possible if the lack of TCO is really of any concern?

Answer 1

Consider this, let's say we got rid of all loops in Java (the compiler writers are on strike or something). Now we want to write factorial, so we might right something like this

int factorial(int i){ return factorial(i, 1);}
int factorial(int i, int accum){
  if(i == 0) return accum;
  return factorial(i-1, accum * i);
}

Now we're feeling pretty clever, we've managed to write our factorial even without loops! But when we test, we notice that with any reasonably sized number, we're getting stackoverflow errors since there's no TCO.

In real Java this isn't a problem. If we ever have a tail recursive algorithm, we can transform it into a loop and be just fine. However, what about languages with no loops? Then you're just hosed. That's why clojure has this recur form, without it, it's not even turing complete (No way to do infinite loops).

The class of functional languages that target the JVM, Frege, Kawa (Scheme), Clojure are always trying to deal with the lack of tail calls, because in these languages, TC is the idiomatic way of doing loops! If translated to Scheme, that factorial above would be a good factorial. It'd be awfully inconvenient if looping 5000 times made your program crash. This can be worked around though, with recur special forms, annotations hinting at optimizing self calls, trampolining, whatever. But they all force either performance hits or unnecessary work on the programmer.

Now Java doesn't get off free either, since there's more to TCO then just recursion, what about mutually recursive functions? They can't be straightforwardly translated to loops, but are still unoptimized by the JVM. This makes it spectacularly unpleasant to try to write algorithms using mutual recursion using Java since if you want decent performance/range you have to do dark magic to get it to fit into loops.

So, in summary, this isn't a huge deal for many cases. Most tail calls either only proceed one stackframe deep, with things like

return foo(bar, baz); // foo is just a simple method

or are recursion. However, for the class of TC that don't fit into this, every JVM language feels the pain.

However, there is a decent reason why we don't yet have TCO. The JVM gives us stack traces. With TCO we systematically eliminate stackframes that we know are "doomed", but the JVM might actually want these later for a stacktrace! Say we implement a FSM like this, where each state tail-calls the next. We'd erase all record of previous states so a traceback would show us what state, but not anything about how we got there.

Additionally, and more pressingly, much of bytecode verification is stack based, eliminating the thing that lets us verify bytecode is not pleasant prospect. Between this and the fact that Java has loops, TCO looks like a bit more trouble than it's worth to the JVM engineers.

Answer 2

Tail calls optimizations is mainly important because of tail recursion. However, there is an argument why it is actually good that the JVM does not optimize tail calls: As TCO reuses a part of the stack, a stack trace from an exception will be incomplete, thus making debugging a bit harder.

There are ways to work around the limitations of the JVM:

1. Simple tail recursion can be optimized to a loop by the compiler.
2. If the program is in continuation-passing style, then it is trivial to use “trampolining”. Here, a function does not return the end result, but a continuation which is then executed on the outside. This technique allows a compiler writer to model arbitrarily complex control flow.

This may need a larger example. Consider a language with closures (e.g. JavaScript or similar). We can write the factorial as

def fac(n, acc = 1) = if (n <= 1) acc else n * fac(n-1, acc*n)

print fac(x)

Now we can have it return a callback instead:

def fac(n, acc = 1) =
  if (n <= 1) acc
  else        (() => fac(n-1, acc*n))  // this isn't full CPS, but you get the idea…

var continuation = (() => fac(x))
while (continuation instanceof function) {
  continuation = continuation()
}
var result = continuation
print result

This now works in constant stack space, which is kind of silly because it's tail-recursive anyway. However, this technique is able to flatten all tail calls into constant stack space. And if the program is in CPS, then this means that the callstack is constant overall (in CPS, every call is a tail call).

A major disadvantage of this technique is that it's much harder to debug, a bit harder to implement, and less performant – see all the closures and indirection I'm using.

For these reasons it would be vastly preferable to have the VM implement a tail call op – languages like Java that have good reasons not to support tail calls would not have to use it.

Answer 3

A significant portion of calls in a program are tail calls. Every subroutine has a last call, so every subroutine has at least one tail call. Tail calls have the performance characteristics of GOTO but the safety of a subroutine call.

Having Proper Tail Calls enables you to write programs that you cannot otherwise write. Take, for example, a state machine. A state machine can be very directly implemented by having each state be a subroutine and each state transition be a subroutine call. In that case, you transition from state to state to state, by making call after call after call, and you actually never return! Without Proper Tail Calls, you would immediately blow the stack.

Without PTC, you have to use GOTO or Trampolines or exceptions as control flow or something like that. It's much uglier, and not so much a direct 1:1 representation of the state machine.

(Note how I cleverly avoided using the boring "loop" example. This is an example where PTCs are useful even in a language with loops.)

I deliberately used the term "Proper Tail Calls" here instead of TCO. TCO is a compiler optimization. PTC is a language feature that requires every compiler to perform TCO.

Answer 4

"The JVM doesn't support tail-call optimization, so I predict lots of exploding stacks"

Anyone who says this either (1) doesn't understand tail-call optimization, or (2) doesn't understand the JVM, or (3) both.

I'll start with the definition of tail-calls from Wikipedia (if you don't like Wikipedia, here's an alternative):

In computer science, a tail call is a subroutine call that happens inside another procedure as its final action; it may produce a return value which is then immediately returned by the calling procedure

In the code below, the call to bar() is the tail call of foo():

private void foo() {
    // do something
    bar()
}

Tail call optimization happens when the language implementation, seeing a tail call, doesn't use normal method invocation (which creates a stack frame), but instead creates a branch. This is an optimization because a stack frame requires memory, and it requires CPU cycles to push information (such as the return address) onto the frame, and because the call/return pair is assumed to require more CPU cycles than an unconditional jump.

TCO is often applied to recursion, but that's not its only use. Nor is it applicable to all recursions. The simple recursive code to compute a factorial, for example, cannot be tail-call optimized, because the last thing that happens in the function is a multiplication operation.

public static int fact(int n) {
    if (n <= 1) return 1;
    else return n * fact(n - 1);
}

In order to implement tail call optimization, you need two things:

• A platform that supports branching in addition to subtroutine calls.
• A static analyzer that can determine whether tail call optimization is possible.

That's it. As I've noted elsewhere, the JVM (like any other Turing-complete architecture) has a goto. It happens to have an unconditional goto, but the functionality could easily be implemented using a conditional branch.

The static analysis piece is what's tricky. Within a single function, it's no problem. For example, here's a tail-recursive Scala function to sum the values in a List:

def sum(acc:Int, list:List[Int]) : Int = {
  if (list.isEmpty) acc
  else sum(acc + list.head, list.tail)
}

This function turns into the following bytecode:

public int sum(int, scala.collection.immutable.List);
  Code:
   0:   aload_2
   1:   invokevirtual   #63; //Method scala/collection/immutable/List.isEmpty:()Z
   4:   ifeq    9
   7:   iload_1
   8:   ireturn
   9:   iload_1
   10:  aload_2
   11:  invokevirtual   #67; //Method scala/collection/immutable/List.head:()Ljava/lang/Object;
   14:  invokestatic    #73; //Method scala/runtime/BoxesRunTime.unboxToInt:(Ljava/lang/Object;)I
   17:  iadd
   18:  aload_2
   19:  invokevirtual   #76; //Method scala/collection/immutable/List.tail:()Ljava/lang/Object;
   22:  checkcast   #59; //class scala/collection/immutable/List
   25:  astore_2
   26:  istore_1
   27:  goto    0

Note the goto 0 at the end. By comparison, an equivalent Java function (which must use an Iterator to imitate the behavior of breaking a Scala list into head and tail) turns into the following bytecode. Note that the last two operations are now an invoke, followed by an explicit return of the value produced by that recursive invocation.

public static int sum(int, java.util.Iterator);
  Code:
   0:   aload_1
   1:   invokeinterface #64,  1; //InterfaceMethod java/util/Iterator.hasNext:()Z
   6:   ifne    11
   9:   iload_0
   10:  ireturn
   11:  iload_0
   12:  aload_1
   13:  invokeinterface #70,  1; //InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object;
   18:  checkcast   #25; //class java/lang/Integer
   21:  invokevirtual   #74; //Method java/lang/Integer.intValue:()I
   24:  iadd
   25:  aload_1
   26:  invokestatic    #43; //Method sum:(ILjava/util/Iterator;)I
   29:  ireturn

Tail call optimization of a single function is trivial: the compiler can see that there is no code that uses the result of the call, so it can replace the invoke with a goto.

Where life gets tricky is if you have multiple methods. The JVM's branching instructions, unlike those of a general-purpose processor such as the 80x86, are confined to a single method. It's still relatively straightforward if you have private methods: the compiler is free to inline those methods as appropriate, so can optimize tail calls (if you're wondering how this might work, consider a common method that uses a switch to control behavior). You can even extend this technique to multiple public methods in the same class: the compiler inlines the method bodies, provides public bridge methods, and internal calls turn into jumps.

But, this model breaks down when you consider public methods in different classes, particularly in light of interfaces and classloaders. The source-level compiler simply does not have enough knowledge to implement tail-call optimizations. However, unlike "bare-metal" implementations, the *JVM( does have the information to do this, in the form of the Hotspot compiler (at least, the ex-Sun compiler does). I don't know whether it actually performs tail-call optimizations, and suspect not, but it could.

Which brings me to the second part of your question, which I'll rephrase as "should we care?"

Clearly, if your language uses recursion as its sole primitive for iteration, you care. But, languages that need this feature can implement it; the only issue is whether a compiler for said language can produce a class that can call and be called by an arbitrary Java class.

Outside of that case, I'm going to invite downvotes by saying that it's irrelevant. Most of the recursive code that I've seen (and I've worked with a lot of graph projects) is not tail-call optimizable. Like the simple factorial, it uses recursion to build state, and the tail operation is combination.

For code that is tail-call optimizable, it's often straightforward to translate that code into an iterable form. For example, that sum() function that I showed earlier can be generalized as foldLeft(). If you look at the source, you'll see that it's actually implemented as an iterative operation. Jörg W Mittag had an example of a state machine implemented via function calls; there are lots of efficient (and maintainable) state machine implementations that do not rely on function calls being translated into jumps.

I'll finish with something completely different. If you Google your way from footnotes in the SICP, you might end up here. I personally find that a much more interesting place than having my compiler replace JSR by JUMP.