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

https://news.ycombinator.com/item?id=32069418

by apignotti • 4 years ago

625 290 4 years ago

news.ycombinator.com

WebAssembly is a modern bytecode supported by all browsers and designed to be a compiler target for a wide variety of programming languages.

To effectively support some forms of Functional Programming support for tail-calls has been proposed as an extension to the WebAssembly standard.

This proposal has reached Phase3 of the standardization process years ago, but has since stalled.

Phase3 is known as "the implementation phase" and the prerequisite for advancing the proposal to Phase4 is to have support in two different browser engines. V8/Chrome support has been available for a long time, so another engine is required.

To unblock this situation we have contributed full support for WebAssembly Tail Calls to JavaScript/WebKit/Safari. The PR is available here:

https://github.com/WebKit/WebKit/pull/2065

An in-depth article about the challenges of implementing this feature is also available. This is intended both as documentation for our contribution, but also as a general explainer about how tails calls actually work, with a particular focus on stack space management.

https://leaningtech.com/fantastic-tail-calls-and-how-to-impl...

convolvatron6• 4 years ago

I'm working on a relational stream processor and this is pretty critical to making it work well. a runtime standard with support for network connections would be nice too, but lets not get greedy

apignotti4• 4 years ago

support for network connections

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

convolvatron6• 4 years ago

pointer to a draft?

andsoitis• 4 years ago

tail-calls has been proposed as an extension to the WebAssembly standard.

Do you know why it wasn't in the standard to begin with?

Even ECMAScript 6 mandates PTC (proper tail call) - article from 2016 on Webkit.org no less - https://webkit.org/blog/6240/ecmascript-6-proper-tail-calls-...

apignotti4• 4 years ago

I am unsure, but I can make a guess. The first release of Wasm has been always considered a Minimum Viable Product, which a strong emphasis on Minimum. Pretty much only features already part of the legacy asm.js "standard" made the cut.

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.

pygy_4• 4 years ago

The standard mandates it, and the V8 team implemented it, shipped it behind a flag, then unshipped based on reasons that initially seemed and ultimately were proven fuddy, when WebKit shipped PTC, and the world didn’t fall down.

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.

silon42• 4 years ago

If I understand what cross-realm means (code security), then I'm not sure that can be done at all.

leoc2• 4 years ago

These absolute bozos. A Web Assembler that can't do jumps. What a show.

miclill• 4 years ago

Thanks for clarifying. What is this PTC you mention?

brrrrrm2• 4 years ago

How is ECMAScript 6 (high level language) related to WebAssembly (low level target)?

afiori2• 4 years ago

Wasm is meant to run efficiently on the same VM as JavaScript (an ECMAScript implemention), so Wasm features are restricted by browser VM current architectures.

(It is probably the main reason why Wasm only has structured control flow)

labrador12• 4 years ago

I'm using Blazor (C#) WebAssembly and I'm really wishing it could do DOM manipulation. My favorite tool for that is Dart, so I'm working on marrying C# and Dart for my client solutions.

traviswt2• 4 years ago

Genuine question: is the goal to get something that is not achievable with JS/TS, or is the goal to simply avoid JS/TS?

labrador12• 4 years ago

I really dislike JavaScript for a number of reasons. Dart gives me more distance from it than TypeScript. Of course, I can't avoid it, but I don't have to deal with many annoyances such as which 'this' is this? Should I put 'this' into a var called 'self' to be safe? That's just one example of how JavaScript and I don't get along. I understand some people have brains that think this way, but mine doesn't

vbezhenar2• 4 years ago

What's wrong with JS bindings? Surely DOM manipulation is slow enough for WASM/JS overhead not being noticeable.

labrador12• 4 years ago

You still need to go through a port with Blazor, but you can minimize those calls for the most part. DOM manipulation was slow as recently as a few years ago, but improvements to Blink have made it blazingly fast. I agree with Svelte that we no longer need a virtual DOM

