Continuations

[autumnontape]

Some way of saving the WebAssembly execution state and later restoring it would be useful in order to port blocking APIs to platforms whose equivalent APIs are async, especially the Web itself, which relies heavily on async APIs. Only a very limited form of continuations would be necessary to open a wide range of possibilities.

Searching for "continuations" in the issue tracker brings up a few comments by @rossberg mentioning plans for "delimited continuations"/"stack switching" in a later revision of WebAssembly: #796 (comment), #919 (comment), #1171 (comment). There doesn't seem to be any mention of the feature on the website, nor a dedicated issue in this repository, so I'd like to ask -- what's the status here?

[aardappel]

I believe these features will be implemented as an extension (generalization) of exception handling support, so that being completed is probably where the current focus is.

I agree it would be nice to have more of a roadmap for what comes afterwards, yes.

[binji]

There was some description of this here, though the exception handling proposal has changed since then, so perhaps it's not relevant anymore. Maybe @rossberg and @aheejin can provide more info.

[rossberg]

Some folks among us are currently working on an experimental design that generalises the current exception proposal with resumption, yielding the equivalent of effect handlers, which are a structured and typable form of delimited continuations. We have a basic semantics but it is far too early for a proposal. Next steps will be prototyping it in the reference interpreter and experiment with the design and perhaps some producers (as a side product, this would yield a reference implementation and spec proxy for the exception proposal).

But regardless of design specifics, the fundamental mechanism of creating, managing and switching between multiple execution stacks is not easily added to existing VMs, to say the least. This will be the far greater hurdle. There is some interest e.g. in the V8 team, but I expect that implementing it and evaluating performance viability will take considerable time.

[bitwalker]

This comment got a bit long, but bear with me, I promise it is all useful:

I'm currently working on an alternative implementation of Erlang that is based on ahead-of-time compilation rather than bytecode interpretation; the primary target is WebAssembly, but other targets will be supported eventually to support usage as a general native code compiler for BEAM languages. To implement the language and compiler, a few key requirements have to be met:

• Proper tail calls, as recursion is heavily used in the language, there is no other means to express iteration
• Cheap non-local returns, Erlang's throw is commonly used to simplify code which needs to exit early, or to allow returning a value from deep in a call stack; it is not something that is used just for exceptions
• Pseudo-preemptive scheduling (implemented as cooperative scheduling in the runtime, but appears preemptive from Erlang code), which is used to implement green threads (called processes in Erlang)
• Per-process garbage collection; important for performance, especially to avoid stopping the world to collect. In many cases, Erlang processes die before a GC of that process needs to be performed, which means large swaths of memory never need to be scanned at all.

To build an ahead-of-time compiler that meets these requirements, I chose to use continuation-passing style as described in Cheney on the MTA which provides a solution that elegantly addresses each requirement. In short, here is a description of how it works and how it solves my problems as a language implementer:

• A program is converted into CPS form. In CPS form, and in this flavor in particular, every call is in tail position, and the callee receives both a return and an escape continuation (so-called "double barrel" continuations) in addition to any arguments.
• Since no call ever returns, the stack would eventually blow, but the trick used in Cheney on the MTA is that the entry point takes the address of the stack pointer, and uses it to check periodically (usually each function call) to determine if the stack is about to run out of space. When that occurs, the live values on the stack are moved to the heap, along with the current continuation, and a longjmp is used to jump back to the entry point (which acts as a trampoline). This effectively resets the stack to square one, with very little overhead.
• The jump also gives us a chance to perform garbage collection, scheduling, and as a consequence of resetting the stack, ensures that tail calls never blow the stack. Additional yield points can be added above and beyond the current state of the stack pointer, such as reduction counting (how Erlang determines when to preempt a green thread), or determining if a major garbage collection is needed.
• The use of continuations means that we easily obtain cheap non-local returns
• The use of continuations means that it is easy to suspend one green thread and resume another

None of what I described above actually requires explicit continuation support from the machine - it only requires some means by which the stack size can be checked (which we already have solutions for today, if a little hackish) and something like setjmp/longjmp to allow rewinding the stack cheaply.

From the research I've done so far though, the use of setjmp/longjmp in WebAssembly via JS exceptions comes at a significant performance penalty, and is basically just a compatibility shim. This makes any language using a Cheney on the MTA style compilation approach unnecessarily slow. A rather well-known example of such a language is Chicken Scheme, and I believe Chez Scheme also uses a similar, if not the same trick.

One alternative is to use trampolines - i.e. rather than longjmp when the stack is about to blow or a yield point is needed, the compiler generates code which returns to a trampoline every time one needs to invoke the next continuation. The problem of course is that it incurs an extra return + function call for each continuation called; however I suspect this is better today in WebAssembly vs the current setjmp/longjmp hack. One could also use an explicit return to unwind the stack, but I suspect that is even slower than the setjmp/longjmp solution.

