Offer a primitive for delimited continuations

[mnieper]

For many applications, delimited continuations and not undelimited ones (which can be captured by call/cc) are needed. They are also the basis for algebraic effect handlers, which have become very popular in recent functional programming.

While delimited continuations can be implemented via mutable global state and the host's call/cc (see [1], for example), the result would not play along well with the host's call/cc (because of the mutable global state) and the host's dynamic-wind, so new user-facing versions would have to be exposed. This can only happen on the level of standard libraries (which implicitly use call/cc or dynamic-wind, e.g. in the guard macro), though, so delimited continuations can effectively not be implemented portably.

Thus, I would like to see some primitive form in Chez's library that gives access to delimited continuations and that plays along well with the other standard procedures (including the versions of call/cc and dynamic-wind exposed to the user.

In SRFI 248 I propose a minimal API for delimited continuations that is compatible with other (larger) APIs in the sense that they can express each other portably. I'd love to hear your comments on this SRFI, which is still in draft status.

It would be great if Chez supported a primitive on that SRFI 248 can be implemented; one way for this would be that Chez just offers SRFI 248 support in its (chezscheme) library. I would not shy away from some work needed to implement this if there is some consent about the ideas.

--

[1] A Monadic Framework for Delimited Continuations

[samth]

Chez Scheme does offer enough to implement delimited continuations. Racket has a wide variety of delimited operators, all implemented on top of Chez internals. See the implementation here: https://github.com/racket/racket/blob/master/racket/src/cs/rumble/control.ss

[mflatt]

The Racket implementation uses a few #%$ names, though, and it carefully avoids around Chez Scheme's winders. So, there's more to be done to provide a public API.

[mnieper]

I know of Racket's implementation and studied it before I wrote my SRFI 226 (which, to a large extent, makes Racket's control features available to other Schemes). The sample implementation of SRFI 226 is also based on what is currently available in Chez Scheme. However, as much as Racket's implementation, it cannot export the host's call/cc and the host's dynamic-wind but must provide its own versions for the user to call.

The situation is analogous to R4RS, which has call/cc but not dynamic-wind. One can portably implement dynamic-wind in R4RS but not without replacing the user-facing call/cc with a version that ultimately calls the R4RS call/cc but also pays attention to the winder stack.

As long as I can control all the code in my program, all of this is not a problem (replacing call/cc with some custom version throughout is just a global program transformation, after all). As soon as third-party code comes into play, this is no longer possible. Say, if I offer a library exporting a higher-order procedure that internally uses delimited continuations, it will only work as long as I can be sure that the user does not call a call/cc, dynamic-wind, guard, parameterize, etc. that is not modified to play along with the implementation of delimited control within the dynamic extent of my procedure.

In Racket, I can do this because the call/cc that is exported by the Racket libraries (on which third-party code builds) is the one from Racket's control.ss and not Chez's primitive one.

Thus, delimited continuations need to go into the core of Chez Scheme so that the versions of call/cc and dynamic-wind found in (chezscheme) and (rnrs (6)) are no longer the primitive ones but the delimited-continuation-aware ones. As different APIs of delimited continuations are inter-expressible, the exact form is not important. SRFI 248 proposes a minimal API that would fit well into the scope and breadth of Chez Scheme's libraries. This integration of delimited continuations into the core can be done in two ways: either by doing it independently from Racket's needs so that Racket's control.ss will continue to be based on Chez's original primitives or by doing it in a way that basically factors out some part of Racket's delimited continuations into the core of Chez, allowing to reduce control.ss in size.

I believe that delimited continuations would be the most important single addition to a future Scheme standard. While Scheme has always been at the head when it comes to representing control in programming languages, since the advent of algebraic effect handlers, other languages have taken over. It would be an investment into the future if Chez Scheme supported some form of delimited continuations as Racket and Guile, for example, already do.

[mnieper]

Besides incompatibility with the host call/cc and the host dynamic-wind, another problem with implementing delimited continuations as a library on top of what Chez Scheme currently provides will be incompatible with the host continuation marks.

Thus, delimited continuations really have to be offered by the Chez Scheme core to be useful for R6RS+/ChezScheme users. As Racket's implementation would still need the primitives that are currently provided by Chez Scheme, I wonder whether the best course of action is to integrate the non-Racket specific parts of https://github.com/racket/racket/blob/master/racket/src/cs/rumble/control.ss in Chez Scheme so that both Racket and R6RS+/ChezScheme programs can make use of it.

[mnieper]

A new draft of my SRFI 248: Minimal delimited continuations has been published.

Would you accept pull requests that would implement the procedures and syntax in the (chezscheme) library? Or would you prefer a different interface to delimited continuations? Feedback is very much welcome.

Alternatively, would the Racket team be move enough of Racket's/Rumble's control.ss into Chez Scheme proper so that it can be accessed through (chezscheme) and so that SRFI 248 can be implemented on top of it (and in a compatible way with the R6RS semantics)?