https://svelte.dev/blog/virtual-dom-is-pure-overhead

Edit: I didn't answer your question. There's nothing wrong with JS bindings. Both Blazor and Dart use them, which could get awkward going from Blazor -> Dart (as JS) -> JavaScript lib. I'm considering TypeScript again because no port is needed to call JS libs.

asabla• 4 years ago

For someone about to go knees deep into Blazor very soon.

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.

worble• 4 years ago

If one of your main concerns is performance, then all I can say is don't use Blazor. WASM will never be able to compete with regular JS so long as it has to go through an interop layer, plus it has to send down and parse an entire interpreter before it can even start looking at your actual UI and business logic. Server Side has to wait for a server response for every single action you take, and any small drops can make the entire thing sluggish, or even buggy.

That's not to say it isn't cool and can't work for some projects where say, development speed is more important, but performant it just aint.

labrador12• 4 years ago

If you're talking site load time you'd have to be careful because netdot is compiled as wasm, which doesn't leave a lot of room below the standard site size. It's hard to tell because even ordinary sites now are huge. I need to do some testing.

lmm5• 4 years ago

What's C# giving you that Dart isn't, OOI? My impression is they're fairly similar languages. (Does Dart not have a WebAssembly backend?)

labrador12• 4 years ago

Blazor is using C# to build web pages, which isn't new, but using C# on the client with a webassembly version of .NET. It works well enough, but is limited to simple things like onClick="SomeCSharpFunction" and can not do things like getting elements by id or class. That's were Dart shines. Most will use either JavaScript or TypeScript, but I like Dart so I want to see how it is to combine Blazor Webassembly with Dart.

It would be even more interesting if there were a Dart.NET

kbelder• 4 years ago

I was struck by how reactionary some of the responses to this comment are. Many people seemed to feel obliged to firmly question your preferences. Kind of odd, I don't normally notice that as much here on HN.

labrador12• 4 years ago

I expected it because over the years any Dart or Microsoft positive statements I've made have received pushback. Some people can't let go what Microsoft did 20 years ago and assume they are still evil (with GitHub Copilot for example.) Others who are JavaScript programmers can't let go that a Google exec said at the outset that Dart was meant to replace JavaScript. They have fought it over the years.

I almost felt like I was trolling by combining the two, but I'm actually using Dart and Blazor to see how they can work together because Blazor Wasm doesn't do DOM manipulation and Dart does it in such a easy to use fashion that the marriage feels natural to me.

I try not to attack back and have a bit of a sense of humor about it, but it does feel like suppression of thought on HN

traviswt2• 4 years ago

Well personally I wasn't questioning the preference itself, I was curious about the purpose of the preference since I've seen people avoid JS/TS both because they don't like it and because it struggles to accomplish certain things. I was simply curious which it was (if either).

codedokode• 4 years ago

Recursion indeed can be useful when working with trees or graphs. However, I don't like using recursion instead of a loop, because you make reader to unroll your code in their head to understand what it really does. If you need to add two arrays of numbers, use loop or array addition, but don't use recursion as a replacement for a loop.

Sadly the article uses a poor example, writing a useless factorial function. I have never needed such a function in production code, and if I needed, I would write it using a loop. Using bad examples like this might create an impression that recursion is not useful in real code (which is wrong). It would be better if you have used an example that looks like real code and that would become less readable without recursion.

RHSeeger• 4 years ago

If you need to add two arrays of numbers, use loop or array addition

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.

kmeisthax• 4 years ago

More specifically: if you don't want to recursively iterate a tree, you have to hold a list of prior nodes to return to anyway... which is no different from weaving that information into the stack. Non-recursive iteration in this case literally requires you to emulate the recursion.

vbezhenar2• 4 years ago

Those algorithms usually use non-tail recursion. Most tail recursion uses usually is trivial to rewrite in a loops.

