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

211–220 of 300 posts

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

#211

Post by slimsag »

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

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

#212

Post by yuubi »

marshray wrote: post #164
kevin_thibedeau wrote: post #156

Earlier quoted context omitted.

The point is that tail calls obscure the transitions between states by spreading it everywhere.

I'm not too clear on how one would implement a state machine without "spreading the transitions everywhere". Can you share a link to some example code showing the format you prefer? Typically, we'd see the code that implements the logic for each state gathered together. Since this is where the outgoing transitions get decided, the transitions end up being distributed across their originating states.

erlang/otp gen_fsm maybe?

you define a function with a clause per state (and some other args including the incoming message), and each clause returns a tuple with the new state and some other stuff. the loop is part of the framework, and handles generic otp stuff like updating code in a running system.

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

#213

Post by MereInterest »

haberman wrote: post #204
wyager wrote: post #167

Earlier quoted context omitted.

> each function call must consume at least N bits of memory This is going to be a problem for any long-running recursive program. Why would we mandate this?

You don't want it to be implementation-specific whether tail call optimization is performed or not. The nightmare scenario is that you spend months writing a program that works great in browsers A and B, but when you roll it out to prod it immediately fails in browser C, which doesn't perform TCO. You only want to write code that depends on TCO if you can get a guarantee that TCO will be performed. This is the motiva…

This might be a silly question, but why is that a nightmare scenario? The exact same argument could be made for any compile-time optimization. If one compiler inlines a function where another doesn't, or unrolls a loop, or performs better constant propagation, any of those could impact the resource usage between the two compilers, leading to exactly that same scenario. But I wouldn't want to forbid improvements altogether out of a desire for consistency.

To me, I'd see a distinction between code that requires a specific optimization and code that could benefit from that optimization. If the standard forbids an optimization to avoid the former, it also removes the latter.

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

#214

Post by lmm »

matheusmoreira wrote: post #208
lmm wrote: post #177

Earlier quoted context omitted.

Iteratees are immensely useful in practice and they involve doing this all the time (basically you do stream processing with a source and a sink that are mutually recursive - the source emits an element by calling the sink to process it, the sink processes it and then recurses into the source for the next element. It feels a bit forced if you describe it like that, but it gives you a model wiht lots of natural struct…

> the source emits an element by calling the sink to process it, the sink processes it and then recurses into the source for the next element I think I understood that concept but it still seems a bit strange to me. Doesn't that imply a potentially infinite stack of function calls? I've seen this idea in other functional program examples as well. Instead of having a sequence of instructions, they have a sequence of f…

> I think I understood that concept but it still seems a bit strange to me. Doesn't that imply a potentially infinite stack of function calls?

Yes, which is exactly why tail calls are so important. Otherwise you'd stack overflow after processing the first few thousand elements of your stream.

> I've seen this idea in other functional program examples as well. Instead of having a sequence of instructions, they have a sequence of function calls. Instead of a function returning to the caller, it calls the next function in the program which is analogous to the virtual machine moving on to the next line of code in the sequence. It implies the program's structure and state is actually expressed within the function call stack and its frames. I admit I'm not sure what the purpose of this is.

Well, if you want to express your function as an actual function, in the mathematical sense, recursion is often the natural way to do it. Things like the call stack are an implementation detail; often a natural way to describe a function is "do this, do that, then do the same thing for all the rest of it", and usually the easiest way to translate that into a program is recursion.

It also tends to be more compositional, because you don't have to worry about control flow (or at least, control flow isn't a special case: all your control flow is just function calls). For example if you are calling several nested functions in an imperative-style loop, there's no way to break out of that loop from the inner function. But if you write the same thing as several mutually recursive functions, you can "break out of the loop" by just not recursing under particular conditions.

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

#215

Post by haberman »

MereInterest wrote: post #213
haberman wrote: post #204

Earlier quoted context omitted.

You don't want it to be implementation-specific whether tail call optimization is performed or not. The nightmare scenario is that you spend months writing a program that works great in browsers A and B, but when you roll it out to prod it immediately fails in browser C, which doesn't perform TCO. You only want to write code that depends on TCO if you can get a guarantee that TCO will be performed. This is the motiva…

This might be a silly question, but why is that a nightmare scenario? The exact same argument could be made for any compile-time optimization. If one compiler inlines a function where another doesn't, or unrolls a loop, or performs better constant propagation, any of those could impact the resource usage between the two compilers, leading to exactly that same scenario. But I wouldn't want to forbid improvements altog…

Most optimizations only offer constant factor improvements. Tail call optimization is the difference between O(1) and O(N) stack size.

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

#216

Post by anfilt »

Jtsummers wrote: post #141
anfilt wrote: post #138

Earlier quoted context omitted.

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

So no self modifying code either, since it seems like I can't just get the address of a function and modify the byte code?

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

#217

Post by aaron_m04 »

apignotti wrote: post #18
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…

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…

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

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

#218

Post by afiori »

brrrrrm wrote: post #17
andsoitis wrote: post #3

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

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

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)

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

#219

Post by titzer »

slimsag wrote: post #211

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

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

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

#220

Post by titzer »

int_19h wrote: post #206
leoc wrote: post #171

Earlier quoted context omitted.

Graaagh, sorry.

It's not that much better. Apparently at least some of the idiosyncracies in the design of wasm, such as the lack of regular unstructured branches, is due to the internal implementation details of V8.

Every optimizing JIT for JavaScript has the same limitations.
Post reply on HN