Some of the most amazing quality-of-life features of many programming languages are centered around control flow. For example, lazy-evaluated iterators in the form of generators in Python, async/await for asynchronous control, etc. are all ways to improve the control flow in a language. However, as more disciplines become more computational, it is becoming apparent that new types of control flow operators are necessary. For example, modern machine learning relies heavily on reverse-mode autodifferentiation, which in many languages is implemented as a secondary DSL embedded in the host language.
Wouldn’t it be great if our languages had an abstraction that allowed us to build any control flow operator we wanted? These atomic objects are known a delimited continuations. Recall that a continuation is merely an abstraction of “the rest of a computation”. For example, consider the following computation
if x == 0 then 1 + 3 else 4After the evaluation of x == 0, its continuation is the remaining holed-computation
if [] then 1 + 3 else 4However, these aren’t really true continuations! Philosophically, the continuation extends beyond the code, to the effects generated by the hardware, etc. Hence, we really want to consider continuations restricted to a certain point. These are delimited continuations, and these are the objects that can be reified into functions in the host language. Delimited continuations allow us to manipulate the control flow of our programs. And although monads allow us to control the sequential flow of computational effects in our programs, delimited continuations give us the flexibility to do more with that control.
shift/reset
Delimited continuations are realized in a language via control operators, which allow us to capture both the scope of the continuation and to express the flow of the program. The most written about operators are shift and reset, though there are others in the PLT literature.
First we recall continuations in Haskell. A continuation is a suspended computation, that is, to resume it we need to give it a callback. Hence the type is given by
To understand the monadic instance, it might be easier to see what happens in CPS (Python):
def f(x, k):
y = <computation in f>(x)
k(y)
def g(y, k):
z = <computation in g>(y)
k(z)
def comp_g_f(x, k):
f(x, lambda y: g(y, k))In Haskell, this same inversion of control is explicit in the monad instance:
{-# LANGUAGE InstanceSigs #-}
instance Monad (Cont r) where
return :: a -> Cont r a
return a = Cont $ \rest -> rest a
(>>=) :: Cont r a -> (a -> Cont r b) -> Cont r b
f >>= g = Cont $ \k -> runCont f (\a -> runCont (g a) k)Next we turn our heads towards the control operators shift/reset. The semantics are fairly complicated, so it suffices to look at an example. Lets look at the expression
1 + reset (2 * (shift \k -> k (k 5)))The way to interpret this is to look at the bound variable k in shift. It is bound to the continuation outside the shift, delimited by the reset, which in this case is given by 2 * []. Hence k 5 is 5 applied to this continuation, so 10. Applying k again gives 20, so we replace the above with 1 + 20 == 21.
Written out, we can express these two control operators in terms of the continuation monad:
-- helper function for running computations
runC :: Cont r r -> r
runC ct = runCont ct id
reset :: Cont a a -> Cont r a
reset f = Cont $ \rest -> rest $ runC freset wraps a computation to set the boundaries of the delimited continuation. Once the computation inside finishes, it returns the rest of the computation outside of the reset statement. The shift operator is a bit trickier:
The input to shift is a function that takes a callback function to form a computation. All shift does is run this continuation! By itself, this does nothing– there isn’t any control flow present here. However when combined with reset, the callback k is bound to the “continuation delimited by reset”.
As an example, we use the computation above, translated to Haskell:
example :: Cont Int Int
example = liftM2 (+) (return 1) $
reset (liftM2 (*) (return 2)
(shift (\k -> k <$> k <$> (return 5))))Notice the Scheme-esque parentheses and operators! Anyway, it’s fairly straightforward to lift these things. Evaluating with runC we get our desired answer.
exceptions as control
People who use Python (I refuse to use the neologism for them) are familiar continuations even though they aren’t first-class objects in the language– they use exceptions! Exceptions capture the control stack at a future time and allows one to swap out for that stack completely when an error is raised.
This effect can be replicated via delimited continuations. Throwing an exception can be thought of as interrupting a computation in a try-block, forcing the short-circuiting of the block. As above, this is a shift-block where the callback is ignored, and instead control is handed directly to a handler object:
Of course, a throw statement is useless without a handler to deal with it (this is the framework of algebraic effects that I’ll talk about in a later post). This is given by a try-except block: The computation occurs in the try statement until a throw statement is encountered. In this case, the computation’s continuation in the try block is ignored, and control is completely given to the handler. This is a delimited continuation, where the try is contained in a reset!
However, this is a bit tricky to write. To simplify matters, lets look at how we can just exit from a computation early (without handling the output). Just like the throw statement, an early exit in a delimited continuation is a shift-block:
exit :: e -> Cont e a
exit e = shift (\_ -> return e)
test = reset (liftM2 (+) (return 2)
(shift (\k -> k <$> (exit 0))))Running the above results in 0, which is the exit value. However, the exit value is undistinguished from a normal value, which is bad since thrown exit values should be passed to the exception handler, while normal values ignore it. We could distinguish it by creating a custom type, or we can “functionalize” the continuation. This trick gives the try-except block:
tryExcept :: (e -> r) -> Cont ((e -> r) -> r) r -> r
tryExcept h s = runCont (reset
(do
x <- s
return (\_ -> x))) hf
where hf = flip ($) hAs an example of how it works, look at
example1 = tryExcept (\e -> e + 42) $
(liftM2 (+) (return 17) (return 4))
example2 = tryExcept (\e -> e + 42) $
(liftM2 (+) (return 17) (throw 4))Running example1 gives 21, as nothing is thrown. However, in example2 a throw statement is called with the exception value 4, which is handled in the handler \e -> e + 42 giving us 46 as the final value.
the yield statement
Our delimited continuations are awesome, and we wish languages had a fun way to expose these objects without turning to continuation-passing style (CPS). (Yes, the Cont monad is CPS– code written wrapped in the Cont-context is implicitly in CPS). It turns out that languages that expose a yield primitive actually have a way to access delimited continuations! This is the central result of the paper by James-Sabry “Yield: Mainstream delimited continuations”, written by two professors at IU. For some reason I never really spent any time near Lindley Hall (the CS department) even though Rawles was literally across the street…
Since yield statements are used in Python generators, let’s explore how to build a generator with continuations. Recall that a generator is effectively a lazy iterator. What this entails is that once a generator is called to output a value, it suspends until the next time it is called. This should immediately scream reified continuation! A generator will output not only a value, but also keeps track of the reified continuation corresponding to the remainder of the iterator. When the generator resumes, it merely starts over by running this continuation object.
We can capture these continuations using the reset/shift control operators. Consider an example:
gen = reset (do
(shift (\k -> liftM2 (:) (return 1) (k <$> (return []))))
(shift (\k -> liftM2 (:) (return 2) (k <$> (return []))))
(shift (\k -> liftM2 (:) (return 3) (k <$> (return [])))))We see that in this, whenever the expression k <$> (return []) is reached, a continuation is reified, and that continuation object represents the rest of the iteration! When we run this generator we get back [1,2,3]. We abstract the repeated statement– this is a yield:
This yield statement has the right credentials: calling it suspends the computation by reifying the remainder of the computation, which exists outside of the shift statement. With this operator, we get the generator as:
The main insight of the above paper is a generator (with yield statement) entirely encapsulates a delimited continuation, where each yield statement is equivalent to a shift statement. In this way, the reset block tells us how to run the generator. This can be extracted in familiar language as run:
We see that running gen gives back our [1,2,3] as desired.
python?
Since Python generators are so prevalent, could we use them like delimited continuations? As an experiment, I wanted to try replicating the above exception handling. However I ran into an issue– generators are not really designed to be flattened. I needed multiple layers of generators, and the yield statements in Python seems to only capture the continuation in its base generator.
This presents a small issue. It seems like Python generators and its built-in try/except exception handling are orthogonal abstractions! This is exploitable, and is the focus of one of my favorite papers in computer science: thermometer continuations. This is the content of my next post.