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

61–70 of 300 posts

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

#61

Post by bordercases »

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.

No post body was provided.

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

#62

Post by nynx »

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…

.stack definitely seems like a mistake in the context of Webassembly. I’d be interested in seeing the justification for it.

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

#63

Post by [deleted] »

jhgb wrote: post #56
shadowgovt wrote: post #52

Earlier quoted context omitted.

Jump as a concrete implementation is easy to understand (it's just math on a program counter). But code is both a mechanical implementation and an abstract, often mathematical, concept. In the concept space, jump is as abstract as call, variable assignment, operator evaluation, etc. A Von Neumann machine is but one way to implement an abstract mathematical / conceptual machine. In the mathematical space, there's no "…

Possibly, but when I talk about "low-level stuff", I usually imagine very concrete things that are suitable for physical hardware implementation. Things like what the simplest RISC-V chip is designed to do. Unlimited jumps definitely are one of those things. Notions of stack frames or block structured languages (limitations on jumps) etc. definitely aren't among them. So I couldn't possibly ever consider something li…

[deleted]

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

#64

Post by k__ »

Kaze404 wrote: post #51
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!).

Have you looked into ReasonML by any chance?

I lost track of it since the Reason/ReScript split.

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

#65

Post by munificent »

shadowgovt wrote: post #52
jhgb wrote: post #46

Earlier quoted context omitted.

I never expected WASM to be low-level to begin with, so I don't believe it could ever possibly be "as low level as I might expect". Something like NaCl (the original one) perhaps could have been called "low level". > But even still you're assuming that low level means a specific model of computation a la PDP-11 that's as fictional as any other. I don't see how jumps are "fictional". Plenty of CPUs have them. Even act…

