Tail calls in Schism

[eholk]

I have a branch of Schism (a self-hosting Scheme-to-Wasm compiler) that makes use of the new return_call and return_call_indirect instructions: https://github.com/eholk/schism/tree/tail-call-instr

I thought I'd give some feedback on the proposal from the standpoint of a language implementation.

Adding tail call support to Schism

Adding the new opcodes was a pretty straightforward affair. I chose to do it by implementing a new pass, replace-tail-calls, that finds all calls in tail position with tail call instructions instead. The rest of the work was just forwarding those changes through the compiler until the encoding step where it outputs the right opcodes.

The result validates in the spec interpreter, but I don't have a VM to run the output in yet. As time allows, I hope to modify the spec interpreter to implement Schism's runtime so that will be an option for running the output.

Schism's requirements from the tail call proposal

Scheme requires that an unbounded sequence of calls in tail position use a constant amount of stack space. All of Scheme's iteration facilities are expressed in terms of tail recursion (although some compilers recognize special cases and generate more traditional loops instead). Whereas in C and C++, tail recursion is an optimization the compiler may do, in Scheme tail recursion is not an optimization and is required for correctness.

So what does Scheme need from Wasm? Technically nothing. It's possible to generate a giant function with a big loop and a switch. It sounds like this is more or less what Go is doing. While this technically works, it's less than ideal. For example, it makes linking several Schism-compiled modules together impossible.

If Wasm has tail call instructions, Schism will happily use them. The most important thing for these instructions is that they are an honest-to-goodness tail call. For example, LLVM has the tail and musttail annotation, where the tail annotation can be ignored. Schism needs the semantics of musttail or else the instructions will be useless. Fortunately, this is the direction we're going with the proposal.

The ideal case for Schism is that Wasm supports tail calls from any Wasm function to any Wasm function, including to imported functions that were exported from Wasm. This will make for the easiest implementation and give the most flexibility. As far as Wasm-to-JS calls, I think it is fine if these cannot be done as tail calls.

As far as whether may-tail-call or may-be-tail-called should be tracked in the type system, this doesn't particularly matter for Schism. All functions in Scheme need to be able to make tail calls and be tail called, so if extra type annotations are required, Schism will just use them unconditionally.

There was a suggestion of making the tail call annotation a per-module setting. In my mind, I would think of this as a section that provides requirements on the calling convention, similar to how LLVM supports different calling conventions. Basically, the new calling convention section would have the option to say "this module requires a calling convention that supports proper tail call handling." If we do this route, I think it's important to be a specced section, rather than a custom section like most of the hint section proposals have been. The reason is that custom sections are allowed to be completely ignored or even dropped (for example, you could imagine a CDN that drops custom sections on the fly to save bandwidth), whereas Schism needs to be able to rely on tail calls being tail calls.

Another suggestion was to only support tail calls with the caller and callee signature are the same (so-called natural tail calls, although from my perspective this is an unnatural restriction on tail calls). This is actually more workable for Schism than I thought at first. While I haven't settled on a design yet, there's a reasonable chance that all functions in Schism will have the same signature, due to the way Scheme does varargs. Still, even if all functions have the same signature, these would probably be done as a wrapper function with the standard signature that calls the real function with a more precise signature. Schism would then be able to directly call the precise function in a lot of cases. This optimization would not be possible if tail calls can only go from the same signature to the same signature. Basically, Schism could work with this restriction, but it would significantly limit what it's able to do.

Anyway, I'm excited to see Wasm get support for tail calls. Hopefully this perspective from at least one language implementation is helpful.

[bitwalker]

I just wanted to chime in here with a link to a comment I posted in another thread about continuations which can be found here. It has a lot of overlap with this.

In short, I'm working on an implementation of a compiler for Erlang, which leans heavily on continuations, implemented using a CPS-converted representation, so all calls are tail calls, and no function ever returns. Furthermore, the technique I'm using, Cheney on the MTA, handles the lack of tail calls in general by using setjmp/longjmp to reset the stack when it is about to overflow (which can coincide with garbage collection, but not always and not necessarily). In WebAssembly, this approach comes with a steep performance penalty, due to the need to use JS exceptions for the implementation of setjmp.

This is not a technique unique to my compiler either: two very popular Scheme implementations use it as well, or some variant of it; Chicken Scheme and Chez; and I believe there are quite a few others that are less well-known that do as well. More importantly, a wide variety of functional languages could be implemented this way, as continuations provide an elegant foundation upon which to build exceptions/non-local returns, green threading, coroutines, backtracking (for the implementation of logic programming, e.g. Prolog), and more. Continuations depend heavily on optimized tail calls.

My compiler is using LLVM, and on other platforms, I generally can't rely on, say, the fastcc calling convention and musttail annotations to ensure that all functions are performed as tail calls, primarily because that requires that all function prototypes are the same, which is an onerous restriction. This is the main reason why I'm using the Cheney on the MTA technique, as it relaxes this restriction entirely, at the cost of an occasional jump and checking the stack pointer at the beginning of each function. One alternative is to use trampolines, but those come at a steep cost as well.

From the perspective of a language implementer, even if WebAssembly gains something akin to LLVMs musttail or fastcc calling convention, that won't necessarily be a solution for all language implementations. The bottom line is that I think WebAssembly should have tools to implement continuations efficiently, of which tail calls are an important part of course, but even without explicit support for tail calls, something along the lines of setjmp/longjmp (implemented efficiently) or the resumable exceptions/effect handlers work could allow one to implement them anyway.

[rossberg]

IIUC, there is nothing actionable left for the proposal. Please reopen concrete issues otherwise.