23 ms·

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

• AtNightWeCode 4y 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?
  • Jtsummers 4y 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.
  • xenadu02 4y 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_19h 4y 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.
• convolvatron 4y 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
  • apignotti 4y 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 ;-)
    • convolvatron 4y ago
      pointer to a draft?
• andsoitis 4y 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-in-webkit/ https://webkit.org/blog/6240/ecmascript-6-proper-tail-calls-...
  • apignotti 4y 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_ 4y 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 4y ago
      If I understand what cross-realm means (code security), then I'm not sure that can be done at all.
      • pygy_ 4y ago
        Firefox can’t eliminate tail call across realms. The spec could make an exception for that scenario
        • 4y ago
• labrador 4y 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.
  • traviswt 4y 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?
    • labrador 4y 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
      • kkdaemas 4y ago
        Surely it's easier to stick to JavaScript The Good Parts than to introduce a whole new layer in the form of Blazor?
        • labrador 4y ago
          Blazor is not equal to JavaScript. Blazor is Microsoft's answer to React and Flutter. So far of the three, I like Blazor, but not the server version that uses SignalR to communicate with the client because it locks you in. Blazor Webassembly is awesome, but just needs a good DOM manipulation library. With Blazor Wasm on the client, I can use anything on the back end.
      • atwood22 4y ago
        What do you like about Dart over TypeScript? The type system in TypeScript is far superior to Dart's. Other than that, the languages are more-or-less the same.
• codedokode 4y 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 4y 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 4y 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.
    • vbezhenar 4y ago
      Those algorithms usually use non-tail recursion. Most tail recursion uses usually is trivial to rewrite in a loops.
      • wtetzner 4y ago
        > Most tail recursion uses usually is trivial to rewrite in a loops. Except for tail calls that aren't self-calls. Which for code I write is actually fairly frequent.
  • 4y ago
• deleted 4y ago
  [deleted]
• j-pb 4y 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/presentation/lehmann https://www.usenix.org/conference/usenixsecurity20/presentat...
  • brrrrrm 4y 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_while_statement” https://en.wikipedia.org/wiki/Tail_call#Relation_to_the_whil...
    • mibsl 4y ago
      Only tail recursion, not tail calls in general.
    • apignotti 4y 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.
      • throwaway17_17 4y ago
        I am genuinely asking, is your position that a compiler cannot convert: g(): a = 1+1; b = 2+a; print(b); return f() into code that does not allocate stack space and just reuses the frame allocated for g()?
• jacobmischka 4y 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/download/1.0.0/thesis.pdf https://github.com/jacobmischka/uwm-masters-thesis/releases/... [2]: https://github.com/WebAssembly/tail-call/issues/10 https://github.com/WebAssembly/tail-call/issues/10
  • diarrhea 4y ago
    That might be the shortest (in word count) Master's thesis I have ever seen!
    • jacobmischka 4y 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.
    • IshKebab 4y ago
      Looks typical for a master's thesis to me. Maybe you're thinking of a PhD thesis?
      • diarrhea 4y ago
        No, in my industry (mechanical engineering) Master (and also Bachelor) theses were always much, much longer. Longer lines, less vertical line spacing, many more pages. Lots of faffing about ('Introduction', 'State of the Art', 'Theoretical foundation', ...). Faculties urge supervisors and students to keep it below 100 pages (of relatively dense type).
        • jacobmischka 4y ago
          Agreed on the formatting of mine being ridiculous with huge margins and line spacing, it wasn't my choice.
• miloignis 4y 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.
• 202206241203 4y 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 4y 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-tail-calls/63249 https://discourse.llvm.org/t/supporting-coroutines-without-t...
  • azakai 4y ago
    It isn't one or the other. Work on Wasm GC is ongoing and separate from this.
  • Jtsummers 4y 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 4y ago
  I'm waiting for constant time WASM. https://github.com/WebAssembly/constant-time/blob/main/proposals/constant-time/Overview.md https://github.com/WebAssembly/constant-time/blob/main/propo...
• jolux 4y 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 4y ago
    Have you looked into ReasonML by any chance?
    • k__ 4y ago
      I lost track of it since the Reason/ReScript split.
  • azakai 4y 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.
    • marcosdumay 4y 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.)
    • titzer 4y 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!
• titzer 4y ago
  Thank you for this!
• doublerabbit 4y ago
  ELI5: Tail-calls?
  • qsort 4y ago
    https://www.youtube.com/watch?v=-PX0BV9hGZY https://www.youtube.com/watch?v=-PX0BV9hGZY
  • Jtsummers 4y 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.
  • ufo 4y ago
    A contrived example: https://godbolt.org/z/17T5MzvGY 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.
• continuational 4y 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.
  • azakai 4y 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 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 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%.
    • continuational 4y 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.html 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 4y ago
  Thanks for doing this!
• carterschonwald 4y 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 4y 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 4y 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.
• egberts1 4y 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.
  • egberts1 4y 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-and-amd-cpus-vulnerable-to-a-new-speculative-execution-attack/ https://arstechnica.com/information-technology/2022/07/intel...
    • egberts1 4y 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.pdf 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.
• lloydatkinson 4y 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.
  • Jtsummers 4y 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?
  • titzer 4y 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 4y 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 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 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 4y 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-309312286 https://github.com/golang/go/issues/18892#issuecomment-30931...
  • titzer 4y 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/MachStackifier.v3 https://github.com/titzer/virgil/blob/master/aeneas/src/mach...
  • hahnchen 4y ago
    Wow sweet! How do you find cool coworkers like these?
• aliceryhl 4y 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 4y 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 4y 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)
• IshKebab 4y 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 4y ago
  The industry doesn’t care about functional programming, are tail calls really necessary?