Continuation Passing Style

The functions you have been writing until now have been in a form known as direct style. The functions take an argument, and then return a result to the calling expression.

Consider this simple example:

dec a = a - 1
double a = a * 2
inc a = a + 1
report a = a

We can run it like this:

Main> double (dec 3)
4

How does this happen? The first thing to execute is the call to dec. Function dec consumes the 3, and when it finishes, returns its result to the surrounding expression. The result is the expression double 2.

Let’s consider the role of double in this expression. It is waiting to receive the result of the dec 3 computation. We can represent this by writing “double \(\bullet\)”. This is an expression with a “hole” where the \(\bullet\) is. When dec returns, that hole is filled with the result, and the expression continues. We can call double the continuation of dec 3.

Consider another example:

Main> dec (double (inc 20))
41

The first function called is inc. When it finishes, it will return its result to the surrounding expression, which we represent as dec (double \(\bullet\) ) — its continuation. Function double consumes the result and returns 42 to its own continuation dec $\bullet$.

One way to think of a continuation is that it’s a way of identifying the rest of the program.

You will notice that the expressions we called continuations were like normal expressions, but each had a hole which we could fill with a value later. We have seen this before! Functions do the same thing: they are expressions with a hole (a named one, called a parameter) that we fill in later when we call the function.

The similarity is good enough that we can use functions to implement continuations. Consider the following program. Each of these functions takes an additional argument k as a continuation, and the continuation represents “what comes next” in the program.

cdec a k = k (a - 1)
cdouble a k = k (a * 2)
cinc a k = k (a + 1)
report a = a

Let’s try this out:

Main> cdec 3 report
2

Here, cdec took an argument 3 and a continuation report. When it had finished performing its computation with 3, it passed the result to report rather than returning the result to the calling expression. This is one of the properties of functions written in CPS: they do not return Truth in advertising: in Haskell, the report function actually does return the final result. But you will notice that it is a tail call, so the computation is over by the time that happens. In a language that supports real continuations, a “final” continuation such as report would not return at all. . Instead, they call their continuation directly.

Another way to look at this is to say that a continuation is a generalization of a return keyword. We can override what return does. Instead of returning to the expression which called it, a function can pass its result to an arbitrary location. (Imagine what our code would look like if we used the name return (which is not a keyword in Haskell) instead of k.)

We can rewrite the double (dec 3) example in CPS like this:

Main> cdec 3 (\v -> cdouble v report)
4

Here, cdec took 3 as an argument and (\r -> cdouble r report) as a continuation. When cdec finished, it passed its result to the continuation instead of returning it. The resulting expression was cdouble 2 report. Next, double consumed the 2 and passed its result to the continuation report.

Our second example looks like this:

Main> cinc 20 (\v1 -> cdouble r1 (\v2 -> dec v2 report))
41

It is only slightly more involved than the first example.

Note that we can rewrite the example this way:

Main> cinc 20 (\v1 ->
  cdouble v1 (\v2 ->
  cdec v2 report))
41

You can pretend this is an imperative language. The first line “assigns” 20 to v1. The second line “assigns” cdouble v1 to v2. The third line “decrements” v2 and reports it.

Let’s look at a more complicated example.

cinc a k = k (a+1)
cdec a k = k (a-1)
cadd a b k = k (a+b)
report a = a

Suppose you wanted to evaluate the expression add (inc 4) (dec 5). How would you do it using the continuation passing style versions above?

Pretending for a moment that Haskell isn’t lazy, the first thing to execute is inc 4, so we would need call cinc first and save its result in the continuation. Next, we would want to call cdec, and again save its result. Finally, with the two saved results, we can call cadd, and pass the final answer to report. Here is what it looks like:

Main> cinc 4 (\a ->
  cdec 5 (\b ->
  cadd a b report))
9

Please make sure you understand how that code works. Notice that the first continuation encloses the second one and that the inner continuation (the \b -> ... one) has access to the scope of the outer one.

But now consider this code:

Main> cdec 5 (\b ->
      cinc 4 (\a ->
      cadd a b report))
9

It is different from the previous example in only one way: the order of operations has changed. In the direct style example, the compiler has the option (in some languages, such as C) of evaluating dec and inc in any order. But, if we use CPS, then there is only one order of operation for the expression. What CPS has done for us is it has exposed the program’s flow of control, and allowed us to constrain it.

In review, this is what we have so far:

• A function written in CPS doesn’t return. Instead it passes its result to another function.
• A continuation represents “the rest of the computation”.
• The order of operations in CPS code is explicit and constrained.
• Calls to continuations are always tail-calls.

Another style of recursion avoids the use of the stack by accumulating the value in a separate parameter. The amlutlist function below is an example:

amlutlist []      acc = acc
amlutlist (x::xs) acc = amultlist xs (x * acc)

If we were to run it with the input [2, 3, 4] and 1 we would get

1: amultlist [2, 3, 4] 1
2: amultlist [3, 4] (* 2 1)
3: amultlist [3, 4] 2
4: amultlist [4] (* 3 2)
5: amultlist [4] 6
6: amultlist [] (* 4 6)
7: amultlist [] 24
8: 24

Notice this time that we only need to keep track of a single call to multlist at any one time… the result of one call is simply the value of the next call. We discussed this in the chapter on tail-recursion. Tail recursive functions allow the compiler to eliminate the call-stack, speeding things up and reducing the amount of memory we need on the stack.

Notice the flow of the computations. In the simple recursion example the function first descended to the end of the list and then performed the computations as the recursive calls returned. It the tail recursive example the computations occur first, and then the function passes the result to the recursive call.

Integers and lists are not the only things a function can accumulate. We can also accumulate computations. Consider kmultlist, which is the same as amultlist but it is in CPS.

kmultlist []     k = k 1
kmultlist (x:xs) k = kmultlist xs (\v -> k (x * v))

As before, we have an extra argument k to specify where the result should go. If we call kmultlist on the empty list, it will pass 1 to k.

The recursive case is more complex. Suppose we call kmultlist on a non-empty list x:xs. In order to compute the result, kmultlist needs to make a recursive call on xs.

This function needs a continuation to tell it what to do with that result. This continuation captures the result of the recursive call, multiplies it by x, and then passes that to the continuation given to the initial call.

You should notice a correspondence between the continuation and the original direct-style version:

multlist (x:xs) = x * multlist xs

The v parameter is equivalent to multlist xs, and the call to k represents returning the value to the caller.

Here is a sample run.

 9: kmultlist [2,3,4] report
10: kmultlist [3,4] (\v1 -> report (2 * v1))
11: kmultlist [4] (\v2 -> (\v1 -> report (2 * v1)) (3 * v2))
12: kmultlist [] (\v3 -> (\v2 -> (\v1 -> report (2 * v1)) (3 * v2)) (4 * v3))
13: (\v3 -> (\v2 -> (\v1 -> report (2 * v1)) (3 * v2)) (4 * v3)) 1
14: (\v2 -> (\v1 -> report (2 * v1)) (3 * v2)) (4 * 1))
15: (\v1 -> report (2 * v1)) (3 * 4))
16: report (2 * 12)
17: report 24

Each recursive call builds a new, larger continuation out of the one it received.