#### Continuations

A Haskell continuation has the following type:

newtype Cont r a = Cont { runCont :: (a -> r) -> r }A continuation takes a function of type

`(a -> r)`and generates an

`r`, where

`r`can sometimes be a fixed value like

`Int`or

`IO ()`.

For example, I might write a long-running process that spawns an action every time the user enters a line of input:

onInput :: (String -> IO ()) -> IO () -- i.e. Cont (IO ()) String onInput f = forever $ do str <- getLine f strYou will recognize this idiom if you've ever used frameworks with callbacks. We supply the framework with a function (i.e. a continuation) and the framework uses that function to do its job.

#### "Complete me Later"

You generally use continuations when you are programming something, but you want somebody else to complete it. Common reasons include:

- You are programming a framework with callbacks that users supply
- You are defining a custom map engine for game players to program
- You are lazy

unitAttack :: Target -> IO () unitAttack target = do swingAxeBack 60 valid <- isTargetValid target if valid then ??? target else sayUhOhLet's imagine you have to package up and compile this code for somebody else (say, a fellow colleague) to use later, but it won't compile yet because you still have the unspecified

`???`function. What do you do?

Like all good programming, the best solution is the laziest one. We punt and take the incomplete behavior as a parameter so that whoever finishes the function later on can complete the function by passing the specified behavior in:

unitAttack :: Target -> (Target -> IO ()) -> IO () unitAttack target todo = do swingAxeBack 60 valid <- isTargetValid target if valid then todo target else sayUhOhProblem solved! Notice how the right hand side of the type signature resembles the shape of our

`Cont`type. If we just add a newtype, we can wrap it in

`Cont`ourselves:

unitAttack :: Target -> Cont (IO ()) Target unitAttack target = Cont $ \todo -> do swingAxeBack 60 valid <- isTargetValid target if valid then todo target else sayUhOh... or, even better, we can use

`ContT`instead. The benefit of

`ContT`is that it is also a monad transformer, which comes in handy.

`ContT`has the exact same

`Monad`instance as

`Cont`, so they are otherwise interchangeable:

newtype ContT r m a = ContT { runContT :: (a -> m r) -> m r } unitAttack :: Target -> ContT () IO Target unitAttack target = ContT $ \todo -> do swingAxeBack 60 valid <- isTargetValid target if valid then todo target else sayUhOhThis is great because now somebody else can "continue" where we left off (thus the name: continuations). They would just define the missing function:

damageTarget :: Target -> IO ()... and then supply it to our continuation to complete it:

runContT (unitAttack target) damageTarget :: IO ()

#### Variable Arguments

Our strategy works well if we have exactly one hole in our function, but what if we have two holes in our function, each of which takes a different argument?

unitAttack :: Target -> IO () unitAttack target = do ???_1 60 valid <- isTargetValid target if valid then ???_2 target else sayUhOhWell, we might try to accept two continuations:

unitAttack :: Target -> (Int -> IO ()) -> (Target -> IO ()) -> IO () unitAttack target todo1 todo2 = do todo1 60 valid <- isTargetValid target if valid then todo2 target else sayUhOh... but that no longer cleanly fits into our

`Cont`type, which expects exactly one continuation.

Fortunately, there is a clean and general solution. Just define a data type that wraps both possible arguments in a sum type, and just define a single continuation that accepts this sum type:

data Hole = Swing Int | Attack Target unitAttack :: Target -> ContT () IO Hole unitAttack target = ContT $ \k -> do k (Swing 60) valid <- isTargetValid target if valid then k (Attack target) else sayUhOhEach constructor acts as a place-holder that signals to the continuation which hole it is currently filling. Then somebody else can continue where we left off and just write:

damage :: Target -> IO () swingBack :: Int -> IO () continue :: Hole -> IO () continue (Swing n) = swingBack n continue (Attack t) = damage t runContT (unitAttack target) continue :: IO ()This trick generalizes to

`n`holes with variable arguments per hole. Just define a type with

`n`constructors, one for each hole, where each constructor stores whatever arguments that particular continuation will need:

data Hole = Hole1 Arg1 Arg2 | Hole2 | Hole3 Arg3 | Hole4

#### Algebraic Data Types

I want to digress for a moment to talk about algebraic data types. If you are not interested, skip to the next section.

It turns out we can elegantly derive the above trick for multiple holes. Type algebra says that if we squint then we can translate the following type constructors to algebraic operators and derive equivalent types from simple algebraic manipulations:

