Typed continuations to model stacks

[rossberg]

Motivation

Wasm currently lacks any support for multiple stacks of execution and switching between them.
That prevents it from efficiently representing most control flow abstractions that appear in many modern programming languages, such as

• lightweight (“green”) threads
• coroutines
• generators
• async/await
• effect handlers
• call/cc
• …

In the spirit of Wasm as a low-level engine, it's highly undesirable to add a multitude of ad-hoc features for each of this mechanisms individually.
Instead, it's preferable to identify a sufficiently general mechanism for managing execution stacks that allows expressing all of them.
More concretely, Wasm needs a way to represent, create, and switch between stacks.

Challenges

1. In order to be able to express features like green threads and others, switching stacks must be possible at any stack depth, not just at the bottom of the stack (“deep coroutines”).

2. In order to be able to express features like generators, it must be possible to pass values (back and forth!) when switching to a different stack.

3. In order to be able to validate the usage of stacks, both stacks and the values being passed when switching must be properly typed.

4. In order to inform the semantics of the interaction with other control flow, esp exceptions, it is desirable to have a semantic framework that can explain all such constructs.

5. In order for multiple of the above features to be usable at the same time, they must be expressible in a composable fashion that allows arbitrary nesting.

6. The mechanism must not require copying or moving stack frames, since some engines could not easily do that due to the heterogeneous nature of their stacks.

7. It must not be possible to create cyclic references to stacks, since that would require GC.

Proposal

One known way to address the above challenges is to view stacks slightly more abstractly, through the notion of a delimited continuation.
Broadly speaking, that represents “the rest of” a computation (a continuation) “up to” a certain point (delimited).
Concretely, that certain point is the bottom of a specific stack, while the stack frames on the stack essentially describe the remaining tasks to be completed.

In particular, we can apply known ways to type such continuations, which is not a problem with an immediately obvious solution otherwise.
One specific way of typing continuations and the values communicated back and forth is by following the approach taken by so-called effect handlers, one modern way of representing delimited continuations, which essentially are exception handlers with resumption, where both throw and resume can carry along arguments.

Like with asymmetric coroutines, switching between stacks then occurs through a pair of resume and suspend instructions.
The suspend instruction “throws” a value akin to an exception — we call it an event below — which the resume handles.
The event's tag, like a regular exception tag, determines the types of values passed from suspend to resume point, but also those passed back.

Details

The first central addition is a new form of resumable exception, a.k.a. event.
Such an event is declared with a respective new form of exception definition
(in the binary format this is an exception definition with a certain flag bit):

(event $evt (param tp*) (result tr*))

Unlike a regular exception, events can have return values.

The other central addition is a new (reference) type of continuations:

(cont $ft)

where $ft is a type index denoting a function type [t1*] -> [t2*].
Intuitively, this describes a suspended stack that is resumable with values of types t1* and will ultimately terminate with values of types t2*.

A new stack is created with the instruction

cont.new : [(ref $ft)] -> [(cont $ft)]

which takes a function reference to run on the new stack.
Execution isn’t started before resuming the continuation.

The instruction

cont.resume (event $evt $handler)* : [t1* (cont $ft)] -> [t2*]

