Home » forums » LtU Forum

Should continuation capture always be considered to be stack unwinding?

Take the case of using continuations to implement coroutines: when a coroutine yields, do we really want to run unwind handlers (i.e. dynamic-wind)? After all, we are still "in" the coroutine, only its execution has been suspended, and is expected to continue at the point of suspension. It would seem strange to run the unwind handlers in this case, no?

Would it make sense to have two forms:

  • (dynamic-wind pre-thunk thunk post-thunk) as in Scheme: pre and post thunks are always performed, whether control enters/exits the thunk normally, or through an exception, or through continuation capture.
  • (unwind-protect thunk post-thunk) as in Common Lisp: post thunk is not performed if control exits thunk through continuation capture, only if it exits normally or through an exception.
By Manuel J. Simoni at 2012-08-22 12:20 | LtU Forum | previous forum topic | next forum topic | other blogs | 6531 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

What is an exception?

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?

By johnwcowan at Wed, 2012-08-22 14:47 | login or register to post comments

Exceptions would use a means

Exceptions (or rather exception handlers) would use a means of nonlocal transfer of control other than continuations (e.g. Common Lisp's CATCH/THROW). Continuations would strictly be used for higher-order control ops, whereas exceptions would be first-order.

By Manuel J. Simoni at Wed, 2012-08-22 18:43 | login or register to post comments

While I feel it's a workable

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.

By Andres Navarro at Wed, 2012-08-22 15:12 | login or register to post comments

no one right answer

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."

By Thomas Lord at Wed, 2012-08-22 19:23 | login or register to post comments

A brief thought.

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

By Ray Dillinger at Thu, 2012-08-23 09:03 | login or register to post comments

Processes

I'm using an abstraction that I call Processes, that I've mentioned around here several times, that I think nicely integrates exceptions and continuations (and also state and effects). The intuition is that a Process is a computation in a box that accepts and issues signals. A function can be modeled as a Process that issues a signal 'return'. A function with exceptions can be modeled as a Process that also has other signals. A co-routine can be modeled as a Process with a signal 'yield'. The ambiguity that I think you're referring to amounts to the open decision as to whether 'yield' is an exception, but if you just stick to thinking about protocols (which type back and forths of signals between Processes) and don't bother classifying some subset of them as "the exceptions", there's not really a problem.

IMO, continuations (delimited or not) are a very unintuitive interface to control flow and Processes are much better. Functions that can non-locally exit can do so because they aren't really functions at all. They're monadic. Processes are monadic but have additional structure that allows them to be easily composed. They are probably closely related to Algebraic Effect Handlers.

By Matt M at Thu, 2012-08-23 17:05 | login or register to post comments

it's context saving, not exceptionality, that causes problems.

The bulk of problems with the interaction between continuations and exceptions (indeed, problems with the interaction of differing kinds of continuations) are caused by the different ways they treat return context. Keeping the stack so that you can return to a continuation later is a simple idea, but when you have exceptions unwinding the same stack that's saved in continuations, especially when different continuations have captured the stack at different points in time sharing some but not all of the return frames and wanting to treat the same frames differently when reentered, it turns into a deeply complicated simple idea.

It doesn't matter whether you consider any transfer of control "exceptional" or not; it matters what the heck you're doing with the saved return context.

I'm with you about "Processes" -- that's pretty much the same idea Alan Kay had, except when he had it he called them "Objects" and then went on to invent Smalltalk. His notion was of computation proceeding by Objects (Processes) exchanging Messages (Signals), where the response to each Message was determined by the Object, and could vary from object to object, and that aside from sending and recieving Messages, there should be no way to look inside an Object, leaving people free to do things a different way later as long as it resulted in something that implemented the same message protocol.

IOW, he found a simplified way to express the 'encapsulation' property of ADT's with interfaces. Up until Smalltalk, encapsulation had been mainly a matter of programmers having a specified interface and being told, "Don't do that" when they wrote code that interacted with another ADT's data by means other than the interface. Previous attempts to turn "Don't do that" into "You CAN'T do that" were unsuccessful because they resulted in languages that weren't expressive enough. They banned too much.

With Kay's notion of Messages and Objects, it became possible to design languages in which encapsulation was of the "You CAN'T do that" variety, without sacrificing (much) flexibility and expressiveness.

Subclasses, hierarchies, and inheritance were all different ideas that got added to Kay's notion of "Object Oriented" later.

You should read starting at

http://www.smalltalk.org/smalltalk/TheEarlyHistoryOfSmalltalk_Abstract.html

it's inspirational.

Ray

By Ray Dillinger at Thu, 2012-08-23 18:40 | login or register to post comments

The semantics aren't complicated

Processes have a control state, which is commonly represented as a stack. To suspend / clone a Process (i.e. capture a continuation and treat it as a value), the simplest implementation is to copy that control state. There are some mildly complicated optimizations you might want to make, but the core semantics are very simple. If you don't believe me, you could provide an example that you think would be challenging and I can explain how you'd handle it with Processes. I don't know exactly what you have in mind when you say something like this:

it matters what the heck you're doing with the saved return context.

Conceptually, Processes don't manage their context; the context manages the Process. How an implementation save contexts is a detail that's not very hard to work out from the semantics. If a Process is no longer reachable, you can collect its stack just like other garbage.

I'm aware of the parallels between Processes and Objects and I think I've read some version of the contents of your link. The most important thing Smalltalk gets wrong is that it thinks of objects as global entities with identity. That's a big problem semantically if you intend to clone objects, since you now have to figure out what portion of the object soup to copy (and even then you have to carefully rewire references in the copy to refer to the copied objects).

So once you decide to get rid of identity, you have figure out what to replace it with. If you stick with a simple OOP calculus, where objects are just records of functions (of the kind that William Cook wants to define OOP), you've lost the power to gracefully deal with side effects. That's the point of Processes - building pure objects that also have side channels. Given these differences to OOP and the fact that OOP means all kinds of things now, I use a different name. Not that "Process" is going to avoid all confusion.

By Matt M at Thu, 2012-08-23 19:31 | login or register to post comments

Are algorithms specified in

Are algorithms specified in terms of processes in your language, or do you provide both processes and functions?

By naasking at Sat, 2012-08-25 13:07 | login or register to post comments

re: A brief thought

About this claim and similar ones:

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.

Well, so what? Isn't that a problem to be solved in application specific ways by means such as programming conventions? It is demonstrably possible to write useful programs in a language with both features.

What you've said seems to me similar to saying: "If you try to combine continuations and exceptions in ways that don't make a lot of sense, then it won't work well." That's trivially true but I don't think it tells us much if anything about language design.

By Thomas Lord at Thu, 2012-08-23 20:34 | login or register to post comments

Play nice

First: I cannot imagine any way for both exceptions and continuations to coexist in the same language without causing semantic problems

It's very difficult to get them to play well together. Exceptions in
destructors in C++ had similar problems. You may have to prohibit some combinations to prevent trouble. Funny things happening during exception processing are particularly hard to debug, because exceptions don't happen that often and may be difficult to force from test cases.

By John Nagle at Fri, 2012-08-24 06:12 | login or register to post comments

Delimited

Oleg was talking about call/cc, not about delimited continuations. I am quite confident exceptions can be implemented with delimited continuations and play well with them.

You just have to define clearly what different combinations do, so that they can be expressed in terms of delimited continuations - such as returning a value in the exception handler, throwing an exception in the middle of processing a yield sequence, etc.

By Denis Bredelet -jido at Fri, 2012-08-24 07:29 | login or register to post comments

another "no to always" vote

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.

By Rys McCusker at Fri, 2012-08-24 02:37 | login or register to post comments