jagger27• 4 years ago

Readability is really not a relevant factor for WebAssembly. Having tail-call recursion support is critical for the languages that compile to Wasm that use tail-calls themselves.

j-pb3• 4 years ago

Sorry if I miss something obvious, but how is this not solvable by the compiler?

I'm a huge functional programming evangelist, but high-level stuff like this does not belong in a low level language bytecode like WASM.

Wasm should only care about two things: Security and Performance.

With the standard blowing up like crazy we'll get neither. Worse, we'll cemenent the current duopoly of browser engines, because we'll make it (again) so complex that no-one can create an alternative.

We shouldn't have GC, Exceptions or Tail calls in WASM, as long as the compiler can provide them.

What we should have is multi memory support and memory read permissions, because without them WASM lacks basic security primitives.[1]

Reference types maybe. But I've yet to see a convincing argument as to why they are absolutely necessary.

Everything else (as long as it can be done by the compiler) is just bloat.

1. https://www.usenix.org/conference/usenixsecurity20/presentat...

brrrrrm2• 4 years ago

Edit: this is wrong.

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...

mibsl2• 4 years ago

Only tail recursion, not tail calls in general.

apignotti4• 4 years ago

This is possible, and trivial, when self-recursing: A -> A

If you have an A -> B, or A -> [indirect] call, that is not the case.

mibsl2• 4 years ago

Compilers can easily lower tail recursion into loops, but not general tail calls between arbitrary (possibly unknown, indirect) functions.

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

apignotti4• 4 years ago

Tail-calls is fundamentally something that the compiler _cannot_ solve. Trust me, if there was a way we would have avoided ourselves all this work.

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.

j-pb3• 4 years ago

Fair enough. Sounds more like an issue with .stack being an observable property though.

I've long suspected exceptions making it into WASM being it's million dollar mistake, and this further confirms it.

nynx• 4 years ago

.stack definitely seems like a mistake in the context of Webassembly. I’d be interested in seeing the justification for it.

nu11ptr3• 4 years ago

Tail-calls is fundamentally something that the compiler _cannot_ solve

Possibly a stupid question as I haven't given this much thought, but I thought tail call elimination could be used to convert recursive calls in tail position into loops. Could a compiler not do this (like Scala does, for example)?

keithwinstein• 4 years ago

Heya,

(1) Thank you for implementing this in JSC!! I hope they take it, it makes it into Safari, and the tail-call proposal advances.

(2) I don't think you are exactly right about the call stack being observable via thrown exceptions. There's no formal spec for the v3 exceptions proposal yet, but in the documents and tests, there's nothing that would change in WebAssembly core to make the call stack observable. (There's no ".stack property" that would be added to Wasm itself.) It's true that the proposal amends the JS API (but only the JS API) to describe a traceStack=true option; from Wasm's perspective I understand that's just an ordinary exception that happens to include an externref value (just like any other value) to which Wasm attaches no special significance. The Web-based engines can attach an informative stack trace if they want, but there's no requirement preventing frames from having been optimized out. The non-Web engines won't have to think about this.

(3) I think the real reason that a Wasm engine can't implicitly make tail calls proper is that the spec tests forbid it, basically because they didn't want the implementation base to fragment by having some engines perform an optimization that changes the space complexity of a program, which some programs would have started to depend on. (The spec tests say: "Implementations are required to have every call consume some abstract resource towards exhausting some abstract finite limit, such that infinitely recursive test cases reliably trap in finite time. This is because otherwise applications could come to depend on it on those implementations and be incompatible with implementations that don't do it (or don't do it under the same circumstances.)")

But the issue is much weaker than "call stack is observable" -- it's more like "infinite recursion must trap eventually, but it can be nondeterministic when."

More discussion here: https://github.com/WebAssembly/spec/issues/150

OskarS2• 4 years ago

