Disclaimer

It’s been a few years since I’ve tried to explain continuations to anyone, much less in English. This is my take on what, why, when, how, and WTF when using continuations for fun and profit. I’m probably not the first one explaining them this way, and I’ve borrowed ideas from many places.

I hope former CI3641 and CI4251 students who heard the hand-wavy «I want a sandwich» explanation realize I was trying to convey a very complicated topic that wasn’t worth mentioning in class. Also hope former CI4721/CI4722 students feel my pain at having to focus on less interesting non-functional code generation instead of vastly superior continuation based code generation for functional languages.

Comments are welcome at the usual e-mail addresses.

Going with the flow

There are several ways to describe continuations, all equally confusing and «mystic». Many rely on your understanding on how a programming language actually works, and many requiring you to suspend all that knowledge as well. I agree and disagree with all of them, so this would be my explanation.

Imagine your program executing. Don’t think of the actual code you see on your editor, but «the flow» of the instructions chugging along, after several function calls and what have you. At some point, your program will reach some instruction S and just as it finishes executing said instruction:

• There are a bunch of current active values. From the low-level notion of «the machine registers and its values» all the way to the higher-level «all active variables» and «the call stack».

• There is a particular next instruction S' that is about to be executed in the «normal» flow of execution. It could be the immediately next one in the program text, or it could be a non-local one thanks to an explicit or implicit branch.

Those two things together would be a good enough approximation for what a «continuation» is: some sort of snapshot of the current «interesting values» and immediate «next step».

In most programming languages, continuations appear and disappear with each program step. As a programmer, you’re oblivious to them because the language definition already has a somewhat precise behavior for what must happen at each step. And that’s fine because «normal» people rarely ever handle continuations.

However, there are languages that allow you to save the «current continuation» before moving along, giving you the opportunity to reenact said continuation. If you are thinking «travel back in time» or being able to «choose the future», you wouldn’t be right, but you wouldn’t be wrong. There’s a catch: side effects will not be reversed nor reenacted.

So, let’s build knowledge to go from letting the language control the flow of execution for you, to you being able to create arbitrary flow of execution.

Continuation Passing Style (CPS)

Your average run-of-the-mill function normally takes some input, in the form of arguments, and returns some useful values. A piece of code (the caller) uses the function (the callee). Once the callee «returns» results, the caller continues execution.

Basic knowledge of how programming languages work tells us this means the caller must «pass parameters» and reserve space from the return values. Since this calling of functions can be arbitrarily nested, languages use a «call stack» to store this information. The most recently called function will be at the top of the stack, a new call will add a stack frame, while returning to a previous caller will remove the top frame.

The callee has access to the same stack, so it can take out arguments to perform its computations. Once computation is complete, the callee will store the results in said stack, and will be able to return execution to the exact instruction after it was invoked. Again, because said position is stored in the «call stack».

So, if we have a regular function such as

fac :: Integer -> Integer
fac 0 = 1
fac n = n * fac (n-1)

When a caller invokes fac 42, it has to pass 42 through the stack, jump to fac’s body of code, and wait for fac to compute. Since fac is recursive, it will call (and wait) on itself to compute intermediate values.

In Continuation Passing Style every function receives its usual arguments, and also receives the «continuation function», as an additional argument customarily named k. That is, instead of returning a value to the caller, a CPS function completes its computation and feeds the result directly to the continuation function as its last step – hence, it «continues» computing.

Assuming arithmetic is «primitive» ¹ we can rewrite the above function into CPS like so

fak :: Integer -> (Integer -> r) -> r
fak 0 k = k 1
fak n k = fak (n-1) $ k . (*n)

Notice how there’s a new second argument, the continuation function k, that must take the Integer produced by fak and may return whatever is required. This allows fak to be «continued» by any given function that consumes an Integer.

So, something like fak 42 print would print the result, something like fak 42 even would tell if the result is even or not, and something like fak 42 id would just give the result.

