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

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.

(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. (There's no ".stack property" that would be added to Wasm itself.) It's true that the proposal amends the JS API (but only the JS API) to describe a traceStack=true option; from Wasm's perspective I understand that's just an ordinary exception that happens to include an externref value (just like any other value) to which Wasm attaches no special significance. The Web-based engines can attach an informative stack trace if they want, but there's no requirement preventing frames from having been optimized out. The non-Web engines won't have to think about this.

(3) I think the real reason that a Wasm engine can't implicitly make tail calls proper is that the spec tests forbid it, basically because they didn't want the implementation base to fragment by having some engines perform an optimization that changes the space complexity of a program, which some programs would have started to depend on. (The spec tests say: "Implementations are required to have every call consume some abstract resource towards exhausting some abstract finite limit, such that infinitely recursive test cases reliably trap in finite time. This is because otherwise applications could come to depend on it on those implementations and be incompatible with implementations that don't do it (or don't do it under the same circumstances.)")

But the issue is much weaker than "call stack is observable" -- it's more like "infinite recursion must trap eventually, but it can be nondeterministic when."

More discussion here: https://github.com/WebAssembly/spec/issues/150

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. Something like "each function call must consume at least N bits of memory" or something concrete like that. Or heck, "implementations may not perform tail-call optimization" or even "implementations must be able to reconstruct the full logical call stack at any point".

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

The nightmare scenario is that you spend months writing a program that works great in browsers A and B, but when you roll it out to prod it immediately fails in browser C, which doesn't perform TCO.

You only want to write code that depends on TCO if you can get a guarantee that TCO will be performed. This is the motivation for the clang:musttail attribute in C/C++ (I implemented musttail in Clang): https://clang.llvm.org/docs/AttributeReference.html#musttail

To me, I'd see a distinction between code that requires a specific optimization and code that could benefit from that optimization. If the standard forbids an optimization to avoid the former, it also removes the latter.

Indeed much of this discussion, including the title and text of the original post, carefully avoids using the word "optimisation". Somehow it got introduced at some point in these comments.

To flip it the other way: consider a normal (non-tail-call) program and choose a local variable in a routine that happens to be called quite a lot. Replace it with a list that you append to every time you call the routine, even though only the last entry is ever examined. The program will leak memory, potentially quite quickly, and eventually crash. Is it fair to say it's just less optimised than before? I would say it's worse than that: it has an actual bug.

That's exactly the situation in a program created with the assumption of tail calls that is then used in an environment without them.

I had to think on this example a bit, but I believe these programs exist and are quite common. This is an accurate description of any program in which memory is allocated and never explicitly freed. Some languages include runtimes that perform garbage collection, but until the garbage collection runs, the program is leaking memory and would crash without the garbage collection.

Which is to say, I think I agree with you, but had to chew over the example a bit. That it isn't a quantitative difference in speed or memory usage, but a qualitative difference in the types of programs that are acceptable in a language. Thank you for it.

Yes, a program that depends on tail call optimization, despite having no guarantee of tail call optimization being performed, has a bug.

That doesn't mean that tail call optimization is not an optimization. In languages that allow, but do not guarantee, tail call elimination, it is an optimization performed by the optimizer that makes a program run more optimally than it would have otherwise. There is a long history of referring to it as an optimization, for example in the docs of LLVM: https://llvm.org/docs/LangRef.html#call-instruction

I don't think it makes sense to redefine the word "optimization" such that it excludes examples where a program could erroneously depend on a certain optimization being performed.

(1) In languages (or runtimes) where tail calls are not guaranteed to be elided, tail call elision is an optimisation. In that context, you could quite reasonably describe it as tail call optimisation. Programs that are written in these languages and rely on tail call elision are buggy.

(2) In languages (or runtimes) where tail calls are guaranteed to be elided, tail call elision is not an optimisation. In that context, you cannot reasonably describe it as tail call optimisation. Programs that are written in these languages and rely on tail call elision are not buggy (at least, not for that reason!).

This conversation is about making tail call elision a guaranteed feature of WASM. Therefore, in this context, it is not reasonable to describe tail call elision as an optimisation.

I still don't understand why some people seem to like the idea of iterating simpler things with recursion using a tail call.

No.

For other optimization, the difference is the speed of execution. For tail call optimization, the difference can be normal execution and stack overflow.

(Specifically, to prevent one implementation getting an optimization for them that leads people to rely on it, making code that blows up in practical use on other implementations, despite both being nominally correct implementations of the same spec.)

It's a nice detail for you to highlight, but surely that exists in the test spec specifically because the opcode spec doesn't mandate tail-call handling. If the latter did (a la Scheme), then the test spec would be updated to no longer have this note...?

I think this would be the correct design even if tail calls were desired from the start. It makes for a better debugging experience and allows language implementations more control. (A trend in some functional languages is to require explicit annotation when tail recursion is desired, both to improve debugging for regular functions and to allow the compiler to check that you don’t accidentally stop being tail-recursive)

I've long suspected exceptions making it into WASM being it's million dollar mistake, and this further confirms it.

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.

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.

Actually I wonder if one couldn't adapt the tail-call mechanism slightly to also serve as an exception mechanism. I think you could do both by allowing `br` to jump to an arbitrary label previously established. An exception then simply being a "tail-call" that unwinds more than one stack frame, and calls into the "catch".

Not sure how well JITable this would be, but I think an arbitrary backjump and call should be mostly fine in terms of control flow?

Wasm cannot throw the exception itself, nor can it catch the exception. How exceptions are handled when raised in code called via FFI in another language are a property of the embedding and wasm engine, not of wasm itself, which (as of yet, barring that exceptions proposal) has no concept of them besides unrecoverable traps.

I actually did this in my purely functional language, but had it off by default for performance reasons - if you hit an error at runtime, the debugging code would re-execute from the last checkpoint with debugging information turned on to construct the missing debug data, something I could only do because the language is side-effect free.

Possibly a stupid question as I haven't given this much thought, but I thought tail call elimination could be used to convert recursive calls in tail position into loops. Could a compiler not do this (like Scala does, for example)?

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.

I think I understood that concept but it still seems a bit strange to me. Doesn't that imply a potentially infinite stack of function calls?

I've seen this idea in other functional program examples as well. Instead of having a sequence of instructions, they have a sequence of function calls. Instead of a function returning to the caller, it calls the next function in the program which is analogous to the virtual machine moving on to the next line of code in the sequence. It implies the program's structure and state is actually expressed within the function call stack and its frames. I admit I'm not sure what the purpose of this is.

Yes, which is exactly why tail calls are so important. Otherwise you'd stack overflow after processing the first few thousand elements of your stream.

> I've seen this idea in other functional program examples as well. Instead of having a sequence of instructions, they have a sequence of function calls. Instead of a function returning to the caller, it calls the next function in the program which is analogous to the virtual machine moving on to the next line of code in the sequence. It implies the program's structure and state is actually expressed within the function call stack and its frames. I admit I'm not sure what the purpose of this is.

Well, if you want to express your function as an actual function, in the mathematical sense, recursion is often the natural way to do it. Things like the call stack are an implementation detail; often a natural way to describe a function is "do this, do that, then do the same thing for all the rest of it", and usually the easiest way to translate that into a program is recursion.

It also tends to be more compositional, because you don't have to worry about control flow (or at least, control flow isn't a special case: all your control flow is just function calls). For example if you are calling several nested functions in an imperative-style loop, there's no way to break out of that loop from the inner function. But if you write the same thing as several mutually recursive functions, you can "break out of the loop" by just not recursing under particular conditions.

In functional code written where general tail call elimination (or special tail call operations) are available, non- or mutually-recursive tail calls are not uncommon.

Heck, non-recursive (potentially fairly nested) tail calls are common in languages without any optimization for it. Anytime you see something like “return f(x)” (or, because operators are implemented via special methods, even “return x+y”) in Python, for instance, you've got a tail call.

If it isn't direct or mutual recursion, it has to be a pretty degenerate case to blow the stack even without elimination, so elimination is must necessary for those cases. But other cases bene for from not having the extra memory usage and reducing pushing stuff onto and popping it off of the stack.

How likely is it that the depth of the JSON structure would exceed the maximum depth of the stack? This doesn't appear to be a compelling example to me.

It probably is a shame that it's called tail call optimisation since nobody wants to mandate low level details for an optimisation.

Not that unlikely i'd say, at lest if the stack size is unreasonably small.

For example, on nodejs, JSON.stringify() chokes with a nested array of 10K depth:

  > N=10_000; JSON.stringify(JSON.parse("[".repeat(N) + "]".repeat(N)))
  Uncaught RangeError: Maximum call stack size exceeded
      at JSON.stringify (<anonymous>)

Imagine that you build some software that lets users nest things —e.g., a circuit designer, a visual programming language, a UI builder, etc— and you wanna save these nested structures as JSON, or process them recursively. Pretty natural fit i'd say. Now, as a user, i'd be pretty upset if my magnum opus of a very complex circuit, or giant visual program, or very busy beast of UI art, starts creashing the program when exceeding a mere 10K elements. My computer has gigabytes of memory! And, presumably, there's a lot still available. But nope, a meager stack can ruin all the fun.

I personally think this is a pretty silly limitation to have on software, especially given today's memory sizes.

A state machine is, in fact, a well-understood method of applying structure to spaghetti.

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.

you define a function with a clause per state (and some other args including the incoming message), and each clause returns a tuple with the new state and some other stuff. the loop is part of the framework, and handles generic otp stuff like updating code in a running system.

well if the same function is in the "tail" it would still apply a tail call elimination.

But a lot of the time tail call eliminiation is only needed in some extreme cases. it can eliminate stack overflow exceptions by a big amount. C#'s new System.Text.Json would greatly benefit with tail call ops, because it often has a call chain that is recursive and does not call itself (its mostly like ReadObject, ReadObjectAsync, ReadObject, ReadBla, ReadObject, etc. and if the object has a ref to itself system.text.json often blows up.

In Java and Scala this thing can btw. also happen (and I've already seen it) however at least you can configure the stack size there and thus most often eliminate the problem somewhat.

it's an edge case, but one that would be cool to fix, since it makes code often more reasonable especially parsers.

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.

    last [x]                =  x
    last (_:xs)             =  last xs
    last []                 =  errorEmptyList "last"

Such a program never returns until it finishes interpreting, and can make an unlimited number of such calls.

This is a bad idea without TCE.

You can split it up a bit if you use a trampoline, but then you lose some efficiency.

Which would definitely work, no doubts about that, but it might be nicer to just get it handled at a more fundamental level.

Same thing applies, I think, to any other language compiled to WASM. C/C++ compilers regularly inline huge amounts of the code when optimizations are turned on, as well as do tail-call optimization. I haven't tried, but I would assume that they do that for WASM just as they do for x86 or ARM or whatever other build target I choose. As long as my users are ok with this (and they presumably are, otherwise they wouldn't turn optimizations), what's the problem, exactly?

Stack overflows are stopping you, if you implement Scheme calls as Wasm calls.

In Scheme, tail call elimination is not merely an optional "optimization", so the compiler can't opt to not do it when it's inconvenient.

You might enjoy participating in an interoperable standardization process sometime.

For instance: the C and C++ standards have very strict rules for how to handle floating point math, and compilers aren't allowed to deviate from that according to the standard. Which turns off all sorts of cool optimizations you can do. But of course, all modern compilers implement some version of "-ffast-math" which turns off those rules and allows for the optimizations. It's no longer standard C/C++, but that doesn't mean that switch can't exist. The compiler is a computer program, it can output anything it wants, regardless of what the standard says. Nobody is going to go to jail because you turned on -ffast-math. The code will still run just fine.

So, my question is, why can't you write a compiler with an option that's like "I don't particularly care that .stack changes, do the tail call optimization". A -ffast-math, but for tail calls. Is there a technical reason why you can't do this?

Because the stack in web assembly is only observable. It is implicit. You cannot modify it yourself. There are simply no instructions for this. The WASM stack is not present on the WASM heap, like it is for your physical machine.

You simply cannot express tail calls with the instruction set given to you by WASM right now. No hacks are possible.

https://clojuredocs.org/clojure.core/recur

I don't see why. Compilers are how tail calls are literally always implemented. It's not like there's hardware support.

What makes this impossible?

.

> The issue is that to avoid stack blow-up you need the engine to recycle stack frames.

I mean, what's stopping you from just implementing a trampoline?

.

> The problem with this is that in WebAssembly (and JavaScript) the call stack is observable via the .stack property of thrown exceptions.

Okay? This seems fine to me. What makes this a problem?

WASM doesn't have the same set of operations as a typical CPU. It's not something a compiler to WASM can do.

You could also handle exceptions manually too, without VM support, but that too would incir considerable overhead.

EDIT: Also as another commenter mentioned, this is a property exposed by the VM engine to the host environment, not something directly observable from within WebAssembly itself.

I have been out of the loop regarding compilers development for a long time but what prevents you from converting your program to CPS and using a trampoline like some LISP still do?

Its just a jmp? Does the wasm VM not have a jmp instruction?!?

Those are the list of control instructions. WASM seems to be a bit of a misnomer as it is not an assembly language in the more conventional sense. It is a structured language and provides a limited goto in the form of branches (in the section I linked to) which are constrained to a particular scope.

If you compile your whole program so it fits within a single function, then yes you can use this to do universal tail call elimination. Otherwise you are restricted to doing TCE only on auto-recursive functions and maybe mutually recursive functions if you have a single entry point (of the set of functions) and decide to optimize by moving all of them into one function.

Otherwise, function calls are performed using one of the two call instructions which (presently) implement a behavior more like conventional call stack/stack frames. This proposal would add a second pair of call instructions that a compiler can emit which the WASM runtime would then optimize (by not generating new stack frames).

How does the famous 1977 Guy Steele paper on compilers optimizing tail calls not apply?

https://dl.acm.org/doi/10.1145/800179.810196

Auto-recursive functions can switch to using a branch or using another loop construct, and the compiler can generate that WASM code. The control structures available are described in the link below. Mutually recursive functions where only one is meant as the entry point could be similarly converted into WASM instructions but where the additional functions are, essentially, eliminated and inlined into the original caller (this may not be a good general solution, though). But general tail calls cannot be converted into gotos as you might with a more conventional assembly language since WASM branches cannot go to arbitrary instruction addresses.

The problem is that in a conventional assembly language, if you do TCE then the goto would go to (har har) the same (or nearly the same) point as a regular function call (maybe it skips the first few instructions depending on the calling conventions involved). With TCE and WASM you'd have to, essentially, inline the called function, or a variant of it, in order to be able to branch to the start of it. You cannot branch into a different function or to the start of a different function, you have to call the other function and then you have a single entry point. Which, in WASM as currently specified, means you have to use the current calling conventions which does not permit TCE.

https://www.w3.org/TR/wasm-core-1/#control-instructions%E2%9...

Edit: I should say, they don't have anything equivalent that can jump out of the method you are in.

Edit2: This is a bit more clear if you consider what it means for JVM bytecode to have a "return" set of instructions. Why does the bytecode need a return, if that is all managed by code that the compiler should handle anyway? You can look at the instructions here: https://en.wikipedia.org/wiki/List_of_Java_bytecode_instruct.... Note that it is the "jsr" instructions that let you do the equivalent of a long jump, and those specifically manipulate the stack. There is a "goto", but it is not valid to have that jump outside of the subroutine you are in.

I normally consider TCO something that is a compiler feature. Replace a call to the head of yourself, with a jump (possibly to just after the "pull the arguments from the call stack to where the code wants it" prologue), making sure that the correct locals are present where they need to be.

Well, that's for self-TCO. General TCO is definitely trickier (probably requires juggling stack allocations so as to ensure that the tail-called function has enough space for all that it needs).

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.

>Tail-calls is fundamentally something that the compiler _cannot_ solve.

You write

>it is not possible to solve this performantly in the compiler

So is it fundamental or not? Apologies if the question seems direct or rude.

If we stretch things too far we'll end up in the "wasm is Turing-complete and thus can run anything" type of territory - if you're doing something performance intensive, say x86 virtualization like I believe apignotti is at Leaning Tech, I think it's fair to describe the problem as unsolvable by the compiler.

Obviously a Turing-complete system can simulate any other Turing-complete system. For example you could write an emulation of any system you like in WASM, and in the emulator you could have tail call optimization. Thus from context it should be apparent that we're talking about efficient implementations.

this is measurably worse than just using jump, and as another posted pointed out, can introduce an O(n) term that doesn't need to exist. (edit: nevermind - if you are going through the forward direction n times then it doesn't change complexity to do a little more n work on the way out)

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.

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.

