Tell HN: We are trying to get tail calls into the WebAssembly standard

I wish daily for that as well, but stay tuned: we _might_ have found a half-satisfactory solution for that ;-)

The fact that WebKit had some level of support for tail calls on the JS side is exactly the reason we choose it as the right platform to invest in.

The reason actual why it was withdrawn is that it would have required expensive changes to Microsoft’s Chakra (the calling conventions were incompatible).

Then Edge died... and Google didn’t add it back. Go figure.

Firefox also has problems implementing cross-realm tail calls. That could be spec’ed around, but there’s no will to do so.

Do you have any gotchas which isn't really mentioned on MS documentation site? primarily related to performance, since it will be one of my main concerns.

There are plenty of algorithms that make more sense when expressed using recursion. Iterating over a list of numbers generally isn't one of them. But walking a tree is a good example.

For posterity my original comment was:

“From what I understand, tail calls can always (?) be lowered to while loops[1], which are expressible in WASM.

1. https://en.wikipedia.org/wiki/Tail_call#Relation_to_the_whil...

The best they can do are trampolines, which come with a high performance cost.

The issue is that to avoid stack blow-up you need the engine to recycle stack frames. You might argue that this could happen implicitly in the VM, with all the calls in tail position being automatically converted to tail-calls. The problem with this is that in WebAssembly (and JavaScript) the call stack is observable via the .stack property of thrown exceptions.

Since an implicit conversion would be observable engines cannot simply optimize the problem away, and that is the reason why new opcodes (return_call/return_call_indirect) are actually required at the WASM level.

For the specific case of direct calls (return_call opcode) the compiler could solve the problem by inlining, with some luck. But for the case of return_call_indirect there is no other possible solution.

There are a bunch of reasons why WASM was designed to be higher level than native assembly. One is that they want it to be more compact to save bandwidth when downloading via the internet. Another is that they want to make it faster to compile down to native code; one way they do this is that the control flow is more structured, for example it forbids irreducible control flow graphs. There is also the matter of safety. WASM defines several validation constraints that are checked before the bytecode is run e.g.: the target of a jump instruction must be listed in labels list. If WASM were too low level, it wouldn't be possible to do the safety checks they want.

Because wasm only has structured control flow & no way for user code to modify the wasm stack, there isn't any good way to tail call between multiple independent functions, particularly dynamic function calls. Simple tail recursion of a function calling itself is simple enough and can be implemented in the compiler (and I did), but that's it, and not enough to correctly implement Scheme, for instance.

I also want the wasm standard to remain as simple as possible, but this isn't a very complex addition and it is required for reasonable performance for both functional languages as well as C++20 features like coroutines, as mentioned by the article.

A tail call is a jump. Jumps are not "high-level stuff". They're very simple instructions. If WASM can't do a jump, it is actually WASM that you can't call "a low level bytecode".

Are you referring to WASM GC here (or managed memory in general)?

If so, I think the main compelling reason is interop. Without GC in underlying architecture, any managed language targeting WASM must include its own runtime and GC. If you then want to write a polyglot program using multiple languages, you now have a single WASM executable containing multiple garbage collectors each managing their own objects. If you end up with cycles between those different managed heaps, you can end up in a situation where the GCs are unable to reclaim memory because they don't understand cross GC cycles.

This is why Chrome did Oilpan [1]: so that they could more easily handle cycles between the DOM, JS heap, and (aspirationally at the time) Dart VM heap.

A more general user-value proposition argument is that putting the GC in the WASM implementation means any improvements made to it are amortized across all managed languages that target WASM. Also, it makes applications written in managed languages and compiled to WASM smaller because they don't have to ship a runtime and GC with the app.

[1]: https://chromium.googlesource.com/v8/v8/+/main/include/cppgc...

I’m not a compiler guy, but spent my time with runtimes closely, and can say that befriending GCs/RCs, exceptions, continuations, etc between them was my least favorite part.

That said, wasm is already a potential target for different runtimes built with no common vm in mind, so interop headaches are imminent either way.

The result is a fairly high-level VM that doesn't export enough power for your program to implement GC or exceptions without sacrificing a lot of performance. Tail calls is a different matter, and there is a cost-benefit analysis for it.

