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

91–100 of 300 posts

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

#91

Post by jhgb »

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?

For example pretty much any higher-order function that wants to do some decision-making and then hand over execution to one of several functions provided will want to hand over execution by means of a tail call, so that it doesn't unnecessarily change stack complexity for whatever algorithm is being run around that piece of code.

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

#92

Post by msla »

Spivak wrote: post #41
jhgb wrote: post #37

Earlier quoted context omitted.

> I'm a huge functional programming evangelist, but high-level stuff like this does not belong in a low level language bytecode like WASM. A tail call is a jump. Jumps are not "high-level stuff". They're very simple instructions. If WASM can't do a jump, it is actually WASM that you can't call "a low level bytecode".

WASM doesn't have jumps [1]. And it's not as low-level as you might expect. But even still you're assuming that low level means a specific model of computation a la PDP-11 that's as fictional as any other. https://webassembly.github.io/spec/core/syntax/instructions....

WASM isn't particularly low-level, in that it's a compiler's IR, with a few concomitant restrictions on how control flow is allowed to work. Here's a piece on those restrictions, and how they make implementation more difficult:

http://troubles.md/why-do-we-need-the-relooper-algorithm-aga...

> WebAssembly isn’t designed as a front-end language for general programming though, so what’s the problem? Well, WebAssembly does have some constraints, specifically it must produce code that is valid. WebAssembly is a stack machine, and you can’t jump to just any label since that label might point to code that pops too many values off the stack, or pops the wrong types off the stack, or pushes too many values onto the stack.

Also, to summarize another part, when a compiler targeting WASM sees control flow WASM can't directly express, it has to implement it in a loop-and-switch form, something called the Relooper algorithm; therefore, compilers taking WASM down to native code have to understand that, and undo it back into a performant form. This adds up to a lot of work most VMs don't require, hence the proposal to move WASM towards a control-flow model friendlier to tail-call optimization, which would bring it more in line with physical hardware.

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

#93

Post by labrador »

chmod775 wrote: post #88
labrador wrote: post #82

Earlier quoted context omitted.

I know but that's just bizarre. One function has it's own this and another doesn't so if my arrow function gets big and I want to make it a regular function I may have to rewrite it. Ugh. Edit: I'm thinking of cognitive load too. I like to eliminate load I don't need. Keeping track of this is not something I want to do with my life https://drpicox.medium.com/reducing-programmers-cognitive-ov...

> so if my arrow function gets big and I want to make it a regular function I may have to rewrite it. There's absolutely no reason to make an arrow function a regular function just because it goes past a certain number of lines. It really seems like you should become more familiar before forming an opinion. There's valid criticism to be made, but those aren't it.

I sometimes refactor code for purely aesthetic reasons. To each his own.

http://www.synergeticapplications.com/ergonomics.htm

By the way, I feel like I'm at a bar and you're negging me

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

#94

Post by keithwinstein »

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…

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. (There's no ".stack property" that would be added to Wasm itself.) It's true that the proposal amends the JS API (but only the JS API) to describe a traceStack=true option; from Wasm's perspective I understand that's just an ordinary exception that happens to include an externref value (just like any other value) to which Wasm attaches no special significance. The Web-based engines can attach an informative stack trace if they want, but there's no requirement preventing frames from having been optimized out. The non-Web engines won't have to think about this.

(3) I think the real reason that a Wasm engine can't implicitly make tail calls proper is that the spec tests forbid it, basically because they didn't want the implementation base to fragment by having some engines perform an optimization that changes the space complexity of a program, which some programs would have started to depend on. (The spec tests say: "Implementations are required to have every call consume some abstract resource towards exhausting some abstract finite limit, such that infinitely recursive test cases reliably trap in finite time. This is because otherwise applications could come to depend on it on those implementations and be incompatible with implementations that don't do it (or don't do it under the same circumstances.)")

But the issue is much weaker than "call stack is observable" -- it's more like "infinite recursion must trap eventually, but it can be nondeterministic when."

More discussion here: https://github.com/WebAssembly/spec/issues/150

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

#95

Post by lilyball »

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?

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.

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

#96

Post by bitwalker »

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?

One example would be in a parser, as various parsing functions would be invoked recursively until end of input, or until some non-matching input is encountered. In pretty much any scenario where you would use recursive functions, it is quite common to have mutual recursion between multiple functions. Not always of course, which is where the tail call elimination optimization is typically applied, but not being able to freely use mutual recursion to arbitrary depth turns out to be quite an annoying limitation.

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

#97

Post by ilaksh »

jhgb wrote: post #37
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…

> I'm a huge functional programming evangelist, but high-level stuff like this does not belong in a low level language bytecode like WASM. A tail call is a jump. Jumps are not "high-level stuff". They're very simple instructions. If WASM can't do a jump, it is actually WASM that you can't call "a low level bytecode".

I don't think web assembly is low level at all. Actually the name is confusing because it's really not much like an assembly language.

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

#98

Post by kaba0 »

convolvatron wrote: post #74
kamaal wrote: post #47

Earlier quoted context omitted.

I think its Rich Hickey who said something to the effect that tail calls are so fundamental that the underlying platform should be providing them.

tail calls are so fundamental that its trivial to build a call-push, return-pop stack calling protocol on top of them, but not the converse

Could you point me to some further info on this?

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

#99

Post by asabla »

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.

Post reply on HN