Jump as a concrete implementation is easy to understand (it's just math on a program counter). But code is both a mechanical implementation and an abstract, often mathematical, concept. In the concept space, jump is as abstract as call, variable assignment, operator evaluation, etc. A Von Neumann machine is but one way to implement an abstract mathematical / conceptual machine. In the mathematical space, there's no "…

> Jump as a concrete implementation is easy to understand (it's just math on a program counter).

This doesn't take into account what happens to memory on the stack if you jump into or out of the scope of a local variable. You can say that memory and initialization is not the implementation's problem and rely on the compiler to emit instructions that correctly adjust or initialize the stack before and after jumps. Then, yes, you get a very simple jump implementation.

But you also get an architecture that must either do stack analysis before it can safely run code, or you get an unsafe architecture. Those are both valid choices (the JVM does the former and native architectures do the latter), but there are real trade-offs with them.

A third way, that WASM does, is to say that control flow isn't simple, but that you get safe stack management for free with it.

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

#66

Post by miloignis »

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.

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 easing debugging? (though that is important, I think there are other valid solutions for that)

To be clear, I do want wasm to support the major language use cases, and I think implementing exception support is a good (though tricky, see the exceptions proposal) idea.

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

#67

Post by Jtsummers »

202206241203 wrote: post #34

Why not focus on features that would unlock better integration of actual mainstream languages - Java, C#, Python etc.? Let functional programmers discuss monoids on their endofunctor forums or something.

Recursion has been a part of programming and programming languages for a very long time, and not just the functional ones. See ALGOL for recursion from very early on.

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

#68

Post by munificent »

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…

> Reference types maybe. But I've yet to see a convincing argument as to why they are absolutely necessary.

Are you referring to WASM GC here (or managed memory in general)?

If so, I think the main compelling reason is interop. Without GC in underlying architecture, any managed language targeting WASM must include its own runtime and GC. If you then want to write a polyglot program using multiple languages, you now have a single WASM executable containing multiple garbage collectors each managing their own objects. If you end up with cycles between those different managed heaps, you can end up in a situation where the GCs are unable to reclaim memory because they don't understand cross GC cycles.

This is why Chrome did Oilpan [1]: so that they could more easily handle cycles between the DOM, JS heap, and (aspirationally at the time) Dart VM heap.

A more general user-value proposition argument is that putting the GC in the WASM implementation means any improvements made to it are amortized across all managed languages that target WASM. Also, it makes applications written in managed languages and compiled to WASM smaller because they don't have to ship a runtime and GC with the app.

[1]: https://chromium.googlesource.com/v8/v8/+/main/include/cppgc...

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

#69

Post by shadowgovt »

jhgb wrote: post #56
shadowgovt wrote: post #52

Earlier quoted context omitted.

Jump as a concrete implementation is easy to understand (it's just math on a program counter). But code is both a mechanical implementation and an abstract, often mathematical, concept. In the concept space, jump is as abstract as call, variable assignment, operator evaluation, etc. A Von Neumann machine is but one way to implement an abstract mathematical / conceptual machine. In the mathematical space, there's no "…

Possibly, but when I talk about "low-level stuff", I usually imagine very concrete things that are suitable for physical hardware implementation. Things like what the simplest RISC-V chip is designed to do. Unlimited jumps definitely are one of those things. Notions of stack frames or block structured languages (limitations on jumps) etc. definitely aren't among them. So I couldn't possibly ever consider something li…

To be clear, I deleted that comment because it was inaccurate. GLSL has break, continue, and return, which are flow-control statements. It excludes goto, and my explanation for why it excludes goto is probably incorrect (but I don't have time today to rabbit-hole on why goto was excluded or why the SIMD architecture can support break and continue just fine while excluding goto).

> In case of sequential machines, I don't consider removal of features that makes programs unnecessarily long "making the machine even more low-level", that's just "making the machine dumber"

You may be interested to consider how incredibly complex the modern x86 architecture is to implement because it supports sequential program execution as a core invariant principle. As a result, modern computers (which strive to be faster than a PDP-11) have to do a massive amount of work to parallelize that sequential code because parallel execution is the only frontier of fast computation that remains. They literally rewrite the opcodes on the fly into something that can be SIMD'd and do branch prediction, where code is run speculatively just to discard the result. All to support the idea that deterministic flow control should be possible in 2022. It's a brilliant fantasy the chipset manufacturers have constructed for us so we don't have to reframe our thinking.

I think I get what you're saying, but in modern times calling jump "low level" (or, for that matter, calling branching in general low level) is a very "Do you think that's air your breathing?" kind of position. I'm not aware of anyone seriously considering approaching the challenge of all this implementation complexity by throwing out fundamental assumptions of our PDP-descendant instruction sets and saying "Here's a new machine code, it's designed for parallel execution, the first assumption you must throw away is the order in which any of these instructions are executed."

But I suspect we're getting very close to that day.

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

#70

Post by jhgb »

shadowgovt wrote: post #69
jhgb wrote: post #56

Earlier quoted context omitted.

Possibly, but when I talk about "low-level stuff", I usually imagine very concrete things that are suitable for physical hardware implementation. Things like what the simplest RISC-V chip is designed to do. Unlimited jumps definitely are one of those things. Notions of stack frames or block structured languages (limitations on jumps) etc. definitely aren't among them. So I couldn't possibly ever consider something li…

To be clear, I deleted that comment because it was inaccurate. GLSL has break, continue, and return, which are flow-control statements. It excludes goto, and my explanation for why it excludes goto is probably incorrect (but I don't have time today to rabbit-hole on why goto was excluded or why the SIMD architecture can support break and continue just fine while excluding goto). > In case of sequential machines, I do…

Maybe it was inaccurate but I got what you were trying to say -- that "incoherent execution" is difficult on SIMD machines.

> You may be interested to consider how incredibly complex the modern x86 architecture is to implement because it supports sequential program execution as a core invariant principle. As a result, modern computers (which strive to be faster than a PDP-11) have to do a massive amount of work to parallelize that sequential code because parallel execution is the only frontier of fast computation that remains.

I'm aware what recent CPUs do with ISA instructions. That flies very badly in the face of the minimum complexity principle as well. The amount of physical resources dedicated these days to making your legacy code run just slightly faster is exceptionally wasteful.

> but in modern times calling jump "low level" (or, for that matter, calling branching in general low level) is a very "Do you think that's air your breathing?" kind of position

Well, it's low-level for the kind of minimum complexity system that I'd consider ideal. Not necessarily for the abominations forced on us as an accident of history.

Post reply on HN