It sounds like you're confused about how Wasm works, and you imagine that it's like a normal assembly language, with calls and returns implemented by the compiler using instructions that push and pop a stack in memory. You're probably right that that's how it should have been designed.

But that is not how Wasm works. The stack is not in Wasm's "linear memory". (This makes it much easier to compile access to local variables efficiently.) Calls, returns, and in a sense exceptions in Wasm are provided by the virtual machine at a fundamental level in a way that makes it impossible for a compiler targeting Wasm to implement tail calls, call/cc, or cooperative multithreading, except by compiling your entire program into a single function, which ruins the performance of existing Wasm implementations.

But, as Scheme has demonstrated, once the virtual machine supports tail calls, a compiler can implement exceptions and cooperative multithreading by way of compiling to continuation-passing style. So this is not the beginning of a long series of extensions; it's Lambda the Ultimate Goto.

There are some special cased scoped branches but if you read the spec you'll see they are so specific that you can't branch back to the head.

(ex compiler dev)

https://www.lua.org/source/5.4/lopcodes.h.html

For languages that rely heavily on tail calls (functional languages in particular), good performance can only be achieved by having tail calls (or general-purpose jump instructions) as part of the instruction set.

Excluding tail calls hurts performance for these languages as they have to resort to techniques like trampolines. As apignotti suggested, it's impossible for a compiler to generate efficient code for tail calls if the underlying instruction set does not support it.

  let sum list =
    let rec loop a = function
      | [] -> a
      | x::xs -> loop (a+x) xs
    in
    loop 0 list

  let rec even_then b n =
    if n = 0 then b else odd_then (not b) (n - 1)
  and odd_then b n =
    if n = 1 then b else even_then (not b) (n - 1)

  fn even_then_or_odd_then(which_function, b1, n1, b2, n2) {
    loop {
      match(which_function) {
        Even => {
          if n1 = 0 { return b1 }
          else {
            b2 = not(b1);
            n2 = n1 - 1;
            which_function = Odd;
          }
        },
        Odd => { similar }
      }
    }
  }
  
  fn even_then(b,n) {
    even_then_or_odd_then(Even, b, n, null, null)
  }
  
  ...

  let parse_both p1 p2 =
    fun buf pos success ->
      p1 buf pos (fun pos r ->
        p2 buf pos (fun pos r2 ->
          success pos (r, r2)))
  ;;

[1] A trampoline means that functions effectively return continuations except typically they call their continuations (up to some max number of times) and only occasionally return them to the trampoline (which pops everything off the stack) which immediately calls the continuation again. But implementing continuation passing style this way is pretty slow.

The second could easily optimize tail calls but it is required not to do so to increase reliability (all implementations need to agree which calls are tail calls that should be optimized and the simplest way to agree is to never do it) as otherwise a Wasm modules could work fine on an implementation and be unusable in another.

The first compiler cannot, the only possibility is to use whole-program transformations that significantly degrade performances.

In LLVM C++ coroutines compile down to functions with the "musttail" attribute, that right now is not possible to express in Wasm [1].

It is also useful to efficiently implement stuff like interpreters, where you use it as a way to jump to the code of the next instruction directly (Wasm has only structured control flow, but you can see a tail call as a sort of jump/goto instruction)

[1]: https://discourse.llvm.org/t/supporting-coroutines-without-t...

DOM manipulation hasn't changed - you still need to call into JS to do those. Ideas like WebIDL bindings have been proposed over the years but haven't shown enough benefit. JS is better for DOM-heavy code, while wasm excels at computation-heavy code. But you can write bindings from wasm (maybe someone already has for OCaml?), which is what toolchains do today - not as fast as JS, but often good enough.

As for DOM manipulation, that seems to work well enough but I'm sure there are further improvements coming.

  void foo(...) {
    ...
    bar(x,y,z); // <= a tail call
  }

  int foo(...) {
    ...
    return bar(x,y,z); // <= still a tail call
  }