I don't quite get your point here. Suppose I write a compiler to compile Scheme to WASM. I would have write it so that it does proper tail calls, otherwise it wouldn't be Scheme. What's stopping me? Would the browsers not run the code? Like, yeah, it would change .stack, but who cares?

Same thing applies, I think, to any other language compiled to WASM. C/C++ compilers regularly inline huge amounts of the code when optimizations are turned on, as well as do tail-call optimization. I haven't tried, but I would assume that they do that for WASM just as they do for x86 or ARM or whatever other build target I choose. As long as my users are ok with this (and they presumably are, otherwise they wouldn't turn optimizations), what's the problem, exactly?

anfilt2• 4 years ago

What? Compilers handle tail calls all the time even in languages like C and higher level functional languages.

Its just a jmp? Does the wasm VM not have a jmp instruction?!?

jjtheblunt3• 4 years ago

Tail-calls is fundamentally something the the compiler _cannot_ solve.

How does the famous 1977 Guy Steele paper on compilers optimizing tail calls not apply?

https://dl.acm.org/doi/10.1145/800179.810196

JohnHaugeland• 4 years ago

Tail-calls is fundamentally something that the compiler _cannot_ solve.

I don't see why. Compilers are how tail calls are literally always implemented. It's not like there's hardware support.

What makes this impossible?

The issue is that to avoid stack blow-up you need the engine to recycle stack frames.

I mean, what's stopping you from just implementing a trampoline?

The problem with this is that in WebAssembly (and JavaScript) the call stack is observable via the .stack property of thrown exceptions.

Okay? This seems fine to me. What makes this a problem?

aaron_m04• 4 years ago

Is this the reason clojure added the recur form? IIRC, the JVM doesn't support tail calls because Java doesn't need it.

https://clojuredocs.org/clojure.core/recur

skrebbel• 4 years ago

Wouldn't it be much more productive to do a campaign to get `.stack` out of WASM?

randomswede• 4 years ago

There are probably WebAssembly-specific things I am unaware of. So, the following is a general "TCO" discussion.

I normally consider TCO something that is a compiler feature. Replace a call to the head of yourself, with a jump (possibly to just after the "pull the arguments from the call stack to where the code wants it" prologue), making sure that the correct locals are present where they need to be.

Well, that's for self-TCO. General TCO is definitely trickier (probably requires juggling stack allocations so as to ensure that the tail-called function has enough space for all that it needs).

WastingMyTime89• 4 years ago

Tail-calls is fundamentally something that the compiler _cannot_ solve. Trust me, if there was a way we would have avoided ourselves all this work.

I have been out of the loop regarding compilers development for a long time but what prevents you from converting your program to CPS and using a trampoline like some LISP still do?

ufo2• 4 years ago

Wasm is too high level to implement your own tail calls. The WASM virtual machine handles the call stack & function calling convention, instead of being something that the code itself is responsible for. This means that the compiler can't implement tail calls; WASM doesn't allow a jump instruction in one function to jump into a different function.

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.

MikeHolman• 4 years ago

The compiler absolutely can implement tail calls, I don't know why this keeps getting thrown around. Adding a high-level directive in the spec doesn't enable the compiler to do anything, it just enforces it. The only thing preventing it is browser vendors wanting the .stack property to stay well behaved, but that isn't required by the spec and certainly isn't relevant for non-browser targets.

miloignis8• 4 years ago

Throwing in my 2 cents to agree with apignotti - as someone who has implemented a compiler for a functional language that emits wasm, it is not possible to solve this performantly in the compiler.

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.

emmelaich2• 4 years ago

Can you please clarify? apignotti wrote

Tail-calls is fundamentally something that the compiler _cannot_ solve.

You write

it is not possible to solve this performantly in the compiler

So is it fundamental or not? Apologies if the question seems direct or rude.

jhgb7• 4 years ago

I'm a huge functional programming evangelist, but high-level stuff like this does not belong in a low level language bytecode like WASM.

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".

