Chapter 3 - Continuing w/ Style

In this chapter, we introduce continuations and writing functions in continuation passing style (CPS). Writing in CPS provide functional programs control flow simillar to that of imperative ones.

1. Continuation Passing Style

In essence, a continuation is a higher-order function that abstracts over an extended context for performing a certain computation. This is much more easily explained in a functional language, since we can treat continuations simply as a special form of accumulator, where the value being “accumulated” is a function. This also has the added benefit of providing control over program evaluation.

a. Callback Everyday – Continuations

As we mentioned, a continuation is a higher-order function, and writing in CPS is synonymous with using a function as an accumulator.

With this in mind, let’s take a few steps back and recall writing in APS. In Chapter 1, we described how to convert a generally recursive definition into one that uses APS. To reiterate, here is the definition of sum written using general recursion:

sum :: List Int -> Int
sum Nil    = 0
sum (x:xs) = x + (sum xs)

To convert sum to its APS equivalent, we add an accumulator parameter, update its value during the recursive step, then return it once the base case is reached.

sum :: List Int -> Int
sum xs = sumAcc xs 0
  where
    sumAcc :: List Int -> Int -> Int
    sumAcc Nil acc    = acc
    sumAcc (x:xs) acc =
      sumAcc xs (x + acc)

From here, translating an APSed program to a CPSed equivalent requires that we abstract over the accumulator by replacing it with a higher-order function. In this case, sumAcc has two arguments, a List Int and an Int, where the second is the accumulator. Replacing this value with a higher-order function means that we have the following type for sumCPS:

sumCPS :: List Int -> (... -> ...) -> Int

Let’s complete this type declaration. We need to think about:

1. The type of the continuation’s parameter.
2. The return type of the continuation.

(1) and (2) are synonymous with the type of acc in sumAcc. If we inspect the initial value of acc in the context of sum, we discover that it’s initialized to the value 0, an Int. This means that the first ... is Int.

sumCPS :: List Int -> (Int -> ...) -> Int

The second ... is the type of acc after being updated during each recursive case. During the recursive case, given that we peform addition on acc, it should come with no surprise that the type is also Int.

sumCPS :: List Int -> (Int -> Int) -> Int

Declaring this type dictates the definition of sumCPS in two ways:

1. Since our continuation is acting as an accumulator, we must apply the continuation to our base case, 0.
2. We must extend the continuation during the recursive case.

For (1), we apply a continuation to the value 0, the original return value of sum. For (2), we recur normally, while treating our continuation as a form of accumulator. Here, we are not performing the addition to a set value like in sumAcc but are, instead, creating a function that performs the addition under the context of some other computation, k, and is eventually applied to 0 when the base case is reached. Thus, extending a continuation is synonymous with defining how sum continues with its next computation.

EVAL
>

To further illustrate the behavior of this CPSed function, we include a trace of the List and continuation value in computing (sum (1:2:3:Nil)):

-- Recursive case => Continuations are extended
(1:2:3:Nil) id
(2:3:Nil) ((+) 1 >>> id)
(3:Nil) ((+) 2 >>> (+) 1 >>> id)
Nil ((+) 3 >>> (+) 2 >>> (+) 1 >>> id)
-- Base case is reached => Continuations are applied
((+) 3 >>> (+) 2 >>> (+) 1 >>> id) 0
((+) 2 >>> (+) 1 >>> id) 3
((+) 1 >>> id) 5
id 6
-- Final continuation is applied
id 6
6

Aside: id is our old friend the identity function. Since continuations are functions, to properly model the behavior of an accumulator, their base value must be id.

b. One Step at a Time – Control Flow

The primary benefit of writing in CPS is the control over a function’s evaluation order. To illustrate this point, we need a more complex example than sum. Let’s bring back append and rev from Chapter 1:

append :: forall a. List a -> List a -> List a
append Nil ys    = ys
append (x:xs) ys = x:(append xs ys)

rev :: forall a. List a -> List a
rev Nil    = Nil
rev (x:xs) = append (rev xs) (x:Nil)

Let’s CPS both of these functions. First, let’s determine the appropriate types for their CPSed equivalents.

Since neither of these function are written in APS, we must add a continuation parameter to both of their type declarations:

append :: forall a. List a -> List a -> (List a -> List a) -> List a
rev :: forall a. List a -> (List a -> List a) -> List a

In both cases, the type of the continuation parameter is (List a -> List a), since both functions return a List a. Let’s start by implementing the CPSed version of append.

append Nil ys k    = ?basecase
append (x:xs) ys k = ?recur