All this to say, I believe something is needed to make the implementation of languages with similar requirements both feasible and performant. Perhaps that means some kind of native continuation support, or perhaps it means something less robust, like supporting the setjmp pattern I described better. I want to be clear that this isn't just an issue specific to my implementation - the set of languages which has or may have these requirements has some non-trivial members, e.g. Haskell, any standard-conforming Scheme implementation, Erlang (and BEAM languages in general), and essentially any language which depends on proper tail call support, not just the limited version made possible by the fastcc calling convention.

@rossberg Is there a place where I can review the rough sketch of what you are working on with the exception proposal + resumption? I'd like to dig in and see if it holds a solution for me or not. If so, and I can be of any help, I'm happy to try and lend a hand as well to keep it moving along.

If you have any questions (or even suggestions!) about the above, definitely let me know!

[aardappel]

@bitwalker What is not clear to me from the options you describe:

• Using longjmp would imply you use the actual wasm stack (which is not under your control), which means you have no way of determining how much you're using and when you're about to run out of stack space, currently?
• If instead you used you own "shadow stack" in linear memory for storing stack frames, you could reset it without using longjmp, assuming you don't use wasm functions to implement the functions in your language, but instead have all bodies live inside a huge for(;;) switch(..) construct. This might be slower for other reasons (hard to do register allocation?), but at least requires no help from wasm.
• Using a trampoline (with the wasm stack) would preclude uses where the stack frame has to survive, like green threads?

As an aside.. "Cheney on the MTA" is indeed elegant.. its almost like a copying collector, but unlike a full GC a list of stack frames is trivial to copy. Also love that Baker has been serving that paper in the same form from the same url for >20 years :)

[bitwalker]

@aardappel Sure, let me clarify :)

Using longjmp would imply you use the actual wasm stack (which is not under your control), which means you have no way of determining how much you're using and when you're about to run out of stack space, currently?

This is true on more platforms than just WebAssembly, but the trick is that you first define an arbitrary max stack size (say, the smallest size of all the platforms you support if you don't want to conditionally compile with different constants), and then the very first thing done on entry is to take the address of something on the stack (so not technically the stack pointer, but essentially can be used as one), or get the stack pointer itself. Given your max size, the stack pointer (approximated or no), and the knowledge of whether the stack grows up or down on a given target, you can check how much buffer you have between the maximum you have defined and the stack address you hold.

If instead you used you own "shadow stack" in linear memory for storing stack frames, you could reset it without using longjmp, assuming you don't use wasm functions to implement the functions in your language, but instead have all bodies live inside a huge for(;;) switch(..) construct. This might be slower for other reasons (hard to do register allocation?), but at least requires no help from wasm.

You pretty much nailed one major issue here - it destroys the ability to optimize register allocation, which may not be an issue with WebAssembly (?), given its stack machine semantics, but it is definitely something I would avoid unless I had no other choice. A bigger problem is that prevents a whole host of optimizations in the compiler backend (I'm using LLVM, but I've heard the issue is the same with various compile-to-C language implementations).

Using a trampoline (with the wasm stack) would preclude uses where the stack frame has to survive, like green threads?

It may help to understand how execution flows when scheduling. So assume we have some process (read: Erlang green thread) which is executing, and upon entry to the current function, and after checking if the stack needs to be reset, and whether a major GC is required, checks its reduction count (essentially an approximation of how much work it has done since the last yield) and sees that it needs to yield to the scheduler because it is going to exceed its quota:

1. Control branches to what I call a "yield point", where a continuation is constructed which points to the current function, and references the current return and escape continuations, as well as any other arguments.

• These arguments all represent live values on the "real" stack - in CPS form, anything not an argument to the current function is dead or on the heap.

2. Any of the live values which are on the stack are moved to the heap (in our case, each process has its own heap, so the values are moved there).
3. The constructed continuation is stored in the process struct (each process/green thread has a struct with all of its key metadata, such as a pointer to its heap, reduction count, etc.
4. A jump is performed, which returns control to the scheduler.
5. The scheduler pulls the next process to be scheduled off its run queue, gets the continuation for that process, and calls it with the arguments stored in that continuation.

So with that in mind, using a trampoline doesn't prevent this flow, instead it just imposes a costly overhead - rather than being able to call a continuation directly (really just a function pointer at this point), using arguments already on the stack; a continuation must be constructed, and live values moved to the heap, before returning to the trampoline. Doing that for every call is significantly slower than only constructing a continuation when scheduling, GC, or a stack reset occurs.

As an aside.. "Cheney on the MTA" is indeed elegant.. its almost like a copying collector, but unlike a full GC a list of stack frames is trivial to copy. Also love that Baker has been serving that paper in the same form from the same url for >20 years :)

Using the stack as a young generation is a brilliant stroke I thought. And it gets better! Since we're in CPS form, you don't need to copy stack frames, the only live values that need to be copied must be in, or referenced by, arguments to the current function, anything not reachable from those arguments is dead, and effectively collected by the jump :)

