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

151–160 of 300 posts

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

#151

Post by light_hue_1 »

kragen wrote: post #135
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?

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.

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

Scalaz and cats use tail calls extensively and wouldn't be possible without them.

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

#152

Post by kragen »

light_hue_1 wrote: post #151
kragen wrote: post #135

Earlier quoted context omitted.

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.

> In languages like Scala, Java, C#, and Swift, it basically never happens. Scalaz and cats use tail calls extensively and wouldn't be possible without them.

How does that work on the JVM?

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

#153

Post by jillesvangurp »

jolux wrote: post #38

Tangential but what's the status of garbage collection and DOM manipulation in WASM? Are we ever getting those? I understand it's a high-value technology without them, but I'm interested in writing full apps in say, OCaml (so I'm glad to hear that WASM is getting TCE!).

Kotlin 1.7.0 shipped with a WASM compiler recently that currently requires some experimental flags in Chrome to enable features related to garbage collection, threads, and memory management. So, it looks like this is progressing nicely. Once this lands, I imagine there will be a whole range of languages that will be able to make good use of this.

As for DOM manipulation, that seems to work well enough but I'm sure there are further improvements coming.

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

#154

Post by kragen »

light_hue_1 wrote: post #149
kragen wrote: post #129

Earlier quoted context omitted.

Your concern with burgeoning standards reinforcing the browser duopoly is well-founded, but unfortunately you're sticking your stake in on the wrong side of the dragon here. It sounds like you're confused about how Wasm works, and you imagine that it's like a normal assembly language, with calls and returns implemented by the compiler using instructions that push and pop a stack in memory. You're probably right that…

> But, as Scheme has demonstrated, once the virtual machine supports tail calls, a compiler can implement exceptions and cooperative multithreading by way of compiling to continuation-passing style. So this is not the beginning of a long series of extensions; it's Lambda the Ultimate Goto. Well to an extent. CPS can be extremely slow. Scheme shows that continuations will also be needed down the road. But yes, that's…

In theory CPS is very fast indeed, but of course our hero can easily collapse attempting to cross the chasm of the Sufficiently Smart Compiler. I suspect Chicken using CPS for everything is the main reason http://canonical.org/~kragen/urscheme, which doesn't implement call/cc, is so much faster than Chicken.

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

#155

Post by dmkolobov »

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?

If you’re implementing a compiler for a language like Haskell, then everything is compiled into mutually-recursive tail calls.

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

#156

Post by kevin_thibedeau »

marshray wrote: post #132
kevin_thibedeau wrote: post #121

Earlier quoted context omitted.

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.

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

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

#157

Post by jjtheblunt »

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…

> 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

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

#158

Post by pygy_ »

leoc wrote: post #109
pygy_ wrote: post #6

Earlier quoted context omitted.

The standard mandates it, and the V8 team implemented it, shipped it behind a flag, then unshipped based on reasons that initially seemed and ultimately were proven fuddy, when WebKit shipped PTC, and the world didn’t fall down. The reason actual why it was withdrawn is that it would have required expensive changes to Microsoft’s Chakra (the calling conventions were incompatible). Then Edge died... and Google didn’t…

These absolute bozos. A Web Assembler that can't do jumps. What a show.

My comment is about ES6 proper tail calls. WASM is another story

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

#159

Post by [deleted] »

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…

[deleted]

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

#160

Post by taeric »

jjtheblunt wrote: post #157
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 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.
Post reply on HN