6 ms·

WebAssembly Tail Calls

135 points by feross 4y ago

admax88qqq 4y ago
Amazing and sad that V8 is going to add tail call elimination in WASM before JavaScript.
- hnav 4y ago
  does some JS idiom rely on TCO or is this for transpiled languages?
  - ISV_Damocles 4y ago
    It would help any recursively-defined code, parsers of some input format are often more naturally represented that way, for instance, where rewriting as an imperative loop requires mixing of different logical states, eg, a JS JSON parser might determine if the current character is for an object, array, or leaf type, and then pass the input along to whichever that is, and if it was an array, for instance, would then pass back to that initial function one character over to determine what the first type of the first element of the array is. This is easy in a recursive style and would require all of this logic to be mixed in the same function with some state tracking variable to decide which branch to use in imperative style. You can use trampolines[1] to get around this, but there's a performance penalty versus TCO and other recursive optimizations. [1]: https://blog.logrocket.com/using-trampolines-to-manage-large-recursive-loops-in-javascript-d8c9db095ae3/ https://blog.logrocket.com/using-trampolines-to-manage-large...
  - MrJohz 4y ago
    Honestly, the impression I get is that it seemed like a cool thing to have, rather than something that came out of genuine need. I very rarely see recursive functions in the wild, and while I quite like them and probably use them more often than average, I rarely write tail-recursive functions. Specifically, Javascript has pretty good iteration tools, so the basic recursion-as-iteration stuff isn't necessary, and usually pretty inefficient. Which means recursion tends to only get used when you're dealing with a recursive data structure of some description, or doing something naturally recursive. But in my experience these cases of natural recursion tend not to lend themselves to tail recursion - in the general case, you need a stack argument somewhere to allow the tail recursion to work, at which point you might as well just write a non-recursive, loop-based version. The result of this is that truly tail-recursive functions are fairly rare in "idiomatic" Javascript code, which means implementation effort spent there is going to affect relatively little code. I could imagine that transpiled code might use this technique more often, but then the rise of WASM probably means that fewer languages are going to see Javascript as their primary compilation target, and instead choose WASM.
    - int_19h 4y ago
      Natural recursion that stems from data structures will be tail-recursive if they themselves are recursive in this manner. Thus e.g. walking a linked list is a problem that naturally translates to tail recursion, but walking a binary tree isn't. But also, part of the reason why you don't see much deeply recursive code in the wild is because there's no guarantee that it'll be tail-call-optimized, which means that it'll likely fail on large inputs, and will be written iteratively to begin with.
      - MrJohz 4y ago
        Even many operations performed on a linked list will not be tail recursive if you do them naively. For example, a naive sum function might look like: const sum = (node: Node): number => { if (!node.tail) return node.value; return node.value + sum(node.tail); } Even if tail call optimisation were a thing, I'd still expect most recursive functions to be written in a non-tail-recursive fashion, and only later optimised to be tail recursive. But in practice, it's already possible to rewrite those functions in an imperative way when they do become a performance issue. So in practice, I can see why implementors don't prioritise TCO in Javascript, coming from both directions: there's not a lot of free wins available, because tail calls are rarely the most natural way to express a recursive algorithm; and even if you want to explicitly optimise for them, there's already plenty of ways to optimise an inefficient recursive algorithm if that's necessary. That said, I can see the value a lot more in a language that's being used as a compilation target, which it probably made more sense when there was more buzz around compile-to-JS languages, and why it makes more sense now with WebAssembly.
- jalino23 4y ago
  how did safari implement tail call but not chrome? its the one thing that discourage me from continuing reading the new sicp with JS
- baq 4y ago
  amazing I agree, sad - no, not really, why?
  - debugnik 4y ago
    Because it's been part of ECMAScript since ES 6 but still not implemented. The only browser supporting it is Safari, I think.
