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

161–170 of 300 posts

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

#161

Post by jjtheblunt »

taeric wrote: post #160
jjtheblunt wrote: post #157

Earlier quoted context omitted.

> Tail-calls is fundamentally something the the compiler _cannot_ solve. How does the famous 1977 Guy Steele paper on compilers optimizing tail calls not apply? https://dl.acm.org/doi/10.1145/800179.810196

My guess is that this is assuming that the compiler can rewrite a return into a jump. That is, these compilers have control over the stack on the machine.

compilers always have control over the stack on the machine: they generate the code which realizes the notion of a stack (and happily usually have dedicated registers to use for that generated code)

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

#162

Post by taeric »

jjtheblunt wrote: post #161
taeric wrote: post #160

Earlier quoted context omitted.

My guess is that this is assuming that the compiler can rewrite a return into a jump. That is, these compilers have control over the stack on the machine.

compilers always have control over the stack on the machine: they generate the code which realizes the notion of a stack (and happily usually have dedicated registers to use for that generated code)

Not something compiling to WASM. Nor something compiling to JVM Bytecode.

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

#164

Post by marshray »

kevin_thibedeau wrote: post #156
marshray wrote: post #132

Earlier quoted context omitted.

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.

The point is that tail calls obscure the transitions between states by spreading it everywhere.

I'm not too clear on how one would implement a state machine without "spreading the transitions everywhere". Can you share a link to some example code showing the format you prefer?

Typically, we'd see the code that implements the logic for each state gathered together. Since this is where the outgoing transitions get decided, the transitions end up being distributed across their originating states.

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

#165

Post by Jtsummers »

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 is the mainstream browser with proper tail calls implemented. Was there some historical point where Apple blocked it and so others followed along but then Apple turned around and did it anyways?

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

#166

Post by eloff »

kevin_thibedeau wrote: post #156
marshray wrote: post #132

Earlier quoted context omitted.

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.

The point is that tail calls obscure the transitions between states by spreading it everywhere.

That doesn't compute for me. You'd need to give an example for me to understand you.

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

#167

Post by wyager »

dataflow wrote: post #126
keithwinstein wrote: post #94

Earlier quoted context omitted.

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…

> Implementations are required to have every call consume some abstract resource towards exhausting some abstract finite limit 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. Somethi…

> each function call must consume at least N bits of memory

This is going to be a problem for any long-running recursive program. Why would we mandate this?

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

#168

Post by discreteevent »

munificent wrote: post #105
smolder wrote: post #101

Earlier quoted context omitted.

I'm likely in the minority in my thinking, but I don't think targeting wasm with managed languages is such a great use case for wasm anyway, and so it wasn't worth building in GC to support. For the times you want to, something light like reference counting should be easy enough.

I'm biased since I work on a managed language that targets the web, but I strongly believe that it is a great use case for WASM. Most programs targeting WASM are client-side apps with rich user experiences and I believe all but a small fraction of users would be better served implementing rich UIs in managed languages. Doing UI work in C++ (which I have done plenty of) is a special exercise is pain for almost no upsi…

I went back to that pain a few years ago after many years away from it. After a few months I got right back in the swing of things. Spending my days arranging and solving little memory ownership problems.I got to thinking: "This is programming". And I didn't really mind it.

But every so often I had to be honest and remind myself of what I had noticed at the beginning: Thinking about and managing memory is a colossal waste of time, even with smart pointers and the like - The machine can do that and has been able to do it efficiently for most things for a long time.

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

#169

Post by jjtheblunt »

taeric wrote: post #162
jjtheblunt wrote: post #161

Earlier quoted context omitted.

compilers always have control over the stack on the machine: they generate the code which realizes the notion of a stack (and happily usually have dedicated registers to use for that generated code)

Not something compiling to WASM. Nor something compiling to JVM Bytecode.

If WASM and JVM Bytecode have a goto, then the compiler can use it. Anyway, if you've never read that paper i linked to above, i do believe you'll find it mind-blowingly cool stuff. not kidding.

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

#170

Post by azakai »

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 fundamental overhead of wasm's sandboxing as opposed to a specific wasm VM, and it finds just 14%.

Post reply on HN