resumes such a continuation, by passing it the expected arguments t1*.
Once the computation terminates, it returns with t2*.
If the computation suspends before termination (see next instruction), with one of the event tags listed, then execution branches to the respective label $handler.
This happens without unwinding the stack.
The label receives the event arguments tp* and a continuation of type (cont $ft'), where $ft' is the function type [tr*] -> [t2*] of the next continuation.

Continuations are single-shot, that is, they cannot be resumed more than once.
An attempt to resume an already resumed continuation traps.

A computation running on its own stack (i.e., initiated as a continuation), can suspend itself with the following instruction:

cont.suspend $evt : [tp*] -> [tr*]

where $evt is an event of respective type [tp*] -> [tr*].
Essentially, this passes control back to the parent stack.
That is, like throw the exception takes arguments tp*, and transfers control to the innermost cont.resume, or rather, its handler label, respectively.
But unlike regular exceptions, execution can also be resumed, which returns here with values of type tr*.

As described above, the innermost active handler matching the event tag receives the event's tp* and a new continuation.
Resuming this continuation (with cont.resume) will therefore pass back tr* to the originating cont.suspend.

Resumption can nest, i.e., a continuation may itself resume another continuation.
Consequently, an event may generally pass through multiple parent stacks before hitting a matching resume handler.
The same chain of stacks is maintained when resuming.

Note how the exception tag ties together the types of the values passed in both direction between a matching suspend and resume.
Different suspension points within the same computation can use different exception tags and thereby pass different types of values back and forth between parent and child stack.

Continuations are first-class values that are allowed to escape a handler.
That way, a stack can be kept live to be resumed at a later point.
The stack’s lifetime ends when the final resume terminates regularly (or with an exception, see below).
Managing the lifetime of continuations/stacks and evtrefs generally requires reference counting in the VM.
However, it’s impossible for them to form cycles, so general garbage collection is not needed.

Finally,

cont.throw $exn : [te* (cont $ft)] -> [t2*]

aborts a continuation by injecting the (regular) exception $exn with arguments of type te* at the suspension point.
This is a way to explicitly unwind the stack associated with the continuation.
In practice, a compiler should make sure that every continuation is used linearly, i.e., either resumed or aborted with a throw.
However, there is no simple way to enforce this in a type system, so Wasm validation won’t be able to check this constraint.

Example: A simple generator

To see how these mechanisms compose, consider encoding a generator enumerating i64 integers from 0 up until a certain condition is met.
The consumer can signal back this condition by returning a bool (i32) to the generator.
This can be expressed by the following event.

(event $enum-yield (param i64) (result i32)) 

Here is the actual generator:

(func $enum-until
 (param $b i32)
  (local $n i64)

  (local.set $n (i64.const -1))

  (br_if 0 (local.get $b))
  (loop $l

    (local.set $n (i64.add (local.get $n) (i64.const 1)))

    (cont.suspend $enum-yield (local.get $n))

    (br_if $l)

  )

)

Here is one possible consumer, which runs the generator until a given max value is reached:

(func $run-upto (param $max i64)

  (local $n i64)

  (local $cont (cont (param i32)))
  (local.set $cont (cont.new $enum-until))

  (loop $l

    (block $h (result i64 (cont (param i32)))
      (cont.resume (event $enum-yield $h)
        (i64.ge_u (local.get $n) (local.get $max))

        (local.get $cont)
      )
      (return)
    )

    (local.set $cont)
    (local.set $n)
    ;; ...process $n...
    (br $l)
  )
)

Note how the handler $h takes both the i64 argument produced by the generator and the next continuation.

Example: A simple thread scheduler

For a more interesting example, consider a simple scheduler for green threads.
We define two events with which a thread can signal the scheduler to either yield or spawn a new thread:

(event $yield)
(event $spawn (param (ref $proc)))

where

(type $proc (func))

We further assume that there is a global variable encoding a thread queue in form of a list of coninuations:

(global $queue (list-of (cont $proc)) ...)

The exact representation does not matter, so list-of is just pseudo code.
All we need is three obvious operations on this queue, ignoring their details:

(func $enqueue (param (cont $proc)) …)
(func $dequeue (result (cont $proc)) …)
(func $queue_empty (result i32) …)

Given these prerequisites, a simple scheduler loop can be implemented as follows:

(func $scheduler (param $main (ref $proc))
  (cont.new (local.get $main)) (call $enqueue)
  (loop $l
    (if (call $queue_empty) (then (return)))   ;; program is done
    (block $on_yield (result (cont $proc))
      (block $on_spawn (result (ref $proc) (cont $proc))
        (call $dequeue)
        (cont.resume (event $yield $on_yield) (event $spawn $on_spawn))
        (br $l)                                ;; thread terminated
      )
      ;; on $spawn, proc and cont on stack
      (call $enqueue)                          ;; continuation of old thread
      (cont.new) (call $enqueue)               ;; new thread
      (br $l)
    )
    ;; on $yield, cont on stack
    (call $enqueue)
    (br $l)

  )

)

TODO: More examples.

Interaction with regular exceptions

Regular exceptions and events are disjoint.
An exception handler will not catch events and vice versa.

If resuming a continuation throws a regular exception that is uncaught on its stack then it propagates through the active resume, unwinding the stack encapsulated in the continuation and ending its lifetime.

Yielding an event on the other hand does not trigger exception handlers between the suspend and the resume point.
They become active again when the continuation resumes and execution thereby switches back to their stack.

Note that this dichotomy could, in principle, be used to implement exceptions with two-phase unwind: the first phase is represented by an event, whose handler then injects back a proper exception to unwind. However, such a an implementation would be fairly expensive, since every exception handler would have to run on its own stack.
It is still useful as a semantic explanation of what ought to happen, and how two-phase unwind would interact with single-phase exceptions.

[kripken]

Is this identical to what you presented in the past @rossberg ? (If not a summary of the changes might be useful.)

[rossberg]

@kripken, yes, up to some renaming and minor tweaks.

[kripken]

Got it, thanks @rossberg .

[RossTate]

Is there another proposal on the way on how to support applications of stack inspection, e.g. two-phase exception handling, resumable exceptions, C#/Python-style generators, stack tracing, linear-memory garbage collection, stack duplication?

[taralx]

cont.throw doesn't take an evtref, so it's not possible to respond to an unknown suspension with an exception. Is that intentional?

The new function type $ft' : [tr*] -> [t2*] isn't a type that the module specifies, but one that is synthesized from other types. Doesn't that make for significantly more work at validation-time, as the synthesized type has to be checked for compatibility with a (later) specified function type?

[taralx]

@RossTate Doesn't this support those, if indirectly, since the exceptions are resumable?

[tlively]

@taralx I believe you're right that all of those features can be implemented in terms of this proposal. However, for many of those features, allocating an entire new stack would be overkill. Proposals for stack inspection, two-phase unwinding, etc. are essentially special cases of the feature proposed here that can be implemented more efficiently.

[RossTate]

Yes, and on top of that, this proposal requires running code just to find out if an inspection site is relevant to the inspection at hand. So I'm wondering if interaction with (more efficient) stack inspection has been taken into account in this design.

[RossTate]

Putting stack inspection aside, the lightweight-threads example seems to be a relatively inefficient implementation of lightweight threads. Ideally, switching between threads just involves a few instructions to switch contexts. But in this proposal, switching threads involves a stack walk to find the relevant br_on_evt, which is not necessarily cheap.

[rossberg]

@taralx:

cont.throw doesn't take an evtref, so it's not possible to respond to an unknown suspension with an exception. Is that intentional?

That's a good point. But you cannot actually get an evtref for an unknown suspension either, since each handler is guarded by a list of known events. The idea here was that a handler has no business interacting with an unknown suspension -- that would destroy composition. But maybe there are use cases for a handle-all.

The new function type $ft' : [tr*] -> [t2*] isn't a type that the module specifies, but one that is synthesized from other types. Doesn't that make for significantly more work at validation-time, as the synthesized type has to be checked for compatibility with a (later) specified function type?

I don't think so, since validation already has to be able to treat multiple definitions of the same function type as compatible. Function types are structural, even in the MVP.

FWIW, there is a similar question regarding func.bind and other such instructions. Currently, it takes a target type as immediate to side-step the issue, but it would actually be enough (and cheaper to check) if it just had an numeric immediate that indicates the number of parameters to bind and synthesise the resulting function type.

So generally speaking, we have to decide whether we want to avoid synthesising, at the price of more type annotations and checking on instructions like these, or if we're fine with synthesising such types (which may require slightly more work in the spec primarily).

@RossTate Doesn't this support those, if indirectly, since the exceptions are resumable?

It does, and more importantly, it does so in a composable fashion -- an important point I forgot to include (added). I.e., you can use multiple of these features together at the same time, even if they are implemented separately.

@tlively is correct however that there is one special case where creating a new stack can be overkill, namely when the continuation does not escape the handler. In practice, though, handling some of these cases without a stack would require the introduction of either fragmented stack frames, display chains, or scope restrictions that essentially make it equivalent to just calling another function. It is worth investigating if adding those mechanisms is a relevant win over implementing them in user space.

@RossTate:

Putting stack inspection aside, the lightweight-threads example seems to be a relatively inefficient implementation of lightweight threads. Ideally, switching between threads just involves a few instructions to switch contexts. But in this proposal, switching threads involves a stack walk to find the relevant br_on_evt, which is not necessarily cheap.

That is not correct. Handlers are associated with resume points, not branches. Consequently, a handler is only present "at the bottom" of each non-suspended stack, and there is no need to walk an actual stack. Moreover, each resume declares a list of tags it handles. So transferring control to a handler can e.g. be implemented by an indirect jump through a (thread-local) side table associating each event tag with its active handler.

[RossTate]

It does, and more importantly, it does so in a composable fashion -- an important point I forgot to include (added). I.e., you can use multiple of these features together at the same time, even if they are implemented separately.

Yes, and the same is true for every other suggestion that has been made for directly supporting these features. Only the suggestion of implementing shadow stacks within WebAssembly without direct support is not composable.

however that there is one special case

Let's work through the first such "special case" that was discussed four months ago: linear-memory garbage collection. Runtimes and programs with their own (linear-)memory management generally have some way to inspect the stack to find and later update the GC roots on demand. These programs now want to compile to WebAssembly and want some way to inspect the stack on demand to find and update these roots (albeit in a safer manner per WebAssembly's security requirements).

