## Implementor's guide/tutorial to delimited continuations?

Is there are really simple tutorial on implementing a language with delimited continuations?

E.g. this is how you represent stack frames, this is how you capture a continuation, etc.

Something like this, but complete:

when a continuation is captured a chain of exceptions gets propagated up the stack. At each "stop" on the way up the stack, an exception handler cons-es up a closure which will continue the function whose frame is active at that point. When the exception reaches the top level of the stack, the frames are packaged up as the continuation. Activating the continuation simply calls the closures in order to resume the saved computation where it left off. All the implementation needs to provide is some way to unwind the stack, stopping at each frame along the way. In C, it would be a longjmp/setjmp; in Java it would be catch/throw; in .NET catch/throw.

Thanks.

[Edit: I realized that something like A Monadic Framework for Delimited Continuations is probably the closest thing to what I'm looking for.]

## Comment viewing options

### Compiling with Continuations

Compiling with Continuations by Andrew Appel.

I have an unopened copy collecting dust on my bookshelf. I was not impressed with one of Appel's other books. So I cannot speak to the quality of this one.

### I don't think that has

I don't think that has anything about delimited continuations in particular.

Another one worth looking at was a paper about doing it in Scala a few years ago (ICFP09), but the focus seems to have been more about dealing with the JVM and a clean implementation. I'm not sure about papers interested in efficient implementations (which can have many different use cases to optimize for).

### Performance doesn't matter to me

I'm looking for the simplest implementation (which is probably the first Haskell one in the Monadic Framework paper). Once I have delimited continuations in my language, that will be so awesome, that I won't care about performance anymore ;)

### If performance doesn't

If performance doesn't matter, it might be simpler to just support continuations and add delimited control as a library. I think "Functional Pearl: The Great Escape Or, How to jump the border without getting caught" and its predecessor were along these scheme-ish (rackety?) lines.

### Do not implement undelimited continuations

If performance doesn't matter, it might be simpler to just support
continuations and add delimited control as a library.''

I'm puzzled by such suggestions: I know of several ways of
implementing undelimited continuations, and each is more complex than
implementing delimited continuations. If you are going to copy the
whole stack, it is simpler to copy a part of it. The efficient
undelimited continuation methods, with underflow frames, essentially
implement delimited continuations. The Cont monad is the
monad of delimited control; one has to jump through extra hoops to
make it behave like the undelimited continuation monad.

Implementing undelimited control is always more trouble than
implementing delimited control -- and for what purpose? I cannot
recall a single practical application that requires specifically
undelimited continuations. I'm amazed at the persistence of call/cc
in Scheme; the only reason I can find for the support of undelimited
control in Scheme is to deliberately confuse students: the captured
undelimited continuation looks like a function, but it is not.

### harm caused by undelimited continuations?

Oleg: I'm amazed at the persistence of call/cc in Scheme; the only reason I can find for the support of undelimited control in Scheme is to deliberately confuse students: the captured undelimited continuation looks like a function, but it is not.

Since I expect to add undelimited continuations to another Lisp dialect, I'm interested in why it's a bad idea (if an explanation doesn't require a sophisticated language theory background). I'm aware you have famously done nice work in delimited continuations, so I expect your opinion is useful since grounded in practical experience, giving you insight I probably lack.

I have a strong "do no harm" ethic, but confusing students doesn't count as harm. :-) I'm really interested in what harm is caused by undelimited continuations, though, if you have examples.

As context, note I plan to use cactus stacks instead of monolithic, contiguous, C-style stacks. This is partly because I need a stackless design friendly to language-native async semantics. So there's no stack copying involved. Instead I have advantages and disadvantages of high granularity stack allocation on a per-frame basis. It would be slow unless async delays happen a lot, which is what the architecture is for.

An undelimited continuation model is natural with cactus stacks. It sounds like you're saying delimited continuations would be easier or safer. (I'm much less interested in safer.) I agree undelimited is more awkward with contiguous stacks.

Assume I want 100K lightweight threads serving tens of thousands of network connections, so cactus stacks are the only choice in available memory resources. How do undelimited continuations do harm here? I'd rather know sooner than later if it affects my plans. Apologies if you lack time or inclination to reply.