In general, any «regular» function with type

a -> b

can be rewritten to become a «CPS» function with type

a -> (b -> r) -> r

How is CPS useful?

First of all, notice how fac is not tail recursive, whereas fak is fully tail recursive. If you’re using a civilized programming language that does tail-call optimization, your functions will «never return», they just continue one after the other. The callers never have to wait for the callee to return a value.

Secondly, notice how this transformation has made many function call related notions explicit. There’s no need to save a return address in the stack, just jump to the continuation. In fact, you don’t need a complete call stack, because you just follow the sequence of continuations. That’s why many people think of continuations as «goto with arguments», or something like that.

Notice how evaluation order and needed intermediate results are clearly established at any given step. Any programming language that employs or translate into CPS as intermediate representation, makes it easy for their compiler to generate better code. Languages that allow «side effects» anywhere cannot fully translate everything to CPS precisely because of those side effects, as well as aliasing caused by mutable pointers and references. Purely functional languages like Haskell do translate into CPS, this being one of the reasons of the generated code quality.

Last, but not least, CPS allows you to come up with arbitrary flow control management. Regular functions can only return once they finish computation, and to the place where they were invoked. CPS functions can receive one or more continuations, and jump or pass them around again. CPS functions can use continuations from enclosing lexical functions. CPS functions can even save continuations in data structures for invocation at a later time.

Therefore, CPS becomes useful:

• As a general way to re-write functions into tail-call form, to improve «stack safety» and execution speed. This is most helpful on languages that have full Tail Call Optimization (TCO) such as Haskell or Racket.

  Note that in many cases explicit iterative tail-recursion via fold has better speed performance due to fusion, but is less flexible that using continuations. The Haskell compiler allows you to take advantage of both.

• As a way to provide non-local exits. It makes it really easy to jump to any particular part of the code as long as we have the corresponding continuation available. This means you can selectively express what break, continue and goto imply in imperative languages, and then some.

  Working with the proverbial recursive Tree data type, we’re asked to implement a function sumT to add all values present in any given Tree.

  data Tree = Leaf Int | Node Tree Int Tree
  sumT :: Tree -> Int
  sumT (Leaf v)     = v
  sumT (Node l v r) = sumT l + v + sumT r

  This function can be translated into CPS with little effort

  sumTCPS :: Tree -> (Int -> r) -> r
  sumTCPS (Leaf v)     k = k v
  sumTCPS (Node l v r) k = sumTCPS l $ \sl ->
                           sumTCPS r $ \sr ->
                           k (sl + v + sr)

  Now suppose there’s a new (absurd ;-)) requirement that if any Node or Leaf holds the value 13, you don’t care about the actual sum, and must return 42 instead.

  Solving that with the pure recursive function implies two traversals (first to check, then sum), fusing two traversals in one (check while summing), or rewrite to an iterative traversal. They will work, but they’ll be doing more work than needed, as well as harder to understand, optimize, and even justify during code review.

  However, thanks to CPS we can write

  sumTCPS' :: Tree -> (Int -> r) -> r
  sumTCPS' t k0 = go t k0
    where
      go (Leaf 13)     _  = k0 42
      go (Leaf v)      k1 = k1 v
      go (Node l 13 r) _  = k0 42
      go (Node l v r)  k1 =
         go l $ \sl ->
         go r $ \sr ->
         k1 (sl + v + sr)

The outer continuation (k0) expects the «final» result, while the inner continuation (k1) expects the current «local» result. If this looks suspiciously like return in any programming language other that Haskell, it’s because, well, it is…

• As a compact way to express backtracking.

  There are many computation problems complex enough that the only currently known effective way to solve them is by traversing a possibly (very) large search space. There are also less complex problems that are easier to express and understand when written in a backtracking fashion.

  In these algorithms the code «guesses» the best branch to follow, remembers said choice, and carry on computing. If it hits a wall that forces to retreat to this choice point, it takes a different guess and proceeds. This process repeats until a solution is found or all possible guesses have been covered without finding one.

  Prolog was designed with that idea in mind. You can express Prolog’s flow control strategy using continuations.

  (I’m still looking for a simple yet meaningful example of backtracking to place here – n-Queens is too much, regex matching is too*o much)