Your proposal is to allocate a new stack at every point someone would want to perform such inspection. For these applications, nearly every stack frame has such a root and therefore such a need. So your proposal is essentially to have these applications allocate every stack frame on its own separate stack. @aardappel, as someone who has been particularly advocating for this feature, do you think this would serve your needs?

Now the second "special case" that was discussed was stack tracing. All the most-used garbage-collected languages have some means for collecting/examining the stack trace (sometimes even lazily using an interactive stack walk) during execution even in production mode (not just debug mode). Again, nearly every frame would need to provide stack-trace information, so again your proposal would have all these languages allocate every stack frame on its own separate stack.

Moreover, each resume declares a list of tags it handles.

Ah, missed this change. There's a bug though. cont.forward also needs to specify a (handler) label and a list of events.

Oh, and another (unrelated) bug: cont.throw needs to consider that the continuation might catch the thrown exception. So it has an output type, and it needs to specify a (handler) label and a list of events.

Consequently, a handler is only present "at the bottom" of each non-suspended stack, and there is no need to walk an actual stack. Moreover, each resume declares a list of tags it handles. So transferring control to a handler can e.g. be implemented by an indirect jump through a (thread-local) side table associating each event tag with its active handler.

This assumes a particular implementation strategy and infrastructure, essentially baking in decisions that would often be made at the application level (e.g. should this dynamically scoped variable be implemented using a stack walk or using thread-local storage). If we're going to assume there is always the infrastructure for thread-local storage, it might be a good idea to incorporate the feature directly into WebAssembly, since it's useful for a lot more than just continuations. Regardless, this means that in the examples above every call and return (in the surface language) would have to update thread-local storage. In general, every suspend/resume, forward, and throw will have to update thread-local storage, which common implementations of lightweight threads do not need.

