Should Switching be 'entangled' with communication

[fgmccabe]

Most of the designs that we have considered for stack switching have the feature that, along with switching computation between activities, we also 'communicate' some data.
The reason for this is a combination of two requirements: (a) it is often the case that data does need to be communicated (for example, when a generator yields, it also needs to 'return' the value it found to the generator's consumer; and (b) it is also often necessary to communicate the reason for the switch: in a suspend/resume pattern the yielder needs to communicate it's reason for suspending and, when a computation is resumed, some way of encoding the success or otherwise needs to be transmitted.

These are compelling reasons for simultaneously communicating some data along with the switch.

However, many, if not most, languages that offer coroutining capabilities separate these functions. For example, in go-lang, channels are used to communicate data. Furthermore, entangling them can make some run-time tasks more difficult. For example, in Swift, the starting and stopping of tasks is the responsibility of the scheduler; and the scheduler does not manage the data portion of the switch. One reason for this is that the types of data communicated are inherently private to the switching (sic) parties and the scheduler cannot be aware of it.

Separating the functionalities would undoubtedly enable a simpler design; at a potential cost of performance. Effectively, languages that use channels rely on storing results and tasks in memory during a stack switch.

[dead-claudia]

I can think of one language that could benefit from a more coupled model: Rust. Its async/await works at a high level as follows:

• Each future is polled for completion. Poll::Pending signifies it's still in progress, and Poll::Ready(result) signifies completion.
• There's a notion of async fns and async blocks that return futures driven by the usual internal coroutine-like mechanisms. Each poll call drives this internal coroutine to its next return or yield.
• When awaiting a future, it calls that future's poll. If that method returns Poll::Pending, the call to the outer future's own poll returns Poll::Pending.
• When an async fn or async block returns, the poll call that caused it to run returns Poll::Ready.

If this sounds similar to JS's async/await, it's because it works more or less the same way, just using a pull-driven API instead of a push-driven one.

Edit: Rust is also looking into coroutines that work more or less the same way, and those are very likely to require returning values from suspends as well. Lowering that to underlying function returns will of course be simpler than using a global variable.

[dead-claudia]

@Pauan

And the only thing an executor needs is some way to spawn global "threads" and sleep/wake those "threads". [...]

At a high level, yes(ish), but there's a couple more things they need:

• A way to track these "threads" as first-class values
• A way to know the difference between a "thread" sleeping/yielding and one returning

Also, executors do not need a way to cause threads to sleep - they rely on the "threads" doing that on their own.

[fgmccabe]

As far as I can tell, there should be no 'entanglement' between any stack switching design and linear memory. There are some constraints, such as not requiring GC to be implemented and not requiring a language to use GC even if it is implemented. But, generally, these appear to be totally orthogonal aspects. Unless I am missing something?

[dead-claudia]

@fgmccabe Couple things admittedly got lost in the weeds:

• I didn't initially realize Rust did exactly what C compilers did with using linear memory for the stack, and so I'll take all those concerns back.
• I had to dig a lot deeper into what everyone was doing to actually understand what I was looking at (and to stop making such an ignorant ass out of myself).

For all that, I apologize for the mess.

[RossTate]

@dead-claudia I appreciate you engaging in the discussions. It's a big space, and we're all developing an understanding of it together 😃 (@Pauan Your engagement is also appreciated!)

[Pauan]

I didn't initially realize Rust did exactly what C compilers did with using linear memory for the stack, and so I'll take all those concerns back.

To be clear, Rust uses linear memory for everything: the stack, the heap, and also static pre-initialized data. The entirety of Rust programs run in linear memory. Rust's memory model is quite similar to C/C++ (and indeed Rust has an FFI that allows for seamlessly combining Rust and C/C++ code in an ABI compatible way).

Because Rust does not have a garbage collector, it doesn't really benefit from GC or refs (except when interoperating with JS or other Wasm modules). And it also doesn't benefit much from higher-level features, because it's such a low-level language. Since everything is managed by Rust in linear memory, it only needs a very small number of simple runtime primitives.

Because Rust is so self-contained, many Rust programs and libraries already work perfectly in Wasm (with the same behavior and performance as natively). Rust async/await and generators already work perfectly fine in Wasm. The programs that don't work are the ones that rely on system APIs like the filesystem, or threads. Those programs require some sort of JS shim to emulate the system API.

[rossberg]

Again, a comparison with functions and calls/returns helps. Functions have parameters and results. Those do not replace more complex data structures in memory, but they provide the building blocks for realising them. Nobody would want to communicate everything through global state.

The same holds for stacks and suspend/resume. The ability to put payload on a suspend/resume provides a building block for constructing more complex abstractions, like channels, which otherwise would have to be bootstrapped with global state in memory or globals.

In both cases, functions and stacks, the ability to pass parameters is part of their structure, and avoids the need for global state where it doesn't belong.