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

#231

Post by systoll » Wed, Jul 13, 2022, 4:15 AM UTC

lloydatkinson wrote: post #163

Please don't let apple block this proposal like they did for browsers. We don't have tail calls because apple decided they couldn't be bothered to implement it.

Safari has tail-call optimisation.

We don’t have it elsewhere mostly because Google:

1. Agreed to implement it [it’s in ES6]

2. Implemented and shipped it behind a flag

3. Unshipped it.

4. Proposed something else [ https://github.com/tc39/proposal-ptc-syntax ]

Prior to that, Firefox had proposed a carve out for cross-realm calls, but then they didn’t bother implementing anything.

While apple is against Syntactic tail calls, they’re mainly just opposed to versions of it that would remove/unrequire the tail-call optimisation they already do: https://github.com/tc39/ecma262/issues/535

For the version of it that is backwards compatible, they wouldn’t need to do anything other than ignore the syntax. Their main concern is that it "could add confusion with very little benefit."

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

#232

Post by int_19h » Wed, Jul 13, 2022, 4:17 AM UTC

titzer wrote: post #228

int_19h wrote: post #223

Earlier quoted context omitted.

Then maybe we shouldn't be repurposing VMs written for JavaScript for that brand new thing? Ditch the baggage and do it right. Especially given that, if successful, wasm is basically the next JS, and will be around for decades.

I'm all for rewriting things from scratch. That's why I'm doing a new Wasm engine from scratch. But reusing TurboFan is how we took Wasm from concept to near-native performance, shipped in Chrome, in 2.5 years.

That's all well and good - but, again, the spec will be around for decades. Compromises made today to ship things faster means a lot of pain in those years ahead. I pity all the compiler writers who will have to implement relooper again and again.

But instead we'll probably do things like asm.js - that is, bless certain wasm patterns such that advanced VMs would be guaranteed to optimize them. And so everything will be way more complicated than it needs to be. Just like the JS stack today.

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

#233

Post by epidemian » Wed, Jul 13, 2022, 4:19 AM UTC

robocat wrote: post #198

dwohnitmok wrote: post #103

Earlier quoted context omitted.

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.

> parsing deeply nested JSON structures How likely is it that the depth of the JSON structure would exceed the maximum depth of the stack? This doesn't appear to be a compelling example to me. It probably is a shame that it's called tail call optimisation since nobody wants to mandate low level details for an optimisation.

> How likely is it that the depth of the JSON structure would exceed the maximum depth of the stack?

Not that unlikely i'd say, at lest if the stack size is unreasonably small.

For example, on nodejs, JSON.stringify() chokes with a nested array of 10K depth:

  > N=10_000; JSON.stringify(JSON.parse("[".repeat(N) + "]".repeat(N)))
  Uncaught RangeError: Maximum call stack size exceeded
      at JSON.stringify ()

Curiously, JSON.parse() is OK with arrays of 10M depth (and probably more). A difference of over 3 orders of magnitude between functions that seem pretty symmetrical at first glance.

Imagine that you build some software that lets users nest things —e.g., a circuit designer, a visual programming language, a UI builder, etc— and you wanna save these nested structures as JSON, or process them recursively. Pretty natural fit i'd say. Now, as a user, i'd be pretty upset if my magnum opus of a very complex circuit, or giant visual program, or very busy beast of UI art, starts creashing the program when exceeding a mere 10K elements. My computer has gigabytes of memory! And, presumably, there's a lot still available. But nope, a meager stack can ruin all the fun.

I personally think this is a pretty silly limitation to have on software, especially given today's memory sizes.

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

#234

Post by matheusmoreira » Wed, Jul 13, 2022, 4:22 AM UTC

lmm wrote: post #214

matheusmoreira wrote: post #208

Earlier quoted context omitted.

> the source emits an element by calling the sink to process it, the sink processes it and then recurses into the source for the next element I think I understood that concept but it still seems a bit strange to me. Doesn't that imply a potentially infinite stack of function calls? I've seen this idea in other functional program examples as well. Instead of having a sequence of instructions, they have a sequence of f…

> I think I understood that concept but it still seems a bit strange to me. Doesn't that imply a potentially infinite stack of function calls? Yes, which is exactly why tail calls are so important. Otherwise you'd stack overflow after processing the first few thousand elements of your stream. > I've seen this idea in other functional program examples as well. Instead of having a sequence of instructions, they have a…

Thanks, I think I have a better grasp now.

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

#235

Post by continuational » Wed, Jul 13, 2022, 5:22 AM UTC

azakai wrote: post #170

continuational wrote: post #50

Tail calls are super important for non-C like control flow, and it's great that it might be added. But what I really think wasm should focus on is to get near native performance (say, <50% overhead). Until that happens, the whole endeavor seems pointless to me.

Estimates vary (because benchmarks and use cases vary), but it's generally faster than 50%. That number was seen here, https://www.usenix.org/system/files/atc19-jangda.pdf (I assume that's what you refer to?) It's a good measurement, but it's from 2019, and it's just on 2 wasm engines. There are other estimates, like here: https://kripken.github.io/blog/wasm/2020/07/27/wasmboxc.html That tries to measure the fundamen…

