|
|
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 make it (again) so complex that no-one can create an alternative. We shouldn't have GC, Exceptions or Tail calls in WASM, as long as the compiler can provide them. What we should have is multi memory support and memory read permissions, because without them WASM lacks basic security primitives.[1] Reference types maybe. But I've yet to see a convincing argument as to why they are absolutely necessary. Everything else (as long as it can be done by the compiler) is just bloat. 1. https://www.usenix.org/conference/usenixsecurity20/presentat...
|
|
 |
|
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 (and JavaScript) the call stack is observable via the .stack property of thrown exceptions. Since an implicit conversion would be observable engines cannot simply optimize the problem away, and that is the reason why new opcodes (return_call/return_call_indirect) are actually required at the WASM level. For the specific case of direct calls (return_call opcode) the compiler could solve the problem by inlining, with some luck. But for the case of return_call_indirect there is no other possible solution.
|
|
|
|
Fair enough.
Sounds more like an issue with .stack being an observable property though. I've long suspected exceptions making it into WASM being it's million dollar mistake, and this further confirms it.
|
|
|
|
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 otherwise invisible property of the engine - that is, tail call elimination isn't just an optimization, it's a critical aspect of language semantics that needs to be guaranteed to be relied on.
|
|
|
|
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.
|
|
|
|
.stack definitely seems like a mistake in the context of Webassembly. I’d be interested in seeing the justification for it.
|
|
|
|
Throwing in my 2 cents to agree with apignotti - as someone who has implemented a compiler for a functional language that emits wasm, it is not possible to solve this performantly in the compiler. Because wasm only has structured control flow & no way for user code to modify the wasm stack, there isn't any good way to tail call between multiple independent functions, particularly dynamic function calls. Simple tail recursion of a function calling itself is simple enough and can be implemented in the compiler (and I did), but that's it, and not enough to correctly implement Scheme, for instance. I also want the wasm standard to remain as simple as possible, but this isn't a very complex addition and it is required for reasonable performance for both functional languages as well as C++20 features like coroutines, as mentioned by the article.
|
|
|
|
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 than native assembly. One is that they want it to be more compact to save bandwidth when downloading via the internet. Another is that they want to make it faster to compile down to native code; one way they do this is that the control flow is more structured, for example it forbids irreducible control flow graphs. There is also the matter of safety. WASM defines several validation constraints that are checked before the bytecode is run e.g.: the target of a jump instruction must be listed in labels list. If WASM were too low level, it wouldn't be possible to do the safety checks they want.
|
|
|
|
> 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...
|
|
|
|
Compilers can easily lower tail recursion into loops, but not general tail calls between arbitrary (possibly unknown, indirect) functions. The best they can do are trampolines, which come with a high performance cost.
|
|
|
|
We shouldn't have GC, Exceptions or Tail calls in WASM, as long as the compiler can provide them.I’m not a compiler guy, but spent my time with runtimes closely, and can say that befriending GCs/RCs, exceptions, continuations, etc between them was my least favorite part. That said, wasm is already a potential target for different runtimes built with no common vm in mind, so interop headaches are imminent either way.
|
|
|
|
> I'm a huge functional programming evangelist, but high-level stuff like this does not belong in a low level language bytecode like WASM. A tail call is a jump. Jumps are not "high-level stuff". They're very simple instructions. If WASM can't do a jump, it is actually WASM that you can't call "a low level bytecode".
|
|
|
|
|
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 actual stack CPUs, for that matter.
|
|
|
|
I feel like you're ascribing some judgement to the word fictional, it just means that machines, real or virtual, present programs a model of computation that is an abstraction over the implementation. One such abstraction is the notion of a program that is a block of instructions executed in sequence with a program counter, registers, memory, a stack. But that's not the only abstraction you could imagine. The JVM for example eschews manual memory management. And WASM eschews the concept of a program counter, and arbitrary jumps, and instead only allows structured control flow.
|
|
|
|
I feel like you're using the word "fictional" in a sense that renders all models of computation "fictional" to the same extent and hence renders the word "fictional" itself meaningless/uninformative. Personally I feel like there should be some distinction between features depending on how much supporting machinery you need to physically implement them. To me at least, "low-level features" are those that require the smallest amount of physical machinery to implement them. Things like bitwise operations, indirect addressing, arbitrary IP adjustments, etc. Definitely not things like enforcing stack discipline, enforcing block structure and such. (Just so that you know what I mean when I say "low-level". Opinions on that may differ very wildly, of course, and it's perfectly possible that other people use that term differently.) I'm not saying that "fictional" things are bad. Tail calls themselves are "fictional" to me in the sense that all tail calls are jumps but not all jumps are tail calls, and the distinction between a tail call and a general jump is too difficult to make for a reasonably sized physical machine and best left to the compiler. But that is not me being judgmental against tail calls, of course -- I love tail calls and consider their lack a huge design failure wherever they're absent.
|
|
|
|
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 "high level" vs. "low level," there's just "features a language has" vs. "features it does not." There are other abstractions that are actually harder / impossible to do correctly with jump in the language (stack unwinding comes to mind, which is why C++ solves the exceptions vs. setjmp / longjmp dichotomy by... Not solving it, and a program that uses both will just do something undefined. C++ without setjmp / longjmp would be a language with fewer undefined behaviors).
|
|
|
|
> 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.
|
|
|
|
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 like WASM to be "low-level", because it places constraints on your code that no reasonable physical CPU would ever enforce. [EDIT, from a deleted comment of yours: > The RISC-V chip is in the same family as the PDP-11 architecture. The Turing machine itself requires no JMP instruction, so it is possible to build a CPU without one. Has anyone done so? In general no, because the PDP-11 had profound impact on the world of physical computing. But one does see it from time to time; GLSL, for example, has no `goto` instruction because the graphics card shader hardware it was built to operate on does its magic by running exactly the same instructions on multiple data; jump would imply the ability for one of the instruction flows to be different from the others in its processing cell, which the hardware cannot support while maintaining the throughput it must to accomplish its task. I get what you're trying to say here, but sort of a guiding principle for me here for many years has been what I call "the principle of minimal total complexity". While you can keep making the CPU simpler in many cases, if that causes your program to become excessively long in the sense that the total size of the description of your program AND the device it's running on starts actually increasing, that's a place you don't want to design yourself into in practice. 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" to me. Feel free to look at the Oberon system (both HW and SW) to see what I have in mind by that -- that seems to be about as minimal a complete system as I can imagine in practice.]
|
|
|
|
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.
|
|
|
|
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.
|
|
|
|
|
This is possible, and trivial, when self-recursing: A -> A If you have an A -> B, or A -> [indirect] call, that is not the case.
|
|
|
|
I am genuinely asking, is your position that a compiler cannot convert: g():
a = 1+1;
b = 2+a;
print(b);
return f() into code that does not allocate stack space and just reuses the frame allocated for g()?
|
|
|
|
Only tail recursion, not tail calls in general.
|
|
|
|
I think its Rich Hickey who said something to the effect that tail calls are so fundamental that the underlying platform should be providing them.
|
|
|
|
tail calls are so fundamental that its trivial to build a call-push, return-pop stack calling protocol on top of them, but not the converse
|
|
|
|
|
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.
|
|
|
|
GC is making a lot of progress. There are VM and toolchain prototypes. You can compile Java and Dart to wasm on those today and it generally works and is pretty fast. (There is also a Kotlin prototype but I have less information about it.) Most of the big spec questions have also been resolved. DOM manipulation hasn't changed - you still need to call into JS to do those. Ideas like WebIDL bindings have been proposed over the years but haven't shown enough benefit. JS is better for DOM-heavy code, while wasm excels at computation-heavy code. But you can write bindings from wasm (maybe someone already has for OCaml?), which is what toolchains do today - not as fast as JS, but often good enough.
|
|
|
|
|
I lost track of it since the Reason/ReScript split.
|
|
|
|
|
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 add it back. Go figure. Firefox also has problems implementing cross-realm tail calls. That could be spec’ed around, but there’s no will to do so.
|
|
|
|
If I understand what cross-realm means (code security), then I'm not sure that can be done at all.
|
|
|
|
Firefox can’t eliminate tail call across realms. The spec could make an exception for that scenario
|
|
|
|
I am unsure, but I can make a guess. The first release of Wasm has been always considered a Minimum Viable Product, which a strong emphasis on Minimum. Pretty much only features already part of the legacy asm.js "standard" made the cut. The fact that WebKit had some level of support for tail calls on the JS side is exactly the reason we choose it as the right platform to invest in.
|
|
|
|
How is ECMAScript 6 (high level language) related to WebAssembly (low level target)?
|
|
|
|
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.
|
|
|
|
What's wrong with JS bindings? Surely DOM manipulation is slow enough for WASM/JS overhead not being noticeable.
|
|
|
|
You still need to go through a port with Blazor, but you can minimize those calls for the most part. DOM manipulation was slow as recently as a few years ago, but improvements to Blink have made it blazingly fast. I agree with Svelte that we no longer need a virtual DOM https://svelte.dev/blog/virtual-dom-is-pure-overhead
|
|
|
|
Genuine question: is the goal to get something that is not achievable with JS/TS, or is the goal to simply avoid JS/TS?
|
|
|
|
I really dislike JavaScript for a number of reasons. Dart gives me more distance from it than TypeScript. Of course, I can't avoid it, but I don't have to deal with many annoyances such as which 'this' is this? Should I put 'this' into a var called 'self' to be safe? That's just one example of how JavaScript and I don't get along. I understand some people have brains that think this way, but mine doesn't
|
|
|
|
The comment reads like you used JavaScript 10 years ago. For instance, just use arrow functions and this remains untouched.
|
|
|
|
Surely it's easier to stick to JavaScript The Good Parts than to introduce a whole new layer in the form of Blazor?
|
|
|
|
Blazor is not equal to JavaScript. Blazor is Microsoft's answer to React and Flutter. So far of the three, I like Blazor, but not the server version that uses SignalR to communicate with the client because it locks you in. Blazor Webassembly is awesome, but just needs a good DOM manipulation library. With Blazor Wasm on the client, I can use anything on the back end.
|
|
|
|
What do you like about Dart over TypeScript? The type system in TypeScript is far superior to Dart's. Other than that, the languages are more-or-less the same.
|
|
|
|
Actually, I'm taking another look at TypeScript today. I liked it well enough when I last investigated it in 2016, but the code I wrote then was just a veneer over jQuery. I'm sure things have improved dramatically, which I am about to find out. Frankly, a Turing complete type system [1] seems like over-kill to me and a complication I don't need. Still, Dart had everything I wanted in a front end language in 2013. I think JS devs were short sighted to reject it out of hand. It's a shame it never caught on by itself and not as a just a Flutter language. I read that Google is using it in Fuchsia so there is still a chance Dart will be big in the future! [1] TypeScript and Turing Completeness: https://itnext.io/typescript-and-turing-completeness-ba8ded8...
|
|
|
|
I highly recommend TypeScript. I don't really like the JS runtime, but, purely from a language point of view, TS is my favorite. Some cool features: 1) Type unions interface A { a: string; } interface B { b: string; } type C = A | B; const c: C = { a: 'a' }; 2) Type assertions
if ('a' in c) { /* compiler knows c is of type A here */ } function isA(c: A): c is A { return 'a' in C } // compiler knows c is A if this returns true 3) Nice helper types
interface A { ... } ReadOnly<A> // Like A, but all properties are read-only Partial<A> // Like A, but all properties are optional Omit<A, 'someProp'> // Like A, but without 'someProp'
|
|
|
|
Interesting. I'll learn more today as I rewrite one of my Dart components into TypeScript. But I also dislike Node and Npm so I'll try Deno first.
|
|
|
|
TBH, TypeScript's type system really impressed me. It's the strongest type system of any language I regularly use (I haven't had time to unpack Rust yet, and I learned enough Haskell to decide Haskell didn't help me solve problems I had).
|
|
|
|
It’s an expressive type system, but ime it allows developers to go crazy on type interdependencies and general entanglement, so you can’t just go to the “header” and quickly figure out what your method or a return value really is, despite TS has structural typing. E.g. look at this: https://github.com/telegraf/telegraf/blob/v4/src/telegram-ty...
|
|
|
|
> I really dislike JavaScript for a number of reasons. Might I suggest being less sensitive/that your reasons are overblown?
|
|
|
|
I don't like liver and horse radish either. Should I eat that because a lot of people like it?
|
|
|
|
Yes, let's keep using JavaScript for all eternity now. It's COBOL of this century.
|
|
|
|
This is wonderful news! Thank you so much for doing this, and doing it right - this is much better than my idea of making a bad MVP web browser to provide second implementations to push through proposals when other vendors drag their feet. As an author of a functional compiler that targets wasm, this is a dream come true - yall do really cool work.
|
|
|
|
|
|
I'm working on a relational stream processor and this is pretty critical to making it work well. a runtime standard with support for network connections would be nice too, but lets not get greedy
|
|
|
|
> support for network connections I wish daily for that as well, but stay tuned: we _might_ have found a half-satisfactory solution for that ;-)
|
|
|
|
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.
|
|
|
|
|
|
A tail call is a function call occurring in the final position of a function: void foo(...) {
...
bar(x,y,z); // <= a tail call
}
If the function has a return value (vice void like above): int foo(...) {
...
return bar(x,y,z); // <= still a tail call
}
In the way most languages are compiled, function calls generate a new entry in the call stack (a stack frame). This is necessary for all non-tail calls in order to handle the bookkeeping around what to do when the call finishes, how does the caller resume. With tail calls, that additional stack frame has no real value (outside, maybe, debugging information to give you a stack trace but traces can be collected other ways). Tail call elimination (or tail call optimization) will reuse the current stack frame rather than construct a new one. This reduces the memory overhead (you aren't constructing unnecessary stack frames) and gives some performance improvement (less bookkeeping overhead, and the function call becomes a simple jump). These two functions can, in principle, get compiled to the same thing if you have TCE: uint factorial(uint n) {
uint acc = 1;
for(; n > 0; n--) {
acc *= n;
}
return acc;
}
uint factorial(uint n, uint acc = 1) {
if (n == 0) return acc;
return factorial(n - 1, acc * n);
}
But while that's a recursive example, tail calls and tail call elimination (TCE) aren't just for recursive cases. My first two examples, though they are just sketches, show a non-recursive example of tail calls. With full TCE (it isn't uncommon to have TCE only apply to self-recursive cases) those examples would also have tail call elimination performed.
|
|
|
|
|
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.
|
|
|
|
Actually even C++ can benefit from this. In LLVM C++ coroutines compile down to functions with the "musttail" attribute, that right now is not possible to express in Wasm [1]. It is also useful to efficiently implement stuff like interpreters, where you use it as a way to jump to the code of the next instruction directly (Wasm has only structured control flow, but you can see a tail call as a sort of jump/goto instruction) [1]: https://discourse.llvm.org/t/supporting-coroutines-without-t...
|
|
|
|
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.
|
|
|
|
It isn't one or the other. Work on Wasm GC is ongoing and separate from this.
|
|
|
|
Recursion indeed can be useful when working with trees or graphs. However, I don't like using recursion instead of a loop, because you make reader to unroll your code in their head to understand what it really does. If you need to add two arrays of numbers, use loop or array addition, but don't use recursion as a replacement for a loop. Sadly the article uses a poor example, writing a useless factorial function. I have never needed such a function in production code, and if I needed, I would write it using a loop. Using bad examples like this might create an impression that recursion is not useful in real code (which is wrong). It would be better if you have used an example that looks like real code and that would become less readable without recursion.
|
|
|
|
> 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.
|
|
|
|
More specifically: if you don't want to recursively iterate a tree, you have to hold a list of prior nodes to return to anyway... which is no different from weaving that information into the stack. Non-recursive iteration in this case literally requires you to emulate the recursion.
|
|
|
|
Readability is really not a relevant factor for WebAssembly. Having tail-call recursion support is critical for the languages that compile to Wasm that use tail-calls themselves.
|
|
