Should the WebAssembly machine enforce 'structured concurrency'

[fgmccabe]

Structured concurrency is an interesting extension to the well established notion of structured programming. One of the early promoters of this idea is Nathaniel Smith, in his introduction to Python trio.

Other language communities, notably Kotlin, are also taking up the challenge of offering structured concurrency features for their users.

Support for structured concurrency is implicit in the typed continuations proposal and in the fibers proposal; in the suspend/resume pattern: every computation has a specific owning computation (although that can change too).

Such support for structured concurrency is not free: the machine needs to establish that the parent chains for computations are always valid. Unlike for structured programming concepts such as for-loops and if-then-else (c.f. unstructured goto) which can be verified at compile time, the parent chains of coroutines need dynamic support. The fundamental reason is that the parent chains can and do mutate during an application's lifetime. (For example, an async function's original parent may be a click handler attached to a button; but, after awaiting a Promise, the async' parent becomes the browser's micro task runner.)

The question is: is it the responsibility of the engine to enforce structured programming guarantees? Or is it the responsibility of the toolchain?

[rossberg]

I am not sure the last paragraph is posing the right question. In the case of Wasm, structure is a means not an end. For example, the structure of functions and calls enables the engine to maintain important invariants and safety guarantees at minimum cost. It also enables it to apply high-level optimisations, like inlining.

Wasm deliberately chose functions as a structured abstraction. It could have provided a single br-to-subroutine instruction instead, making the whole program one big code area, but didn't.

We also have to consider interaction with other structured control features beside functions, especially exceptions, which assume a well-formed stack discipline. Decoupling stack switching from it and put it fundamentally at odds with such structure would require a very convincing argument IMHO.

There is no evidence yet that a less structured approach is more efficient. In fact, the opposite may be true, especially if the producer has to emulate much of the structure in user space, without giving the engine the same ability to optimise it (or when it requires more dynamic checks). We can only find out through experimentation.

[RossTate]

In yesterday's meeting, we worked through a particular use case of Python's widely used greenlets (implemented in mostly C++, with some platform-specific assembly for switching), and some of that discussion is relevant to this topic.

In particular, Python has a form of "structured concurrency"; specifically, every (user/non-rooted) greenlet has a parent that its returned value or thrown exception (except for GreenletExit) is forwarded to, much like the delimited continuations in both the fibers and the typed-continuations proposals. However, despite that similar structure, the discussion concluded that Python greenlets would not be able to use the delimited structure already present in those proposals; in fact, the discussion concluded that WebAssembly probably should not try to make it so that Python greenlets can reuse any delimited structure WebAssembly's design might provide.

There were two issues in particular. The first is that the parent of Python greenlets is mutable, even while it is executing, and in particular the same greenlet can be a parent of multiple other greenlets. (The hierarchy is dynamically enforced to form a forest, with each thread's "main"/rooted greenlet as the only roots.) The second is that a switch/throw/return to a "dead" greenlet (i.e. one that has finished executing) needs to be automatically redirected to its parent. These two properties seem to be how greenlets were able to move the application's particular specification of the "structure" of "structured concurrency" into user space rather than language/library space.

We observed that, unless we were to build in precisely greenlets' "structured" semantics, greenlets would have to disregard any structure WebAssembly provides and resort to direct switching—as best as it can be emulated in whatever design WebAssembly provides—including for returning or forwarding exceptions to parents. We also observed that it would likely be less effort on the greenlets' maintainer's part to use direct switching (or an emulation thereof) than to hook into WebAssembly's "structured" design. We estimated that both of those observations would likely generalize to other libraries/languages.

These observations/estimations suggest to me that efforts to provide/enforce "structured concurrency" for an application to use internally would likely often go to waste. Worse yet, attempting to do so will bring various application-space problems into WebAssembly-space (e.g. detecting cycles when mutating parents or forwarding control flow through dead fibers/continuations) when they needn't be our problems. (Note that there might be value in maintaining some "structured concurrency" across applications with no knowledge of each other's structure, for the sake of composition or abstraction, but that's a separate issue from providing built-in structured concurrency for application components to use even when they have knowledge of each other's structure.)