You wanted a practical application that requires specifically undelimited continuations. While not required, I think async apps are less convoluted with undelimited continuations. You can always simulate async code in sync systems, via callbacks and other styles, but at the cost of slightly strained organization. I can only elaborate easily by analogy.

Suppose you want something done: task X. But your library doesn't do X directly. Instead it says, "We handle X by getting everyone in line over there ... so get in line." Internally, the line-handling for X uses other services, who also have their own lines, and all the bits of code follow severe rules about what can happen when, and rules you must satisfy to qualify. The result can be fragile, puzzling, and dependency inducing in a way that limits choices, to the extent you assume no choices are allowed.

Undelimited continuations have an allure of permitting direct action without intermediaries and their various rules and bugs, and this is the appeal.

### I've been on the side of

I've been on the side of full (undelimited) continuations and no continuations at all (to simplify security reasoning). However, as a design principle, going all the way in one direction or another was worth it; frustration with the evolution of JavaScript makes me loathe to do intermediate approaches. In this case, my guess is that someone wanting delimited continuations will also find use for other forms: at that point, first implement the general feature, and if delimited continuations need more specialized support, only do it then.

OTOH, it might be possible to go the other way -- from delimited to full -- making this all moot, but I haven't reasoned that through.

### The issue is that

The issue is that undelimited continuations are not composable. They are strictly less powerful than delimited continuations.

It sounds like you want to make a kind of system / userspace delineation in your program. The best tool for that is the delimited continuation. Using call/cc is generally a mistake, IMHO; delimited continuations can do backtracking/escaping better, and any other use of call/cc usually requires set!' to do anything useful, which is a composability lose.

### less is more?

Andy Wingo: The issue is that undelimited continuations are not composable. They are strictly less powerful than delimited continuations.

What makes them not composable? (I'm not seeing it.) I wonder if you mean it's easier to type delimited continuations, making it easier to compose them in strongly typed system, but that's a wild guess. This is interesting, so I hope to understand.

It's clear you're saying delimited continuations do something undelimited ones cannot, which seems surprising. Usually more limited things do less. So perhaps you mean since you can see where it's limited, you make more assumptions, and that feels more powerful?

I would only expose continuations via call/cc and not use that directly, so I can't speak to ills in that formulation. I'm not grasping the system / userspace delineation idea. My plan is a soup of userspace continuations, which includes language runtime. Did you mean the language runtime as system?

any other use of call/cc usually requires set!' to do anything useful, which is a composability lose.

If your runtime allows mutation, so calling a function has side effects, then part of contracts in calling any function is how many times you can call it. (For example, if you pass a callback method to an api, the number of times it can be called is part of the contract.)

I assume this is what your remark means: that to call a continuation more than once, usefully, implies the continuation was prepared to consume more than one such event, modifying state somewhere to good effect.

While it's true you need to design a continuation to be called more than once, if this is to occur, that's not much different from needing to design how often anything is called in a system with side effects. Are you saying functional systems are composable, but others aren't?

### All continuations are

All continuations are delimited, in practice. The difference between delimited and "undelimited" continuations is that in the latter case, the limit of your continuation is defined by your operating system. Adding a delimiting operator to your programming language makes your language more expressive, because the user can reset that barrier. For more on continuations and operating systems, see Kiselyov & Shan's 2007 paper.

But, there is a conflation in terms here. What is often called a "delimited" continuation is often also a "composable" continuation, in the sense that application composes with the current continuation, like a function call. Continuations captured by call/cc do not have this property. This leads to the result that you can't implement exceptions correctly using call/cc if your users have access to call/cc. Again I think that Oleg's papers are the ones to cite here; for example, Undelimited continuations are not functions.

### too authority oriented

I see no relation between anything I asked and your reply, which seemed evasive, so I assume that will be the trend and I won't press you further. But thanks for your time.

The difference between delimited and "undelimited" continuations is that in the latter case, the limit of your continuation is defined by your operating system.

Or, if I implement them myself, the limit is whatever I want. I needn't read more about continuations and operating systems, since I can pursue my plans so far.

I lack interest in continuations captured by call/cc, since I'll use continuations at a lower level I write myself, exposing those in a call/cc entry point for folks who prefer that api instead of another. Limits of call/cc won't affect me at all if I'm the implementor. If it helps, think of me as writing in assembler, although it will actually be C.

You asked, "what makes call/cc not composable"; I think I gave an answer to that. No need for the rude reply. Of course you can pursue your plans, your use case might be different from Scheme's. I gave my experience, such as it is.

### apology offered

I thought about it and I agree, I was rude, so I'm sorry. You were being helpful and didn't deserve negative feedback. I hope my bad manners don't stop you from helping others later, or saying whatever you want. I'll be more polite.

### It sounds like what you want

It sounds like what you want is a tutorial on what delimited continuations are, and why they are more powerful than undelimited continuations. Un-de-limited continuations are henceforth referred to as limited continuations ;)