With tail calls, that additional stack frame has no real value (outside, maybe, debugging information to give you a stack trace but traces can be collected other ways). Tail call elimination (or tail call optimization) will reuse the current stack frame rather than construct a new one. This reduces the memory overhead (you aren't constructing unnecessary stack frames) and gives some performance improvement (less bookkeeping overhead, and the function call becomes a simple jump). These two functions can, in principle, get compiled to the same thing if you have TCE:

  uint factorial(uint n) {
    uint acc = 1;
    for(; n > 0; n--) {
      acc *= n;
    }
    return acc;
  }
  uint factorial(uint n, uint acc = 1) {
    if (n == 0) return acc;
    return factorial(n - 1, acc * n);
  }

The compiler is able to optimize the function calls in the return statement. Note how the calls are compiled into a jmp instruction, instead of a call instruction. This means that it doesn't need a new stack frame for each call. Even if the "x" is very big, it won't blow the stack.

The most basic application of tail call optimization is when you optimize a recursive function. It essentially turns the recursion into a loop. In fact, is how you write loops in certain functional languages. But TCO is not jut for that. It can also be used when one function calls a different function, like in the first example I linked. In this case the gotos can model any state machine, not just a self loop.

https://www.usenix.org/system/files/atc19-jangda.pdf

(I assume that's what you refer to?) It's a good measurement, but it's from 2019, and it's just on 2 wasm engines. There are other estimates, like here:

https://kripken.github.io/blog/wasm/2020/07/27/wasmboxc.html

That tries to measure the fundamental overhead of wasm's sandboxing as opposed to a specific wasm VM, and it finds just 14%.

Naysayer (downvoters) seems sure that JavaScript engine having this new tailcall would not be impacted. Of course, I would be talking about the generated microcode, not the JavaScript LIR bytecode.

https://arstechnica.com/information-technology/2022/07/intel...

Unlike regular machine language, WASM does not allow you to control the call semantics. That is, if you emit x86 machine instructions you can handle TCE entirely in your own compiler, the machine itself does not care.

WASM has special call instructions, these perform basically a conventional stack frame/call stack approach and you can't short circuit it. The closest you can get, which works fine for auto-recursive functions and maybe some detectable mutually recursive functions, is to convert tail calls into loops within the compiled WASM output. So recursive tail calls work fine in WASM if your compiler doesn't turn them into calls, but leaves them as a self-implemented (by the compiler) loop structure using whatever appropriate WASM instructions are available. This is fine for auto-recursive functions, but puts the burden at implementing TCE for them on the compiler writer. Which means you'll get it for some languages that compile to WASM, but not all. And only for the limited cases they support (probably restricted to auto-recursive and some mutual recursive circumstances).

What this proposal introduces is a new version of the call instruction that would be used in tail call positions. Then the WASM interpreters would do the work of actually combining the stack frames internally. Detecting that a call is a tail call is actually pretty straightforward for a compiler. Given that it is a tail call, it can emit (or not) the new call instruction and will get TCE "for free". It doesn't have to do a code transformation from recursive to looping, and it can be applied more broadly than just recursive circumstances.

Unfortunately self recursion is only a subset of tail calling.

We don’t have it elsewhere mostly because Google:

1. Agreed to implement it [it’s in ES6]

2. Implemented and shipped it behind a flag

3. Unshipped it.

4. Proposed something else [ https://github.com/tc39/proposal-ptc-syntax ]

Prior to that, Firefox had proposed a carve out for cross-realm calls, but then they didn’t bother implementing anything.

While apple is against Syntactic tail calls, they’re mainly just opposed to versions of it that would remove/unrequire the tail-call optimisation they already do: https://github.com/tc39/ecma262/issues/535

For the version of it that is backwards compatible, they wouldn’t need to do anything other than ignore the syntax. Their main concern is that it "could add confusion with very little benefit."

In Virgil I implemented this for both the JVM and Wasm. Here's the algorithm used for Wasm:

https://github.com/titzer/virgil/blob/master/aeneas/src/mach...

Since WebAssembly has a concept of functions, and doesn't allow jumps outside of the current function for security reasons, a compiler can't eliminate tail calls across functions (unless it can in-line all of those function calls, which isn't always possible, nor it is always the best performance).