agency 4y ago
Very exciting to see this continuing to progress and hats off to those who kept pushing on the proposal to get it here. I've been building a little compiler from a toy dialect of Lisp to WASM as a side project but let it fall by the wayside. I should pick it back up now that tail calls are usable in several runtimes.
keithwinstein 4y ago
Argh, I really wish we could implement the tail-call proposal in wasm2c (while preserving the straightforward transformation of Wasm functions -> C functions), but it seems like it's going to be one of the tougher proposals to handle. The C committee voted 8-7-8 against including mandatory tail calls in C23 (https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2941.pdf https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2941.pdf), mostly I think because of a lack of implementation experience. LLVM has everything needed via the musttail marker, but the musttail attribute in clang is a lot more restrictive (it enforces that the caller and callee function signatures are the same). It might theoretically be possible to get more flexibility plumbed through to clang, but then I'm guessing getting GCC on board would be a huge job too. :-/
- mananaysiempre 4y ago
  Scheme implementations targeting C (e.g. Chicken[1] and Gambit[2]) have literal decades of experience doing tail calls, but admittedly the resulting translations (trampolining, Cheney on the MTA, whatever Gambit does) do not make for very natural C. The C paper[3] you mention does make note of this. The limits of Clang’s musttail stem from the limitations of calling conventions (which, regardless of what the standard says, allow for passing more arguments than the callee expects, thus require caller cleanup). So far the solutions[4] to this seem rather awkward and definitely not backwards compatible. Are you aware of any convincing proposals in this direction? [1] https://www.call-cc.org/ https://www.call-cc.org/ [2] https://gambitscheme.org/ https://gambitscheme.org/ [3] https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2920.pdf https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2920.pdf [4] https://www.complang.tuwien.ac.at/schani/diplarb.ps https://www.complang.tuwien.ac.at/schani/diplarb.ps
- titzer 4y ago
  wasm3 uses tailcalls to implement its interpreter bytecode handlers and it manages to successfully force tail-call optimization in both gcc and llvm. Worth having a look on how it does that?
  - shadowofneptune 4y ago
synthetigram 4y ago
What isn't clear to me is why tail calls need to be implemented in WASM, rather than in the compiler? The post linked to Josh Habermans post on tail calls, which show how tail calls can help the compiler decide where to inline (cool!). But that was needed for the C++ text, not the LLVM code. It feels like tail calls are too high level of a concept to be in an "assembly" language.
- CyberDildonics 4y ago
  It doesn't and I hope whoever is in charge of web assembly doesn't ruin what they have by giving in to nonsense trends that are part of a silver bullet syndrome and don't offer real utility.
  - chriswarbo 4y ago
    > giving in to nonsense trends Tail-calls have been pretty standard since at least the 'Lambda the Ultimate GOTO' paper from 1977 https://en.wikisource.org/wiki/Lambda_Papers https://en.wikisource.org/wiki/Lambda_Papers For example, it's done by all of the Schemes, all of the MLs (SML, Ocaml, Haskell, Rust, Scala, Idris, etc.), scripting languages (Lua, Elm, Perl, Tcl, etc.), and many others. > that are part of a silver bullet syndrome and don't offer real utility Their "real utility" is right there in the subtitle of that original paper: Debunking the "Expensive Procedure Call" Myth or, Procedure Call Implementations Considered Harmful or, Lambda: The Ultimate GOTO In other words, any implementation of procedure/function/method-calls which doesn't eliminate tail-calls is defective (slow, memory-hungry, stack-unsafe, etc.)
    - CyberDildonics 4y ago
      Tail-calls have been pretty standard Not standard, since almost no programming is actually done using tail calls. Programming is done with loops, tail calls are an exotic and niche way of working. Even in lua and rust tail calls are rarely used and the other languages you listed are extremely niche. Debunking the "Expensive Procedure Call" Myth or, Procedure Call Implementations Considered Harmful or, Lambda: The Ultimate GOTO These are not explanations of utility, these are titles that you are using to claim something without backing it up. In other words, any implementation of procedure/function/method-calls which doesn't eliminate tail-calls is defective (slow, memory-hungry, stack-unsafe, etc.) This is a very bold claim with no evidence for it and pretty much the entire history of programming against it.