So lets compare it to a simpler construct: exceptions and exit(). In C you can call exit(c) to return c from main(), the difference is that exit(c) also works inside functions called by main. Lets assume a simple but peculiar exception handling facility like this:

throw(v) // unwinds the stack to the nearest try block, and returns v from the try block
try { ... }


For example:

try { 8 } // returns 8
try { 8 + throw(3) } // returns 3


Which one of these constructs is more powerful, exit() or this try-throw feature? The answer is, of course, the try-throw feature: you can not only unwind the stack completely, but you can even specify to which point you want to unwind it (with try blocks). Calling exit(c) corresponds to putting a try block only around your main function, and invoking throw c instead of exit(c).

We are in a similar situation with delimited and limited continuations. Limited continuations can only capture the whole program stack. Delimited continuations allow you to specify to which point you want to capture the stack, in a similar way as a try block.

In fact, delimited continuations implement our exception handling facility directly! Delimited continuations have two operations: reset and shift. Reset is like try, and shift is like throw, but more powerful. Instead of just taking a value like throw, shift binds the continuation up to the nearest try block to a variable.

The equivalence is:

try { ... }  ~=~  reset { ... }
throw(3)     ~=~  shift(k -> 3)


So the examples above:

reset { 8 } // returns 8
reset { 8 + shift(k -> 3) } // returns 3


You see that if you call shift(k -> v), then v will be returned from the enclosing reset block.

The difference comes in when we actually call the continuation k. This function represents the computation around shift up to reset. So in the example above k represents 8 + [], in other words k(x) = 8 + x, i.e. k is the code that would have been skipped if you'd thrown an exception. There is nothing special about calling k, it just happens to be the function representing the surrounding code. Now you can guess what this does:

reset { 8 + shift(k -> k(3)) }


Because here k(x) = 8 + x, this is the same as:

reset { 8 + shift(k -> 8 + 3) }


And as you know, the value in the shift is returned from reset, skipping the surrounding computation like in exception handling. So the program returns 11.

Quiz: what does reset { 8 + shift(k -> k(k(3))) } return?

In the same way that exit() is a degenerate form of exception handling, limited continuations are a degenerate form of delimited continuations where you only put a reset block around your whole program. Like with exit() this is not such a useful place to put your handler:

The difference between delimited and "undelimited" continuations is that in the latter case, the limit of your continuation is defined by your operating system.

### Try/throw highlights problems with delimited continuations

Your example of generalizing try/throw to delimited continuations reminds me of why I don't like the API for delimited continuations. When we generalize throw from throwing a value to capturing a continuation, that's very much like adding resumable exceptions (re-resumable, in fact), with the bizarre caveat that the code throwing the exception is required to provide the exception handler. A more friendly API might work more like this:

try { 8 + throw(3) }
except(n, k) { k(k(n)) }

I understand that delimited continuations are usually used at a low level to implement more sane APIs, but I'm not sure it's not better to just start with a more sane API. You can always encode back to shift/reset:

try { 8 + throw(k -> k(k(3))) }
except(f, k) { f(k) }

