15
$\begingroup$

Tail Call Optimization allows a function call as the returned value of a function to be optimized to a goto, preventing the stack from growing. Among other things, this allows infinite recursion without worrying about the call stack size. While TCO applies to any function call performed as the final action of a function, a subset of this is Tail Recursion Optimization, which applies only when the function returns a call to itself. This still allows recursion without worrying about the call stack, but not much else.

What are the trade-offs when supporting TRO, but not TCO? This could include implementation difficulties present with TCO but not TRO on one side, or useful applications of TCO that TRO can't handle on the other.

$\endgroup$

3 Answers 3

13
$\begingroup$

The major advantage of TRO is that it's (often much) easier to implement: a purely local analysis can inspect the final statement and convert the function body to a loop. In all other technical respects, general TCO is strictly better, only harder, though the performance envelope can be worse on some platforms.

Use cases

The most common use case that TRO misses is immediate mutual recursion. Two functions bouncing back and forth to one another is a common functional pattern that isn't detected by a pure tail recursion analysis. This is common enough that occasionally a mutual tail-recursion optimisation is implemented without going all the way to general TCO, though the same effect can be accomplished by inlining one of the functions and applying TRO to the result.

A major—perhaps the main—benefit of general tail-call optimisation is enabling code in continuation-passing style or similar approaches, where (very) long chains of unrelated functions calling each other are expected. Without TCO either manual or generated CPS code tends to fall over at even moderate complexity when it runs out of stack space. Solely optimising tail recursion is no help in this case, though the continuation-passing approach isn't something that every language will care about.

Implementation

While tail recursion can always reuse the function's existing activation record, full TCO has to handle the next function's being bigger or smaller, which can be complex on some platforms. The extra work may make tail calls more expensive than otherwise, so the benefits would only appear in the deep recursion cases that couldn't otherwise run at all. For a language that is interpreted on top of a higher-level language with reified stack frames this cost is likely to be negligible if extra allocations can be eliminated, while at the machine level it is liable to be comparatively expensive, and on virtual machines it may not be permitted at all. In the latter case the decision may have been made for you.

Often performance is not a particular goal of these languages, and the purpose is to enable the programming model, so small overheads can be acceptable in any case. The implementation difficulty otherwise is generally not so high above tail recursion, for functional languages at least.

Ergonomics

One of the significant ergonomic drawbacks of any tail-call optimisation is in error reporting that loses track of the call stack and cannot report how the program reached the point of failure. With only self-recursive tail calls, this is reduced somewhat, as the final frame can be marked as looping and the stack that reached the function in the first place stays intact. The typical mitigation in tail-call-optimised systems that want to address this is a ring buffer of recent function calls, which is unhelpful precisely in recursive cases.

Tail call optimisation that doesn't always work, for example if it excludes functions using certain features, can make for unexpected surprise failures. If it relies on the functions being in the same module then otherwise-simple refactorings become difficult for non-obvious reasons. This is likely to be more of an issue for the "clever" middle-ground solutions than either full TCO or TRO.


In a system that doesn't expect extremely long function call chains, full tail-call optimisation probably isn't worth the initial effort in terms of gained expressivity, but expectations can be wrong. In a Scheme, where programming in that style is the norm, it's essential.

$\endgroup$
2
  • 1
    $\begingroup$ The prime example for paragraph 1 is the JVM, where it is trivial to implement direct TRO using GOTO, but implementing TCO requires using trampolines, implementing your own call stack instead of using the JVM's, using exceptions as continuations, or something along those lines which means your implementation is either slow, does not seamlessly integrate with the rest of the Java ecosystem, or both. Since those two are often some the primary reasons for implementing a language on the Java platform, this means supporting TCO on the JVM is pragmatically impossible. $\endgroup$ Jul 5, 2023 at 12:08
  • $\begingroup$ Quoting Rich Hickey, the creator of Clojure: "Speed, Interop, Tail Calls – Pick Two" and "Clojure is a hosted language – the JVM is not an implementation detail". $\endgroup$ Jul 5, 2023 at 12:09
7
$\begingroup$

useful applications of TCO that TRO can't handle

Having Proper Tailcalls, i.e. TCO that is mandated by the language specification and implemented by all implementations (as in Scheme) allows to write code that could not otherwise be written in the same way.

Note that there three aspects to having Proper Tailcalls that are all important:

  • The language specification must define, precisely, what is and isn't a tail call.
  • The language specification must mandate that tail calls must be eliminated.
  • Language implementors must follow the specification.

Examples of where this fails are:

  • IBM's J9 JVM performs TCO in many cases. However, this is not guaranteed by the JVM specification, so no other JVM does it, and even with J9, there is no guarantee that code that gets TCO'd today still does so tomorrow.
  • The Common Language Infrastructure (CLI)'s Common Intermediate Language (CIL), aka .NET's MSIL, has support for explicitly annotating tail calls, but as far as I understand, this annotation is advisory only and merely suggests to the implementation that calls may be optimized.
  • ECMAScript mandates Proper Tailcalls, but almost no implementation actually implements TCO.

In all these three cases, it is not possible to write code that only works with Proper Tailcalls, since you can never be guaranteed that TCO will be performed.

So, what are examples of code that can only be written with Proper Tailcalls?

One example is a state machine. A popular C-style implementation of a state machine uses a state table and GOTO to jump to the next state. However, with PTC, it is possible to implement a state machine using procedures for the states and procedure calls for the state transition.

In other words, each state simply calls the next state. This obviously leads to long call chains, but since the state machine just moves forward, there is no need for a return (except for terminal states), and thus, all state transitions are tail calls.

$\endgroup$
1
  • $\begingroup$ An important advantage of having a distinct syntax for tail calls is that machine code which implements such a state machine using ordinary calls rather than tail calls may require many so many orders of magnitude more stack space than would be required with tail calls, that if a tail call can't be performed it would be better to reject the program than produce machine code that would be virtually guaranteed to bomb the stack. $\endgroup$
    – supercat
    Jul 17, 2023 at 17:10
4
$\begingroup$

If you implement TRO but not TCO then a programmer may have fewer options to refactor a complex tail-recursive function.

For example, they couldn't, without affecting stack usage, split code that includes the tail call out into a helper function to get two, smaller & simpler co-recursive functions.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .