# UW CSE P 505 Notes – Continuation Passing Style

Continuation passing style (CPS) is a style of programming wherein function calls are chained together. Each function in the chain performs some computation on a value and then passes the result of that computation on to the next function in the chain. Using this style, functions do not directly return a value. Instead, they return a function call. Exactly which function is called next is determined by making it an explicit argument to the current function.

Functions written in CPS will have the form … ->(a -> r) -> r in Haskell where “…->” denotes the set of argument values that this function does a computation on. This portion of the function signature would match up exactly with an equivalent function that did not use CPS. For example, a sum function would have signature Int->Int->Int in direct style, and have signature Int->Int->(Int->r)->r in CPS style. The difference lies in the (a -> r) –> r, that is, a function that takes as an argument another function that takes a value and returns a value, and that itself returns a value. (a->r) is the continuation and represents the next function in the chain that will be called. Note that the type of the argument a does not have to match the return type of r. The only constraint is that the return type of the continuation must match up with the return type of the current function.
This is abstract, so some simple examples can help illustrate what is going on. Consider the quadratic equation y =3×2 + 2x + 5. A function that solves for y given a value of x might look something like the following without continuations:

add :: Int -> Int -> Int
add x y = x + y

square :: Int -> Int
square x = x * x

mult :: Int -> Int -> Int
mult x y = x * y

add (add (mult 3 (square x)) (mult 2 x)) 5

With continuations, the code becomes:

addCont :: Int -> Int -> ((Int -> r) -> r)
addCont x y = \k -> k (x + y)

squareCont :: Int -> ((Int -> r) -> r)
squareCont x = \k -> k (x * x)

multCont :: Int -> Int -> ((Int -> r) -> r)
multCont x y = \k -> k (x * y)

solveQuadraticExampleCont :: Int -> ((Int -> r) -> r)
multCont 2 x (\twoX ->
squareCont x (\x2 ->
multCont 3 x2 (\threeXSquared ->
addCont sum 5 k)))))

This can be invoked by passing in a top level continuation of type (Int -> r) to the solveQuadraticExampleCont. We can use the identity function:
solveQuadraticExampleCont 3 id which prints out 38 from the ghci REPL. The continuations serve to dictate what happens next with the result of the current function, with the order of operations and the intermediate values calculated made explicit. The continuations are somewhat analogous to callback functions. Event driven frameworks that use callbacks to define what happens next in an asynchronous call are a form of CPS. Indeed in Node JS, you will typically see nested anonymous callback functions chained together, as in this contrived example:

http.createServer(function (req, res) {
});