skybrian 4y ago
> One observable consequence of tail calls is (besides a reduced risk of stack overflow) that tail callers do not appear in stack traces. Neither do they appear in the stack property of a caught exception, nor in the DevTools stack trace. By the time an exception is thrown, or execution pauses, the tail caller frames are gone and there is no way for V8 to recover them. It seems like a compiler could unroll a function one step, so the first internal call isn't a tail call? Then the first stack frame with the initial arguments would remain on the stack, and the stack trace would be similar to what it would be if you wrote a loop instead.
- Rusky 4y ago
  Sometimes it's not just a single function calling itself, but a whole bunch of functions calling into each other, which can get more confusing. This is also tricky when you have indirect tail calls, because now you don't know if it's the first call to that particular function so you can't always unroll it anyway.
  - skybrian 4y ago
    I'm thinking of something like an interpreter, where each function implements one instruction and it does tail calls to go to the next instruction, instead of having a giant switch statement in a loop. To match the implementation without tail calls, you probably don't want the previous instruction(s) on the stack, but all entry points into the interpreter should probably be on the stack.
    - Rusky 4y ago
      You can get this without the compiler doing any unrolling, by doing non-tail calls at the points where you enter the interpreter.
- cryptonector 4y ago
  This is really not a problem.
  - 4y ago
msla 4y ago
Previously: https://news.ycombinator.com/item?id=32069418 https://news.ycombinator.com/item?id=32069418
singularity2001 4y ago
If they focused on finally getting WebIDL instead of perpetually postponing direct DOM access wasm would already be much further
apignotti 4y ago
We (Leaning Technologies) are proud to have been a big contributing factor to the standardization of WebAssembly tail calls. https://news.ycombinator.com/item?id=32069418 https://news.ycombinator.com/item?id=32069418

135 points by feross 4y ago

admax88qqq 4y ago

Amazing and sad that V8 is going to add tail call elimination in WASM before JavaScript.

hnav 4y ago
does some JS idiom rely on TCO or is this for transpiled languages?
- ISV_Damocles 4y ago
  It would help any recursively-defined code, parsers of some input format are often more naturally represented that way, for instance, where rewriting as an imperative loop requires mixing of different logical states, eg, a JS JSON parser might determine if the current character is for an object, array, or leaf type, and then pass the input along to whichever that is, and if it was an array, for instance, would then pass back to that initial function one character over to determine what the first type of the first element of the array is. This is easy in a recursive style and would require all of this logic to be mixed in the same function with some state tracking variable to decide which branch to use in imperative style. You can use trampolines[1] to get around this, but there's a performance penalty versus TCO and other recursive optimizations. [1]: https://blog.logrocket.com/using-trampolines-to-manage-large-recursive-loops-in-javascript-d8c9db095ae3/ https://blog.logrocket.com/using-trampolines-to-manage-large...