[RossTate]

When you presented this proposal six months ago, it was really great. You provided a lot of great ideas and garnered a lot of interest for an unconventional yet useful feature. That sparked a lot of productive conversations within the CG. Those conversations explored the design space, identifying weaknesses in the specifics you presented and then searching for alterations and extensions that would address those weaknesses. That is exactly what the effect of a good presentation should be. But this design has barely changed to incorporate those many related conversations within the group over the months since.

[aardappel]

This design seems especially well suited to implement first class stack-full asymmetric co-routines, as it maps relative 1:1 on its implementation needs.

One place where it is more general than such a co-routine feature is the use of event tags, which essentially allow one to yield not just from the current co-routine, but from any of the parents, presumably suspending a chain of co-routines in the process. It is not quite clear to me when this is useful, and I could imagine it having an implementation cost. I guess this gives us the flexibility of continuations where each stack frame has its own lifetime.

The machinery also seems quite heavy-weight for typical uses of "generators", which tend to function more like fancy for-loops than anything else. There would have to be some kind of guarantee that it is easy to collapse this functionality (no dynamic allocations, re-use of the same stack etc etc) for this to be feasible. Leaving this up to the cleverness of the engine makes it useless.

That holds even more if this is to be useful for stack inspection like @RossTate mentions. Even if we can specify that in simple cases these instructions translate to something close to no-ops, it seems like it would generate a lot bigger binaries than the simpler stack inspection proposal. To me, the whole point of having something like a stack inspection feature is that it is more efficient than a shadow stack, so if there's even a small chance that it isn't (e.g. requires a dynamic allocation) then it will not be used.

So as it stands, this feature seem limited in its applicability, unless its generality can be subdivided in semantically more restrictive uses with different implementation requirements. That is counter-intuitive maybe: the more general a feature is, the more things it can represent. But potentially the less features it can represent efficiently, which is what matters the most for Wasm, I feel.

[RossTate]

Another consideration is how to inspect (efficiency aside) the delimited continuations. For example, a garbage-collecting lightweight-thread manager needs to collect (and later update) the roots across all the lightweight threads. Given a particular cont representing a yielded lightweight thread, it's not clear how the thread manager can reasonably collect the cont's roots using this approach.