Spivak2• 4 years ago

WASM doesn't have jumps [1]. And it's not as low-level as you might expect. But even still you're assuming that low level means a specific model of computation a la PDP-11 that's as fictional as any other.

https://webassembly.github.io/spec/core/syntax/instructions....

ilaksh• 4 years ago

I don't think web assembly is low level at all. Actually the name is confusing because it's really not much like an assembly language.

kamaal2• 4 years ago

I think its Rich Hickey who said something to the effect that tail calls are so fundamental that the underlying platform should be providing them.

convolvatron6• 4 years ago

tail calls are so fundamental that its trivial to build a call-push, return-pop stack calling protocol on top of them, but not the converse

dan-robertson4• 4 years ago

And yet Clojure doesn’t have general tail calls (it has recur which allows something like tail calls so long as they are non-mutually recursive) and seems to do ok.

munificent3• 4 years ago

Reference types maybe. But I've yet to see a convincing argument as to why they are absolutely necessary.

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...

smolder2• 4 years ago

I'm likely in the minority in my thinking, but I don't think targeting wasm with managed languages is such a great use case for wasm anyway, and so it wasn't worth building in GC to support. For the times you want to, something light like reference counting should be easy enough.

wruza2• 4 years ago

We shouldn't have GC, Exceptions or Tail calls in WASM, as long as the compiler can provide them.

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.

marcosdumay4• 4 years ago

The problem here is that for security, your interpreted code can not do whatever it wishes on your memory. And for performances, you can't validate every small memory operation your code does.

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.

kragen8• 4 years ago

Your concern with burgeoning standards reinforcing the browser duopoly is well-founded, but unfortunately you're sticking your stake in on the wrong side of the dragon here.

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.

light_hue_15• 4 years ago

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.

Well to an extent. CPS can be extremely slow.

Scheme shows that continuations will also be needed down the road. But yes, that's about it.

dan-robertson4• 4 years ago

The purpose of the wasm rules (eg declaring variables/function args instead of having push/pop operations) is to allow the compiler to efficiently determine that functions follow the calling convention and won’t be able to mess with non-wasm functions they call or are called by. It means that you can put return pointers on the stack without the wasm being able to ever touch return pointers.

gumby• 4 years ago

Webassembly doesn't have a 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)

usrn• 4 years ago

WebAssembly is actually very high level. You need tail call support if you want to preserve the original structure of the program (which seems to be the intention.) I think you can get around it with eg CPS but then you'd get something more like traditional assembly.

LAC-Tech• 4 years ago

Not a compiler expert, but don't a lot of VMs for languages with TCO have a special tail call instruction? I know Luas VM does.

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

peterkelly• 4 years ago

Wasm should only care about two things: Security and Performance

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.

dan-robertson4• 4 years ago

An example of a tail-call that can easily be compiled to a loop is:

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

An example of a more tricky case which may be compiled to a loop is the following mutual recursion:

  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)

And this may be compiled either to a loop which uses a trampoline (or switch on the next function to run, which is a bit like a static trampoline) or to two separate functions that duplicate some code and are implemented as loops. A simple way this might get compiled is:

  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)
  }
  
  ...

An example of a tail-call that is hard to compile would be in a parser combinator library for example:

  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)))
  ;;

(As I’ve written it this design has some issues but they aren’t so relevant). Here it is important to be able to tail-call a function that you take as an argument (e.g. you want the parser p2 to tail call the success callback you give it, and if you parse and arbitrary-length list you want to do it tail-recursively). Speaking more generally, general tail-calls are like a safe long-distance goto. Wasm doesn’t have goto and so a whole-program transformation (or a trampoline[1] which may have performance issues) is required to support tail-calls.