[Edit: I'm being a little disingenuous. I understand that reset/shift is simpler than the mechanisms needed to get my proposal working. But I also don't think you'd encounter many people who consider re-resumable exceptions mind-bending in the same way that they consider delimited continuations mind-bending.]

### I wonder what I did

When implementing exception handling for my language I also took a glance at reset/shift. I didn't really understand all of it, that came later, and didn't have a stack, so wanted something simpler, so the thing I did was introduce two operators.

Described really trivially -I actually might have done something more complex,- it just has two rules:

R f = f S (remember the current context in S)

S x = x (but also, whenever S evaluates it replaces the original R f term)


An example:

1 + R (\s -> 1 + s 3) = 1 + (\s -> 1 + s 3) S = 1 + (1 + S 3) = 1 + 3 = 4


Anyone any idea where this falls in the whole debate?

### Leaking shift

So basically you got rid of shift as a special form and pass it to reset's parameter as a value. What happens then when the value escapes from the evaluation context of R? For example, what does (R id) evaluate to?

[Edit: It occurs to me now that maybe you're also passing in a different version of S to each R call? So this is a mechanism for you to name prompts? That seems reasonable, but I think my complaint about this setup as an API still applies.]

### No idea, it never happens (I hacked it)

The compiler makes sure that try/catch and throw blocks are compiled correctly; uh, I hope. Basically, a try/catch block is replaced with a somewhat difficult term involving R and passing around exception handlers correctly. Your example won't occur translating well-formed try/catch blocks, but yes, it would evaluate to what you would expect:

R id = id S = S S = S


Since, in my runtime, S refers to the old context (a thunk expecting a value), the result would be non-sensical: a thunk referring a combinator S which would refer into that thunk again and when applied to something would overwrite the thunk's value S.

(Btw, the compilation/evaluation should make sure that S cannot escape an R f which introduced it. Basically the R is the try/catch block and S is used whenever something is thrown. I omitted the exception handlers above for brevity. In case of an exception, the translation makes sure that S is applied to g x where g is an exception handler an x the value being thrown. If no exceptions are thrown, S will never be applied and just a value is returned - and therefore, since S is never handled explicitly, it is 'lost'.
At least, I hope it works that way, debugging compiled/evaluated terms showed no errors so far. But I hacked it in a 'let's see if this works' mood a long time ago, don't even remember what I did exactly, I should check it once again.)

[ I usually just glance at some papers for inspiration, try to 'dumb it down,' and then puzzle something together which should work in my setting, which is a combinator evaluator. Just wondering whether it is a known approach.
It might leak, or do something unexpected, not sure about curried values and such. ]

[ Hmm, I convinced myself that the current translation leaks in corner cases, returned curried functions. Fortunately, it seems to be solvable with a slightly different translation. ]

### Yes, each R introduces an S

Yes, each R introduces an S in which the 'current context' is stored; i.e., the thunk which expects the value of the evaluation of some R f. You can also see that as that S saves the 'term' which must be replaced.

I could also write the example with indexed curly braces and S, where S_i x will replace the term enclosed with the similarly tagged curly braces, to make everything explicit.

R f = {_j f S_j }_j    (j is chosen uniquely)
{_j .. S_j x .. }_j = x       (when evaluated it replaces the whole term enclosed between {_j and }_j)


For example:

1 + R (\s -> 1 + s 3) = 1 + {_i (\s -> 1 + s 3) S_i }_i = 1 + {_i 1 + S_i 3 }_i = 1 + 3 = 4


[ Edit: one could say that R/S are necessary and sufficient since the only 'thing' you need for exception handling support is just a mechanism to unwind a part of the stack. And unwinding part of a stack in LC terms means nothing more than that at any time a previously tagged part of a term can be replaced. ]

### focus on reset and shift?

Jules Jacobs: It sounds like what you want is a tutorial on what delimited continuations are, and why they are more powerful than undelimited continuations.

Perhaps I did without realizing it. I'm quite impressed by your nice presentation, though I still have more to digest. If I come to grasp reset and shift well enough to implement them (and it makes sense to support what folks use) then I'll write about it later.

I made the mistake of assuming both delimited and continuations were descriptive and related to notions I already understood. But it seems this is a brand-X name for a mechanism with which continuations are associated. So it appears to have little to do with, for example, Smalltalk blocks that no longer function once a method scope exits, or anything similar.

But thanks for writing cogent descriptions in response to my poorly framed questions.

### The naming is consistent

I made the mistake of assuming both delimited and continuations were descriptive and related to notions I already understood.

A continuation is usually understood as (some form of reification of) an evaluation context. "Delimited" means that the scope/extent of the continuation is clearly... delimited. This means that the evaluation context captured is not "all the context" (usual, non-delimited continuation), but only "the local context upto ". The name seems rather appropriate and descriptive to me.

### Continuation Stuff for Schemers

Hi Rys! Long time no chat!

There are a couple of papers (and by "couple" I literally mean "two") that might clarify some of the terminological (ab?)use around "delimited continuations." The first I suggest is How to remove a dynamic prompt: static and dynamic delimited continuation operators are equally expressible. It's a tech report, but there's also R5RS Scheme code because I know you like things to be as concrete as possible. :-)

The second is Delimited Control in OCaml, Abstractly and Concretely. While the paper is focused on the OCaml implementation(s), it defines an API, "scAPI," for an abstract machine, implementing delimited continuations. Multi-prompt delimited control in R5RS Scheme, then, is the scAPI expressed in R5RS Scheme, again so as to make it concrete.

I hope this helps a bit!

### not yet, but thanks

Hey Paul! Hope you're having fun these days. You don't post often. (I lurk myself.)

Neither of those help much yet. The former, tech report TR611, goes into notation I can't read in the second section and I'm lost thereafter. The latter uses OCaml whose syntax I don't follow yet, and it seems unlikely I will later. Presumably the concrete Scheme code will be useful as soon as I understand the spec of what delimited continuations are supposed to do. The Wikipedia page on the topic was only suggestive.

Are delimited continuations static and syntax only? Can they escape the context in which they appear? I haven't seen an answer to that one yet.

I read a paper, Delimited continuations in operating systems, which said delimited continuations were involved, but I saw no relation to descriptions elsewhere. (I saw nothing resembling what is called a delimited continuation in examples.)

### Sure, delimited

Sure, delimited continuations are just functions. For example in the example I gave there is really no observable difference between using k and using x -> 8 + x.

As for implementing delimited continuations, there are basically two methods. You can do some kind of CPS-transformation, or you can manipulate the call stack. The call stack manipulation is described in Oleg's paper mentioned above. The CPS-transformation method is described in A Monadic Framework for Delimited Continuations.

Which one is easier to follow depends on who you ask, but I think that the stack manipulation is easiest unless monads or CPS-transforms are a piece of cake for you (in that case the whole of multi-prompt delimited continuations can be described in 6 lines of code, see page 18). The OCaml syntax is not hard, it's actually very close to Scheme. With an introductory tutorial you can get up to speed in minutes if you are already familiar with Scheme's features (let, lambdas, structs).

### "just functions"?

I think calling delimited continuations "just functions" is a bit problematic. The interface to delimited continuations may certainly be functions, but the implementation may be very different from functions - they're special objects (e.g. holding a reference to a stack segment in the stack manipulation implementation style).

### That is an implementation

That is an implementation detail :) The point is that they act like functions, that is, they are not special apart from their representation. You could view a list as a function from indices to values. The representation happens to be a list, but from the outside it looks like a function.

