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.
Tell HN: We are trying to get tail calls into the WebAssembly standard
121–130 of 300 posts
Re: Tell HN: We are trying to get tail calls into the WebAssembly standard
#122Earlier 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…
Re: Tell HN: We are trying to get tail calls into the WebAssembly standard
#123Earlier 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.
Re: Tell HN: We are trying to get tail calls into the WebAssembly standard
#124I'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.
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
#125Earlier 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.
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
#126Earlier 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…
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
#127Sorry 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…
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
#128Re: Tell HN: We are trying to get tail calls into the WebAssembly standard
#129Sorry 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…
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
#130Earlier 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…
You might enjoy participating in an interoperable standardization process sometime.