Why does TCO require support from the VM?

Question

Some VMs, most notably the JVM, are said to not support TCO. As a result, language like Clojure require the user to use loop recur instead.

However, I can rewrite self-tail calls to use a loop. For example, here's a tail-call factorial:

def factorial(x, accum):
    if x == 1:
        return accum
    else:
        return factorial(x - 1, accum * x)

Here's a loop equivalent:

def factorial(x, accum):
    while True:
        if x == 1:
            return accum
        else:
            x = x - 1
            accum = accum * x

This could be done by a compiler (and I've written macros that do this). For mutual recursion, you could simply inline the function you're calling.

So, given that you can implement TCO without requiring anything of the VM, why don't languages (e.g. Clojure, Armed Bear Common Lisp) do this? What have I missed?

Answer 1

Inlining is not a solution to the general tail call elimination problem for a number of reasons. The list below is not meant to be exhaustive. It is, however, sorted -- it starts with an inconvenience and ends with a complete showstopper.

1. A function called in a tail position may be a large one, in which case inlining it may not be advisable from a performance standpoint.

2. Suppose there are multiple tail calls to g in f. Under the regular definition of inlining, you'd have to inline g at each call site, potentially making f huge. If instead you choose to goto the beginning of g and then jump back, then you need to remember where to jump to and all of a sudden you're maintaining your own call stack fragment (which will almost certainly exhibit poor performance when compared to the "real" call stack).

3. For mutually recursive functions f and g, you'd have to inline f in g and g in f. Clearly this is impossible under the usual definition of inlining. So, you're left with what's effectively a custom in-function calling convention (as in the goto-based approach to 2. above).

4. Real TCE works with arbitrary calls in tail position, including in higher-order contexts:

   (defn say-foo-then-call [f]
     (println "Foo!")
     (f))
   

   This can be used to great effect in certain scenarios and clearly cannot be emulated with inlining.

Answer 2

1. It can be surprising, and may make debugging harder, since you can't see the call stack.

2. It only works in very special cases, rather than the general cases that are handled when the VM supports TCO.

3. Programmers often don't write their code tail-recursively, unless the language gives them incentive to do so. E.g. recursive factorial is usually written with the recursion step as n * fact(n-1), which is not tail-recursive.