Thinking about it a bit more about multi prompt delimited continuations as described by Delimited Control in OCaml,
Abstractly and Concretely and A Monadic Framework for Delimited Continuations. There is a push_subcont with type ('a,'b) subcont -> (unit -> 'a) -> 'b. The type I would have expected is ('a,'b) subcont -> 'a -> 'b, since ('a,'b) subcont is just a function 'a -> 'b with push_subcont being the apply function for this special function representation.

Somehow the control effects in the second argument of push_subcont had to be delayed, probably until after the subcont is pushed. I wasn't able to find an example of code that uses this mechanism, in the examples I found the (unit -> 'a) were expressions without effects, so the type ('a,'b) subcont -> 'a -> 'b would have sufficed for push_subcont.

Does anybody know an example where this extra feature is used?

What bugs me (slightly) about treating continuations as functions in Scheme is that the language here makes use of a feature (namely, ad-hoc polymorphism) that it doesn't make available to users.

### I find that unlikely; that

I find that unlikely; that would add overhead to a fundamental operation (function calls). Instead, I'd expect most implementations to actually represent continuations as closures whose body actually invokes the low-level machinery for continuations.

### Not necessarily

In Chicken Scheme, which is a Cheney on the MTA implementation, continuations and Scheme functions alike just are C functions, and the magic stack tricks are done for all of them.

### Are delimited continuations

Are delimited continuations static ...

Not sure what that's supposed to mean.

But: they're relevant even without static typing, and describe control flow that can't be trivially compiled away.