[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.

jb1991• 4 years ago

One need only look at the Clojure language to see how tail calls are not solved by a compiler.

afiori2• 4 years ago

There are two compilers involved, Source to Wasm and Wasm to native (usually JIT).

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.

jacobmischka3• 4 years ago

Neat! This proposal caused me a lot of headaches, mechanizing its specification was the primary contribution of my Master's thesis a couple years ago[1]. I forgot until rereading it just now, but doing so caught a typo in the proposal specification[2], my extremely minor contribution to advancing WebAssembly.

Glad to see it finally moving forward after stalling for so long! Excellent work!

[1] https://github.com/jacobmischka/uwm-masters-thesis/releases/... [2]: https://github.com/WebAssembly/tail-call/issues/10

diarrhea2• 4 years ago

That might be the shortest (in word count) Master's thesis I have ever seen!

jacobmischka3• 4 years ago

Ha well the mechanization was a nontrivial amount of work (for me at least) and was considered part of it too. If it's still short despite that, then welp I guess I got lucky somehow.

IshKebab2• 4 years ago

Looks typical for a master's thesis to me. Maybe you're thinking of a PhD thesis?

anitil• 4 years ago

Claude Shannon's masters thesis was quite short as well [0], around 25 pages!

[0] https://www.cs.virginia.edu/~evans/greatworks/shannon38.pdf

miloignis8• 4 years ago

This is wonderful news! Thank you so much for doing this, and doing it right - this is much better than my idea of making a bad MVP web browser to provide second implementations to push through proposals when other vendors drag their feet.

As an author of a functional compiler that targets wasm, this is a dream come true - yall do really cool work.

2022062412032• 4 years ago

Why not focus on features that would unlock better integration of actual mainstream languages - Java, C#, Python etc.?

Let functional programmers discuss monoids on their endofunctor forums or something.

yuri91• 4 years ago

Actually even C++ can benefit from this.

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...

azakai3• 4 years ago

It isn't one or the other. Work on Wasm GC is ongoing and separate from this.

Jtsummers6• 4 years ago

Recursion has been a part of programming and programming languages for a very long time, and not just the functional ones. See ALGOL for recursion from very early on.

Zamicol• 4 years ago

I'm waiting for constant time WASM. https://github.com/WebAssembly/constant-time/blob/main/propo...

jolux2• 4 years ago

Tangential but what's the status of garbage collection and DOM manipulation in WASM? Are we ever getting those? I understand it's a high-value technology without them, but I'm interested in writing full apps in say, OCaml (so I'm glad to hear that WASM is getting TCE!).

Kaze404• 4 years ago

Have you looked into ReasonML by any chance?

k__• 4 years ago

I lost track of it since the Reason/ReScript split.

azakai3• 4 years ago

GC is making a lot of progress. There are VM and toolchain prototypes. You can compile Java and Dart to wasm on those today and it generally works and is pretty fast. (There is also a Kotlin prototype but I have less information about it.) Most of the big spec questions have also been resolved.

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.

marcosdumay4• 4 years ago

JS is better for DOM-heavy code

If you only look at performance, yeah. Performance isn't the only thing we get from WASM, and it would be nice to get the other benefits without having to sacrifice it.

(That said, the marshaling needed for DOM access isn't that relevant, I wouldn't say this is a high-priority problem and would prefer people to focus on GC instead, like they are doing.)

titzer7• 4 years ago

I will add to this that we are in a healthy design loop that is tightening in on what I feel is a reasonable final design that is implemented in at least one high-performance engine, V8. AFAIK there are Igalia folks trying to get a parallel implementation in JSC to meet the 2-engine bar.

GC will not directly make DOM manipulation easier, but it will make it easier to integrate DOM references into a managed language that compiles to WASM, since it obviates the need for indirections through tables. This feature alone is majorly opens up capabilities for WASM on the Web!

wtetzner3• 4 years ago

While I'm also looking forward to TCE and GC for WASM, you can build full apps in OCaml now via js_of_ocaml.

jolux2• 4 years ago

