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?

Genoa

Note that TCO is not specifically about self recursive calls. That's only a special case. – Clark

True. But either you're calling the same function (which you can write as a loop), or you're calling another function (which you can inline). I believe those two techniques together are a general solution. – Genoa

Inlining is no solution. – Clark

Can one simply inline a function call in Clojure? The cases I've seen attach a (hopefully corresponding) macro as metadata to the defn. – Slosh

You're talking about the most trivial form of a tail recursion. Now consider tail-calling a virtual method. You don't necessarily know which function you're calling. – Subservient

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.

Sibylsibylla

Brilliant answer, lots of points I hadn't considered. Thank you :) – Genoa

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.

Overspend

What cases aren't covered with rewriting as a loop and inlining? Could you give an example? – Genoa

Well, you wouldn't generally want all function calls inlined. – Overspend

Answer 3

TCO per se doesn't require VM support. That is to say, not for local functions. Tail calls spanning external functions require VM support. Ideally, a complete implementation of tail recursion allows functions in separately compiled program units to mutually recurse in constant space, not only functions that are local to one parent function, or functions that are all visible to the compiler at once.

In a VM without tail call support, function calls are encapsulated, and allocate a new frame on exit. Tail calls require a special entry point which bypasses that. Functions can participate in tail calling as well as non-tail calling, so they require both entry points.

Tail call elimination can be simulated without VM support using non-local returns and dispatch. That is to say, when a tail call takes place syntactically, it is translated to a non-local return which abandons the current function via dynamic control transfer, passing the arguments (packaged as an object, perhaps) to a hidden dispatch loop, which transfers control to the target function, passing it those arguments. This will achieve the requirement that recursion takes place in constant space and will "look and feel" like tail calling. However, it is slow, and perhaps not entirely transparent.

Wield