Live data from Hacker News

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

news.ycombinator.com

121–130 of 300 posts

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

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

State machines can often be implemented with a set of functions that each handle a single state and then tail-call into the function for the next state.

This is just a fancy form of spaghetti code. Don't do it unless you actually need the performance.

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

#122

Earlier quoted context omitted.

I am genuinely asking, is your position that a compiler cannot convert: g(): a = 1+1; b = 2+a; print(b); return f() into code that does not allocate stack space and just reuses the frame allocated for g()?

It depends on the calling convention used -- whether it is caller clean-up or callee clean-up. With caller clean-up, the stack pointer is left below the argument list when the function returns. With callee clean-up, it gets popped above the argument list. You can perform tail calls naturally if it's callee clean-up. (With caller clean-up, a compiler might hypothetically pull off a tail call if the callee's argument l…

Thanks, that explains the trouble I was having. I was thinking about it without any consideration to calling-convention.

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

#123

Earlier quoted context omitted.

I haven't messed with .stack, but on first impression I agree with you that it seems like a mistake. Even if it wasn't observable though, I think guaranteed tail-call elimination via either a new opcode or having it be a required property of regular calls in the spec (we already missed that ship, of course) is important. Without it, proper compilation and execution of some languages on wasm would depend on an otherwi…

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.

Maybe I'm naive and I surely don't know anything about the WASM spec, but aren't CPUs implementing both exceptions and tail call elimination as gotos (some jump machine code instruction) ? Exceptions might have to pop some frame, TCE doesn't.

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

#124
post #99
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 one of your main concerns is performance, then all I can say is don't use Blazor. WASM will never be able to compete with regular JS so long as it has to go through an interop layer, plus it has to send down and parse an entire interpreter before it can even start looking at your actual UI and business logic. Server Side has to wait for a server response for every single action you take, and any small drops can make the entire thing sluggish, or even buggy.

That's not to say it isn't cool and can't work for some projects where say, development speed is more important, but performant it just aint.

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

#125

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.

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 intensive, say x86 virtualization like I believe apignotti is at Leaning Tech, I think it's fair to describe the problem as unsolvable by the compiler.

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

#126

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…

Heya, (1) Thank you for implementing this in JSC!! I hope they take it, it makes it into Safari, and the tail-call proposal advances. (2) I don't think you are exactly right about the call stack being observable via thrown exceptions. There's no formal spec for the v3 exceptions proposal yet, but in the documents and tests, there's nothing that would change in WebAssembly core to make the call stack observable. (Ther…

> 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. Something like "each function call must consume at least N bits of memory" or something concrete like that. Or heck, "implementations may not perform tail-call optimization" or even "implementations must be able to reconstruct the full logical call stack at any point".

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

#127
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…

I don't quite get your point here. Suppose I write a compiler to compile Scheme to WASM. I would have write it so that it does proper tail calls, otherwise it wouldn't be Scheme. What's stopping me? Would the browsers not run the code? Like, yeah, it would change .stack, but who cares?

Same thing applies, I think, to any other language compiled to WASM. C/C++ compilers regularly inline huge amounts of the code when optimizations are turned on, as well as do tail-call optimization. I haven't tried, but I would assume that they do that for WASM just as they do for x86 or ARM or whatever other build target I choose. As long as my users are ok with this (and they presumably are, otherwise they wouldn't turn optimizations), what's the problem, exactly?

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

#129
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 that's how it should have been designed.

But that is not how Wasm works. The stack is not in Wasm's "linear memory". (This makes it much easier to compile access to local variables efficiently.) Calls, returns, and in a sense exceptions in Wasm are provided by the virtual machine at a fundamental level in a way that makes it impossible for a compiler targeting Wasm to implement tail calls, call/cc, or cooperative multithreading, except by compiling your entire program into a single function, which ruins the performance of existing Wasm implementations.

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.

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

#130
post #127

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…

I don't quite get your point here. Suppose I write a compiler to compile Scheme to WASM. I would have write it so that it does proper tail calls, otherwise it wouldn't be Scheme. What's stopping me? Would the browsers not run the code? Like, yeah, it would change .stack, but who cares? Same thing applies, I think, to any other language compiled to WASM. C/C++ compilers regularly inline huge amounts of the code when o…

> yeah, it would change .stack, but who cares?

You might enjoy participating in an interoperable standardization process sometime.

Post reply on HN