The compiler cannot implement tail calls correctly as it stands. You do not have access to modify the WASM stack and it's not present on the heap like it is for normal programs.

No compiler tricks can enable tail calls in WASM at the moment (with the exception of trampolines which always work and are absurdly slow).

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 that's how it should have been designed.

But that is not how Wasm works. The stack is not in Wasm's "linear memory". (This makes it much easier to compile access to local variables efficiently.) Calls, returns, and in a sense exceptions in Wasm are provided by the virtual machine at a fundamental level in a way that makes it impossible for a compiler targeting Wasm to implement tail calls, call/cc, or cooperative multithreading, except by compiling your entire program into a single function, which ruins the performance of existing Wasm implementations.

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 about it.

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

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 upside. GC is great.

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.

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".

https://webassembly.github.io/spec/core/syntax/instructions....

http://troubles.md/why-do-we-need-the-relooper-algorithm-aga...

> WebAssembly isn’t designed as a front-end language for general programming though, so what’s the problem? Well, WebAssembly does have some constraints, specifically it must produce code that is valid. WebAssembly is a stack machine, and you can’t jump to just any label since that label might point to code that pops too many values off the stack, or pops the wrong types off the stack, or pushes too many values onto the stack.

Also, to summarize another part, when a compiler targeting WASM sees control flow WASM can't directly express, it has to implement it in a loop-and-switch form, something called the Relooper algorithm; therefore, compilers taking WASM down to native code have to understand that, and undo it back into a performant form. This adds up to a lot of work most VMs don't require, hence the proposal to move WASM towards a control-flow model friendlier to tail-call optimization, which would bring it more in line with physical hardware.