I'm aware of js_of_ocaml and Reason, but I want it to run closer to native speed and use multithreading eventually.

jillesvangurp• 4 years ago

Kotlin 1.7.0 shipped with a WASM compiler recently that currently requires some experimental flags in Chrome to enable features related to garbage collection, threads, and memory management. So, it looks like this is progressing nicely. Once this lands, I imagine there will be a whole range of languages that will be able to make good use of this.

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

titzer7• 4 years ago

Thank you for this!

doublerabbit• 4 years ago

ELI5: Tail-calls?

qsort• 4 years ago

https://www.youtube.com/watch?v=-PX0BV9hGZY

Jtsummers6• 4 years ago

A tail call is a function call occurring in the final position of a function:

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

If the function has a return value (vice void like above):

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

In the way most languages are compiled, function calls generate a new entry in the call stack (a stack frame). This is necessary for all non-tail calls in order to handle the bookkeeping around what to do when the call finishes, how does the caller resume.

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);
  }

But while that's a recursive example, tail calls and tail call elimination (TCE) aren't just for recursive cases. My first two examples, though they are just sketches, show a non-recursive example of tail calls. With full TCE (it isn't uncommon to have TCE only apply to self-recursive cases) those examples would also have tail call elimination performed.

ufo2• 4 years ago

A contrived example: https://godbolt.org/z/17T5MzvGY

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.

continuational2• 4 years ago

Tail calls are super important for non-C like control flow, and it's great that it might be added.

But what I really think wasm should focus on is to get near native performance (say, <50% overhead). Until that happens, the whole endeavor seems pointless to me.

azakai3• 4 years ago

Estimates vary (because benchmarks and use cases vary), but it's generally faster than 50%. That number was seen here,

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%.

continuational2• 4 years ago

That seems very promising. If it really is that good, wasm has a lot more potential in my eyes.

But e.g. sharp/vips ended up with a much worse result: https://www.libvips.org/2020/09/01/libvips-for-webassembly.h...

It may just be a matter of waiting for simd and threads though.

dannyobrien• 4 years ago

Thanks for doing this!

carterschonwald• 4 years ago

How can I help this?!

I’ve been wanting tailcalls to be in wasm for years! I consider it a blocker for all sorts of uses I’d be interested in

Animats• 4 years ago

I want threads more than tail calls. WASM has processes with limited shared memory, but not real threads. This is a headache for porting high-performance games to the web.

neilv• 4 years ago

I have to resist the urge to implement Scheme in this, right now, but I hope someone else has a chance to try this out for Scheme soon, and help inform the standard before things finalized.

egberts13• 4 years ago

“proposal to move WASM towards a control-flow model friendlier to tail-call optimization, which would bring it more in line with physical hardware.“

perhaps it is nigh time to bring the CPU hardware closer to the current WASM design.

Might simplify a lot of issues related to pipelining, cache-busting, and Spectre-like mitigations, not to mention crazy varied breakout of legacy microcode to subfunctions (Intel, I am looking at you as well).

But what do I know, I just play with Unicorn engine.

egberts13• 4 years ago

meanwhile, the new Spectre-BTI variant just now embroils both AMD and Intel on media.

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...

egberts13• 4 years ago

For those who specialize in emitting platform-dependent native machine code translated from macrobytecode to MIR to LIR, following paper outlines the pitfalls of tailcall:

https://www3.cs.stonybrook.edu/~mikepo/papers/devil.ndss15.p...

Speaking in Firefox-ese, within its JavaScript engine, IonMonkey taking JavaScript bytecode down to Mid-level Intermediate Representation (MIR), then OdinMonkey (TraceMonkey) translates to Low-level Intermediate Representation (LIR), then for WarpMonkey (NanoJIT) to translate into native machine code.

OdinMonkey and WarpMonkey should not be handling tailcalls.

AtNightWeCode• 4 years ago

You can use F# with WASM. I know F# convert recursive tail calls to loops but I understand this is another case. But shouldn't F# have the same problem?

Jtsummers6• 4 years ago

I have not been following WASM generally, but my understanding after reading this:

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.

xenadu022• 4 years ago

Self recursion is a special case that WASM backend targets can more or less efficiently resolve the same way a human can convert a recursive function into a non-recursive one: explicitly put arguments onto your own simulation of a stack and perform the computation in a loop.

Unfortunately self recursion is only a subset of tail calling.

int_19h7• 4 years ago

F# compiles to CIL bytecode, which has a tail call instruction. I'm not sure what happens to that when CIL is compiled to wasm, but since there's no way to do a general translation, it probably just drops the tail part and makes it a regular call.

lloydatkinson• 4 years ago

Please don't let apple block this proposal like they did for browsers. We don't have tail calls because apple decided they couldn't be bothered to implement it.

Jtsummers6• 4 years ago

Safari is the mainstream browser with proper tail calls implemented. Was there some historical point where Apple blocked it and so others followed along but then Apple turned around and did it anyways?

titzer7• 4 years ago

JavaScriptCore did not block tail calls. In fact, they were one of the biggest proponents of it because of their Shadow Chicken approach.

systoll• 4 years ago

Safari has tail-call optimisation.

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."

slimsag• 4 years ago

Finally :) My coworker back in 2017 implemented the WebAssembly backend for the Go compiler[0], and noted at the time that WASM doesn't have any equivalent to setjmp/longjmp. As a result, Go's WebAssembly implementation actually emulates a register machine on top of the WASM stack machine. Quoting him (some parts omitted):

