Proposal: First-Class Stacks

[RossTate]

There are a number of control-flow patterns that go beyond the classic "last-in first-out" form. Coroutining, iterators based on yield, asynchronous I/O and, more exotically, delimited continuations, are all examples of non-linear control flow. These patterns are becoming increasingly important in applications that are intended to be dynamically responsive.

While it is possible to emulate many of these control-flow patterns using standard core WASM features, there is significant cost in doing so — in terms of run-time efficiency, code size, and composability.

At the same time, the space of control-flow patterns is sufficiently diverse that it may not be appropriate to design special mechanisms for each of them. Even focusing on coroutining, for example, there are at least two common patterns of coroutines—so-called symmetric and asymmetric coroutines—with significantly different implementation requirements. Furthermore, the details of how data is exchanged between coroutines also varies greatly; reflecting choices made at the language-design level as well as application design.

This proposal focuses on a suite of low-level mechanisms that would allow language implementers to build different variations on cooperative multi-tasking. Specifically, we focus on enabling the execution of WebAssembly programs on multiple stacks that a WebAssembly application can switch between.

Although important, we do not directly provide the mechanisms necessary to exchange messages between coroutines, nor do we "take a stand" on issues such as whether to support asymmetric vs. symmetric coroutines. Instead we provide the primitives that—in conjunction with other functionality WebAssembly already provides—enables the language implementer to develop their own mechanisms. We do, however, establish the framework for communicating the status of a coroutine when switching to another stack. That status must encode whether the coroutine is terminating and may encode values as part of that event.

A detailed presentation of this proposal can be found here, including detailed examples of how it can be used to support cooperative lightweight threads, asynchronous I/O, and (coming soon) multi-shot tagged delimited continuations. Here we (@fgmccabe and I) present a summary of the key ideas.

Stacks

The proposal introduces a single type: stackref. A stackref is a reference to a complete stack. In particular, the stack never returns and is equipped with a "grounding" frame generated by the host that determines what to do if ever the stack completes execution through other means (e.g. traps). Depending on how the stack was created, that grounding frame might terminate the thread worker the stack is running on or might cause the next event in the event loop to be processed. Details aside, the point is the stack is self contained and can be executed on its own.

In terms of implementation, a stackref references the leaf or active frame of the stack, rather than its root. This is represented by an instruction pointer paired with a stack pointer.

Stack Switching

The key instruction in the proposal is stack.switch:

• stack.switch $event : [t* stackref] -> unreachable
  • where event $event : [t* stackref]

This instruction transfers control to the designated stack. The event is repurposed from the exception-handling proposal. It is used to convey a message to the target stack. The t* values are the payload of that message plus a stackref. The stackref in the message is the reference to the stack that was just switched from, which is now in a suspended state.

So if a lightweight thread (implemented as a stackref) wanted to yield control to another lightweight thread, it would do so with the following (where we use catch $yielding $yielded as shorthand for "catch only $resuming exceptions and branch to $resumed):

(event $resuming (param stackref))
(func $add_thread_to_schedule (param $thread stackref) ...)
(func $yield_to (param $thread stackref)
  (block $resumed
    (try
      stack.switch $resuming (local.get $thread)
    catch $resuming $resumed
    )
  ) ;; $resumed : [stackref]
  (call $add_thread_to_schedule)
)

The output type of stack.switch is unreachable. That is because the instruction leaves the current stack in a suspended state, and when control is transferred back, the conveyed message is conceptually thrown as an exception from that point. In practice, we expect engines to optimize for this pattern and only throw an exception (i.e. start an unwinding stack walk) if there isn't a statically known catcher for the event.

Notice that this design provides extremely fast switches between stacks. One essentially just swaps the instruction-pointer and stack-pointer registers with the registers storing the instruction pointer and stack pointer of the target stackref.

Stack Construction

Because the host needs contextual information to create a grounding frame (e.g. is this module instance running on a thread worker or on the event loop), we provide no instruction for creating stacks, instead expecting modules to import a function for creating stacks from the environment, e.g. (import "host" "new_stack" (func $new_stack (result stackref))).

Instead, we provide a process for extending stacks with additional stack frames. This is particularly useful for initializing a new stack, but can also be used to implement (at the application-level) multi-shot continuations.

For this, we need a way to describe stack frames, and in particular stack frames that are ready to be switched to receive events. The following is an example of a func one could use to describe the initial stack frame of a lightweight thread:

(event $completing : [i32 f64 stackref])
(func $do_work (param f64) (result f64) ...)
(func $get_thread_manager (result stackref) ...)

(rout $thread_root (param $id i32) (param $input f64) (local $output f64)
  (block $aborted
    (try
      (block $resumed
        (try
          stack.start
          unreachable
        catch $resuming $resumed
        )
      ) ;; $resumed : [stackref]
      (call $add_thread_to_schedule)
      (local.set $output (call $do_work (local.get $input)))
      (stack.switch $work_completed (local.get $id) (local.get $output) (call $get_thread_manager))
    catch $abort $aborted
    )
  ) ;; $aborted : [stackref]
  (stack.switch $resuming)
)

Notice the instruction stack.start. This is used only by stack.extend (below) to say where execution should start when the added (suspended) stack frame is resumed, and it can only be preceded by event-handling setup instructions (like block and try). So in this example, the thread is set up to so that the first time it is resumed it starts to $do_work. The implementation of which may in turn call $yield_to, but eventually all the work gets done, in which case the lightweight thread switches control to the thread manager, handing off the result of its work.

To extend a stack, say to add $thread_root to a newly created stack, one uses stack.extend:

• stack.extend $func : [t* stackref] -> unreachable
  • where func $func (param t*)

Stack Destruction

This example also illustrates how one can implement their own thread-aborting mechanism. Given a stackref for a lightweight thread, you can send it an $aborting message. That message is not handled by $yield_to, and as such will be thrown and cause the stack to be unwound, until eventually $thread_rout is reached, in which case it will transfer control back to the stack that initiated the aborting (which in turn will drop the stackref in the payload).

Stack Redirection

Many applications "compose" stacks together. This composition, however, is an illusion. The stack components are of course distinct entities, but stack walks are redirected from one stack to another. In this manner, a WebAssembly application can run its entire body on its own stack, but have any exceptions thrown by host code called within that body be redirected to the host stack that initiated the application in the first place. Changing this redirection lets an application conceptually detach its stack from the current host stack, e.g. the current event handler, and attach it to another host stack, e.g. the handler for a promise. A full account of how to support asynchronous I/O with stack redirection can be found here.

Stack-walk redirection is supported by the following instruction:

• stack.redirect $local instr* end : [ti*] -> [to*]
  • where local $local : stackref
  • and instr* : [ti*] -> [to*]

Whenever a stack walk (say due to an exception being thrown or due to a stack inspection) reaches stack.redirect, the walk is redirected to the stackref in the local variable $local at the time.

Summary

With a new stackref type, a new rout construct, and a few new instructions, this proposal enables applications to treat stacks as first-class values. Every instruction is constant time. The proposal is designed to make use of the existing exception-handling infrastructure, and is designed to compose well with stack inspection. The proposal is independent of garbage collection (e.g. introduces no cycles), and the only implicit memory management is that a stack must be implicitly freed when its stackref is implicitly dropped. But with the combination of these proposals, we have conducted case studies suggesting that this proposal can implement a wide variety of features in the same manner as many existing industry implementations. The only significant shortcoming we have found so far is that stack duplication, needed for multi-shot continuations, is substantially more complicated than would be necessary if the language had complete trusted control over the runtime.

[aardappel]

On first glance this seems more low level than #1359, which generally seems like a good direction. Can you give a summary of the major differences?

"a process for extending stacks with additional stack frame".. this is the least clear to me. Generally a stack receives a new stack frame on every function call.. what is the run-time cost of this "extension"? Does it have benefits (in terms of needed to pre-allocate less memory)?

[kayceesrk]

I should say that multi-shot continuations make programming with resources quite difficult. When a programmer writes a function, there is an implicit assumption that the function will return exactly once (either normally or exceptionally). Developers write code that defensively guards against these two cases. With multi-shot continuations, the functions may return more than once and this can break code that has nothing to do with continuations. Consider the hypothetical example,

   m = malloc ();
   try f () with e -> free m; throw e end;
   free m

f may yield to another lightweight thread, which may duplicate the captured continuation and resume both of them. The second resumption would lead to a double-free error. This is due to no fault of the above code snippet as it is unaware that f was going to capture the current continuation.

[RossTate]

@aardappel I'll try to write that summary up for you shortly. As for extension, it lets you add a stack frame to a stack that is not being executed. I don't know if that answers your question though.

@kayceesrk Your concern is one of the reasons why we chose not to offer direct support for multi-shot continuations or stack duplication. That is, programs do not have to worry about their stacks being arbitrarily duplicated. But for programs that do want multi-shot continuations, they can combine stack inspection and stack extension to build duplicates of (just) their own stack frames. So if you want the functionality, you can implement it for yourself, but only for yourself.

[taralx]

I'm not clear on why stack.switch injects an exception into the receiving stack instead of just resuming it. Is it so that the stackref doesn't have to be typed?

[taralx]

I also don't understand the semantic difference between the rout that has a stack.start and a similar function that also accepts a stackref parameter.

[RossTate]

Is it so that the stackref doesn't have to be typed?

Yes. We've found a number of more advanced examples have multiple receiving events, and we didn't find that types would save much (if any) performance, for reasons similar to call tags (switching on the event tag is easy, and then you can turn it into an exception if you don't recognize it). I also am writing up an example right now that happens to make use of the dynamic scoping of handlers.

I also don't understand the semantic difference between the rout that has a stack.start and a similar function that also accepts a stackref parameter.

Can you clarify what this similar function you are envisioning does?

[taralx]

Hm, well, the example you have catches two different exceptions at that point, so I retract my earlier comment. It is different from the equivalent function.

[RossTate]

@aardappel This proposal is certainly lower level than that of #1359. I've written up a translation of #1359 into this proposal in soil-initiative/stacks#10. The translation should illustrate both the versatility of this proposal and how #1359's instructions are each a combination of lower-level operations, some of which are not obviously cheap. I can give a summary of it and the takeaways later, but at the moment I need to go to bed. This was a surprisingly fun exercise that I probably should not have let keep me up so late 😄

[kayceesrk]

IIUC stack.switch is symmetric in the sense that it allows the transfer of control from one stack to another. In particular, switch has to name the stack to which the control has to switch to. In this respect, it is similar to other control operators like shift from shift/reset and throw from call/cc where one would specify the target of the control transfer. Explicitly naming the target hinders composability. Here's what I mean by that. Consider the compilation of a program that composes an asynchronous I/O scheduler and a python style generator? It is natural to have the asynchronous I/O scheduler wrapping the entire program, with the driver for the generator sitting at a higher level. Something like:

aio_scheduler (
   ....
   spawn (....
        generator_driver (... foo ...)
     ....)
  ....)

where foo can both yield a value to the generator and perform asynchronous I/O. When performing a blocking socket.accept, the continuation captured should include the generator driver as part of the continuation. The symmetric view of the stacks does not capture the hierarchical nature of the two schedulers. The captured continuation in foo would be delimited by the generator_driver. With #1359, this hierarchical nature is naturally captured leading to the easier compilation of such compositions. foo doesn't name the target stack when performing socket.accept and the current dynamic stack of handlers captures the intended hierarchical relationship. In particular, neither the generator nor the aio_scheduler needs to be aware of the other users of delimited control operators in the current dynamic scope, which is what I mean by composability.

I also am writing up an example right now that happens to make use of the dynamic scoping of handlers.

I suppose you are planning to show how something like this works in your example.

[RossTate]

In this respect, it is similar to other control operators like shift from shift/reset and throw from call/cc where one would specify the target of the control transfer.

I see your reasoning, but the comparison is imprecise. For example, shift from shift/reset involves performing a stack inspection to find the closest containing reset in the evaluation context. That reset then informs you what stack to switch to.

Notice that this involves two steps: find the stack to switch to, and then switch to it. This is generally true for control operators in surface-level languages, and it is likewise true for #1359. But this proposal is much lower lever, and as such we have made those steps separate, and we have found that applications make use of them in a wide variety of manners.

The issue with composability you allude to has to do with how the stack is found. As you say, shift/reset has the problem that its semantics for finding the stack often finds the wrong stack (i.e. features interfere). But our proposal, being low level, does not prescribe in any way how the stack is found. It is up to the application to specify that process, and we have found that they do so in a wide variety of manners.

Part of the misunderstanding is my fault though. In the linked detailed write-up, I make clear that this is designed to complement a design for stack inspection (such as in #1356), which is the low-level feature used by most control operators to implement their stack-finding process. The design in #1356, and used by our examples, repurposes call tags in a manner that ensures composability in much the same way that the event in #1356 ensures composability.

If you want to understand this in more detail, I recommend reading the write up on how to implement composable stacks in this proposal provided here. Or, if you're up for a deep dive, you can read the write up on how to implement all of #1356 in this proposal here.

[kayceesrk]

Thanks for the response @RossTate.

If you want to understand this in more detail, I recommend reading the write up on how to implement composable stacks in this proposal provided here. Or, if you're up for a deep dive, you can read the write up on how to implement all of #1356 in this proposal here.

I'll have a read through this.

[aardappel]

@RossTate Thanks for https://github.com/soil-initiative/stacks/pull/10/files?short_path=4d5ad29#diff-4d5ad29d317b0ffd003c55a1b691f51e. The first thing I wonder is the try catch around the stack switching code in resume.. does that imply this functionality is inherent in #1359, and/or that it is compositional with your proposal and you wouldn't need it for most uses?

It seems obvious that your proposal is more low level / has smaller/simpler primitives, though typically if you express 2 language features with the other, they can both end up looking verbose from the perspective of the other :)

[RossTate]

@aardappel Unfortunately, I am not quite sure what you are asking (as in, I can read it multiple ways, each of which is sensible, but among which I cannot tell which is your intention). Do you mind clarifying? If it helps in the meanwhile, I've added a second translation of #1359 to the pull request, this time using thread-local storage as was suggested here (supposing such an extension were made to WebAssembly).

though typically if you express 2 language features with the other, they can both end up looking verbose from the perspective of the other :)

Certainly. I tried to emphasize the points in the translation that are meaningful rather than those that are just shuffling. However, there do seem to be some important features missing from #1359. For example, this concern about the inability to inspect continuations, say for linear-memory GC roots, has yet to be addressed. So it seems likely that translating this proposal into #1359, while likely possible, would be unlikely to be faithfully represent a realistic implementation.

[aardappel]

@RossTate apologies, I am simply trying to get a sense of to what extend your translation of the #1359 primitives reflects the required semantics of #1359 or is simply an "impedance mismatch" between the two proposals. In particular, whether the use of a try catch in your resume is inherent in #1359.