> 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'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.

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).

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.

[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.]

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

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

History is arbitrary but not random, and it's fun to think about how things might have been different if the first machines started embarrassingly parallel with follow-up work to consolidate the data instead of embarrassingly centralized with us now in the era of how to make the monoliths fast. It's interesting to think about what's "ideal" about a machine that supports arbitrary jumps (and the global address space that demands, and the sequential execution necessary to prevent decoherence, and the memory protection demanded because some addresses are not executable code and should never be executed, etc., etc.).

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 completely from scratch, surely you wouldn't end up with an AMD64-based IBM PC descendant as your best idea you could come up with?

The best they can do are trampolines, which come with a high performance cost.

For languages that rely heavily on tail calls (functional languages in particular), good performance can only be achieved by having tail calls (or general-purpose jump instructions) as part of the instruction set.

Excluding tail calls hurts performance for these languages as they have to resort to techniques like trampolines. As apignotti suggested, it's impossible for a compiler to generate efficient code for tail calls if the underlying instruction set does not support it.

https://www.lua.org/source/5.4/lopcodes.h.html

There are some special cased scoped branches but if you read the spec you'll see they are so specific that you can't branch back to the head.

(ex compiler dev)

The second could easily optimize tail calls but it is required not to do so to increase reliability (all implementations need to agree which calls are tail calls that should be optimized and the simplest way to agree is to never do it) as otherwise a Wasm modules could work fine on an implementation and be unusable in another.