In the original definition of append, we return ys in the event that xs is Nil. In the CPSed version, we return ys by applying the continuation k to it:

append Nil ys k = k $ ys

In the recursive case, we extend our continuation with the : operation.

append (x:xs) ys k =
  append xs ys ((:) x >>> k)

Next, we implement the CPSed version of rev:

rev Nil k    = ?basecase
rev (x:xs) k = ?recur

Implementing rev requires that we reason about the order of evaluation, which is a quite bit different from the general functional style of writing code. Since the base case of rev is straightforward to implement, let’s focus on its recursive case:

rev (x:xs) = append (rev xs) (x:Nil)

Here, we are calling append and rev. The question is: Which one should happen first? The natural answer would be that the call to rev happens first. In general, this is correct, but writing code in the general functional style provides us the liberty of not having to reason about which call happens first!

In CPSing rev, we gain the ability to choose which call happens first.

EVAL
>

NOTE: Don’t forget to use id when calling these functions!

Here, we’ve implemented rev to first evaluate the recursive call to itself. Doing this, we discover that the recursive call to rev must happen before the call to append! This is because append depends on the result of the rev computation, which is made clearer when written in CPS style. In fact, it is impossible to properly evaluate the call to append without having xs', the result of the call to rev.

c. If You Squint Your Eyes – Tail Calls

One might have noticed someting strange about the implementation of fully CPSed functions, especially in the way we’ve written append and rev above. This particular something is not actually strange at all but instead is one of the other benefits of writing in CPS.

In a CPSed function, every call is a tail call. This is a side-effect of regaining control over the flow of program execution. That is, the execution of each line happens right when we expect them to, just like it would in an imperative language! Let’s focus again on the recursive case in rev:

rev (x:xs) k =
  rev xs $ \xs' ->
  append xs' (x:Nil) k

Then, let’s add a bit of whitespace, η-expand and rename our continuation variable, k:

rev (x:xs) Nil return =
  rev xs             $ \xs' ->
  append xs' (x:Nil) $ \ans ->
  return ans

Whoa. Doesn’t that look familiar?

In this manner, looking at a CPS function (almost) feels analogous to looking at an implementation in an imperative language. That is, in the recursive case of rev, we know that the following happens:

1. The call to rev is executed.
2. Once (1) finishes, the current continuation is applied to its result.
3. From (2), the variable xs' holds the value of (rev xs).
4. After the continuation is applied in (2), the code continues with the next line.
5. Once (4) finishes, the current continuation is applied to its result.
6. From (5), the variable ans holds the value of (append xs' (x:Nil)).
7. After the continuation is applied to (4), the code continues with the next line.
8. Finally, applying return to ans results in program exit.

2. CPS the Interpreter – Implementation

We’re bringing interpreters back!

In this section, we’ll implement a CPSed interpreter by making changes to interpD from Chapter 2. With the complexity of an interpreter, we are able to further illustrate the power of having explicit control over the flow of program evaluation.

We’ll start with a few changes in the Closure type and the ValueD Type:

Then we’ll implement the rest of the interpreter in the same way we did in Chapter 2:

1. Number Valued expressions
2. Boolean and Branching expressions
3. λ-calculus expressions

Let’s begin!

a. Number Valued Expressions

Let’s recall our previous implementation for number Valued expressions:

interpD _ (Num i)    = ND i
interpD e (Sub x y)  = ND (calcValueD e (-) x y)
interpD e (Mul x y)  = ND (calcValueD e (*) x y)

Here, we defined calcValue to handle the special case of Sub and Mul, which is defined as:

on :: forall a b c.
      (b -> b -> c) -> (a -> b) ->
      a -> a -> c
on op f x y = f x `op` f y

calcValue :: Env Value -> (Number -> Number -> Number) ->
             Term -> Term -> Number
calcValue e op =
  on op $ \x ->
  case interp e x of
    N num -> num
    _     ->
      error "arithmetic on non-number"

calcValue also used the function on to apply the function that interps to both sub-expressions of Sub and Mul and pattern matches on their (N i) case.

Before we CPS these functions for our new interpreter, let’s take the time to reason about what happens in each of them and the order that they should occur.

For on:

1. A function, f, is applied to both x and y.
2. An op function is applied to the results of (1).
3. The result of (2) is returned.

Thus, to CPS on, we must first apply an f to an x and y before returning the result of applying an op to their results. This gives us:

onC op f x y return =
  f x $ \x ->
  f y $ \y ->
  return $ x `op` y

We’ll get back to properly declaring a type for onC. First, let’s take a look at what calcValue does:

1. Using on, two Terms are passed to a function.
2. This function takes Term, passes it to interp, determines whether or not its Value represents a number.
3. If the Value is a number, the number is returned.
4. Otherwise, an error is raised.

This gives us:

calcValueC e op =
  onC op $ \a return ->
  interpC e a $ \a ->
  case a of
    NC num -> return num
    _      ->
      error "arithmetic on non-number"

Providing the proper type for calcValueC is rather straightforward since its specialized to only handle certain inputs. Originally, calcValue takes an Env, an op function, two Terms, and returns Number. In this case, however, after CPSing, it returns a ValueC!

calcValueC :: Env ValueC -> (Number -> Number -> Number) ->
              Term -> Term -> (Number -> ValueC) -> ValueC

After we CPSed calcValue, we revealed that its return value depends on the result of a call to interp, which always returns a Value. This dicates the type of the continuation passed to calcValueC, which consequently affects the type of the continuation in onC. This is why, due to its complexity, we held off providing the type declaration for onC. Given that onC is used in the context of calcValueC, its type declaration must provide the details for every context it can be used in.

To properly derive the type of onC, let’s recall its non-CPSed type declaration:

on :: forall a b c.
      (b -> b -> c) -> (a -> b) ->
      a -> a -> c

When we derive the type of onC, we must do the following:

1. Add an additional polymorphic variable, representing the function’s return type.
2. Every CPSed function argument must also return this type.
3. The function itself must also return the polymorphic return type.

For (1), let’s add the type variable r to represent the return type of onC.

forall a b c r.
(b -> b -> c) -> (a -> b) ->
a -> a -> c

Then, with (2), we must determine which function arguments passed to onC are CPSed. In this case, f, the second function argument, is CPSed since it includes a call to our CPSed interpreter, interpC.

This means there are two functions that must return the type r:

f :: a -> b
on :: (b -> b -> c) -> (a -> b) -> a -> a -> c

First, let’s fix the type for f. Since f originally returned a b, this means that its CPSed equivalent will have a continuation of type (b -> r) and return an r:

f :: a -> (b -> r) -> r

Lastly, we need to change the type of onC itself. Since on originally returned a c, this means that onC will have a continuation of type (c -> r) and return an r.

onC :: forall a b c r.
       (b -> b -> c) -> (a -> (b -> r) -> r) ->
       a -> a -> (c -> r) -> r

This completes the definitions for onC and calcValueC:

We then use calcValueC to define the number Valued expressions of our interpreter:

interpC _ (Num i) return    =
  return $ NC i
interpC e (Sub x y) return  =
  calcValueC e (-) x y $
  return <<< NC
interpC e (Mul x y) return  =
  calcValueC e (*) x y $
  return <<< NC

b. Boolean and Branching Expressions

Next, let’s handle the cases for IsZero and If. In interpD, these cases were defined as follows:

interpD e (IsZero x) =
  BD $ interpD e x == ND 0.0 
interpD e (If x y z) =
  case interpD e x of
    BD b | b         -> interpD e y
         | otherwise -> interpD e z
    _    -> interpD e y

Let’s use the same strategy we employed in defining the cases for number Valued expressions for the above.

First, let’s reason about what happens in each case:

IsZero:

1. interp the sub-expression x.
2. Determine whether the result of (1) is the value 0.
3. The result of (2) is wrapped with the Boolean Value constructor.
4. The result of (3) is returned.

If:

1. interp the sub-expression x.
2. Determine the truthiness of the result of (1).
3. interp the appropriate sub-expression (y or z).

Which gives us the following:

interpC e (IsZero x) return =
  interpC e x $
  return <<< BC <<< ((==) $ NC 0.0)
interpC e (If x y z) return =
  interpC e x $ \x ->
  case x of
    BC boo
      | boo       -> interpC e y return
      | otherwise -> interpC e z return
    _ -> interpC e y return

c. λ-calculus Expressions

And then there were three.

To compare, let’s recall how λ-expressions were handled by interpD:

interpD e (Var n)   = lookUp e n
interpD e (Lam n b) = FD $ makeClosure n b e
interpD e (App l r) = case interpD e l of
  FD foo -> applyClosure foo (interpD e r)
  _      -> error "applied non function value"

Let’s start with the Var case. Since, lookUp is not a CPSed function, we can simply return its result.

interpC e (Var x) return   =
  return $ lookUp e x

If we had CPSed lookUp, we would be required to first evalaute the call to lookUp, then return its result, which would look like this:

lookUp e x return

Next, let’s implement the case for Lam expressions. In interpD, we used makeClosure to create a Closure, then wrapped it in the FD constructor. For interpC, we’ve chosen not to CPS makeClosure, thus we simply return the result of applying FC to a call to makeClosure:

interpC e (Lam n b) return =
  return $ FC (makeClosure n b e)

Lastly, let’s implement the case for App expressions. In interpD, this case is a bit more complex than the cases for Var and Lam. For the App case, the following occurs:

1. interp the sub-expression l.
2. Determine if the result of (1) is a function value.
3. If (1) is a function, interp the sub-expression r. Otherwise, raise an error.
4. When (3) suceeds, the value of (1) and (3) are passed to applyClosure.

Before we can CPS the case for App, we need to determine whether or not applyClosure should be a CPSed function or not. Let’s recall its original implementation:

applyClosure :: Closure -> ValueD -> ValueD
applyClosure (Closure clos) val =
  interpD (extend clos.name val clos.env) clos.body

We discover that applyClosure calls an interp function. Since our interp function is CPSed, applyClosure must also be CPSed. Luckily, this function is rather straightforward to implement. All we need to do is change its type to include a continuation parameter, then thanks to η-reduction, the new applyClosure looks almost exactly the same! This is because the call to interp in applyClosure is already a tail-call.

We then implement the App case as described above:

interpC e (App l r) return =
  interpC e l $ \l ->
  case l of
    FC foo ->
      interpC e r $ \val ->
      applyClosure foo val return
    _      -> error "applied non-function value"

And that’s all, folks! We’ve successfully CPSed our interpreter!

EVAL
>

One should be able to use this interpreter on every example Term from Chapter 2. Just remember to pass it an empty continuation in addition to its regular arguments!

We include a sample trace for evaluating the Term:

(App (Lam "x" (Lam "y" (Var "x"))) (Num 6.0))

interpC EmptyEnv (App (Lam "x" (Lam "y" (Var "x"))) (Num 6.0)) id
==
interpC EmptyEnv (Lam "x" (Lam "y" (Var "x"))) $ \l ->
  case l of
    FC foo ->
      interpC EmptyEnv (Num 6.0) $ \val ->
      applyClosure foo val id
    _      -> error "applied non-function value"
== cont is applied
\l ->
  case l of
    FC foo ->
      interpC EmptyEnv (Num 6.0) $ \val ->
      applyClosure foo val id
    _      -> error "applied non-function value" $ 
FC (makeClosure "x" (Lam "y" (Var "x")) EmptyEnv)
==
case FC (Closure {name:"x",body:(Lam "y" (Var "x")),env:EmptyEnv}) of
    FC foo ->
      interpC EmptyEnv (Num 6.0) $ \val ->
      applyClosure foo val id
    _      -> error "applied non-function value"
==
interpC EmptyEnv (Num 6.0) $ \val ->
applyClosure
  (Closure {name:"x",body:(Lam "y" (Var "x")),env:EmptyEnv})
  val id
==
\val ->
applyClosure
  (Closure {name:"x",body:(Lam "y" (Var "x")),env:EmptyEnv})
  val id $
NC 6.0
==
applyClosure
  (Closure {name:"x",body:(Lam "y" (Var "x")),env:EmptyEnv})
  (NC 6.0) id
==
interpC (extend "x" (NC 6.0) EmptyEnv) (Lam "y" (Var "x")) id
== 
id $
FC (makeClosure "y" (Var "x") (Ext {name:"x",val:(NC 6.0)} EmptyEnv))
==
FC (makeClosure "y" (Var "x") (Ext {name:"x",val:(NC 6.0)} EmptyEnv))

> Function from y returns x, with context {x: (NC 6.0)}

Exercises:

• Define a CPSed fact function.

EVAL
>

• Define a CPSed ack function.

EVAL
>

• Define a CPSed fib function.

EVAL
>

Too easy? How about these:

• Define a CPSed map function and derive its type.

EVAL
>

• Define a CPSed filter function and derive its type.

EVAL
>

• Define a CPSed foldList function and derive its type.

EVAL
>

Why no tests? How about this one?

EVAL
>

testCPS will trigger a type error if the types of mapC, filterC and foldListC are incorrect!

Here are some sample functions to pass to testCPS–feel free to add a few of your own!

Try testCPS with:

testCPS fibFactC lte120 0 addC (1..5) id

Which does the following:

1. fibFactC is mapped over the list (1..5).
2. All elements greater than 120 is removed from the result of (1).
3. The resulting list from (2) is summed.