Lambda the Ultimate

In the Lisp world, conditions are raised within the context of the procedure that raises them. Only if the condition handler makes a non-local exit does the condition have termination semantics in the usual sense. So how, in the general case, do you determine if condition handlers are making such an exit and therefore count as exception handlers?

While I feel it's a workable idea, the main issue is with the code expectations. If all code were coroutine-aware, then there would be no problem. Otherwise, you may be breaking some invariant in the code.

I faced the same issue last week, when thinking about how to best add concurrency to klisp. I ultimately went with OS threads but I figured it's possible to do what you are mentioning in pure Kernel using guarded continuations.

The trick is to replace the root-continuation in the standard environment with a continuation further down the chain, let's call it R, that still has all user continuations (and error continuations) in its extent. The couroutine mechanism uses the parent of this continuation, let's call it C. To do a couroutine yield, the yield procedure would invoke the continuation C, and no interception is possible using R or any of its children as exit-guards. Once in C, you can invoke the continuation of the yielded-to couroutine, and again, no entry guard based in R or its children can be selected. This works exaclty because in Kernel exit guards are selected based on destination and entry guards based on source, and we arranged this so that neither C nor any of its parents is directly accessible to user code.

While the above works, a naive implementation of Kernel would still try any exit and entry guard only to fail, and this may be a costly operation, depending on the size of the continuation. So probably yield should be implemented "natively" as a simple coroutine state save & switch in the interpeter.

It's not hard to imagine an application like this:

1) We'll have coroutines and we'd like yield to be insensitive to unwind-protect (as you describe).

2) Within a given coroutine we'd like dynamic-wind and a corresponding call/cc-1 which work as in R5RS with the caveat that it is an error to call a continuation created by call/cc-1 unless from the same coroutine in which it was created. For example, I might have a coroutine that uses call/cc-1 to organize a game-tree search -- but I prefer to deny any meaning to invoking one of those search continuations from a different coroutine. As in what you describe, call/cc-1 should be insensitive to unwind-protect.

But now here is where this example diverges from your proposal:

For this (hypothetical but intended to be realistic) application:

• yield should be completely insensitive to the dynamic context within a co-routine
• call/cc-1 should be sensitive to dynamic-wind but insensitive to unwind-protect
• exceptions should be sensitive to both kinds of dynamic context, but of course shouldn't be able to escape from a coroutine.

So that sketches out what should be a pretty familiar flow control pattern but one that is by no means the only one of interest. In this version you need to be able to capture continuations while respecting unwind-protect, while not respecting unwind-protect, and even (for yield) while not respecting dynamic-wind.

With a little imagination we can probably further multiply the number of variations on continuation capture that you'd want present in a given application. We can come up with lots of reasonable examples.

So: "Should a continuation capture always [be] considered to be stack unwinding?"

How about:

"No. A primitive continuation capture should never be considered to be stack unwinding. How and when unwinding happens in practice is application-specific."

I haven't much time now, but I have a couple of brief thoughts on this, which I'll probably develop in more detail later.

First: I cannot imagine any way for both exceptions and continuations to coexist in the same language without causing semantic problems such as ambiguity or implementation problems such as uncollectable floating garbage, or both. Even if you implement exceptions in terms of continuations, that means that using continuations for anything *else* will cause problems. In fact as Oleg pointed out here last week (and in the Scheme mailing list several months ago) implementations of most nonlocal control flow facilities in terms of continuations will interfere with other uses of continuations. They simply aren't a good building block if you want to build more than one thing per program.

Second: You could implement something like dynamic-wind with "guard levels" to strike a better balance between resource control and performance. But this isn't a well-developed idea yet. Basically it involves having multiple guard routines, and allowing the implementation to perform as many "onexits" as it needs, from none to the number defined, in order to free resources, subject to the requirement that for each "onexit" peformed, it performs the corresponding "onentry" when resuming the continuation. As I said, this isn't a well-developed idea yet. I'd have to think very hard about the semantics before recommending it as such, it's just an idea I've had and considered briefly.

Ray

A yield is like blocking if you resume later, and should not be considered unwind. For example, if a thread (native or green—doesn't matter) blocks, or is merely interrupted, it is not unwinding its stack and should not have unwind or exception handlers fire.

So switching from one continuation C-from to another C-to in another thread is not unwind when the original C-from continuation has independent lifetime and will resume later (and be dismayed if its held resources go away). When a language has explicit representation of independent thread lifetime, this isn't confusing. But if code simulates thread-like entities outside a language's model of threads, the language won't be able to figure out this app policy, and a one-size-fits-all treatment won't work in every app if the policy actually varies.

In contrast, if a single thread invokes C-to from C-from, and C-from will never be resumed, this looks like an unwind of C-from's stack if it holds resources that will otherwise leak. But how can the language know whether C-from can ever be resumed? It seems like only the app knows that, so perhaps a way to invoke a continuation with intent-to-unwind would be useful, so policy can be expressed explicitly.

Using unwind-protect semantics only seems necessary when managing shared resources that indirectly cause interference with other code if leaked or held for use by conflicting interests. This has an imperative shared-mutable-state quality to it, making it easy to create messes as bad as those achievable in C, even if your language naively intended to make them impossible. I'm not sure it's feasible to make languages resource safe; it's almost always possible to write code that would use more than all resources. Even if you enforce limits on stack depth or heap size (etc) then signal termination on violations, you can still probably exhaust resources by spawning enough cooperating entities where no one of them exceeds a limit. To make that impossible would require greatly restricting expressiveness of code that might otherwise work fine when resources are used more responsibly. A model wide and open enough to be a pleasure in coding is easy to abuse.

Instead of making bad results impossible, it might be better to enable expressing policy intention more explicitly, so this can be analyzed statically or dynamically. If an app doesn't have a clear enough idea of its own behavior to predict when it's unwinding a stack or not, maybe it's a losing battle to support adding more spaghetti resource usage.

(Aside to Matt M: that Processes idea sounds interesting, so I hope you keep doing it.)

Postscript: I thought I was going to talk about strong and weak refs at first because this topic reminds me of things I see done in C to control distributed management of shared resources. Rather than omit that entirely, I'll just tack on this short suggestion. If a continuation with ambiguous lifetime might keep resources alive too long, or with scope too hard to control, maybe it should indirect via reference that can be revoked by someone managing the resource as the owner. Then it can fail if invoked after a resource becomes stale, or perhaps re-up a new fresh ref.