The first compiler cannot, the only possibility is to use whole-program transformations that significantly degrade performances.

  let sum list =
    let rec loop a = function
      | [] -> a
      | x::xs -> loop (a+x) xs
    in
    loop 0 list

  let rec even_then b n =
    if n = 0 then b else odd_then (not b) (n - 1)
  and odd_then b n =
    if n = 1 then b else even_then (not b) (n - 1)

  fn even_then_or_odd_then(which_function, b1, n1, b2, n2) {
    loop {
      match(which_function) {
        Even => {
          if n1 = 0 { return b1 }
          else {
            b2 = not(b1);
            n2 = n1 - 1;
            which_function = Odd;
          }
        },
        Odd => { similar }
      }
    }
  }
  
  fn even_then(b,n) {
    even_then_or_odd_then(Even, b, n, null, null)
  }
  
  ...

  let parse_both p1 p2 =
    fun buf pos success ->
      p1 buf pos (fun pos r ->
        p2 buf pos (fun pos r2 ->
          success pos (r, r2)))
  ;;

[1] A trampoline means that functions effectively return continuations except typically they call their continuations (up to some max number of times) and only occasionally return them to the trampoline (which pops everything off the stack) which immediately calls the continuation again. But implementing continuation passing style this way is pretty slow.

The result is a fairly high-level VM that doesn't export enough power for your program to implement GC or exceptions without sacrificing a lot of performance. Tail calls is a different matter, and there is a cost-benefit analysis for it.

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.