Before I encountered the paper, I am sad to say that I wasn't familiar with his work, but Baker is brilliant, I'm a huge fan, especially since as you say he continues to host all of his papers after all these years, essentially unchanged!

[bitwalker]

I want to point out as well that although there is some crossover here with the tail call proposal, I feel like my point is more about arguing for supporting continuations as a language implementation strategy, one way or another. Proper tail calls is essentially the catch of course, but the key lesson behind Cheney on the MTA is that the lack of native support for tail calls can be worked around and remain relatively efficient, given the right tools.

More to the point though, the current tail call proposal is flawed in my opinion, as it essentially describes a trampoline (one must incur the cost of a return + call). One of the key benefits of tail calls is that they are efficient, essentially equivalent to a local goto. Without that, I'm not sure what benefit a tail call instruction in the spec provides, beyond a compiler not needing to generate its own trampolines. Perhaps it will be possible for WebAssembly machines to optimize those instructions into "real" tail calls, but I haven't seen any discussion to that point, and it is a critical one.

I'm not sure what the right solution is, but I do think a key indicator on whether WebAssembly has the right primitives is whether or not functional programs can be compiled to code which is essentially as performant as imperative counterparts (barring other issues, such as immutable data), which boils down to supporting tail calls efficiently, one way or the other.

[rossberg]

the current tail call proposal is flawed in my opinion, as it essentially describes a trampoline (one must incur the cost of a return + call).

@bitwalker, I'm afraid I don't follow. Why do you think that there has to be a trampoline? This is certainly meant to be a regular tail call.

Re resumable exceptions / effect handlers: there are some out-of-date example sketches here. Other than that we currently only have a formulation of a formal semantics, without any usable textual explanation in writing. We should probably write something up eventually, but there hasn't been much activity.

[bitwalker]

I'm afraid I don't follow. Why do you think that there has to be a trampoline? This is certainly meant to be a regular tail call.

I apologize if I misinterpreted! I was referring to this section, where the execution semantics are said to behave like a return followed by a call. It seems like a confusing way to explain them, particularly because of the trampoline connection. I've always seen tail calls as something more akin to a jump and that has been my impression of how other people view them as well. While the main point of tail calls is avoiding overflowing the stack by reusing stack frames, my understanding has been that another key property of tail calls is that they avoid a lot of the shuffling of the stack that happens with return+call or even just a call; more in the case of self-recursive calls, but even more generally in the case of calls to functions with arguments in the same position, where the compiler can avoid moving stuff around. I think I was just expecting to see that conveyed in the proposal. I'm not telling you anything you don't already know about tail calls, I'm just trying to explain why I interpreted the proposal the way I did :)

Other than that we currently only have a formulation of a formal semantics, without any usable textual explanation in writing. We should probably write something up eventually, but there hasn't been much activity.

Thanks for the link! It seems to me that this could probably be used to express the kind of control flow that I am using setjmp/longjmp for (as described above, e.g. Cheney on the MTA), assuming that "resuming" control in an outer call rewinds the call stack to that point. Is that the case?

Either way, is there anything I can do to help? Is the issue getting a reference implementation done, are there still open questions that need research/discussion, or does it just need someone to get it through the process?

[rossberg]

Well, given that caller and callee can have completely different parameter lists, tail calls cannot generally avoid argument shuffling, even if it happens in registers. Of course, engines are expected to minimise that in cases where they match, but that isn't semantically observable. Nothing unusual here, that's how they usually work.

@Danielhillerstrom has started hacking the experimental effect handler design into the reference interpreter as a first step, but I doubt that can be parallelised much. The next step would be preliminary experiments with targeting it, and that's where it could use all the help we can get, if people were trying to play with it, help iterating on the design, perhaps by writing an experimental compiler backend targeting it. But the hardest part by far, if we get there, will be an efficient implementation of multiple stacks / continuations (regardless of concrete design details) in a production engine, which is gonna be super tricky, given the utter complexity of existing JS/Wasm VMs.

[bitwalker]

Well, given that caller and callee can have completely different parameter lists, tail calls cannot generally avoid argument shuffling, even if it happens in registers

My main issue is with this line:

Hence they unwind the operand stack like return does

This sounds a lot like it requires performing the same work that a return + a call performs, even if the implementation isn't strictly a trampoline. The reason why I think the distinction is important is that a key feature of tail calls is that they incur no more overhead than a regular call, in fact less, since no stack frame is allocated. But if tail calls are actually doing twice as much work as a normal call, then that is a huge price to pay for languages where tail calls aren't just an optimization.

