Forwards-incompatible with resumable exceptions

[RossTate]

Resumable exceptions are useful for implementing a variety of language features. For example, C++'s throw; and Python's raise; (both without an exception argument) are easily implemented with resumable exceptions, obviating the need to maintain an stack of currently-being-handled exceptions. Regardless, based on the discussion in #102, it seemed that people would appreciate knowing that resumable exceptions are incompatible with the current proposal.

To see why, first remember that resumable exceptions are still exceptions—the handler has no obligation to resume the exception and might just usurp control. With that in mind, consider the following psuedo-code:

resumable exception generate : [] -> [i32]

f() {
    try {
        Resource rec1(...);
        g(&rec1);
        ...
    } catch {
        // handler-1
        // checks to see if exception should be handled
        // cleans up (e.g. destructs rec1) if not
        ...
    }
}

g(Resource *rec1) {
    try {
        Resource rec2(...);
        h();
        ...
    } catch {
        // handler-2
        // checks to see if exception should be handled
        // cleans up (e.g. destructs rec2) if not
        ...
    }
}

h(Resource *rec2) {
    throw generate;
    ... // hand generated i32 to rec2
}

At the point where generate is thrown, we have to walk up the stack to find out if it is resumed. So first we run handler-2. Let's say that doesn't handle the exception, in which case (according to the pattern prescribed/forced by the current design) handler-2 cleans up the resources acquired by g, in particular invoking ~Resource() on &rec2. After cleaning up, handler-2 rethrows the generate exception, which is then caught by handler-1. Let's say handler-1 resumes the generate exception with the value 928, restoring control to h just after the throw. h then hands 928 off to rec2, which then presumably fails in some way because rec2 was destructed.

To summarize, a principle of the current design is that filtering code, handling code, and clean-up code can only be bundled together into one unifying catch clause, but resumable exceptions realistically need clean-up code at-the-least to be separated from filtering and handling code so that, if the exception is resumed, the stack (or really program state) is still in a realistically usable state.

[rossberg]

Generalising the exception proposal with resumption was the starting point for our work on effect handlers (which are more or less exceptions with resumption). That generalisation sounds attractive at first, and I have made sure that the proposal remains extensible in that direction. However, once you get into the details it turns out to be less attractive than one thinks at first, since for reasons of both performance and semantics (see below), you'll need a whole set of annotations distinguishing resumable from non-resumable that ultimately bifurcates the instruction set anyway. Plus other reasons I gave in my talk.

The problem of conditional cancellation is mostly orthogonal to filtering and more complicated. The naive addition of resumption to a language like C++ will definitely wreak havoc; the same is true for any language with finally or equivalent mechanisms. The only sane design is one where resumable exceptions are distinguished from unresumable ones, and so are their handlers. Throwing a resumable exception must not invoke finalisers. Instead, a resumable handler that decides to abandon its resumption has to unwind the stack explicitly, e.g., by injecting an actual exception at the resumption point.

Such a design is compatible with the current exception proposal, our effect handlers design works that way.

[RossTate]

you'll need a whole set of annotations distinguishing resumable from non-resumable that ultimately bifurcates the instruction set anyway

No, from what I can find in the control literature (though I still have a lot left to read), you just need to separate stack walking (e.g. finding handlers) from stack unwinding, like you do in this sentence:

Instead, a resumable handler that decides to abandon its resumption has to unwind the stack explicitly

So why not use such a pattern here?

The only sane design is one where resumable exceptions are distinguished from unresumable ones, and so are their handlers.

Unresumable exceptions are a special case of resumable exceptions (e.g. inhabitable resume type), so a coherent design would treat the two alike.