Either a b <=> a + b (a, b) <=> a * b a -> b <=> b ^ aThat means that if we have a function with two continuations:

(a1 -> r) -> ((a2 -> r) -> r)... we just translate it to the equivalent algebraic expression:

(r ^ (r ^ a2)) ^ (r ^ a1)... and then we can derive equivalent representations just by using the rules of algebra:

(r ^ (r ^ a2)) ^ (r ^ a1) = r ^ ((r ^ a2) * (r ^ a1)) = r ^ (r ^ (a2 + a1))... then if we translate that back to the equivalent type, we get:

(Either a2 a1 -> r) -> r... which is exactly the trick described in the previous section.

Similarly, if we have more than one argument to a continuation:

(a -> b -> r) -> r... we can find an equivalent single-argument form using type algebra:

r ^ ((r ^ a) ^ b) = r ^ (r ^ (a * b))... which transforms back to:

((a, b) -> r) -> rSo type algebra tells us the obvious: uncurry the continuation if it needs a single argument.

#### The Continuation Monad

So far that explains what continuations are useful for, but it does not explain what the continuation

`Monad`is useful for.

I firmly believe that the way to a

`Monad`s heart is through its Kleisli arrows, and if you want to study a

`Monad`s "purpose" or "motivation" you study what its Kleisli arrows do.

So rather than study the

`Monad`instance for

`Cont`, let's instead just study the shape of the

`Cont`Kleisli arrow and infer what it does from its type alone:

a -> Cont r b ~ a -> (b -> r) -> r -- Expand the definition of Cont ~ (b -> r) -> (a -> r) -- Flip the argumentsIn other words, we take a function that handles

`b`s and transform it into a function that handles

`a`s.

This suggests a basic starting intuition for the continuation monad: we transform handlers.

Let's build on that intuition by revisiting our previous example:

unitAttack :: Target -> ContT () IO Target unitAttack target = ContT $ \todo -> do swingBack 60 valid <- isTargetValid target if valid then todo target else sayUhOhWe need to supply a completion function of type:

handler :: Target -> IO ()We

*could*complete this function ... or we could half-ass it and leave our work incomplete:

halfAssedCompletion :: Target -> IO () halfAssedCompletion target = do registerUnitBeingAttacked playDamageSound ??? 40 -- So close...This means we essentially created a new continuation with a slightly smaller hole:

halfAssedCompletion :: Target -> ContT () IO Int halfAssedCompletion target = ContT $ \todo -> do registerUnitBeingAttacked playDamageSound todo 40This is a Kleisli arrow! That means we can compose it with our previous Kleisli arrow:

unitAttack >=> halfAssedCompletion :: Target -> ContT () IO IntThis composition substitutes in

`halfAssedCompletion`for each hole we left in the

`unitAttack`function. However,

`halfAssedCompletion`left smaller

`Int`holes of its own that somebody else now has to finish up.

Notice how now we originally needed a handler of type:

handler :: Target -> IO ()... but now we only need a smaller handler of type:

newHandler :: Int -> IO ()... in other words,

`halfAssedCompletion`acts as an intermediary that transforms handlers of type

`(Int -> IO ())`into handlers of type

`(Target -> IO ())`.

The

`Cont`monad is all about chaining these kinds of partial completions together until all the holes are finally filled. You could use this abstraction to complete a project in stages and seamlessly hand off work from person to person whenever circumstances require a change in maintainer before completing the project. Alternative, you can use this to condense the callback API of a framework into a single point of entry.

#### The Kleisli Category

Earlier I said that the key to a monad is its Kleisli arrows. The reason why is that Kleisli arrows are morphisms in the Kleisli category, where

`(>=>)`is Kleisli arrow composition:

(>=>) :: (Monad m) => (a -> m b) -> (b -> m c) -> (a -> m c) (f >=> g) x = f x >>= g.. and

`return`is the identity:

return :: (Monad m) => a -> m aLike all categories, the Kleisli category must obey the category laws:

return >=> f = f -- Left identity f >=> return = f -- Right identity (f >=> g) >=> h = f >=> (g >=> h) -- AssociativityThings that obey these laws have nice properties. For example, it guarantees that you can reason about each Kleisli arrow in a composition chain in isolation. Each Kleisli arrow's behavior is completely determined by its input (i.e. domain) and output (i.e. codomain). So let's think about how that modularity translates to the