the kind of generalized tail call I'm talking about is generally referred to as a continuation. its easiest to think of it as a jump. so you can imagine that if we have jump and a stack register, we can push+jump and thats the same as 'call'. we can pop+jump and thats the same as 'return'. since 'call' and 'return' have side effects, we cant really use them to replace jump.

so thats really straightforward, but things do get a bit screwy. if we can support arbitrary jumps, and the frame storage (arguments + locals) cant necessarily go on a stack because our frames might have arbitrary liftimes, so we cant reclaim them in stack order.

so in a scheme for example we just pull in a gc and track references to these closures and dust our hands off with a smirk. if that doesn't work for you then you have to adopt some kind of framework that lets you know explicitly when these can be released. reference counting is a poor choice here because these references between frames can easily be cyclic.

For posterity my original comment was:

“From what I understand, tail calls can always (?) be lowered to while loops[1], which are expressible in WASM.

1. https://en.wikipedia.org/wiki/Tail_call#Relation_to_the_whil...

If you have an A -> B, or A -> [indirect] call, that is not the case.

It's an ugly piece of code, but because of parsers, there is a huge amount of know how on it.

For example, what if those functions are in different modules or libraries? Tail calls are still supposed to work.

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

Glad to see it finally moving forward after stalling for so long! Excellent work!