Your compatibility plan is to make an entirely new kind of event that can encode both resumable and unresumable exceptions by separating handler code from clean-up code (like I'm advocating for here). This new kind of event will completely ignore the current try/catch construct. To get at least basic compatibility with the expectations of legacy code using the old try/catch, you'll make a fresh event type, e.g. abort, that no such code understands in order to (hopefully) force just its unwinding code to be executed at the appropriate time.

That's not really forwards-compatibility. That's a plan to abandon this for more general constructs with a backwards-compatibility patch for legacy code.

[rossberg]

Unresumable exceptions are a special case of resumable exceptions (e.g. inhabitable resume type), so a coherent design would treat the two alike.

Not once you start thinking about the different performance implications. Resumable handlers need to run on a new stack. Unless you're thinking of some limited form of resumption that isn't sufficient to encode any interesting control abstraction.

That's not really forwards-compatibility. [...] To get at least basic compatibility with the expectations of legacy code using the old try/catch

AFAICT, this is the only way to be compatible with code (legacy or otherwise) that isn't aware of resumption. An exception handler or finaliser in such code must be bypassed by a resumable exception/event, as any other semantics would break the code's assumptions.

[RossTate]

Resumable handlers need to run on a new stack. Unless you're thinking of some limited form of resumption that isn't sufficient to encode any interesting control abstraction.

Here is how you run generators on the same stack, a technique that is easily adapted to resumable exceptions (assuming you and I mean the same thing by that term).

A [sic] finaliser [sic] must be bypassed by a resumable exception/event

Right. Once you add resumable exceptions, you'll need to add finally or fault clauses so that you know to bypass those until you possibly later unwind the stack.

As for handler code for different exception events, you would bypass them anyways, regardless of whether they're for resumable exceptions or for unresumable exceptions.

So given that you will have to eventually add finally and/or fault clauses later on, you might as well add them now. But then that means that catch will only be useful for actually catching exceptions, so you might as well change it to catch $event (or more accurately catch-and-unwind $event). Once you've done this, you'll have effectively separated unwinding code from handling code, making the design properly forwards-compatible with resumable exceptions. More precisely, you won't have a catch-all construct lying around that doesn't actually catch all exceptions and that would be made obsolete by fault/finally and catch/catch-and-unwind (which would also be more efficient because they aren't constantly reifying an unneeded exnref).

[rossberg]

Here is how you run generators on the same stack, a technique that is easily adapted to resumable exceptions (assuming you and I mean the same thing by that term).

That scheme only works if (1) continuations cannot outlive their handler, (2) the continuation can only be invoked in the syntactic scope of the handler and (3) the coroutine can only yield in the syntactic scope of its definition. IOW, it's limited to shallow generators where continuations aren't first-class -- way too constrained for resumable exceptions or effect handler and the control abstractions you'd want to encode with them, such as lightweight threads.

Right. Once you add resumable exceptions, you'll need to add finally or fault clauses so that you know to bypass those until you possibly later unwind the stack.

You don't need non-bypassed handlers before you have resumption. If you add those later you end up with a design close to what I described.

[RossTate]

That scheme only works if ...

You listed a bunch of requirements that always hold for the standard foreach/yield syntactic constructs of many languages with generators. Same holds true for the standard syntactic constructs for resumable exceptions. I updated #105 with an illustration of how this works.

Note that implementing generators with even one-shot continuations is extremely heavyweight. For every iteration you have to

• acquire the lock on the continuation with a CAS or something (once we get to multithreading)
• switch the stack to the generator
• (proceed until you reach a yield—true for both implementation strategies)
• walk up the stack to find the handler (the implementation in Primer on low-level stack and control-flow primitives #105 only has to do this once for the entire loop, rather than per element, which is important because this is plausibly the slowest step)
• switch the stack to the foreach body
• release the lock on the continuation (once we get to multithreading)
• (execute the foreach body—true for both implementation strategies)

That's a lot of steps for loop iteration, especially if this is a hot loop. Some of this can be optimized with JITing information (e.g. knowing that this is the only reference to the continuation so that locking is unnecessary), but we're supposed to not rely on JITing for reasonable performance.

You don't need non-bypassed handlers before you have resumption.

I'm confused. In the statement you're responding to, I said you'd need to add bypassed handlers. Did you misread or mistype something?

[RossTate]

By the way, I just finished working out how to combine #105 with the continuations sketch you presented. The combination is a nice halfway point between the two and points to a nice way to resolve a corner-case problem I found in each of our sketches. I'm happy to write the sketch up for you somewhere, I'm just not sure where. #105 came to mind, but I was worried that putting it there would make it unclear that all of that works without continuations.

[rossberg]

You listed a bunch of requirements that always hold for the standard foreach/yield syntactic constructs of many languages with generators. Same holds true for the standard syntactic constructs for resumable exceptions.

Yes, for (shallow) generators, but we wouldn't want to make a special feature just for generators. To encode other common control abstractions you need either first-class resumption continuations or, equivalently, the ability to lambda-capture yield and resume instructions (as some languages allow). Both implies delimited continuations, and thereby creation of new stacks.

[RossTate]

Right. So for the features that do not need continuations to express them, we should have primitives that can express them (see #105, which is not at all specialized to generators). And for features that do need to continuations, we have an extension to support stack allocation, pausing, stepping, and running, which are the low-level primitives that combine with the stack primitives in #105 to support continuations and/or yield. (For example, cont.yield in your talk is implemented as a combination of a stack walk and a stack pause.)

[RossTate]

#105 now has the primitives for supporting algebraic effects. Hopefully tomorrow it will have some more primitives for working with stacks/continuations that are inexpressible with algebraic effects.