The Haskell road to continuations

Math ensues

We’ve seen that CPS takes functions with types

a -> b

and turns them into functions with types

a -> (b -> r) -> r

This follows from the fact (Theorem) that types

b

and

(b -> r) -> r

are isomorphic ², thus they can be interchanged. You can continue to the next subsection if you’re not interested in the why, and won’t miss a thing.

Good for you. You’ll see it is indeed true (Proof) if you consider functions

regularToCPS :: b -> ((b -> r) -> r)
regularToCPS = flip ($)

a compact, idiomatic way of saying

regularToCPS = \b -> (\f -> f b)

that takes any b into ((b -> r) -> r); and then consider function

cpsToRegular :: ((b -> r) -> r) -> b
cpsToRegular = ($ id)

a compact, idiomatic way of saying

cpsToRegular = \k -> k id

and finalize realize that

cpsToRegular . regularToCPS :: b -> b

which is id for single values of type b, and

regularToCPS . cpsToRegular :: ((b -> b) -> t) -> ((t -> r) -> r)

which is id for continuations, in the sense that the first continuation doesn’t change the input value. ∎

What type of sorcery is this?

Alas, we have this interesting type ((a -> r) -> r) and we’ll make the most out of it, by wrapping it with a newtype and studying its associated abstract behaviors

newtype Cont r a = Cont { runCont :: ((a -> r) -> r) }

Since a continuation is just a function computing the actual result, we can fiddle with the intermediate result to said function before feeding it to the continuation. This means Cont r is a Functor

instance Functor (Cont r) where
  fmap f m = Cont $ \k -> runCont m (k . f)

We just transform the input value a with f before feeding it to the original continuation k that expects a value of type b. Note that f is a «regular» function, so this allows using primitives or any non-continuation based function within a flow of continuation based control.

Now, realizing that a continuation just needs a value to «continue computing», and that we can have functions that produce continuations and functions that produce values to be consumed by said functions, we can see that Cont r is an Applicative

instance Applicative (Cont r) where
  pure x  = Cont $ \k -> k x
  f <*> v = Cont $ \kf -> runCont f $ \kv -> runCont v (kf . kv)