[1]: https://github.com/jacobmischka/uwm-masters-thesis/releases/... [2]: https://github.com/WebAssembly/tail-call/issues/10

[0] https://www.cs.virginia.edu/~evans/greatworks/shannon38.pdf

Do you know why it wasn't in the standard to begin with?

Even ECMAScript 6 mandates PTC (proper tail call) - article from 2016 on Webkit.org no less - https://webkit.org/blog/6240/ecmascript-6-proper-tail-calls-...

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.

But instead we'll probably do things like asm.js - that is, bless certain wasm patterns such that advanced VMs would be guaranteed to optimize them. And so everything will be way more complicated than it needs to be. Just like the JS stack today.

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.

(It is probably the main reason why Wasm only has structured control flow)

> For example its architecture is a stack machine instead of a register machine. This means that it isn't immediately suitable as simply yet another target at the last stage of the Go compiler next to x86 and friends.

> There might be an alternative: Emulate what we need. We may use the stack machine to emulate a register machine and hopefully do so in a reasonably performant way.

> WebAssembly has linear memory with load and store instructions, which is good. We would not use WebAssembly's call instruction at all and instead roll our own stack management and call mechanism. Stacks would live on that linear memory and be managed by the Go runtime. The stackpointer would be a global variable. All code would live in a single WebAssembly function. The toplevel would be a giant switch statement (or WebAssembly's br_table based equivalent) with one branch for each function. Each function would have another switch statement with one branch per SSA basic block.