Some versions work with lexical scoping to determine the extent of the continuation to capture (a bit like named returns might do, given local functions), others perform a dynamic lookup. With a bit of rewriting, both approaches are equivalent (that's one part of the design space).

and syntax only?

No, although a presentation centered around holes and rewriting rules might give the impression that they (or any concept, really) are.

Can they escape the context in which they appear?

Yes.

what delimited continuations are supposed to do.

I suppose it's the same issue as with continuations: delimited continuations are really hard to understand, until something clicks and then a variety of explanation make sense to you.

Let's say we're writing a green thread system. The natural way to do this would be to have a main loop that calls the next thread, and we'd capture execution context (stack, continuation) before returning to the main loop when a thread yields.

With full continuations, we can't do that. Instead, we have to fake it by capturing a continuation of the main loop (and storing it in a mutable cell) before calling a thread, and threads have to yield by replacing their continuation with the one capture in the main loop.

The reason we have to go through these hoops is that we can't capture only the topmost portion of the continuation. In a green thread system, yielding a thread must capture not the whole continuation (including the main loop and what's underneath), but everything up to the main loop. That's what delimited continuations offer.

Delimited continuations are also true functions. With a green thread system based on regular continuations, we must take care not to let threads return normally. Even when execution is finished, they must yield back to the main loop, since it has been erased by the thread's continuation. Calling a delimited continuation, instead, splices the captured partial continuation on top of the current one, erasing nothing, just like other function calls.

Now, in a green thread system, yielding must also return immediately to the main loop. So, delimited continuations per se only offer half the functionality: we also need a way to unwind back to a given activation record. Most languages already offer that (named returns and first-class functions, or throw/catch, etc). Delimited continuations can also be used to express that: while capturing a partial continuation, they can also erase it from the current continuation.

So, with the previous choice (lexical or dynamic scoping for stack marks) and this new one (unwind while capturing or not), we can see why delimited continuations are a *family* of control operators.

As for implementation, in a stack copying system, it means that, rather than copying the whole stack, capturing a delimited continuation copies a prefix of the stack. And, instead of replacing the stack, invoking a delimited continuation copies the captured prefix on top of the current stack (and fixes up return and frame pointers).

### useful detail, thanks

pkhuong: So, with the previous choice (lexical or dynamic scoping for stack marks) and this new one (unwind while capturing or not), we can see why delimited continuations are a *family* of control operators.

This is quite helpful, since otherwise it's hard to see delimited continuations as defined by attributes they either always have or always do not have. Saying they're not the same control operators, but are similar with respect to certain issues, makes it less confusing.

Thanks for taking the green thread avenue in discussion, since that's a space in which I think about continuations. I only get confused when you talk about erasing when yielding. Under cactus stacks nothing need be erased. You just point a green thread at a different frame, so it's constant time. Only searching for a prompt would have a (shallow) linear cost.

In my approach to green threads, yielding is just unscheduling a thread, and doesn't involve doing anything to the stack. Instead, some other thread is scheduled, and it already knows the top of its own cactus stack. (Async blocking calls make a green thread unscheduleable until it's awakened by a reply.)

### The Four Faces of Delimited Continuations

Hi Rys!

Life is good, thanks! Most recently I landed at VMware doing some stuff in Scala, which I'm liking a lot. I try to only post when I feel a) I've come across something really important, b) I understand it well enough to actually participate in any ensuing thread, and c) doing so won't take too much time from programming. I'm on a bit of a "less talk, more code" kick lately.

To try to answer your questions, with the caveat that I barely understand the material myself...

> Are delimited continuations static and syntax only?

No. There is "static" and "dynamic" terminology around different forms of delimited continuations, but that terminology is quite misleading when viewed through the lens of "static" vs. "dynamic" typing, and I think this is unfortunate. The first of the two papers I pointed to covers the subject nicely, I think, assuming that you go into it with the information that "shift/reset" are so-called "static" delimited continuation operators and "control/prompt" are so-called "dynamic" delimited continuation operators.

> Can they escape the context in which they appear?

That is indeed one of the defining characteristics of the various different delimited continuation operators. Generic implementation of all four *F* operators: from control0 to shift breaks the operators down along two dimensions, one of which is whether the delimiter is kept upon the effect or not. That might shed some more light on the issues. The related code is once again in Scheme.

### set of related tools then

