I'm not sure I follow your example. Is it possible to write it using JS generator functions or some pseudo syntax?

I wrote up a more detailed example for you in another thread.

Okay, thanks for this example.

If I understand it correctly, the relevant summary of what goes wrong for this proposal is:

1. AppendAfterFixed is aiming to be an abstract component that is arbitrarily composable
2. AppendAfterFixed.foreach will setup a handler for it's own 'control tag'
3. AppendAfterFixed.foreach will invoke an interface (which can be anything, including another instance of itself) and provide it a closure which attempts to suspend back to the handler from (2) using its 'control tag'
4. Choosing to compose as a: AppendAfterFixed(b: AppendAfterFixed) causes two handlers from step (2) to be set up, before the outer closure from step (3) is run. The outer closure runs and is erroneously captured by the inner one due to the unexpected stack layout.

My follow up question then is, does this happen with any of the critical use cases of stack-switching?

• Green threads
  • All examples of green threads I've seen rely on a top-level scheduler handler
  • Step (3) therefore sounds like attempting to call into a recursive scheduler handler, which sounds like a bug violating global assumptions.
  • It's also unclear why a scheduler would be invoked with a closure that would perform a yield to a different scheduler such as in step (3).
• Yield style generators
  • Invoking a generator function will setup a handler such as in step (2). I believe the control tag could be 1:1 with the generator function definition.
  • Yield can only happen in the called generator function, not in a closure passed to another function, so there's no chance for the yield to be captured by anything else.
  • If a generator invokes another generator, it must setup a handler for anything from the generator it's calling.
• Async/await
  • My assumption is this is the same as yield style generators.
• First class continuations
  • I know less about how this will be used.
  • Best guess is if the source language feature is nearly the same as the runtime feature, then any accidental capture is the fault of the source language feature.

Am I missing something?

Choosing to compose as a: AppendAfterFixed(b: AppendAfterFixed) causes two handlers from step (2) to be set up, before the outer closure from step (3) is run. The outer closure runs and is erroneously captured by the inner one due to the unexpected stack layout.

The fixed version does not have accidental capture because it uses lexically scoped exceptions.

All examples of green threads I've seen rely on a top-level scheduler handler

In practice, there is no top level schedule handler. That is a device used to encode green threads in dynamic scope, and one that comes at a cost (e.g. an extra context switch on every thread switch). According to the language implementers we have spoken to the following is what actually happens: either the currently executing thread either has an obvious target (e.g. because it is sending a synchronous message to another thread) and directly switches to that target, or it is voluntarily yielding and runs the scheduler on the current green thread and then directly switches to the target returned by the scheduler.

Yield style generators

The paper gives an example of dynamic scoping causing accidental capture for yield-style generators. See Section 2.2.

Async/await and first-class continuations

In general, in any system with higher-order interactions between two components (such as WebAssembly, both within modules and across modules), dynamic scope causes composability issues due to accidental capture.

Am I missing something?

Dynamically scoped semantics can be encoded via lexically scoped semantics. This encoding is efficient in a manner that is already expressible in WebAssembly, and that encoding is how languages implement dynamically scoped features natively, since native environments only support lexically scoped semantics.

On the other hand, while lexically scoped semantics can be encoded via dynamically scoped semantics, it is inefficient as it generally requires more context switches and dynamically-scoped searches.

So why should we use dynamically scoped semantics when it is less efficient and has worse composability properties than lexically scoped semantics and when all language runtimes already know how to implement their features efficiently using lexically scoped semantics because that is what the hardware supports?

We have heard from multiple language teams that the encodings imposed by the typed continuations proposal are suboptimal. As an example, multiple language teams have reported that they found that moving from "scheduler at the top" to "scheduler in the green thread and then direct switch" resulted in appreciable performance improvements because it removes a context switch from every green-thread switch. More generally, the experience relayed is that removing context switches results in better performance. I believe it is undisputed that a lexically-scoped design involves, generally speaking, fewer context switches than the typed continuations proposal for a variety of features (and never involves more context switches). So, putting those two pieces together, it seems reasonable to deduce that the typed continuations proposal can at best match the performance of a lexically-scoped design and in various situations will be appreciably less efficient. If you have a scenario where you have reason to suspect the typed continuations proposal to work better, it would be useful to discuss it.

None of those solutions are present in the (unextended) typed continuations proposal. They are encodable in the typed continuations proposal, but the encodings necessarily involve additional context switches than what the source material requires. For example, one way to fix AppendAfter while using only dynamically scoped exceptions is the following lexical-to-dynamic encoding for exceptions:

class AppendAfterEncoded<Element> implements Sequence<Element> {
 private final Sequence<Element> first, second;
 private final int amount;
 public AppendAfterEncoded(Sequence<Element> first, int amount, Sequence<Element> second) {
 this.first = first; this.amount = amount; this.second = second;
 }
 public void foreach(final Consumer<Element> consumer) {
 final AppendAfterException identifier = new AppendAfterException();
 try {
 first.foreach(new Consumer<Element>() {
 private int count = amount;
 public void accept(Element element) {
 if (count-- == 0)
 throw identifier; // object closes over final "identifier" variable in context
 consumer.accept(element);
 }
 });
 } catch (AppendAfterException e) {
 if (e != identifier)
 throw e;
 }
 second.foreach(consumer);
 }
 private static final class AppendAfterException extends RuntimeException {}
}

But this encoding is worst-case quadratic with respect to the number of non-local control transfers AppendAfterFixed uses, as are many of the more straightforward encodings of the constructs you listed (which all generally would down to the same "allocate something beforehand and then run a user test at each capture site to figure out if the capture was accidental").

For many of the constructs, if you want to avoid this quadratic worst-case, you're essentially forced to implement your own dynamic scope (which is easy to do) and emulate lexically scoped direct switching. So why not just provide lexically scoped direct switching in the first place? It can support all of the constructs you listed without any additional context switches.

However,
one of the extensions described in the proposal is to also support
suspending to a specific named handler (also with a matching event
tag). Both modes of selecting a handler (unnamed and named) are
useful.

There are more modes than just these two. Bidirectional algebraic effects (such as rejections in promises) are another mode. But all of these modes can be implemented using only named handlers. This implementation is fairly easy (the application just implements dynamic scope on its own, e.g. by maintaining a linked-list data structure of stacks) and efficient (e.g. no more context switches than in the source program). On the other hand, named handlers and bidirectional unnamed handlers cannot be encoded using just unidirectional unnamed handlers without increasing the number of context switches.

So why should a wasm engine provide both named and unidirectional unnamed handlers when the application can straightforwardly implement the latter in terms of the former (and implement a bunch of optimizations on top of it! like tail-resumption optimization) or straightforwardly implement its own construct (such as the many you listed) in terms of the latter (but not necessarily the former)?

On the other hand, named handlers and bidirectional unnamed handlers cannot be encoded using just unidirectional unnamed handlers without increasing the number of context switches.

Uh-oh. You should be more careful about making such statements about expressiveness. Using the number of context switches as a measure is dubious, because it is possible to implement suspend and resume such that each requires exactly one context switch irrespective of the length of the active stack chain (i.e. nesting depth of handlers). I wrote such an implementation two years ago in C. As such, the "number of context switches" is a non-informative measure.

So why should a wasm engine provide both named and unidirectional unnamed handlers when the application can straightforwardly implement the latter in terms of the former (and implement a bunch
of optimizations on top of it! like tail-resumption optimization) or straightforwardly implement its own construct (such as the many you listed) in terms of the latter (but not necessarily the former)?

It might be "easy" if your backend is already set up for prompt-passing style. Otherwise, you essentially need to perform some variation of continuation-passing style on your intermediate representation in order to recover modularity, which consequently forces you into accepting new calling convention.

Using the number of context switches as a measure is dubious, because it is possible to implement suspend and resume such that each requires exactly one context switch irrespective of the length of the active stack chain (i.e. nesting depth of handlers).

This seems to miss the point. That implementation strategy (which is what I have expected the typed-continuations proposal would use), enables you to suspend to the most immediate matching unnamed handler with a single context switch. But what I said was "named handlers ... cannot be encoded using just ... unnamed handlers without increasing the number of context switches". The issue is that, if the system only supports unnamed handlers (as in the typed-continuations proposal), then named handlers have to be approximated by unnamed handlers. As a consequence, when you want to suspend to a named handler, you can only suspend to the most immediate unnamed handler approximating that named handler. Then you have to run application code to determine if the named handler for that suspension point is the one you were looking for, or if it accidentally belongs to another named handler with the same approximation, in which case you have to suspend again. Thus, except when you're lucky, it generally takes multiple context switches with unnamed handlers to implement what would have been a single context switch with a named handler.

I also said the same issue for bidirectional algebraic effects. The issue here is that the handler of the effect can be inside another continuation. So first you have to switch to that continuation, and then you have to perform the dynamically scoped suspension. So two context switches when there could have been one.

Another example is direct switching used in implementations of green threads. You can implement this with dynamic scope via a suspend and a resume, but that requires two context switches to perform one direct switch. The typed-continuations proposal does describe a possible extension for this feature, but note that it uses named (i.e. lexically scoped) handlers. This is because it would be unsound to do so with just dynamic scoping (the unnamed handler is expecting some return value for the continuation it resumed, and there's no way to know at the site of the switch_to instruction what that type is in order to ensure it matches the return type of the continuation you're switching to).

It might be "easy" if your backend is already set up for prompt-passing style.

I know of four ways for an application to implement specifically dynamic scope. One of them is already fairly common in WebAssembly. None of them need you to perform CPS on your IR in order to recover modularity. (Some of them do require you to import something from a common "runtime" module, but so does the typed continuations proposal: the common effect tag used across your language's compiled modules.) If this is a concern, then it might be a worthwhile topic for a new Discussion.