I'm not necessarily saying that the proposal is requiring implementations to do it that way, but the way it is worded isn't ideal. Tail calls don't really "unwind" the stack, they overwrite their own stack frame, which I guess has the appearance of unwinding the stack, but is not the same thing. I didn't mean to derail the conversation here, but I think the spec should be explicit about these differences, unless the intention is to avoid requiring tail calls to be implemented as proper tail calls.

@Danielhillerstrom has started hacking the experimental effect handler design into the reference interpreter as a first step

Awesome, is that work public currently, or is it still being hacked together?

The next step would be preliminary experiments with targeting it, and that's where it could use all the help we can get, if people were trying to play with it, help iterating on the design, perhaps by writing an experimental compiler backend targeting it.

Once it is available to play with, even if it takes some work to set up on my end, I'd be open to writing a separate WebAssembly backend for my compiler, rather than using LLVM, or perhaps even by customizing LLVM with some new intrinsics + associated lowering. WebAssembly is an important target for me, so whatever I can do to help.

But the hardest part by far, if we get there, will be an efficient implementation of multiple stacks / continuations (regardless of concrete design details) in a production engine, which is gonna be super tricky, given the utter complexity of existing JS/Wasm VMs.

Yeah, I can imagine. That said, I would think the major engines are all strongly motivated to make it work, if WebAssembly is to become as foundational as it promises to be. Have engineers on those engines commented on this yet? Is it the kind of thing that is feasible and just a matter of time, or fundamentally incompatible with how those engines work today? I have little perspective on how those engines are currently implemented, but having an idea of the constraints they are operating under would be useful context to have for sure.

[rossberg]

My main issue is with this line:

Hence they unwind the operand stack like return does

Ah, don't confuse abstract machine lingo with implementation. This refers to the operand stack within the current function, which is just a notion of the spec's abstract machine and not physically materialised in real engines. This basically says that unused operands are dropped when you tail-call. This is all handled at compile time.

That said, there is no reason to believe that tail calls are faster than regular calls in general. That's a misunderstanding. Their purpose is reducing space, not time! They can well be somewhat more expensive in certain cases.

(The tail call instruction in some commercial engines which shall remain unnamed are notorious for having been up to 100x slower -- I'm confident that we will do better. :) )

Have engineers on those engines commented on this yet?

Of course. Everybody sees the need for some form of stack switching. That doesn't mean that everybody isn't scared...

[bitwalker]

Ah, don't confuse abstract machine lingo with implementation. This refers to the operand stack within the current function, which is just a notion of the spec's abstract machine and not physically materialised in real engines.

Apologies for missing that! That indeed clarifies why it is phrased that way. Thanks for your patience :)

[aardappel]

@bitwalker

but the trick is that you first define an arbitrary max stack size (say, the smallest size of all the platforms you support if you don't want to conditionally compile with different constants), and then the very first thing done on entry is to take the address of something on the stack

Except you can't take the address of anything on wasm stack, by design. The moment you take the address of a local variable (in LLVM or e.g. C++) the wasm code emitted changes the local variable from a wasm local to something on a shadow stack. So you can't measure the wasm stack this way. And you already said you'd be unhappy having everything on a shadow stack.

You could still emulate this.. you could for each wasm function statically compute the total size of all its locals + args + max temps, and use that as a conservative approximation of stack size used, and then execute your stack cleanup (using longjmp or exceptions) once it exceeds some conservative bound you estimate will be an ok amount of wasm stack to be using on any engine. But wasm doesn't specify the min/max stack an implementation should provide, so this is very iffy. You could even try to detect what an implementation provides by running out of stack space on purpose for a variety of recursive functions, count the number of calls, catch the trap, and estimate a conservative stack space bound from that ;)

Again, I think you're better off with a shadow stack, on the whole :)

Frankly, a wasm module should be allowed to at least hint at the amount of stack space it wants the engine to provide, because without such a thing, you would never be able to even use recursive algorithms (that process user data, e.g. a parser) in wasm, if the stack can be arbitrarily small. Or backends would always need to force recursive algorithms to use the shadow stack. Would that make any sense @rossberg @titzer @binji ?

So with that in mind, using a trampoline doesn't prevent this flow, instead it just imposes a costly overhead - rather than being able to call a continuation directly (really just a function pointer at this point), using arguments already on the stack; a continuation must be constructed, and live values moved to the heap, before returning to the trampoline. Doing that for every call is significantly slower than only constructing a continuation when scheduling, GC, or a stack reset occurs.

Ah ok, I was imagining you meant a trampoline for each call/callcc, but you mean it is ideally only used for yield and when you run out of stack space?

Before I encountered the paper, I am sad to say that I wasn't familiar with his work, but Baker is brilliant, I'm a huge fan, especially since as you say he continues to host all of his papers after all these years, essentially unchanged!

Yup, so many "creative" ideas, that are still relevant!