Replies: 3 comments 16 replies
-
|
My latest thinking on direct switch as the fundamental primitive is that it is still an interesting direction to explore, but for many use cases it seems it would be used to implement something that looks more like delimited continuations anyway. The ergonomics of having primitive delimited continuations that already play nicely with returns and exceptions (rather than trapping or doing something more complicated) may make specifying delimited continuations the better choice for the spec even though they are higher level than direct switch. It's hard to say without implementer feedback, though. |
Beta Was this translation helpful? Give feedback.
-
|
Ergonomically speaking, it is not clear that having the engine do that work for you will be easier than doing it yourself. In particular, existing systems already have the code for doing that work themselves, and they will take more code (and possibly refactoring) to get the engine to do it for them. And that's assuming the engine does what they want, which isn't always the case. For example, a Python greenlet, like delimited continuations, has a |
Beta Was this translation helpful? Give feedback.
-
|
It makes sense that there will be cases where one solution or the other will be more ergonomic. It will be nice to get a proper implementer feedback loop going so we can find out and design for what producers will want to do in practice. |
Beta Was this translation helpful? Give feedback.
-
|
We have had many meetings with many language/runtime teams. Given direct switching, everyone knows how to implement the semantics of their surface language (some additional non-control-related features make this easier at times, but they are generally about using stacks as data, and so are an orthogonal concern for this discussion). But the example with greenlets is representative of what happens when we go beyond direct switching. That is, generally the additional structure/functionality gets in the way for the producers whose semantics don't have that structure or is insufficient for the producers who do have that structure. As an example of the latter (since greenlets were an example of the former), if you have delimited continuations, then some producers also need operations for composing suspended delimited continuations, and some of those producers expect that composition to enforce linearity (one child per parent and the former continuations are invalidated) while others need it to be tree (whose components are only invalidated when they are fully executed). When you speak with a wide variety of producers and read about a wide variety of existing systems, you learn that there is a lot of diversity out there, and it seems the easiest way to appease them all simultaneously is to give them the smallest mechanism they need with as little policy as possible; in this case, that appears to be direct switching. |
Beta Was this translation helpful? Give feedback.
-
|
I have a couple questions from trying to work through an example with nested calls into the host. With this control restriction, how would a wasm suspendable stack switch back to the original host stack that first called into wasm? I'm assuming there would need to be a way to get a reference to the system stack, i.e. a How would this work with JS/host function frames that may need to only run on the system stack? In these cases, we'll need to dynamically switch back to the system stack upon call and then dynamically switch back to the caller stack upon return. In addition, the stack that called the import is no longer valid to switch to because it's expecting to be returned to by the import. This would mean the system stack could have multiple points that are waiting to be switched back to. Switching to the system stack would mean switching to the most recent point waiting to be switched to? Imagine the following timeline:
At (6) wasm can no longer switch back to What would happen if an exception/trap happens at (6)? We have options for the wasm stacks, but the system stacks must be unwound all the way to the root, in stack order, or else we break critical host invariants. In this example, that would mean that It seems like we'd need something close to a 'parent field' on a stack then to do that correctly, which makes this seem close to delimited continuations in practice? I suppose the real issue here is that the dynamic switch back to the system violates the 'no leaving the stack except from switch' rule. You could workaround this by trapping when calling an import that is JS/host. That would then require all calls to JS/host functions to have a switch back to the system stack to perform the call and then switch back to the wasm stack with the results. |
Beta Was this translation helpful? Give feedback.
-
|
The big issue with stack.current (or anything like it) is that it allows called functions to acquire capabilities they were not explicitly given. In fact, if you follow this particular rabbit hole, you are left with needing to create a specific token that represents the capability to switch somewhere. You can call this a continuation, a jumpref or whatever. It is different in kind to a fiber/stack reference because it would have to be inherently single use. The next question after that is how do you describe the type of that token? |
Beta Was this translation helpful? Give feedback.
-
|
This is really great, @eqrion! I have some thoughts/answers, but I just left for holiday and this requires more than I can reasonably type on my phone, so I'll have to get back to you on Monday. |
Beta Was this translation helpful? Give feedback.
-
There are multiple ways to achieve this, but for the sake of this discussion it seems there are two important ant "classes" of such means:
The important distinction is the first class gives you a persistent reference whereas the second class gives you a single-shot reference (that expires once that specific suspension point is switched back to). The second seems to be all that is strictly necessary for supporting direct switching, and the first seems to cause problems. There are some middle-ground options (e.g. providing means to avoid dynamically allocating references to suspension points each time you switch), but for the sake of this discussion suppose the second is possible and first is prevented.
tl;dr: Yes. More details and options below.
Your timeline essentially establishes a "sandwich" scenario with embedder frames in the sandwich. It's worth noting that this scenario is possible in all proposals. It's also worth noting that it's easy to prevent by establishing some "opt-in" way to distinguish functions that can versus cannot be run on wasm stacks (i.e. off the embedder stack), in which case the wasm module would be forced to switch back to the embedder stack before calling an import. But, absent that distinction, all proposals need some way to dynamically recognize this situation and handle it accordingly.
This outlines a resource problem: the embedder stack is a limited resource and we need to ensure that embedder frames on it are not corrupted/lost by switching to it. I can think of two ways to address this issue:
Another factor to consider is that not all embedder's will require embedder code to be run on the embedder stack. So we likely want to leave room for JS/embedder code to be runnable on a wasm stack (even if it is not allowed to be "suspended"—see below). Option 1 doesn't really leave much room for that. Option 2 does, while also leaving room for an embedder to run embedder code on the embedder stack if it needs (since it guarantees the suspension point on that stack will be frozen until those frames have been cleaned up).
There are a few possibilities here. One is that if we did only single-shot references then there's no way to switch to the stack except by returning from the imported function as there's no way to get a reference to it. Another is that if we did persistent references (to wasm stacks) then we could make the stack "frozen" until the import returns, so that the program traps if it tries to switch to it. In general, all non-opt-in designs will require the application to be conscious of where there might be embedder frames on its stacks and recognize that various operations will trap in these situations. (Personally, since we know that wasm functions and embedder functions will have to be handled very differently by both tooling and engines with respect to stacks, I think everyone will be spared a lot of grief by making "suspendability" explicit in function signatures. Even just a single bit would prevent all the issues you raised in your second question and all the run-time operations it will take to address these issues in all of the non-opt-in designs.)
Nope. The application will be responsible for ensuring embedder frames are returned to in the right order. Or else it traps.
Exceptions and traps are different. For exceptions, with direct switching the wasm program is responsible for making exceptions be forwarded to the appropriate stack (e.g. using For traps, they can't be handled by wasm code, so control gets transferred to wherever the embedder most recently (chronologically |
Beta Was this translation helpful? Give feedback.
-
This was what I was getting at before with
This first option is what I think would really make direct switching a simpler proposal compared to t-c/fibers, as it would eliminate the sandwich scenario, which is where we have to start tracking I don't know if this option is viable though as it would force two stack switches to call a JS/host import (1 out to do the call, 1 back to pass the results on). On hosts that can run JS on wasm stacks, this is wasted overhead. On hosts that would need to switch to the system stack to run JS/host calls, this will involve stack switches but I'm guessing they can optimize the param/result passing better. |
Beta Was this translation helpful? Give feedback.
-
|
This idea of using undelimited control as the basis for stack switching (really unrestricted jumps) was first conceived in the '60s by Peter Landin. The Scheme/Racket community put this idea into practice during following decades. Through experimentation they discovered a range of issues with this approach, and over time they have moved to using delimited control as the basis for stack switching. In Racket, even History repeats itself, so every so often this idea of using some form of undelimited control as the basis for stack switching is rediscovered along with the issues it entails. Around ten years ago Oleg Kiselyov wrote up an argument against using undelimited control as the basis for stack switching. To me, the key reason why we don't want to use undelimited control as the basis is that we compromise modularity. As you have pointed out yourself, it does not compose with exceptions --- you need to add some special support. However, this approach does not scale to multiple native effects. Personally, I am concerned about the interaction with other native effects in Wasm and the potentially many new native effects, e.g. threads. |
Beta Was this translation helpful? Give feedback.
-
|
We are not designing a surface-level language here. We are designing a low-level language that many surface languages are expected to be able to compile to. The compilation and runtimes of those languages are already generally responsible for maintaining the invariants and operations expected by their respective surface language. So, for a low-level language, please describe the problems you envision direct switching causing. |
Beta Was this translation helpful? Give feedback.
-
I think the concerns about compositionality have been fairly well covered in broad terms, so requesting the problem be restated so generally is unlikely to get new answers. On the one hand, Wasm seeks to be a low level compilation target that provides a minimal safe abstraction on top of the hardware. Strictly from this point of view, having a "bag of stacks" and providing means to directly switch between them is clearly an acceptable and desirable solution because that's what hardware offers. Any language that performs stack switching on native platforms could map that stack switching 1:1 onto Wasm "bag of stacks" stack switching. On the other hand, Wasm seeks to provide composable abstractions that allow mutually untrusted modules to work together safely1. Strictly from this point of view, having delimited continuations is clearly an acceptable and desirable solution that is known to compose well and support industrial systems. There's no single "right" design here and acting as though there is does not help move the conversation forward. Instead, we need to deliberately explore the design space with open minds and figure out precisely what the trade offs are so we can choose the solution that is best for the whole ecosystem. Footnotes
|
Beta Was this translation helpful? Give feedback.
-
|
I think that the 'mutually untrusted modules' is excellently catered for by the component model proposal. We should not therefore ask every other effort to also solve that problem. |
Beta Was this translation helpful? Give feedback.
-
|
Ah, perhaps I should have written the weaker statement "mutually uncoordinated," although there is still some level of coordination necessary to get matching ABIs. The smaller the coordination surface, the better, I suppose. |
Beta Was this translation helpful? Give feedback.
-
The fact that people have concerns about composability is well known, but what properties people hope to achieve and why they would be violated by direct switching have not been. For the paper I know of that does actually articulate those properties, the proof that the properties hold for its system depends explicitly on control being lexical (i.e. targets named explicitly) and seemingly not at all on continuations being "delimited". |
Beta Was this translation helpful? Give feedback.
-
As mentioned at the in-person meeting, existing native implementations of stack-switching constructs all reduce down to a simple
switchpseudo-instruction.Indeed, all the current proposals are basically layered on top of a
switchinstruction.So, putting details of the instruction aside (e.g. typed or untyped), I would like to discuss why or why not to support
switch.In particular, I want to discuss this instruction in the context of a design in which the only way for control to leave a stack is via a
switch(which is how it works natively anyways).Why is that restriction important?
It addresses the composability issue with undelimited continuations.
With undelimited continuations,
callcc"replaces the world" with the given continuation that computes and returns a value.But where does it return that value to?
The point is that undelimited continuations essentially assume some global return target, and that globalness is what causes their composability issue.
With delimited continuations, on the other hand, the answer of "where to return to" is (mutably) associated with each continuation.
With the control restriction, this distinction becomes immediately apparent in the implementation of the root function on an application-created stack.
For applications supporting a language with (surface-level) undelimited continuations, the root function of its stacks will use a
globalto store the "where to return to" target andswitchto it at the appropriate time.For applications supporting a language with (surface-level) delimited continuations, the root function of its stacks will use a mutable reference or table entry to store the "where to return to" target for that stack and
switchto it at the appropriate time.For applications supporting a language with both features, the root function will vary by stack depending on the semantics of the continuation at hand.
As a composability test case, we can consider a wasm instance with no imports and whose only exports are first-order (e.g. no
funcrefparameters) functions.Prior to stack-switching, the only way for such an instance to affect the outside world (besides trapping or not terminating) is to return values to its exports.
With the control restriction, the same is true for
switch; although internally the application can switch between its own stacks, eventually one of these stacks has toswitchback to the stack with the original function call into the instance in order to return a value.That is,
switchcannot "replace the world"!I suspect the advantages of supporting
switchare obvious.(If that suspicion is wrong, please start a thread here asking me to elaborate.)
So my question to the group for this discussion is: why should we not support
switch?Details
For handling foreign exceptions, many root functions will need a
switch_rethrowinstruction, only usable withincatch_all(andcatch) blocks, in order to rethrow foreign exceptions from the appropriate "where to return to" target.Traps are complicated.
We ran out of time at the in-person meeting for me to give my presentation on traps, so for the sake of this discussion please assume applications can trap and there is a good semantics for what to do in such a situation.
Beta Was this translation helpful? Give feedback.
All reactions