Glad to hear life is good. I almost went to VMware a couple years ago, so my work would get more interesting. But they made a big enough effort to retain me where I work now, working on dedup, which amounts to ad-hoc content-based binary diff codecs in C with lots of continuations connecting distributed async local tools and remote endpoint caches, lining up lots of coordinate systems in scatter-gather i/o, etc.

I write a short spec for everything before I do it. I listen to complex or contradictory things people say, then restate problems so folks say, "Well now it's obvious." It's become a habit, so I would only implement delimited continuations if I could write a spec where folks say that after reading it. Some of my code has really interesting control flow.

In the short term I'm doing a toy language, probably without continuations, which I can use to later help write the runtime of another more complex language (probably still a toy, just a hairy one) with green threads and native async scheduling, with pervasive continuations. With lightweight processes and a scheduler, that one subsumes some operating system effects.

I've gotten used to doing manual cactus stacks in C, and writing control operators in C by hand to cause any kind of transfer of control between continuations I need at a given spot. As a model, the configuration space is a call tree of frames, where any point in the tree can be reified as a continuation, as many times as convenient, from as many green threads as needed. It's even possible to mockup a new call tree branch that never existed, if that happens to make things simpler.

I'm getting the idea, from your reply here and other pages I read since, that delimited continuations are a family of control operators whose behavior typically can only be described by characterizing how continuations involved are manipulated. But the actual effects so far just look like one or another of the call tree games I can do in C. (Note to pkhoung: I'll reply tomorrow.)

### Fun With Cactus Stacks

I've gotten used to doing manual cactus stacks in C, and writing control operators in C by hand to cause any kind of transfer of control between continuations I need at a given spot. As a model, the configuration space is a call tree of frames, where any point in the tree can be reified as a continuation, as many times as convenient, from as many green threads as needed. It's even possible to mockup a new call tree branch that never existed, if that happens to make things simpler.

I'm getting the idea, from your reply here and other pages I read since, that delimited continuations are a family of control operators whose behavior typically can only be described by characterizing how continuations involved are manipulated. But the actual effects so far just look like one or another of the call tree games I can do in C.

I think that's right. If you already have the operational ability to create phantom branches in a cactus stack, and all of the manual machinery supporting cactus stacks, then I expect that deriving any of the delimited continuation semantics from the literature you could possibly want would be quite easy. As is so often the case, IMHO, all the verbiage around the constructs has to do with convincing ourselves that our intuitions about them are sound rather than reflecting any implementation hurdles if you've already freed yourself from the machine stack model.

"The continuation that obeys only obvious stack semantics, O grasshopper, is not the true continuation." â€” Guy L. Steele, Jr.

### Implementing undelimited

Implementing undelimited control is always more trouble than
implementing delimited control -- and for what purpose? I cannot
recall a single practical application that requires specifically
undelimited continuations.

Direct threaded C interpreter, which is probably still the most popular interpretive technique. Since the program is already running in CPS form, adding delimited control is a trivial extension. I'm not even sure what delimited continuations would be in the context of such interpreters that could make them easier or more efficient than undelimited continuations/CPS form.

### Several implementors guides

You might find the paper Delimited Control in OCaml, Abstractly and Concretely'' helpful:
http://okmij.org/ftp/continuations/implementations.html#delimcc-paper

The paper describes a general method of implementing delimited control in the systems that have been designed without delimited control in mind. You only need to implement, or map, a simple scAPI. The generality of the method is demonstrated by implementing delimited control in four different systems: OCaml bytecode, OCaml native-code compiler (which produces machine code), Haskell, and Scheme. There should be an extended version of the paper soon.

A different direct implementation is described in: Masuko, M., and K. Asai "Direct Implementation of Shift and Reset in the MinCaml Compiler," Proceedings of the 2009 ACM SIGPLAN Workshop on ML, pp. 49-60 (September 2009).
http://pllab.is.ocha.ac.jp/~asai/papers/tr09-1.pdf

These and other implementations will be discussed at the Continuation Workshop, affiliated with ICFP. Please come! http://logic.cs.tsukuba.ac.jp/cw2011/

### suggestions

Implement the -F- flavor of the prompt operator. The first part of the monadicDC paper has a pretty good overview. If you have dynamic parameters, see also Flatt et al's paper on delimited continuations in PLT Scheme.

