What is Mojo's approach to tail call optimization?

[Brian-M-J]

Python famously does not have tail call optimization as Guido van Rossum is against it. Since Mojo aims to be fully compatible with Python, what would its compiler do when it encountered an opportunity for this optimization? Would it check if the code is pure Python and then avoid performing TCO but perform it when it encounters Mojo-specific code? Would it provide a decorator like always_tail_optimize so the programmer could choose whether TCO is performed or not?

[lattner]

Yes, we will support tail call optimization and it will probably be enabled by default. If needed, we can add a decorator to disable it though.

[Brian-M-J]

Hmm, what about also adding a decorator similar to this Rust crate that guarantees tail call optimizations? It would certainly be nice if programmers had compiler feedback on whether their tail recursive functions were implemented correctly.

There's also the concepts of thunks, trampolines and continuation passing style, which I honestly do not understand at all. Maybe people who do understand them can decide on whether these are features that should be added to the standard library or not.

[Brian-M-J]

thunks, trampolines and continuation passing style, which I honestly do not understand at all

It's been about 8 months since I said that. I've learned a lot since then.

Cringing at myself suggesting thunks, trampolines and CPS be added as standard library features to a PL that already has first class functions aside, I have some more ideas for Mojo supporting tail call optimization.

Mojo already supports¹ tail recursion optimization (tail calls to the same function are replaced with jump instructions and reuse the stack frame), but it's not clear whether it supports tail call optimization (tail calls to any function are replaced with jump instructions and reuse the stack frame). These may not be exactly the right terms but they convey the difference I'm trying to get across.

Generalizing tail call optimization to any function means that patterns like Continuation Passing Style² and Finite State Machines³ can easily be expressed.

I'm also still convinced that it's better to syntactically guarantee the optimization so programmers don't have to second guess themselves (without this, an especially big footgun would be tail calls that implicitly use the return keyword i.e. tail calls to functions that return None). They also wouldn't have to write comments like:

# I'm relying on TCO here. If you are modifying this function, make sure it still performs TCO or the stack will blow up

This can be done in two ways:

• Add a compiler intrinsic similar to clang's musttail:
  This is something I'd rather avoid. Compiler intrinsics are completely foreign to Python and if we can avoid them, we should.
• Add a decorator to guarantee tail call optimizations:
  The decorator, when placed on a function, guarantees that all return statements (even implicit ones) are tail calls. If not, compilation fails. This decorator can be thought of as automatically annotating all explicit and implicit return statements with [[clang::musttail]]. This is more restrictive than the choice to annotate individual return statements, but it is better for programmers' sanity that all return statements are considered.
  Ideally, using this decorator should require no manual transformations of the function by the programmer. If you look at the Python trampoline package, it requires that return statements be replaced by yields. [[clang::musttail]] requires that the return keyword be used, even for calls to functions that return void. It's better to avoid making the programmer do extra work like this.⁴
  Adding a decorator also means leaving room for better support for TCO, like TCO modulo cons and TCO modulo context⁵. Analysis can be performed on functions decorated as such and programmers don't need to maintain explicit accumulators.

I also hope Mojo's support for TCO isn't as restrictive as musttail's:

The target function must have the same number of arguments as the caller. The types of the return value and all arguments must be similar according to C++ rules (differing only in cv qualifiers or array size), including the implicit “this” argument, if any. Any variables in scope, including all arguments to the function and the return value must be trivially destructible. The calling convention of the caller and callee must match, and they must not be variadic functions

Additional Reading:

1. WebAssembly tail calls
2. p2300 - std::execution:

because all the work is done within callbacks invoked on the completion of an earlier sender, recursively up to the original source of computation, the compiler is able to see a chain of work described using senders as a tree of tail calls, allowing for inlining and removal of most of the sender machinery. In fact, when work is not submitted to execution resources outside of the current thread of execution, compilers are capable of removing the senders abstraction entirely, while still allowing for composition of functions across different parts of a program.

3. WebAssembly proposal for tail call optimizations
4. The Story of Tail Call Optimizations in Rust
5. Reviving tail-call elimination (issue 2691 at https://github.com/rust-lang/rfcs)
6. Tail Call Optimization and Memory Management with Trait Objects and Vtables in Rust
7. It’s not always obvious when tail-call optimization is allowed
8. ES2015, ES2016, and beyond
9. C2 Wiki - Tail Call Optimization
10. Parsing Protobuf at 2+GB/s: How I Learned To Love Tail Calls in C

Footnotes

1. See the 'Tail Call Optimization (TCO)' section of this article. ↩

2. See here and here for examples of what TCO and CPS enable programmers to do. ↩

3. See here for an example of an FSM implemented using TCO. ↩

4. The Rust trampoline crate doesn't have this problem, but it is restricted to TRO only. ↩

5. If video's more your style, you can watch this ↩