Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

news.ycombinator.com

Post reply on HN
Print view View original

111–120 of 300 posts

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

#111

Post by j-pb »

miloignis wrote: post #66
coliveira wrote: post #48

Earlier quoted context omitted.

If it is a mistake depends on the point of view. What seems to be more important: exceptions of tail-call elimination? Most modern languages use exceptions in one way or another, conversely very few use the later feature. From the point of view of existing software it is way more important to optimize VMs for exception handling than for tail call elimination.

Well wasm doesn't have exceptions right now either! The exceptions proposal is also in phase 3, like tail-calls. Right now wasm just supports traps, which can't be caught or inspected from within wasm code, and don't actually need to record stack frames (but the JavaScript host does in web browsers). I'm not sure what benefit exposing the wasm part of the stack for traps gives the JavaScript host side except perhaps…

After reading the discussion, I think I'm much more in favour of adding tail calls, than adding exceptions.

Actually I wonder if one couldn't adapt the tail-call mechanism slightly to also serve as an exception mechanism. I think you could do both by allowing `br` to jump to an arbitrary label previously established. An exception then simply being a "tail-call" that unwinds more than one stack frame, and calls into the "catch".

Not sure how well JITable this would be, but I think an arbitrary backjump and call should be mostly fine in terms of control flow?

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

#113

Post by egberts1 »

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

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

#114

Post by marcosdumay »

apignotti wrote: post #20
brrrrrm wrote: post #14

Earlier quoted context omitted.

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

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.

When you have a set of functions that may recourse into each other, you can convert them into a iterative one by doing a `while cond {switch function_selector {..}}` block.

It's an ugly piece of code, but because of parsers, there is a huge amount of know how on it.

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

#115

Post by MikeHolman »

ufo wrote: post #26
j-pb wrote: post #10

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 m…

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…

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.

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

#116

Post by marcosdumay »

j-pb wrote: post #10

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 m…

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.

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

#117

Post by nu11ptr »

retrac wrote: post #110
nu11ptr wrote: post #89

Earlier quoted context omitted.

Understood, but in practice how often does that really happen? (I'm aware of the contrived 'odd'/'even' example always given, but in the real world, I never had anything like that). Even when I wrote more functional code I rarely (if ever?) did that. 98-99% of the time it was the same function calling itself. Is your experience different?

In functional languages, recursive data structures are often most naturally walked with recursive functions. Languages like Haskell and ML take this to its natural conclusion and use it systematically. For example, a linked list. Here's how the Haskell "last" function, to get the last item in a linked list, is implemented in the standard library: last [x] = x last (_:xs) = last xs last [] = errorEmptyList "last" If g…

This is the scenario I am used to using where "last" is called in tail position calling itself, but I see from the other answers there are definitely valid use cases for non-same function recursion as well

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

#118

Post by marcosdumay »

azakai wrote: post #59
jolux wrote: post #38

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

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…

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

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

#119

Post by thayne »

emmelaich wrote: post #108
miloignis wrote: post #27

Earlier quoted context omitted.

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 r…

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.

It might be possible for a compiler to generate code that effectively does trampolining. But that would definitely have a performance cost.

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

#120

Post by convolvatron »

emmelaich wrote: post #108
miloignis wrote: post #27

Earlier quoted context omitted.

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 r…

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.

'call' leaves return state on the stack, so if you use it to implement 'jump'. that has to be cleaned up. a trampoline is kinda the only choice if you are forced to run on a stack. go ahead and use 'call' as much as you like, but as the useless return addresses (and often locals) pile up on the stack, at some point you just return all the way back (or do a longjmp equivalent if your environment supports it) and start over again.

this is measurably worse than just using jump, and as another posted pointed out, can introduce an O(n) term that doesn't need to exist. (edit: nevermind - if you are going through the forward direction n times then it doesn't change complexity to do a little more n work on the way out)

Post reply on HN