- MrJohz 4y ago
  Honestly, the impression I get is that it seemed like a cool thing to have, rather than something that came out of genuine need. I very rarely see recursive functions in the wild, and while I quite like them and probably use them more often than average, I rarely write tail-recursive functions. Specifically, Javascript has pretty good iteration tools, so the basic recursion-as-iteration stuff isn't necessary, and usually pretty inefficient. Which means recursion tends to only get used when you're dealing with a recursive data structure of some description, or doing something naturally recursive. But in my experience these cases of natural recursion tend not to lend themselves to tail recursion - in the general case, you need a stack argument somewhere to allow the tail recursion to work, at which point you might as well just write a non-recursive, loop-based version. The result of this is that truly tail-recursive functions are fairly rare in "idiomatic" Javascript code, which means implementation effort spent there is going to affect relatively little code. I could imagine that transpiled code might use this technique more often, but then the rise of WASM probably means that fewer languages are going to see Javascript as their primary compilation target, and instead choose WASM.
  - int_19h 4y ago
    Natural recursion that stems from data structures will be tail-recursive if they themselves are recursive in this manner. Thus e.g. walking a linked list is a problem that naturally translates to tail recursion, but walking a binary tree isn't. But also, part of the reason why you don't see much deeply recursive code in the wild is because there's no guarantee that it'll be tail-call-optimized, which means that it'll likely fail on large inputs, and will be written iteratively to begin with.
    - MrJohz 4y ago
      Even many operations performed on a linked list will not be tail recursive if you do them naively. For example, a naive sum function might look like: const sum = (node: Node): number => { if (!node.tail) return node.value; return node.value + sum(node.tail); } Even if tail call optimisation were a thing, I'd still expect most recursive functions to be written in a non-tail-recursive fashion, and only later optimised to be tail recursive. But in practice, it's already possible to rewrite those functions in an imperative way when they do become a performance issue. So in practice, I can see why implementors don't prioritise TCO in Javascript, coming from both directions: there's not a lot of free wins available, because tail calls are rarely the most natural way to express a recursive algorithm; and even if you want to explicitly optimise for them, there's already plenty of ways to optimise an inefficient recursive algorithm if that's necessary. That said, I can see the value a lot more in a language that's being used as a compilation target, which it probably made more sense when there was more buzz around compile-to-JS languages, and why it makes more sense now with WebAssembly.
jalino23 4y ago
how did safari implement tail call but not chrome? its the one thing that discourage me from continuing reading the new sicp with JS
baq 4y ago
amazing I agree, sad - no, not really, why?
- debugnik 4y ago
  Because it's been part of ECMAScript since ES 6 but still not implemented. The only browser supporting it is Safari, I think.

agency 4y ago

Very exciting to see this continuing to progress and hats off to those who kept pushing on the proposal to get it here. I've been building a little compiler from a toy dialect of Lisp to WASM as a side project but let it fall by the wayside. I should pick it back up now that tail calls are usable in several runtimes.

keithwinstein 4y ago

Argh, I really wish we could implement the tail-call proposal in wasm2c (while preserving the straightforward transformation of Wasm functions -> C functions), but it seems like it's going to be one of the tougher proposals to handle. The C committee voted 8-7-8 against including mandatory tail calls in C23 (https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2941.pdf https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2941.pdf), mostly I think because of a lack of implementation experience. LLVM has everything needed via the musttail marker, but the musttail attribute in clang is a lot more restrictive (it enforces that the caller and callee function signatures are the same). It might theoretically be possible to get more flexibility plumbed through to clang, but then I'm guessing getting GCC on board would be a huge job too. :-/

mananaysiempre 4y ago
Scheme implementations targeting C (e.g. Chicken[1] and Gambit[2]) have literal decades of experience doing tail calls, but admittedly the resulting translations (trampolining, Cheney on the MTA, whatever Gambit does) do not make for very natural C. The C paper[3] you mention does make note of this. The limits of Clang’s musttail stem from the limitations of calling conventions (which, regardless of what the standard says, allow for passing more arguments than the callee expects, thus require caller cleanup). So far the solutions[4] to this seem rather awkward and definitely not backwards compatible. Are you aware of any convincing proposals in this direction? [1] https://www.call-cc.org/ https://www.call-cc.org/ [2] https://gambitscheme.org/ https://gambitscheme.org/ [3] https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2920.pdf https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2920.pdf [4] https://www.complang.tuwien.ac.at/schani/diplarb.ps https://www.complang.tuwien.ac.at/schani/diplarb.ps
titzer 4y ago
wasm3 uses tailcalls to implement its interpreter bytecode handlers and it manages to successfully force tail-call optimization in both gcc and llvm. Worth having a look on how it does that?
- shadowofneptune 4y ago

