Tell HN: We are trying to get tail calls into the WebAssembly standard • Hacker News Board

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

#131

Post by kragen » Tue, Jul 12, 2022, 7:48 PM UTC

OskarS wrote: post #127

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…

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…

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

Stack overflows are stopping you, if you implement Scheme calls as Wasm calls.

In Scheme, tail call elimination is not merely an optional "optimization", so the compiler can't opt to not do it when it's inconvenient.

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

#132

Post by marshray » Tue, Jul 12, 2022, 7:49 PM UTC

kevin_thibedeau wrote: post #121

lilyball wrote: post #95

Earlier quoted context omitted.

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.

State machines are known for a predilection to use `goto` extensively, but that does not make them 'spaghetti code'.

A state machine is, in fact, a well-understood method of applying structure to spaghetti.

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

#133

Post by kragen » Tue, Jul 12, 2022, 7:50 PM UTC

coliveira wrote: post #48

miloignis wrote: post #39

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.

It's more important for exception handling to be implementable than for TCE to be implementable, yes. But it's more important for TCE to be provided by the virtual machine (or, alternatively, for call and return to be manipulations of user-level state, as on traditional CPUs, rather than magic privileged operations as in Wasm) because you can implement exception handling with TCE but you can't implement TCE with exception handling.

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

#134

Post by User23 » Tue, Jul 12, 2022, 7:52 PM UTC

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?

It's useful anytime you can benefit from the performance advantages of replacing a full fledged function call with little more than a jump. One classic example is implementing an efficient VM.

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

#135

Post by kragen » Tue, Jul 12, 2022, 7:53 PM UTC

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?

In languages like Scheme, Haskell, OCaml, and Erlang it happens all the time, often when the user isn't aware of it; even when these languages have special looping constructs they are often implemented in terms of tail recursion, sometimes mutual tail recursion between several anonymous subroutines.

In languages like Scala, Java, C#, and Swift, it basically never happens.

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

#136

Post by kragen » Tue, Jul 12, 2022, 7:55 PM UTC

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.

This is usually a case where TCE doesn't help, in my experience, because most of the calls to sub-parsers aren't in tail position. This is especially unpleasant when you get bug reports of mysterious segfaults that turn out to be stack overflows...

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

#137

Post by OskarS » Tue, Jul 12, 2022, 7:57 PM UTC

marshray wrote: post #130

OskarS wrote: post #127

Earlier quoted context omitted.

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.

I don't mean to minimize anybody's work, I'm genuinely curious about why it can't be done. Like, what's stopping me from making a compiler that optimizes tail calls?

For instance: the C and C++ standards have very strict rules for how to handle floating point math, and compilers aren't allowed to deviate from that according to the standard. Which turns off all sorts of cool optimizations you can do. But of course, all modern compilers implement some version of "-ffast-math" which turns off those rules and allows for the optimizations. It's no longer standard C/C++, but that doesn't mean that switch can't exist. The compiler is a computer program, it can output anything it wants, regardless of what the standard says. Nobody is going to go to jail because you turned on -ffast-math. The code will still run just fine.

So, my question is, why can't you write a compiler with an option that's like "I don't particularly care that .stack changes, do the tail call optimization". A -ffast-math, but for tail calls. Is there a technical reason why you can't do this?

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

#138

Post by anfilt » Tue, Jul 12, 2022, 7:58 PM UTC

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…

What? Compilers handle tail calls all the time even in languages like C and higher level functional languages.

Its just a jmp? Does the wasm VM not have a jmp instruction?!?

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

#139

Post by merb » Tue, Jul 12, 2022, 8:03 PM UTC

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?

> 98-99% of the time it was the same function calling itself

well if the same function is in the "tail" it would still apply a tail call elimination.

But a lot of the time tail call eliminiation is only needed in some extreme cases. it can eliminate stack overflow exceptions by a big amount. C#'s new System.Text.Json would greatly benefit with tail call ops, because it often has a call chain that is recursive and does not call itself (its mostly like ReadObject, ReadObjectAsync, ReadObject, ReadBla, ReadObject, etc. and if the object has a ref to itself system.text.json often blows up.

In Java and Scala this thing can btw. also happen (and I've already seen it) however at least you can configure the stack size there and thus most often eliminate the problem somewhat.

it's an edge case, but one that would be cool to fix, since it makes code often more reasonable especially parsers.

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

#140

Post by Jtsummers » Tue, Jul 12, 2022, 8:03 PM UTC

AtNightWeCode wrote: post #128

You can use F# with WASM. I know F# convert recursive tail calls to loops but I understand this is another case. But shouldn't F# have the same problem?

I have not been following WASM generally, but my understanding after reading this:

Unlike regular machine language, WASM does not allow you to control the call semantics. That is, if you emit x86 machine instructions you can handle TCE entirely in your own compiler, the machine itself does not care.

WASM has special call instructions, these perform basically a conventional stack frame/call stack approach and you can't short circuit it. The closest you can get, which works fine for auto-recursive functions and maybe some detectable mutually recursive functions, is to convert tail calls into loops within the compiled WASM output. So recursive tail calls work fine in WASM if your compiler doesn't turn them into calls, but leaves them as a self-implemented (by the compiler) loop structure using whatever appropriate WASM instructions are available. This is fine for auto-recursive functions, but puts the burden at implementing TCE for them on the compiler writer. Which means you'll get it for some languages that compile to WASM, but not all. And only for the limited cases they support (probably restricted to auto-recursive and some mutual recursive circumstances).

What this proposal introduces is a new version of the call instruction that would be used in tail call positions. Then the WASM interpreters would do the work of actually combining the stack frames internally. Detecting that a call is a tail call is actually pretty straightforward for a compiler. Given that it is a tail call, it can emit (or not) the new call instruction and will get TCE "for free". It doesn't have to do a code transformation from recursive to looping, and it can be applied more broadly than just recursive circumstances.