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

181–190 of 300 posts

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

#181

Post by saagarjha »

jhgb wrote: post #85
shadowgovt wrote: post #81

Earlier quoted context omitted.

You might be interested in a fascinating game called TIS-100 by Zachtronics. The game is a lot of things, but a core premise is that it imagines a computer from a time approximately parallel to the PDP-11 that took the form of small compute components that were connected to each other instead of a monolithic central processor. It's a fun game, and it sort of raises the question of which is the "abomination[s] forced…

> and it sort of raises the question of which is the "abomination[s] forced on us as an accident of history." What I meant by that is the legacy of AMD64 having thousands of instructions, many of them with arbitrary opcode encoding, half-assed SIMD ISA instead of a proper vector ISA, and the ability to emulate an 8086, all purely for reasons of backwards compatibility. If you started designing a computing ecosystem c…

This would be kind of a sad direction to go in if we didn’t have any constraints, since we already have new architectures going in this direction anyways. When you take the crust of the ISA off though all processors look similar and that’s where the interesting bits lie.

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

#182

Post by smolder »

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…

JavaScript is already a GC'd language effective at UI, so it doesn't seem to me like there's a strong need for wasm to fill the same role. Rather, it seems to me like wasm is better suited to accelerating processing-heavy tasks those rich web apps depend on, like custom [de]compression, ML models, data processing, image processing or simulation of some kind.

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

#183

Post by xenadu02 »

MikeHolman wrote: post #115
ufo wrote: post #26

Earlier quoted context omitted.

Wasm is too high level to implement your own tail calls. The WASM virtual machine handles the call stack & function calling convention, instead of being something that the code itself is responsible for. This means that the compiler can't implement tail calls; WASM doesn't allow a jump instruction in one function to jump into a different function. There are a bunch of reasons why WASM was designed to be higher level…

The compiler absolutely can implement tail calls, I don't know why this keeps getting thrown around. Adding a high-level directive in the spec doesn't enable the compiler to do anything, it just enforces it. The only thing preventing it is browser vendors wanting the .stack property to stay well behaved, but that isn't required by the spec and certainly isn't relevant for non-browser targets.

Most hardware architectures (and software ones based on them) the compiler controls the calling convention: how the stack is managed, what gets pushed there vs passed in registers, and so forth. The architecture may or may not have helpers like specific "return from subroutine" instructions that help manage the stack... but a lot of things are under the compiler's control.

WASM is not like that. It doesn't support jumps or that kind of manipulation. It does not expose enough control over the stack and calling conventions.

In theory could the compiler emit a virtual machine that simulates another machine where it _can_ control these parameters? Sure. It can rewrite it all into a huge loop-and-switch statement. But that is not going to result in anything close to efficient native code. By expressing tail calls directly in WASM the JIT can generate much more efficient code that takes advantage of the platform's native calling convention and tail calls can be _actual_ tail calls on the hardware.

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

#184

Post by xenadu02 »

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?

Self recursion is a special case that WASM backend targets can more or less efficiently resolve the same way a human can convert a recursive function into a non-recursive one: explicitly put arguments onto your own simulation of a stack and perform the computation in a loop.

Unfortunately self recursion is only a subset of tail calling.

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

#185

Post by wtetzner »

vbezhenar wrote: post #84
RHSeeger wrote: post #11

Earlier quoted context omitted.

> If you need to add two arrays of numbers, use loop or array addition There are plenty of algorithms that make more sense when expressed using recursion. Iterating over a list of numbers generally isn't one of them. But walking a tree is a good example.

Those algorithms usually use non-tail recursion. Most tail recursion uses usually is trivial to rewrite in a loops.

> Most tail recursion uses usually is trivial to rewrite in a loops.

Except for tail calls that aren't self-calls. Which for code I write is actually fairly frequent.

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

#186

Post by Retr0id »

wyager wrote: post #167
dataflow wrote: post #126

Earlier quoted context omitted.

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

It is implicitly already mandated, depending on how finite your finite limit is.

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

#187

Post by egberts1 »

egberts1 wrote: post #113

“proposal to move WASM towards a control-flow model friendlier to tail-call optimization, which would bring it more in line with physical hardware.“ perhaps it is nigh time to bring the CPU hardware closer to the current WASM design. Might simplify a lot of issues related to pipelining, cache-busting, and Spectre-like mitigations, not to mention crazy varied breakout of legacy microcode to subfunctions (Intel, I am l…

meanwhile, the new Spectre-BTI variant just now embroils both AMD and Intel on media.

Naysayer (downvoters) seems sure that JavaScript engine having this new tailcall would not be impacted. Of course, I would be talking about the generated microcode, not the JavaScript LIR bytecode.

https://arstechnica.com/information-technology/2022/07/intel...

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

#188

Post by usrn »

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…

WebAssembly is actually very high level. You need tail call support if you want to preserve the original structure of the program (which seems to be the intention.) I think you can get around it with eg CPS but then you'd get something more like traditional assembly.

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

#189

Post by kbelder »

labrador wrote: post #7

I'm using Blazor (C#) WebAssembly and I'm really wishing it could do DOM manipulation. My favorite tool for that is Dart, so I'm working on marrying C# and Dart for my client solutions.

I was struck by how reactionary some of the responses to this comment are. Many people seemed to feel obliged to firmly question your preferences. Kind of odd, I don't normally notice that as much here on HN.

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

#190

Post by jolux »

wtetzner wrote: post #80
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!).

While I'm also looking forward to TCE and GC for WASM, you can build full apps in OCaml now via js_of_ocaml.

I'm aware of js_of_ocaml and Reason, but I want it to run closer to native speed and use multithreading eventually.
Post reply on HN