> There are some details that I'm omitting here, but in the big picture this looks like a decent register machine to me. Of course the performance of this heavily depends on how well WebAssembly can transform these constructs into actual machine code.

[0] https://github.com/golang/go/issues/18892#issuecomment-30931...

In Virgil I implemented this for both the JVM and Wasm. Here's the algorithm used for Wasm:

https://github.com/titzer/virgil/blob/master/aeneas/src/mach...

As an author of a functional compiler that targets wasm, this is a dream come true - yall do really cool work.

I almost felt like I was trolling by combining the two, but I'm actually using Dart and Blazor to see how they can work together because Blazor Wasm doesn't do DOM manipulation and Dart does it in such a easy to use fashion that the marriage feels natural to me.

I try not to attack back and have a bit of a sense of humor about it, but it does feel like suppression of thought on HN

Edit: I'm thinking of cognitive load too. I like to eliminate load I don't need. Keeping track of this is not something I want to do with my life

https://drpicox.medium.com/reducing-programmers-cognitive-ov...

http://www.synergeticapplications.com/ergonomics.htm

By the way, I feel like I'm at a bar and you're negging me

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

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'

E.g. look at this: https://github.com/telegraf/telegraf/blob/v4/src/telegram-ty...

https://github.com/microsoft/TypeScript/issues/14833

Might I suggest being less sensitive/that your reasons are overblown?

It would be even more interesting if there were a Dart.NET

Do you have any gotchas which isn't really mentioned on MS documentation site? primarily related to performance, since it will be one of my main concerns.

That's not to say it isn't cool and can't work for some projects where say, development speed is more important, but performant it just aint.

https://svelte.dev/blog/virtual-dom-is-pure-overhead

Edit: I didn't answer your question. There's nothing wrong with JS bindings. Both Blazor and Dart use them, which could get awkward going from Blazor -> Dart (as JS) -> JavaScript lib. I'm considering TypeScript again because no port is needed to call JS libs.

I’ve been wanting tailcalls to be in wasm for years! I consider it a blocker for all sorts of uses I’d be interested in

Unlike regular machine language, WASM does not allow you to control the call semantics. That is, if you emit x86 machine instructions you can handle TCE entirely in your own compiler, the machine itself does not care.

WASM has special call instructions, these perform basically a conventional stack frame/call stack approach and you can't short circuit it. The closest you can get, which works fine for auto-recursive functions and maybe some detectable mutually recursive functions, is to convert tail calls into loops within the compiled WASM output. So recursive tail calls work fine in WASM if your compiler doesn't turn them into calls, but leaves them as a self-implemented (by the compiler) loop structure using whatever appropriate WASM instructions are available. This is fine for auto-recursive functions, but puts the burden at implementing TCE for them on the compiler writer. Which means you'll get it for some languages that compile to WASM, but not all. And only for the limited cases they support (probably restricted to auto-recursive and some mutual recursive circumstances).

What this proposal introduces is a new version of the call instruction that would be used in tail call positions. Then the WASM interpreters would do the work of actually combining the stack frames internally. Detecting that a call is a tail call is actually pretty straightforward for a compiler. Given that it is a tail call, it can emit (or not) the new call instruction and will get TCE "for free". It doesn't have to do a code transformation from recursive to looping, and it can be applied more broadly than just recursive circumstances.

Unfortunately self recursion is only a subset of tail calling.

I wish daily for that as well, but stay tuned: we _might_ have found a half-satisfactory solution for that ;-)

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.