`Cont`Kleisli category.

When you switch maintainers, you don't have to give the next maintainer a bunch of holes sprawled out over a large code base like this:

largeProgram = do ... x <- ???_1 y ... ???_2 horseTheyRodeInOn ... spawn ???_29 fooInstead you can unify all the holes using a single callback that accepts a single type (the "codomain") unifying all the holes you left:

largeProgram :: () -> ContT () IO Hole largeProgram () = ContT $ \k -> do ... x <- k (Hole1 y) ... k Hole2 ... k (Hole29 spawn foo)This give the next person a single point of entry to continue from, because now they only have to write a Kleisli arrow that handles a single

`Hole`input which encompasses all the previous holes:

nextContribution :: Hole -> ContT () IO NextHole nextContribution currHole = ConT $ \nextHole -> case currHole of Hole1 y -> ... -- Fill first hole Hole2 -> ... -- Fill second hole ... Hole29 spawn foo -> ... -- File 29th holeThen you just use Kleisli composition to connect your code contribution:

largeProgram >=> nextContributionThis cleanly modularizes the first person's contribution so that you can hermetically seal it off from subsequent contributions. By repeating this process, each subsequent contribution to the code base becomes its own modular and composable Kleisli arrow, cleanly separated from other contributions:

alice'sWork :: a -> ContT r m b bob'sWork :: b -> ContT r m c carlo'sWork :: c -> ContT r m d engine = alice'sWork >=> bob'sWork >=> carlo'sWork :: a -> ContT r m d customMap :: d -> ContT r m e completeGame = engine >=> customMap :: a -> ContT r m eThis is why frameworks and game custom map makers all use continuations to delimit the interface between the company's code and the user's code. The continuation monad is all about establishing air-tight code boundaries, both internally within a project, and externally for user facing APIs. This lets you isolate responsibilities if you can separate each code contribution into its own Kleisli arrow.

#### Callback Hell

Frameworks are the canonical example of separating responsibilities, where the framework writer provides some code, but the user is expected to fill in the gap with callbacks of their own. This often results in callback hell in frameworks that take this principle to the extreme, like Node.js.

But it doesn't have to be that way. The continuation monad teaches us that we can always condense a sprawling API filled with callbacks into a single callback that takes a single argument. Even better, we get monadic syntactic sugar for composing multiple layers of callbacks.

I'll use the

`GLUT`package as an example, which requires several callbacks like:

type ReshapeCallback = Size -> IO () type VisibilityCallback = Visibility -> IO () type WindowStateCallback = WindowState -> IO () type CloseCallback = IO () -- there are more, but I'll stop hereInstead, we can wrap GLUT's multiple callbacks into a uniform

`ContT`API:

glut :: () -> ContT () IO Hole data Hole = Reshape Size | Visible Visibility | Window WindowState | Close ...Now the end user has a single entry point to the GLUT monad, so they can now complete the framework in a single function:

userCallbacks :: Hole -> ContT () IO a userCallbacks hole = ContT $ \_ -> case hole of Reshape size -> ... -- Handle reshapes Visibility v -> ... -- Handle visibility switches Window ws -> ... -- Handle changes to window state Close -> ... -- Handle window closing ...Moreover, they can now just compose their code with the glut framework:

glut >=> userCallbacks :: () -> ContT () IO a

#### The Buck Stops Here

How do we know when we are done and there are no continuations left? Well, let's see what type the compiler infers if we have no more holes and never use the continuation:

>>> let done = ContT $ \_ -> return () >>> :t done done :: Monad m => ContT () m aIt says the return type is polymorphic, meaning that there is no hole left to fill. The above function just inserts

`return ()`in all holes and calls it a day. We can even prove a chain of continuations is done if its final return value type-checks as

`Void`, the empty type:

absurd :: Void -> a -- from the "void" package run :: (Monad m) => ContT r m Void -> m r run c = runContT c absurd

`run`only accepts completed programs that have no holes left. We can use

`run`for our previous GLUT example, since the final user callback handler leaves no unfinished holes:

run ((glut >=> userCallbacks) ()) :: IO ()

#### Conclusion

I hope this post inspires people to use the continuation monad to structure and modularize code completion boundaries. The continuation monad naturally arises at the boundaries between programmers and cleanly abstracts away callback hell into a simple and uniform interface with a single entry point.