Let’s kick «functions than produce continuations» up a notch. Suppose we have a plain continuation ((a -> r) -> r) and a function that given an a is able to produce a continuation on a different type b, i.e. (a -> ((b -> r) -> r). Turns out we can «chain» them up thanks to

chainCPS :: ((a -> r) -> r)
         -> (a -> ((b -> r) -> r))
         -> ((b -> r) -> r)
chainCPS s f = s . flip f

and this suggests Cont r is a Monad because

    ((a -> r) -> r)      ≡  Cont r a
    (a -> (b -> r) -> r) ≡  a -> Cont r b
    ((b -> r) -> r)      ≡  Cont r b

which makes

    chainCPS :: Cont r a
             -> (a -> Cont r b)
             -> Cont r b

look eerily similar to the monadic >>=. So we write

instance Monad (Cont r) where
  return  = pure
  m >>= f = Cont $ \k -> runCont m (\a -> runCont (f a) k)

The f a part matches the flip f fragment above, and the explicit chaining matches the composition. The newtype wrapper forces us to write it this way, that’s all.

Can I have a continuation?

At this point we can write continuations by hand, we can compose continuations, and we can meddle with the values being computed within a continuation flow. This means we can convert regular function composition and monadic sequencing into continuation sequencing.

The last thing we need to have First Class ³ continuations is a way to capture any given continuation within a control flow and pass it as an argument to another continuation. That is, at any given point during execution we should be able to save the «current values» and «next step», and feed that to an alternate continuation for it to use or ignore.

In a purely functional language like Haskell, every function already has every «interesting value» it needs to compute. They are closures: bodies of pure functional code with accompanying relevant variables. This means that we only need to capture the «immediate continuation».

callCC f = Cont $ \k -> runCont (f (\a -> Cont $ \_ -> k a)) k

The name callCC stands for «call with current continuation» ⁴, meaning call function f passing as argument the current continuation. Let that marinate for a while…

Indeed, you’ll write something like

    ... code in the Cont monad
    result <- callCC $ \k -> ...
      -- code on the right block
      -- code on the right calls other functions
      -- more code on the right block
    ... right here

callCC will call the block on the right side making k equal to the continuation that is expecting result to work with. Within the right side:

• You can ignore k, do whatever and return a value. The value will be bound to result and code will continue «right there». That’s just the normal, unsurprising, flow of things.

• You can actually use k v to escape early returning v The value will be bound to result and code will continue «right there». That’s convenient custom local flow control.

• You can pass k down as many times as you want, to as many auxiliary functions as you need, that can in turn do whatever they see fit, in particular using k. No matter how deeply nested the calls are, the first use of k v will come back to bind v to result, and code will continue «right there». That’s custom non-local flow control.

But wait, there’s more!

Every Monad can be modified to become a Monad Transformer and Cont r is not the exception. Its transformer is called, unsurprisingly, ContT r. This means we can add custom flow control to any given Monad stack provided you do it Carefully®:

• Use callCC directly to capture continuations

• Use >>= and >> implicitly to sequence continuations

• Use lift to have access to computations in the underlying Monad.

I mention this because the simplest examples of custom control flow require some evidence of «weirdness» happening, and for that I’m going to use functions running on ContT r IO.

Loop control

Functional languages don’t have while loops as a consequence of not supporting mutable state, the fact that recursion is equivalent to while loops, and the ability to separate recursion schemes from operations (hard to achieve using while loops), in a clean fashion.

So, this explanation is not meant to advocate the use of loops in functional environments. Instead, look at it as showing that having continuations affords a way to build your own while loops even if the underlying language does not provide it. Doing this other than for learning purposes is something that would make a competent functional programming look incompetent.

A generic loop over a collection can be thought of as orderly applying a function f to each element of the collection, and said f returning the continuation after the current element has been processed. Recall that if we have two continuations c0 and c1 in any monadic context, c0 >> c1 is just «do c0, then c1» or the semicolon (or lack thereof) in imperative languages. This means we can implement the «imperative style» foreach that one has in Perl (or for in Python) with

foreach :: Monad m => [a] -> (a -> ContT () m c) -> m ()
foreach items f = runContT (mapM_ f items) return

Note the use of a generic underlying monad m, so I can loop over a collection to perform any arbitrarily complex computation as provided by m.

At each step, the function f must return the next step in the form of a continuation. Since f works in the ContT () monad, it doesn’t need to do anything special to «continue to the next», because that’s what ContT does. However, we need some way for f to return an explicit computation to abort the rest of the loop.

breakOut :: Monad m => ContT () m c
breakOut = ContT $ \_ -> return ()

So breakOut returns a continuation that ignores the default continuation and just terminates. This allows us writing

infLoop0 = foreach [1..] $ \i -> do
  if i > 10
    then breakOut
    else lift $ print i

that looks like an infinite loop on account of the lazy infinite list, but when evaluated.

ghci> infLoop0
1
2
3
4
5
6
7
8
9
10
it :: ()

behaves as a while loop exited via a break.

Implementing continue to «skip» to the next step of the loop is actually quite boring. If you want a continuation to «finish» and proceed to the next continuation, just

continue :: Monad m => ContT () m ()
continue = return ()

Make sure you understand this return is in the immediate context, while the return in breakOut is delayed as part of the continuation being produced.

Now, having breakOut and continue, we can write «loops» like

infLoop1 = foreach [1..] $ \i -> do
  if i > 10
    then breakOut
    else if i `mod` 2 == 0                                        
      then continue
      else lift $ print i

that, when evaluated

ghci> infLoop1
1
3
5
7
9
it :: ()

behaves exactly as you would expect.

You don’t need while loops on a functional programming language, yet you can build your own while loops using continuations. If only, to show that while is a way to have regular programmers not have to think about continuations.

Modern imperative languages have «labeled break/continue» statements, where nested loops can be labeled, and you can break from or continue to the next specific label. That requires the notion of a syntactic label like those found in C and Perl.

Labeling statements

In our discussion about loops, we realized that «sequencing» is just having a continuation follow one after the other thanks to >> and that shouldn’t be a surprise. We also realized that «breaking» is just forcing a final continuation that does nothing.

We can have a continuation continuationProducer that returns a continuation and continues on, pun intended. This would allow us to write something like

   aContinuation <- continuationProducer ...
   ... keep going ...

where aContinuation will refer to some continuation created by continuationProducer. Program flow would continue normally, possibly using aContinuation.

Here’s the plot twist. Imagine aContinuation is built in such a way that when used (continued into) it computes at the point it was created, and keeps re-creating itself.

label :: ContT r m (ContT r m b)
label = callCC $ \next -> let here = next here
                          in  return here

The type of label confirms it is a continuation that returns a continuation. As a continuation it can be sequenced, and it has the notion of current continuation to use as «next step».

Recall that callCC passes the current continuation to the function, in this case bound to next, i.e. next is a continuation. Thanks to Haskell’s laziness, we can build here as an infinite continuation that returns itself within itself every time it is used. Since label just returns here, it means it moves on to the next instruction in the sequence, but in so doing it returns the lazy value

    next (next (next (...)))

where next happens to be, well, the next instruction. This means we can use label to «save» the current continuation in the form of a continuation that we can ask to continue to, and at each step it will return itself, ad nauseam.

And this is all we need to have «backward labeled jumps», kind of a goto-light. This allows us to write ugly basic style loops, pun intended.

basicLoop :: IO ()
basicLoop = flip runContT return $ do
  goto10 <- label
  lift $ print "one"
  goto20 <- label
  lift $ print "two"
  (num :: Int) <- lift $ randomRIO (0,2)
  callCC $ \end ->
    case num of
      0 -> goto10
      1 -> goto20
      2 -> do lift $ print "this"
              end ()
  lift $ print "done"

Every use of label produces a unique continuation returning itself infinitely many times. So goto10 is a continuation that returns its next instruction infinitely many times, and goto20 is a continuation that returns its next instruction infinitely many times.

Throw a dice between 0 and 2, and use different continuations depending on its result. Using goto10 has the effect of following that continuation, going back to the appropriate place in the program, and its thunk being updated to itself, on account of its self-referencing construction. That is, using goto10 jumps to where it was created, and uses the nested continuation. That’s why I named them «goto».

Running the function will produce output showing the «jumping back» behavior, and the fact that both labels are used more than once, and intermixed. For instance,

*Main> basicLoop 
"one"
"two"
"two"
"one"
"two"
"one"
"two"
"two"
"two"
"this"
"done"
it :: ()

Yes, I know end does nothing special. It’s there to reinforce the point of where callCC is going to continue.

This way of using continuations to return continuations is a consequence of Haskell treating continuations as First Class. Being able to construct lazy self-referencing values (continuations or not) is unique to Haskell, arguably one of the reasons of its power.

Arbitrary jumping leads to coroutines

Being First Class values, the next step is to capture continuations using callCC, store them in some data structure for «further reference», eventually fetching and continuing onto them as program flow progresses.

A very basic yet flexible approach is to have a queue (FIFO) where «pending» continuations are enqueued at one end, and dequeued at the other. In order to achieve this in the simplest possible way – while performing other computations at the same time – consider the following Monad stack

newtype CoRoT r m a = CoRoT { runCoRoT' :: ContT r (StateT [CoRoT r m ()] m) a }
    deriving (Functor,Applicative,Monad,MonadCont,MonadIO)

The CoRoT stack has continuations (ContT r) on top, followed by a state transformer (StateT) holding a list of continuations as modifiable state. This list will be used as a reasonable start point for «effects» (note the unit type for the results) to keep it simple. Finally, you can use this stack on top of any Monad m you like – this example uses IO.

A couple of auxiliary functions allow the executing continuation currently «on top» to, either get the list of currently stored continuations

getCCs :: Monad m => CoRoT r m [CoRoT r m ()]
getCCs = CoRoT $ lift get

or replace the list of currently stored continuations with a new one.

putCCs :: Monad m => [CoRoT r m ()] -> CoRoT r m ()
putCCs = CoRoT . lift . put

Note the need to lift operations from the StateT to the ContT on top.

Combining both primitives, it will be possible for the currently executing continuation to add a new continuation to the end of the queue. ⁵

queue :: Monad m => CoRoT r m () -> CoRoT r m ()
queue p = do
  ccs <- getCCs
  putCCs $ ccs ++ [p]

If we think of this list as the list of «ready to go, but paused» continuations, it follows we can implement a trivial, yet useful, round-robin scheduler:

schedule :: Monad m => CoRoT r m ()
schedule = do
  ready <- getCCs
  case ready of
    []     -> return ()
    (p:ps) -> putCCs ps >> p

The currently executing continuation looks at the «ready queue». When there’s at least one ready continuation p, it’s taken out of the queue, the queue replaced with whatever is left, and computation continues onto p.

There are two ways in which schedule is useful:

1. When the currently executing continuation wants to relinquish control, giving it to the next «ready» continuation (if any). This is customarily known as yield ⁶. Using callCC captures the current continuation k, so it can be enqueued, and then let schedule choose the continuing continuation (pun intended).

   yield :: Monad m => CoRoT r m ()
   yield = callCC $ \k -> queue (k ()) >> schedule

2. When the currently executing continuation wants to create and start a new continuation. This is customarily known as fork. Using callCC captures the current continuation k, so it can be enqueued before continuing to the new continuation p. Note the need to add a «fail-safe» continuation to schedule just in case p does nothing or terminates before yield-ing. Concis hard!urrency.

   fork :: Monad m => CoRoT r m () -> CoRoT r m ()
   fork p = callCC $ \k -> queue (k ()) >> p >> schedule

We have enough primitives for any continuation to spawn new continuations, and for any continuation to yield control in a voluntary fashion. There are two edge cases we need to cover before having fully functional cooperative concurrency.

The first issue is finishing cleanly when there are no pending continuations. Recall that the pending continuations have type CoRoT r m () so, «finish cleanly» just means producing a unit value.

A new action finished will signal termination when invoked by any executing continuation. If there’s at least one continuation in the «ready» queue, a yield is forced, continuing to finished just in case the next continuation has nothing to do as well. This tail recursive forcing of yield ensures that no pending continuation will be left behind. When there are no more ready continuations in the queue, finished will produce unit so computation finishes altogether.

finished :: Monad m => CoRoT r m ()
finished = do
  remaining <- null <$> getCCs
  if not remaining
    then yield >> finished
    else return ()

The second issue is how to actually start computing. That is, how to run the «main» continuation such that it can fork other continuations at will, let them yield control or fork until finishing, and ensure a clean finish once all are done.

As usual with stack transformers, we have to unravel them from the bottom up. We don’t care what the underlying monad m is ⁷ so, from the bottom up:

• Evaluate the StateT with an initial empty list for the «ready queue». This will take care of feeding the final unit value to the underlying monad.

• Unwrap (runCoRot') and run (runContT) the supplied initial continuation, making sure to use plain return as termination step. This will take care of actually allowing all of the utility functions (fork, yield, etc.) to be used to build the arbitrary control flow our code follows.

• Tack a mandatory finished as the final step of our computations, just in case the initial computation does nothing at all or finishes before other active continuations forked directly or indirectly. Edge case is edgy.

runCoRoT :: Monad m => CoRoT r m r -> m r
runCoRoT = flip evalStateT []
         . flip runContT return
         . runCoRoT'
         . (<* finished)

All this machinery allows us to express Cooperative Coroutines, hence the name CoRoT.

In order to show the interleaving of effects, the following polymorphic function provides a simple yet powerful foundation.

printOne :: (MonadIO m, Enum a, Show a) => a -> CoRoT () m ()
printOne n = do
  liftIO $ print n
  yield
  liftIO $ print $ succ n
  yield

For a given value n, print it and yield control mid computation. Once control is gained back, print n’s succesor, and yield control again. Once control is gained back yet again, it has nothing else to do, so our finished cleanup will take care of actually terminating computation. I’ve chosen to make the function polymorphic on the restriction that n’s type be an Enum, so it can be used with Bool, Int, and Char.

Now, our example program is nothing more than a «main» continuation that forks a couple of coroutines, each one using printOne more than once over different initial values and a different number of times, so we can verify the interleaving of computation, and the correctness of our cleanup strategy.

start :: IO ()
start = runCoRoT $ do
  fork $ replicateM_ 3 (printOne (3 :: Int))
  fork $ replicateM_ 4 (printOne 'a')
  replicateM_ 2 (printOne False)

Evaluating this results in

*Main> start
3
'a'
4
False
'b'
3
True
'a'
4
False
'b'
3
True
'a'
4
'b'
'a'
'b'
it :: ()

Interleaving is completely deterministic:

• The first thing start does is fork. This creates and passes control to the number printing coroutine.

• The number printing coroutine prints 3 and immediately yields. At that point, only start is ready, so it runs and fork. This creates and passes control to the letter printing coroutine.

• The letter printing coroutine prints a and immediately yields. At that point, the number printing coroutine is ready.

• The number printing coroutine prints 4 and immediately yields. At that point, start is ready.

• Control in start moves on to printing False and yielding. At that point, the letter printing coroutine is ready.

• The letter printing coroutine prints b and immediately yields. At that point, the number printing coroutine is ready.

• The number printing coroutine is at the last statement of printOne where there’s nothing to do, but within a replicateM_. Therefore, it evaluates a new printOne within the same continuation, that just prints 3 and yields.

And so on and so forth…

You’ll notice that once the start continuation has printed True and False twice, it reaches its end. This is when the force finished within runCoRoT' will take care of passing control to the next ready continuation. It happens to be the letter printing one, that will print a and yield to the number printing continuation.

The number printing continuation will be in the last print of its second repetition, so it will print 4 and yield, but having nothing else to compute. Control will pass to the letter printing continuation.

The letter printing continuation will print b and yield. But the number printing continuation has nothing else to do. Here’s when the tail-recursive finished within finished will take care of termination, and yield to the letter printing coroutine.

These primitives have allowed us to build full cooperative coroutines. Note that control can be transferred at any point in the execution flow, and once a continuation is paused, it will return to the exact point it yielded.

There aren’t many traditional languages supporting this flow control, because saving call-stacks and captured mutable state is hard and expensive. But on a pure functional language with continuations, it’s very straightforward to implement. And we did not need special runtime support to build a fully functional multiprogramming environment with flexibility beyond simple threads [8].

There are languages were you can transfer control to an explicitly named co-routine, i.e. yieldTo with a specific name. This can be accomplished by having an extended data structure that include names for each co-routine, as well as having fork «name» them on creation. This is left as an exercise to the reader.

Speaking of exercises, you can try solving (literate Haskell source here) to test your understanding.

But I don’t (like/understand) Haskell

I pity the fool.

Followup articles will show you how to do this in Racket and Perl, the former being the best modern true-LISP, and the latter still being the truest modern imperative LISP-y language.

END]]