For example its architecture is a stack machine instead of a register machine. This means that it isn't immediately suitable as simply yet another target at the last stage of the Go compiler next to x86 and friends.
There might be an alternative: Emulate what we need. We may use the stack machine to emulate a register machine and hopefully do so in a reasonably performant way.
WebAssembly has linear memory with load and store instructions, which is good. We would not use WebAssembly's call instruction at all and instead roll our own stack management and call mechanism. Stacks would live on that linear memory and be managed by the Go runtime. The stackpointer would be a global variable. All code would live in a single WebAssembly function. The toplevel would be a giant switch statement (or WebAssembly's br_table based equivalent) with one branch for each function. Each function would have another switch statement with one branch per SSA basic block.
There are some details that I'm omitting here, but in the big picture this looks like a decent register machine to me. Of course the performance of this heavily depends on how well WebAssembly can transform these constructs into actual machine code.

[0] https://github.com/golang/go/issues/18892#issuecomment-30931...

titzer7• 4 years ago

LLVM and other compilers that use SSA but target a stack machine can run a stackification phase. Even without reordering instructions, it seems to work well in practice.

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...

hahnchen• 4 years ago

Wow sweet! How do you find cool coworkers like these?

aliceryhl• 4 years ago

Why do we need an explicit construct for this as opposed to e.g. having the compiler replace the tail call with a goto back to the beginning of the function?

simiones• 4 years ago

This was discussed elsewhere in the thread as well - the main problem is TCO support between multiple functions - e.g. when visiting a tree with nodes of various types, such that you have visitSumNode(&total) -> visitChildren(&total) -> visitMinusNode(&total) -> visitChildren(&total) -> ...

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).

shirogane86x• 4 years ago

That sounds super nice! Maybe this will turn out to be a nice way of compiling languages which make heavy use of tail calls to the browser (I'm thinking Haskell, Purescript, Erlang, Ocaml). For purescript specifically this means no MonadRec needed which is quite exciting! (if and when a wasm backend is made, ofc)

IshKebab2• 4 years ago

Would this mean that relooper etc. are no longer needed since you can just have all your basic blocks as functions and use tail calls to jump between them?

pipeline_peak• 4 years ago

The industry doesn’t care about functional programming, are tail calls really necessary?

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

Related Stories