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

251–260 of 300 posts

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

#251

Post by dragonwriter »

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?

> Understood, but in practice how often does that really happen?

In functional code written where general tail call elimination (or special tail call operations) are available, non- or mutually-recursive tail calls are not uncommon.

Heck, non-recursive (potentially fairly nested) tail calls are common in languages without any optimization for it. Anytime you see something like “return f(x)” (or, because operators are implemented via special methods, even “return x+y”) in Python, for instance, you've got a tail call.

If it isn't direct or mutual recursion, it has to be a pretty degenerate case to blow the stack even without elimination, so elimination is must necessary for those cases. But other cases bene for from not having the extra memory usage and reducing pushing stuff onto and popping it off of the stack.

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

#252

Post by dragonwriter »

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…

> Compilers are how tail calls are literally always implemented.

WASM doesn't have the same set of operations as a typical CPU. It's not something a compiler to WASM can do.

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

#253

Post by bjourne »

samatman wrote: post #87
nu11ptr wrote: post #86

Earlier quoted context omitted.

> Tail-calls is fundamentally something that the compiler _cannot_ solve Possibly a stupid question as I haven't given this much thought, but I thought tail call elimination could be used to convert recursive calls in tail position into loops. Could a compiler not do this (like Scala does, for example)?

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.

If f1 calls f2 that calls f1 why can't the compiler inline f2 into the body of f1? It's not so complicated if the compiler has annotations or other hints to guide it.

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

#254

Post by samatman »

bjourne wrote: post #253
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.

If f1 calls f2 that calls f1 why can't the compiler inline f2 into the body of f1? It's not so complicated if the compiler has annotations or other hints to guide it.

I once wrote an interpreter in continuation-passing style, meaning every final line of a function called the next function in the interpreter, passing a continuation and error continuation on.

Such a program never returns until it finishes interpreting, and can make an unlimited number of such calls.

This is a bad idea without TCE.

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

#255

Post by jacobmischka »

diarrhea wrote: post #244
jacobmischka wrote: post #24

Neat! This proposal caused me a lot of headaches, mechanizing its specification was the primary contribution of my Master's thesis a couple years ago[1]. I forgot until rereading it just now, but doing so caught a typo in the proposal specification[2], my extremely minor contribution to advancing WebAssembly. Glad to see it finally moving forward after stalling for so long! Excellent work! [1]: https://github.com/jac…

That might be the shortest (in word count) Master's thesis I have ever seen!

Ha well the mechanization was a nontrivial amount of work (for me at least) and was considered part of it too. If it's still short despite that, then welp I guess I got lucky somehow.

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

#256

Post by randomswede »

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…

There are probably WebAssembly-specific things I am unaware of. So, the following is a general "TCO" discussion.

I normally consider TCO something that is a compiler feature. Replace a call to the head of yourself, with a jump (possibly to just after the "pull the arguments from the call stack to where the code wants it" prologue), making sure that the correct locals are present where they need to be.

Well, that's for self-TCO. General TCO is definitely trickier (probably requires juggling stack allocations so as to ensure that the tail-called function has enough space for all that it needs).

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

#258

Post by afiori »

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…

There are two compilers involved, Source to Wasm and Wasm to native (usually JIT).

The second could easily optimize tail calls but it is required not to do so to increase reliability (all implementations need to agree which calls are tail calls that should be optimized and the simplest way to agree is to never do it) as otherwise a Wasm modules could work fine on an implementation and be unusable in another.

The first compiler cannot, the only possibility is to use whole-program transformations that significantly degrade performances.

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

#259

Post by simiones »

aliceryhl wrote: post #257

Why do we need an explicit construct for this as opposed to e.g. having the compiler replace the tail call with a goto back to the beginning of the function?

This was discussed elsewhere in the thread as well - the main problem is TCO support between multiple functions - e.g. when visiting a tree with nodes of various types, such that you have visitSumNode(&total) -> visitChildren(&total) -> visitMinusNode(&total) -> visitChildren(&total) -> ...

Since WebAssembly has a concept of functions, and doesn't allow jumps outside of the current function for security reasons, a compiler can't eliminate tail calls across functions (unless it can in-line all of those function calls, which isn't always possible, nor it is always the best performance).

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

#260

Post by bjourne »

samatman wrote: post #254
bjourne wrote: post #253

Earlier quoted context omitted.

If f1 calls f2 that calls f1 why can't the compiler inline f2 into the body of f1? It's not so complicated if the compiler has annotations or other hints to guide it.

I once wrote an interpreter in continuation-passing style, meaning every final line of a function called the next function in the interpreter, passing a continuation and error continuation on. Such a program never returns until it finishes interpreting, and can make an unlimited number of such calls. This is a bad idea without TCE.

Why couldn't the compiler inline the whole interpreter?
Post reply on HN