Continuation Passing Style
You're having a conversation with your buddy, who is a carpenter. (Yes, this story will have a point.) Your buddy has a beautiful piece of mahogany wood in his shed, and your plan today is to talk him into giving it to you so you can craft a table from it. In functional terms, we have
buddy :: Conversation -> Material
buddy conv | isConvincing conv = mahoganyWood
| otherwise = gnarlyBranch
Your buddy is a function that turns a conversation into a piece of mahogany wood or into a gnarly branch he found in his backyard, depending on your coercive skills to talk him out of that piece of mahoganyWood.
Actually, your buddy is a good guy who likes you and will only make you sweat for a while. In the end, he's going to give you the piece of mahogany wood no matter how ingenious your arguments that given you that piece of wood will make him happier:
buddy :: Conversation -> Material
buddy _ = mahoganyWood
Even better, your buddy is a really good friend. Given his training as a carpenter, he knows that he will do a much better job at whatever you want to do with this piece of wood than you would ever be able to do with your two left hands. So he tells you that he's not going to give you that piece of wood; he wants to know what you want to do with the wood, and he does it for you:
buddy :: Conversation -> (Material -> Product) -> Product
buddy _ theThingToMake = theThingToMake mahoganyWood
Given your description of theThingToMake from the piece of mahogany wood, a
function of type Material -> Product, your buddy applies this function (rather
expertly) to the piece of mahogany wood and gives you the beautiful table you
wanted.
Ignoring the difference in carpentry skills between you and your buddy, the result is the same whether you provide your buddy with the procedure to turn the piece of wood into a table, your buddy applies this procedure to the piece of wood, and then gives you the table, or whether he gives you the piece of wood, and you apply the procedure to it yourself.
This is the essence of continuation passing style (CPS). A "normal" function
returns some value of type a:
val :: a
In our first example above, buddy conv returned a value of type Material,
the piece of wood. A function written in CPS does not return this value of type
a directly. Instead, it wants to know what you want to do with this value and
does it for you. The argument to such a function is a continuation of type
a -> r that turns the value into a result of type r, and the function
returns the result, of type r, that is obtained by applying this continuation
to the value a.
Instead of
buddy :: Conversation -> Material
we have
buddy :: Conversation -> ((Material -> Product) -> Product)
More abstractly, instead of
f :: b -> a
we have
f :: b -> (forall r. (a -> r) -> r)
In the former case, f b returns a result of type a. In the latter case, it
returns a result of type (forall r. (a -> r) -> r).
The forall r here is important, and it is allowed only after we turn on a
language extension:
>>> :set -XRankNTypes
forall r here says that we can turn a value of type a into a value of any
type r, as long as we have a function of type a -> r.
It turns out that we can prove that values of type a are the "same thing" as
values of type ((a -> r) -> r). Intuitively, this should make sense. Any value
in our program is useful to us only if we do something with it. If we transform
such a value x :: a using some function f :: a -> r, it makes no difference
whether we apply f to x or whether we provide f to whichever function
produced x, and we let that function apply f to x and then return the
result of that application to us.
Formally, we say that the types a and (forall r. (a -> r) -> r) are
isomorphic. This means that there exist mappings between values of these types
that are inverses of each other. The round trip gives us the original value
back. Here are these two mappings for the types a and
(forall r. (a -> r) -> r).
toCPS :: a -> (forall r. (a -> r) -> r)
toCPS x = ($ x)
fromCPS :: (forall r. (a -> r) -> r) -> a
fromCPS x = x id
If you read the type signature of toCPS, it says that if we have a value of
type a, we can turn this into a function which is able to produce a value of
any type r, as long as you give it a function of type a -> r. The function
that toCPS x produces is simply the function that applies its argument, a
function, to x.
The type signature of fromCPS says that we can take any function that can turn
a function of type a -> r into a value of type r and turn such a function
into a value of type a. Indeed, we simply call our function
x :: (a -> r) -> r with argument id. In this case, we have r = a, so
x id must surely produce a value of type a.
We can try this out in GHCi:
>>> :{
| toCPS :: a -> (forall r. (a -> r) -> r)
| toCPS x = ($ x)
| fromCPS :: (forall r. (a -> r) -> r) -> a
| fromCPS x = x id
| :}
>>> fromCPS $ toCPS 5
5
>>> fromCPS $ toCPS "Hello world!"
"Hello world!"
Let's figure out why the roundtrip is the identity function:
fromCPS $ toCPS x = fromCPS ($ x) -- Definition of toCPS
= ($ x) id -- Definition of fromCPS
= id x -- Definition of ($)
= x -- Definition of id
So we can use functions of type ((a -> r) -> r) to represent values of type
a.
Let's play with this idea using a really simple example, and then we return to what we really want to do: implement exception handling and coroutines.
First, let's implement a function to compute \(n!\). I know, can't we come up with a more interesting example already? It's a good example to illustrate what we want to do though. The "normal" way to do this is this:
fac :: Integer -> Integer
fac 0 = 1
fac n = n * fac (n - 1)
Never mind that this is not tail-recursive.
If we were consistent in using CPS, then we should convert all plain values of
some type a in our program into functions of type forall r. (a -> r) -> r,
but programming in CPS is not exactly natural. So we will do it only for values
where we really need this strange encoding. In our implementation of fac, we
don't "need" CPS anywhere, but let's pretend that we do care about using CPS for
the return value, but not for the argument. Thus, we want a function
facCPS :: Integer -> (forall r. (Integer -> r) -> r)
If n = 0, then fac n = 1. facCPS does not return 1 directly. Instead it
takes a continuation cont of type Integer -> r as argument and applies it to
1 for us:
facCPS 0 cont = cont 1
The implementation of facCPS n for n > 0 is more interesting. We could try
facCPS n cont = cont (n * fac (n - 1))
but this uses our "normal" function fac, which we want to replace with
facCPS everywhere in our program. Instead of \((n - 1)!\), facCPS (n - 1)
returns a function that allows us to apply some continuation of type
Integer -> r to \((n - 1)!\). What exactly do we want to do with \((n - 1)!\)
here? The goal of facCPS n is to apply cont to \(n!\). Thus, we need to
multiply \((n - 1)!\) with \(n\) and then apply cont to it. That's what the
continuation we pass to facCPS (n - 1) should do:
facCPS n cont = facCPS (n - 1) $ \f -> cont (n * f)
The whole implementation is
facCPS :: Integer -> (forall r. (Integer -> r) -> r)
facCPS 0 cont = cont 1
facCPS n cont = facCPS (n - 1) $ \f -> cont (n * f)
Have a closer look at what we did here. In our implementation of fac, we
multiplied the return value of fac (n - 1) with n. Here, we passed an
anonymous function to facCPS (n - 1), and facCPS (n - 1) calls this function
with \((n - 1)!\) as its argument. In other words, the argument f of the
function we pass to facCPS (n - 1) is exactly the same sa the return value of
fac (n - 1). Within the function we pass to facCPS (n - 1), we do the same
as before: we multiply \((n - 1)!\) with \(n\). Only now we don't want to return the
result but invoke the continuation cont on this value. So that's what our
anonymous function does: f -> cont (n * f).
Let's try it out:
>>> :{
| fac :: Integer -> Integer
| fac 0 = 1
| fac n = n * fac (n - 1)
| :}
>>> :{
| facCPS :: Integer -> (forall r. (Integer -> r) -> r)
| facCPS 0 cont = cont 1
| facCPS n cont = facCPS (n - 1) $ \f -> cont (n * f)
| :}
>>> fac 10
3628800
>>> facCPS 10 id
3628800
What if we want to calulate \((n!)!\)? Using fac, this would be
>>> fac (fac 4)
620448401733239439360000
Let's build the facCPS version up in steps. We want to call facCPS n.
Whatever value this produces, we want to compute the factorial of:
>>> facCPS 4 $ \f4 -> fac f4
620448401733239439360000
We observed above that fac n and facCPS n id compute the same thing. Thus,
to obtain a version of this expression that uses only facCPS, we need to
replace the call of fac f4 with a call to facCPS f4 id:
>>> facCPS 4 $ \f4 -> facCPS f4 id
620448401733239439360000
This example is important for the following reason: In the expression
fac (fac 4), the inner fac gets applied to 4, and then the outer fac
gets applied to the result of fac 4. When using CPS, this is reversed. The
outer facCPS produces the value \(4!\) and passes it to the anonymous function
as its argument f4. The inner facCPS inside this function gets applied to
f4. Since we pass the identity function id to facCPS f4, we obtain the
value of f4!, that is, the value of \((4!)!\).
Note the game we are playing. In the continuation that we're passing to
facCPS, the function parameter captures the value that the non-CPS version
fac would have returned. This always works! Let's look at one last example,
and then we get back to more meaningful uses of continuations.
Let's say we want to compute \(3! + 4! + 5!\):
>>> fac 3 + fac 4 + fac 5
150
What does this look like in CPS? First, we call facCPS 3 and provide to it a
function that captures \(3!\) as its argument f3:
>>> facCPS 3 (\f3 -> ...)
Remember, this function \f3 -> ... that we pass to facCPS 3 is a
continuation. It's what we should do after facCPS 3 computes \(3!\). What is
the next thing we should do? We should compute \(4!\). We do this by calling
facCPS 4 with a continuation that captures the result in its argument f4:
>>> facCPS 3 (\f3 -> facCPS 4 (\f4 -> ...))
Now we still have to call facCPS 5 to compute \(5!\). The continuation we pass
to facCPS 5 captures this value in its argument f5:
>>> facCPS 3 (\f3 -> facCPS 4 (\f4 -> facCPS 5 (\f5 -> ...)))
This last continuation that we pass to facCPS 5 should return the final result
of our computation. That's not a problem now because, being nested inside the
continuations that we passed to facCPS 3 and facCPS 4, it has access to all
three parameters f3, f4, and f5. The result we want to return is
f3 + f4 + f5:
>>> facCPS 3 (\f3 -> facCPS 4 (\f4 -> facCPS 5 (\f5 -> f3 + f4 + f5)))
150