That seems very promising. If it really is that good, wasm has a lot more potential in my eyes.

But e.g. sharp/vips ended up with a much worse result: https://www.libvips.org/2020/09/01/libvips-for-webassembly.h...

It may just be a matter of waiting for simd and threads though.

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

#236

Post by the_mitsuhiko » Wed, Jul 13, 2022, 5:50 AM UTC

miloignis wrote: post #66

coliveira wrote: post #48

Earlier quoted context omitted.

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.

Well wasm doesn't have exceptions right now either! The exceptions proposal is also in phase 3, like tail-calls. Right now wasm just supports traps, which can't be caught or inspected from within wasm code, and don't actually need to record stack frames (but the JavaScript host does in web browsers). I'm not sure what benefit exposing the wasm part of the stack for traps gives the JavaScript host side except perhaps…

Would be interested in what other solutions you envision. In production error reporting to services like Sentry relies on getting access to a stack and unlike a native runtime there is nothing one could do to create a stack without the engine’s support.

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

#237

Post by netheril96 » Wed, Jul 13, 2022, 5:56 AM UTC

MereInterest wrote: post #213

haberman wrote: post #204

Earlier quoted context omitted.

You don't want it to be implementation-specific whether tail call optimization is performed or not. The nightmare scenario is that you spend months writing a program that works great in browsers A and B, but when you roll it out to prod it immediately fails in browser C, which doesn't perform TCO. You only want to write code that depends on TCO if you can get a guarantee that TCO will be performed. This is the motiva…

This might be a silly question, but why is that a nightmare scenario? The exact same argument could be made for any compile-time optimization. If one compiler inlines a function where another doesn't, or unrolls a loop, or performs better constant propagation, any of those could impact the resource usage between the two compilers, leading to exactly that same scenario. But I wouldn't want to forbid improvements altog…

> The exact same argument could be made for any compile-time optimization.

No.

For other optimization, the difference is the speed of execution. For tail call optimization, the difference can be normal execution and stack overflow.

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

#238

Post by foldr » Wed, Jul 13, 2022, 6:20 AM UTC

epidemian wrote: post #233

robocat wrote: post #198

Earlier quoted context omitted.

> parsing deeply nested JSON structures How likely is it that the depth of the JSON structure would exceed the maximum depth of the stack? This doesn't appear to be a compelling example to me. It probably is a shame that it's called tail call optimisation since nobody wants to mandate low level details for an optimisation.

> How likely is it that the depth of the JSON structure would exceed the maximum depth of the stack? Not that unlikely i'd say, at lest if the stack size is unreasonably small. For example, on nodejs, JSON.stringify() chokes with a nested array of 10K depth: > N=10_000; JSON.stringify(JSON.parse("[".repeat(N) + "]".repeat(N))) Uncaught RangeError: Maximum call stack size exceeded at JSON.stringify ( ) Curiously, JSON…

TCO likely wouldn’t help here, as the parser is probably using non-tail recursion to build the nested arrays. (I haven’t looked at the code, but that’s the natural way to do it with a recursive descent algorithm.)

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

#239

Post by miloignis » Wed, Jul 13, 2022, 6:27 AM UTC

the_mitsuhiko wrote: post #236

miloignis wrote: post #66

Earlier quoted context omitted.

Well wasm doesn't have exceptions right now either! The exceptions proposal is also in phase 3, like tail-calls. Right now wasm just supports traps, which can't be caught or inspected from within wasm code, and don't actually need to record stack frames (but the JavaScript host does in web browsers). I'm not sure what benefit exposing the wasm part of the stack for traps gives the JavaScript host side except perhaps…

Would be interested in what other solutions you envision. In production error reporting to services like Sentry relies on getting access to a stack and unlike a native runtime there is nothing one could do to create a stack without the engine’s support.

If you control the compiler, you don't need the engine's support for exceptions (though you might want it for performance reasons) - emitting function prologues and epilogues that maintain debugging information like a call stack (or call trace in a ring buffer like some Schemes) would be one way.

I actually did this in my purely functional language, but had it off by default for performance reasons - if you hit an error at runtime, the debugging code would re-execute from the last checkpoint with debugging information turned on to construct the missing debug data, something I could only do because the language is side-effect free.

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

#240

Post by hahnchen » Wed, Jul 13, 2022, 6:45 AM UTC

slimsag wrote: post #211

Finally :) My coworker back in 2017 implemented the WebAssembly backend for the Go compiler[0], and noted at the time that WASM doesn't have any equivalent to setjmp/longjmp. As a result, Go's WebAssembly implementation actually emulates a register machine on top of the WASM stack machine. Quoting him (some parts omitted): > For example its architecture is a stack machine instead of a register machine. This means tha…

Wow sweet! How do you find cool coworkers like these?