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

191–200 of 300 posts

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

#191

Post by JohnHaugeland »

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…

> Tail-calls is fundamentally something that the compiler _cannot_ solve.

I don't see why. Compilers are how tail calls are literally always implemented. It's not like there's hardware support.

What makes this impossible?

.

> The issue is that to avoid stack blow-up you need the engine to recycle stack frames.

I mean, what's stopping you from just implementing a trampoline?

.

> The problem with this is that in WebAssembly (and JavaScript) the call stack is observable via the .stack property of thrown exceptions.

Okay? This seems fine to me. What makes this a problem?

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

#192

Post by emmelaich »

miloignis wrote: post #125
emmelaich wrote: post #108

Earlier quoted context omitted.

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.

No worries - it depends on what your constraints and context are. It's fundamentally something a wasm-emitting compiler cannot solve performantly in general. You can use trampolines, as the sibling comments mention, but you'll take a heavy performance hit. If we stretch things too far we'll end up in the "wasm is Turing-complete and thus can run anything" type of territory - if you're doing something performance inte…

Thanks, that's pretty much what I suspected. I guess the issue is that the term (fundamental) is being used in a specific context assumed by experts in that area.

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

#193

Post by ufo »

doublerabbit wrote: post #49

ELI5: Tail-calls?

A contrived example: 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.

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

#194

Post by labrador »

asabla wrote: post #99
labrador wrote: post #7

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.

For someone about to go knees deep into Blazor very soon. Do you have any gotchas which isn't really mentioned on MS documentation site? primarily related to performance, since it will be one of my main concerns.

If you're talking site load time you'd have to be careful because netdot is compiled as wasm, which doesn't leave a lot of room below the standard site size. It's hard to tell because even ordinary sites now are huge. I need to do some testing.

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

#195

Post by dragonwriter »

wyager wrote: post #167
dataflow wrote: post #126

Earlier quoted context omitted.

> Implementations are required to have every call consume some abstract resource towards exhausting some abstract finite limit If an implementation really wanted to, they could get around this by incrementing a "function call counter" that traps at, say, 2^64, rendering it effectively moot. I feel like these kinds of situations are where being practical might make more sense than being mathematically precise. Somethi…

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

The reason for the existing mandate is to be a problem for recursive programs, so it is a feature, not a bug, of the proposed refinement that it more reliably achieves that.

(Specifically, to prevent one implementation getting an optimization for them that leads people to rely on it, making code that blows up in practical use on other implementations, despite both being nominally correct implementations of the same spec.)

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

#196

Post by contravariant »

dunham wrote: post #175
samatman wrote: post #87

Earlier quoted context omitted.

Tail-call elimination applies to any function which calls another function as the last action. Turning this into a loop is only possible when the function calls itself, not when it calls another function, and not (naively) when two functions call each other in the tail position.

You can turn it into a loop with a case statement inside if you collect the connected component of tail called functions and make those the cases. But it’s gonna be a big function. You can split it up a bit if you use a trampoline, but then you lose some efficiency.

Though at that point you're basically just one step removed from making your own stack frame.

Which would definitely work, no doubts about that, but it might be nicer to just get it handled at a more fundamental level.

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

#197

Post by [deleted] »

nu11ptr wrote: post #89
samatman wrote: post #87

Earlier quoted context omitted.

Tail-call elimination applies to any function which calls another function as the last action. Turning this into a loop is only possible when the function calls itself, not when it calls another function, and not (naively) when two functions call each other in the tail position.

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?

[deleted]

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

#198

Post by robocat »

dwohnitmok wrote: post #103
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?

Happens a fair bit of time when parsing deeply nested structures (e.g. parsing deeply nested JSON structures) using mutually recursive parsers. I've generally resorted to either trampolining or explicit stacks.

> parsing deeply nested JSON structures

How likely is it that the depth of the JSON structure would exceed the maximum depth of the stack? This doesn't appear to be a compelling example to me.

It probably is a shame that it's called tail call optimisation since nobody wants to mandate low level details for an optimisation.

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

#199

Post by naasking »

JohnHaugeland wrote: post #191
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…

> Tail-calls is fundamentally something that the compiler _cannot_ solve. I don't see why. Compilers are how tail calls are literally always implemented. It's not like there's hardware support. What makes this impossible? . > The issue is that to avoid stack blow-up you need the engine to recycle stack frames. I mean, what's stopping you from just implementing a trampoline? . > The problem with this is that in WebAss…

Trampolines are a hack that penalizes the performance of any language that uses tail calls a lot, like functional languages (scheme, lisp, Haskell, etc).

You could also handle exceptions manually too, without VM support, but that too would incir considerable overhead.

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

#200

Post by naasking »

light_hue_1 wrote: post #149
kragen wrote: post #129

Earlier quoted context omitted.

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…

IIRC, one shot continuations can be made pretty efficient, effectively folding back into a single stack. If there's a simple way to safely express this in wasm that might be the right balance. If you want multishot continuations you'd need to explicitly clone the one-shot continuation.
Post reply on HN