If you have a contiguous stack, just copy out the segment of the stack between the prompt and the abort. Reinstating a continuation means splatting it back on the stack, and rewriting the up-pointers in your frames.

FWIW, here were my notes on the process: Guile and Delimited Continuations.

### Which operator to implement

Andy Wingo: Implement the -F- flavor of the prompt operator.''

The experience with delimited control in OCaml shown the need for
another primitive: push_delim_subcont. See Appendix B of the
caml-shift paper. Also, abort is quite handy to have as a
primitive. Overall, multi-prompt shift0 seems like a good choice.

Incidentally, delimited control was first implemented in bytecode
OCaml in February 2006, quite ahead of many systems.
The implementation was fully integrated with
OCaml (in particular, OCaml exceptions) and was perfectly source and
binary compatible. One can use shift with existing, compiled
libraries. The example of differentiating OCaml lexer has demonstrated
that. Now delimcc also supports native OCaml, that is, programs
compiled to machine code.

Thanks for the reply, regarding both implementation and history.

### Limited expressivity and composability of undelimited continuati

A web page http://okmij.org/ftp/continuations/undelimited.html
describes in detail what it means for undelimited continuations not being composable and why they are strictly less expressive than delimited continuations. In my experience, the majority of programs using call/cc also use mutation to store and retrieve continuations across different threads' -- in effect, these programs emulate delimited control. Why to spend effort implementing undelimited control if the user almost immediately will try to emulate delimited control?

Incidentally, emulation of delimited control using call/cc plus a mutable cell is actually more complex than it may appear. A problem may emerge if the language also supports exceptions or dynamic binding. The emulation of delimited control via call/cc may have quite unexpected behavior (see our ICFP06 paper for examples). Second, one has to take extra care to prevent memory leaks: call/cc captures the whole continuation, which is most always more than needed. The heap objects referred from the unneeded part of the captured continuation cannot be collected and constitute a memory leak. The leak may indeed crash a program. The memory leak occurs regardless how you implement continuations: by copying stack, by CPS, using segmented stack, etc. Granted, the leak can be prevented with the help of trampolines. One may wonder though why to implement an inferior facility (undelimited control) and spend effort afterwards patching up the flaws? Why not to implement the needed facility from the outset?

The file bench_coroutine.ml in the delimcc distribution gives a good example contrasting call/cc and delimited control. The file implements two mutually resuming coroutines using call/cc (with several mutations), and shift (with no mutations).

I'm not sure how asynchronous applications are more convoluted with delimited control: the arrival of the signal effectively causes the current process' to execute yield' (or, shift'). The state of the process will be saved and the control reverts to the scheduler, which will decide what to do next. In fact this is how signal handling is commonly implemented -- in CPU firmware or virtual machines or POSIX systems. Virtual machines check the `interrupt line' at some convenient points (typically, upon memory allocation).

### It would help if you would

It would help if you would write your thoughts and prose a tad more in the direction of mere mortals.

### Be happy Oleg is posting!

I for one find Oleg's prose to be clear and straightforward, and I'm definitely no expert in the material. I consider myself lucky to read his more informal thoughts on the subject in this forum, and I want to encourage him to do it as much as possible.

### Thanks; Delimited control in JS

Thank you all for your insightful replies. I'm much further on the path already.

I want to write an interpreter for a language with delimited control in JavaScript.

What implementation approach (e.g. CPS, or heap-based stack frames) would you suggest, keeping an eye on interoperation with JS libraries and language features (such as exceptions)?

### Yield

Javascript has Yield, which is a delimited-control operator.
See:Yield: Mainstream delimited continuations(pdf)

### Clarification

I find that statement somewhat misleading. Just to be clear: standardized JavaScript (aka EcmaScript) does not support yield. Unlike other JS extensions, it's not even a de facto standard.

Generators have been proposed for ES6, but if accepted, will most likely look somewhat different from what is described in that paper.

### Just to be clear:

Just to be clear: standardized JavaScript (aka EcmaScript) does not support yield.

Thanks for this clarification, Andreas.

Just curious, though: when the authors of the paper, that astrobe linked to, use the title "Yield: Mainstream Delimited Continuations", do you think (from you PoV, and how that title relates to today's "state of the art" as one puts it and can see it) that it's a fair enough use of words? I mean, wrt the use of "mainstream"?