synthetigram 4y ago

What isn't clear to me is why tail calls need to be implemented in WASM, rather than in the compiler? The post linked to Josh Habermans post on tail calls, which show how tail calls can help the compiler decide where to inline (cool!). But that was needed for the C++ text, not the LLVM code. It feels like tail calls are too high level of a concept to be in an "assembly" language.

CyberDildonics 4y ago
It doesn't and I hope whoever is in charge of web assembly doesn't ruin what they have by giving in to nonsense trends that are part of a silver bullet syndrome and don't offer real utility.
- chriswarbo 4y ago
  > giving in to nonsense trends Tail-calls have been pretty standard since at least the 'Lambda the Ultimate GOTO' paper from 1977 https://en.wikisource.org/wiki/Lambda_Papers https://en.wikisource.org/wiki/Lambda_Papers For example, it's done by all of the Schemes, all of the MLs (SML, Ocaml, Haskell, Rust, Scala, Idris, etc.), scripting languages (Lua, Elm, Perl, Tcl, etc.), and many others. > that are part of a silver bullet syndrome and don't offer real utility Their "real utility" is right there in the subtitle of that original paper: Debunking the "Expensive Procedure Call" Myth or, Procedure Call Implementations Considered Harmful or, Lambda: The Ultimate GOTO In other words, any implementation of procedure/function/method-calls which doesn't eliminate tail-calls is defective (slow, memory-hungry, stack-unsafe, etc.)
  - CyberDildonics 4y ago
    Tail-calls have been pretty standard Not standard, since almost no programming is actually done using tail calls. Programming is done with loops, tail calls are an exotic and niche way of working. Even in lua and rust tail calls are rarely used and the other languages you listed are extremely niche. Debunking the "Expensive Procedure Call" Myth or, Procedure Call Implementations Considered Harmful or, Lambda: The Ultimate GOTO These are not explanations of utility, these are titles that you are using to claim something without backing it up. In other words, any implementation of procedure/function/method-calls which doesn't eliminate tail-calls is defective (slow, memory-hungry, stack-unsafe, etc.) This is a very bold claim with no evidence for it and pretty much the entire history of programming against it.

skybrian 4y ago

> One observable consequence of tail calls is (besides a reduced risk of stack overflow) that tail callers do not appear in stack traces. Neither do they appear in the stack property of a caught exception, nor in the DevTools stack trace. By the time an exception is thrown, or execution pauses, the tail caller frames are gone and there is no way for V8 to recover them. It seems like a compiler could unroll a function one step, so the first internal call isn't a tail call? Then the first stack frame with the initial arguments would remain on the stack, and the stack trace would be similar to what it would be if you wrote a loop instead.

Rusky 4y ago
Sometimes it's not just a single function calling itself, but a whole bunch of functions calling into each other, which can get more confusing. This is also tricky when you have indirect tail calls, because now you don't know if it's the first call to that particular function so you can't always unroll it anyway.
- skybrian 4y ago
  I'm thinking of something like an interpreter, where each function implements one instruction and it does tail calls to go to the next instruction, instead of having a giant switch statement in a loop. To match the implementation without tail calls, you probably don't want the previous instruction(s) on the stack, but all entry points into the interpreter should probably be on the stack.
  - Rusky 4y ago
    You can get this without the compiler doing any unrolling, by doing non-tail calls at the points where you enter the interpreter.
cryptonector 4y ago
This is really not a problem.
- 4y ago

msla 4y ago

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

singularity2001 4y ago

If they focused on finally getting WebIDL instead of perpetually postponing direct DOM access wasm would already be much further

apignotti 4y ago

We (Leaning Technologies) are proud to have been a big contributing factor to the standardization of WebAssembly tail calls. https://news.ycombinator.com/item?id=32069418 https://news.ycombinator.com/item?id=32069418