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

141–150 of 300 posts

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

#141

Post by Jtsummers »

anfilt wrote: post #138
apignotti wrote: post #18

Earlier quoted context omitted.

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…

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?!?

https://www.w3.org/TR/wasm-core-1/#control-instructions%E2%9...

Those are the list of control instructions. WASM seems to be a bit of a misnomer as it is not an assembly language in the more conventional sense. It is a structured language and provides a limited goto in the form of branches (in the section I linked to) which are constrained to a particular scope.

If you compile your whole program so it fits within a single function, then yes you can use this to do universal tail call elimination. Otherwise you are restricted to doing TCE only on auto-recursive functions and maybe mutually recursive functions if you have a single entry point (of the set of functions) and decide to optimize by moving all of them into one function.

Otherwise, function calls are performed using one of the two call instructions which (presently) implement a behavior more like conventional call stack/stack frames. This proposal would add a second pair of call instructions that a compiler can emit which the WASM runtime would then optimize (by not generating new stack frames).

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

#142

Post by dwheeler »

pygy_ wrote: post #42
silon42 wrote: post #40

Earlier quoted context omitted.

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

Firefox can’t eliminate tail call across realms. The spec could make an exception for that scenario

That seems reasonable. Tail call elimination, limited to within a realm, still seems pretty useful.

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

#143

Post by User23 »

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.

> So is it fundamental or not?

Obviously a Turing-complete system can simulate any other Turing-complete system. For example you could write an emulation of any system you like in WASM, and in the emulator you could have tail call optimization. Thus from context it should be apparent that we're talking about efficient implementations.

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

#144

Post by gumby »

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…

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)

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

#145

Post by light_hue_1 »

OskarS wrote: post #137
marshray wrote: post #130

Earlier quoted context omitted.

> yeah, it would change .stack, but who cares? You might enjoy participating in an interoperable standardization process sometime.

I don't mean to minimize anybody's work, I'm genuinely curious about why it can't be done. Like, what's stopping me from making a compiler that optimizes tail calls? For instance: the C and C++ standards have very strict rules for how to handle floating point math, and compilers aren't allowed to deviate from that according to the standard. Which turns off all sorts of cool optimizations you can do. But of course, al…

> So, my question is, why can't you write a compiler with an option that's like "I don't particularly care that .stack changes, do the tail call optimization". A -ffast-math, but for tail calls. Is there a technical reason why you can't do this?

Because the stack in web assembly is only observable. It is implicit. You cannot modify it yourself. There are simply no instructions for this. The WASM stack is not present on the WASM heap, like it is for your physical machine.

You simply cannot express tail calls with the instruction set given to you by WASM right now. No hacks are possible.

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

#146

Post by light_hue_1 »

MikeHolman wrote: post #115
ufo wrote: post #26

Earlier quoted context omitted.

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.

This is simply false.

The compiler cannot implement tail calls correctly as it stands. You do not have access to modify the WASM stack and it's not present on the heap like it is for normal programs.

No compiler tricks can enable tail calls in WASM at the moment (with the exception of trampolines which always work and are absurdly slow).

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

#147

Post by light_hue_1 »

marcosdumay wrote: post #114
apignotti wrote: post #20

Earlier quoted context omitted.

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.

You really can't.

For example, what if those functions are in different modules or libraries? Tail calls are still supposed to work.

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

#148

Post by wtetzner »

MikeHolman wrote: post #115
ufo wrote: post #26

Earlier quoted context omitted.

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.

I think they're referring to a compiler that is targeting WASM, not a WASM-to-machine-code compiler.

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

#149

Post by light_hue_1 »

kragen wrote: post #129
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…

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…

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

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

#150

Post by titzer »

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…

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!

Post reply on HN