Use Case: Persistent Fibers

[RossTate]

Many designs now have single-shot continuation references—that can be switched to once—as their basis.
Yet many major systems provide persistent fibers—that can be switched to repeatedly—as their basis.
Of course, there seems to be an obvious bridge: a persistent fiber is a reference to a mutable cell containing a (possibly null) continuation reference (or, instead of assuming GC, an index into a table of possibly-null continuation references).
So let us explore what happens when we try to support this bridge; it turns out there is an interesting challenge.

Suppose we want something that implements a (fiberref t*), i.e. something that you can (repeatedly) switch to by giving it t* values.
At any given point, a fiberref is either suspended (has a stack in its mutable cell) or is empty (its mutable cell is null).
Suppose there are various ways to create a fiberref; for the issue at hand, these are not interesting.

Where things become interesting is the key operation: fiber.switch : [ti* (fiberref ti*) (fiberref to*)] -> [to*].
This operation resumes the (fiberref ti*) with the given ti* values (making its mutable cell null—trapping if it was already null) and updates the (fiberref to*) with the current continuation (trapping if its mutable cell was not null); the to* values are the values sent by some fiber.switch to that (fiberref to*) on some other fiber.

Natively, this instruction is straighforward to implement.
After checking the trap conditions, you first put all the live local state onto the stack, along with the code pointer to the following instruction, and put that stack pointer into the mutable cell of the (fiberref to*).
You then put the stack pointer retreived from the (fiberref ti*) into the stack-pointer register, put the ti* values into the appropriate registers or onto that stack (according to some convention), and jump to the code pointer that was on that stack.
Done!
No boxing or even branching necessary (besides checking the trap conditions).
So why is this hard?

The Fundamental Challenge

The issue is that there is some code executed after conceptually suspending the current stack but before conceptually resuming the target stack.
It is a small amount of code—the reference to the suspended stack is placed into the mutable cell of the (fiberref to*)—but it is critical code nonetheless.
Because it is small, it is easy to overlook, but many real-world implementations of stack switching seem to rely on transitioning code like this.
This example of persistent fibers gives us a concrete use case with which to explore this issue.

Problems for Coroutines

The first question to consider is what is a (fiberref t*) a mutable reference to?
The answer that might first come to mind is at least a (ref (cont (param t*) (result ???)), so that you can give it the t* values.
But what should the result payload be?
It is conceptually supposed to be the payload that the stack switching to a (fiberref t*) is expecting to be resumed with.
However, there are many such payloads with persistent fibers!
The issue is that coroutine types essentially bake-in two-party choreographies, where both parties are tightly coupled to the other, whereas persistent fibers are a loosely-coupled many-party system.
As a consequence, coroutines are forced to adopt some lossy workaround, each of which comes with its limitations and overheads.

Lossy Workarounds

Global Side Channel

For each nullable type t and each index i, we could set up a global payload_t_i: t.
Rather than sending the t* payload of the fiber as part of the payload of the continuation, we could instead put the payload into the appropriate globals, simply use (ref null (cont (param) (result))) everywhere, and have the receiver read the payload from the globals.
There would also have to be a global used to indicate the mutable reference of the fiber that sent the payload, whose mutable cell the receiver would update with the coroutine it received.

In addition to the performance overheads caused by passing values through globals rather than registers, this creates difficulties for separate compilation (since a loader would have to canonicalize these globals).
Furthermore, non-nullness information is lost, and it can only support subtyping for types that support downcasts (i.e. every GC reference would have to be stored in an anyref global and then downcast by the receiver).

Boxing

One could alternatively use anyref as the "universal" continuation payoad, i.e. (ref null (cont (param anyref) (result anyref))).
Then one boxes the fiber's payload into an anyref, which the receiver then downcasts.

Since downcasting is restricted to a linear hierarchy, for performance reasons, each field of this box would have to be the top type of the relevant hierarch (e.g. anyref), again requiring further downcasts and null checks by the receiver.
While this avoids separate-compilation issues, it requires taking a dependency on the GC proposal.
It also adds an allocation to every switch, so it seems plausible that this would have higher overhead than using global side channels.

Intermediate Stack

The above lossy workarounds sacrifice type information, relying on dynamic checks to recover the lost information.
Another alternative is to have a (fiberref t*) be a mutable reference to a (ref null (cont (param t*) (result ⊥))) and use an intermediate stack in every switch to perform the transitioning code; this intermediate stack is dropped upon switching, hence the (result ⊥).

That is, one implements fiber.switch : [ti* (fiberref ti*) (fiberref to*)] -> [to*] with a call_switch $transitioning<ti*><to*> to perform $transitioning<ti*><to*> on a separate stack, handing call_switch the ti* payload as well as the mutable reference of the suspending to* fiber and the coroutine of the resuming fiber ti*.
The call_switch then also provides $transitioning<ti*><to*> with the coroutine that just suspended.
$transition<ti*><to*> then stores that coroutine in the mutable cell of the suspending fiber, and then return.switches to the coroutine of the resuming fiber.

This avoids all the shortcomings of the other lossy workarounds, and unlike the other lossy workarounds this generalizes well to more advanced cases, but this also adds significant overhead to every fiber switch: allocating an entirely new stack each time and performing an extra coroutine switch each time.

Problems for Typed Continuations

The first problem for typed continuations is that one needs to first install a trampoline: the suspending fiber suspends up to the trampoline, which then resumes the resuming fiber.
This trampoline can take the role of transitioning code: it can place the continuation reference into the suspending fiber's mutable cell before actually resuming the resuming fiber.
However, even supposing the fiber.switch is performed within such a trampoline, we still run into two more problems.
The first is that we need an event tag for every ti*/to* pair.
This causes problems for separate compilation as these event tags need to be canonicalized.
It also causes problems for subtyping, so again one has to use relevant top types which the receiver then has to downcast.
The other is that there is an unbounded number of these event tags, and yet there is only one trampoline, which can only handle a finite number of predetermined event tags.
As such, typed continuations both needs to deal with installing a trampoline and also needs to adopt one of the lossy workarounds for coroutines.

Solution: Resumptions with resume.switch_call

The resumptions design in #40 offers direct support for transitioning code and as such can support an implementation directly analogous to the implementation we would use natively.
A (fiberref t*) is a mutable cell to a (possibly null) (resumeref (result t*)).
The operation fiber.switch : [ti* (fiberref ti*) (fiberref to*)] -> [to*] is implemented using the resume.call_switch $transitioning<ti*><to*> instruction, handing resume.call_switch the ti* payload as well as the mutable reference of the suspending to* fiber.
The resume.call_switch then also provides $transitioning<ti*><to*> with the coroutine that just suspended.
$transition<ti*><to*> then stores that coroutine in the mutable cell of the suspending fiber, and then simply returns its ti* values.

In other words, rather than allocating a new stack to perform the transitioning code, as with coroutines, it simply performs the transitioning code on the target stack.
And, if an engine were to inline the call to $transitioning<ti*><to*> (which I would recommend but have no means to dictate), it would end up with precisely the native implementation described above.

Conclusion

Regardless of my proposed solution, it seems we should support transitioning code through at least some means.
If one looks through how I support a variety of libraries/features in #40, nearly every example uses some form of transitioning code to perform even just an instruction or two between suspending and resuming the two references.