Continuation Passing Style (CPS) is a useful concept in functional programming. In summary, the goal is to chain computation. Rather than explicitly handling intermediate results at a higher-level, CPS functions should instead pass their result into the next function in the chain of computation. Well see more on how this works below.
What are continuations?
Practically speaking, continuations are functions which take the return value of another function. That is, rather than returning, a function using a continuation passes its result into the continuation instead of returning thus continuing the computation. Given the power of most functional languages, this result (or argument to the continuation) can contain its own state and be arbitrarily complex. However, from the perspective of using a continuation, it can be treated as a simple function.
Why Continuation Passing Style?
Continuation passing style provides several benefits to the programmer. Such benefits include graceful exiting from a computation (i.e. think transaction-like), asynchronous operations, and more. In general, like all other aspects in programming paradigms, its a way of thought meant to make your life easier in particular scenarios. Well try to outline some examples of where it could be useful to help you identify when you want to think in this way.
Note that while we will use Haskell here, this can be done in any language which supports closures and passing functions as arguments. You can see a nice primer using Javascript which goes through many simpler examples.
Continuation Passing Style Examples
Babys first CPS. This first example is trivial. It is to simply provide you with some foundation or notion of what CPS is and how it looks on a very simple level. The following examples will be increasingly more complex but also far more useful.
module Test where
factorial :: (Ord a, Num a) => a -> a
factorial n = factorial' n 1
where factorial' n acc
| n <= 0 = acc
| otherwise = factorial' (n - 1) (n * acc)
factorialCPS :: (Ord a, Num a) => (a -> a) -> a -> a
factorialCPS k n = continuation n 1
where continuation n acc
| n <= 0 = k $ acc
| otherwise = continuation (n - 1) (n * acc)
main :: IO ()
main = do
-- Basic call
print $ factorial 5
print $ factorialCPS id 5
-- Double result
print $ ((factorial 5) * 2)
print $ factorialCPS (*2) 5
-- Over many values
print $ fmap ((*2) . factorial) [1..10]
print $ fmap (factorialCPS (*2)) [1..10]
-- Composed continuation
print $ fmap ((+10) . (*2) . factorial) [1..10]
print $ fmap (factorialCPS ((+10) . (*2))) [1..10]
As I mentioned, this example is contrived solely for demonstration purposes. The first thing you will notice is that we have implemented the factorial method in two different ways: (1) our standard factorial method and (2) a factorial method which passes each result into a continuation (the variable letter k is frequently used for continuations). You can run the program and the results will be identical for either way of performing factorial.
Some final thoughts about this example: you will notice that our factorialCPS method never returns a value. Instead, it returns the result of a computation (i.e. k $ acc). The final continuation k will transform its input and eventually return that value as a result. Similarly, you will notice that our factorialCPS is still recursive and calls itself (rather, its continuation method). It is important to remember that while all final calls should be the final value returned from the continuation, you still have to complete your operation before you can pass your result to the continuation. Consequently, for any algorithm which is multiple steps (i.e. most useful algorithms), it is likely that you will recurse and only use the continuation at the base cases.
Exception Handling with Continuation Passing Style
In this next example, Ill show an artificial example of using CPS for exception handling. In our example we assume an exception occurs anytime our computation reaches 0.
module TryCatch where
type Result = Either String String
type Except a = (a -> Result)
type Cont a = (a -> Result)
exceptionCatch :: (Show a) => Except a
exceptionCatch v = Left $ "Error: Found bad value (" ++ show v ++ ")"
tryIt :: (Num a, Show a) => a -> (Except a -> Cont a) -> Except a -> Result
tryIt v try catch = try catch v
predOp :: (Num a, Show a) => a -> a -> (a -> a -> a) -> (a -> Bool) -> Except a -> Cont a -> Result
predOp q r op p f k = let res = q `op` r in (if p res then k else f) res
addPred :: (Num a, Show a) => a -> a -> (a -> Bool) -> Except a -> Cont a -> Result
addPred q r p f k = predOp q r (+) p f k
mulPred :: (Num a, Show a) => a -> a -> (a -> Bool) -> Except a -> Cont a -> Result
mulPred q r p f k = predOp q r (*) p f k
add :: (Num a, Show a, Eq a) => Except a -> Cont a -> a -> a -> Result
add f k n m = addPred n m (/=0) f k
mul :: (Num a, Show a, Eq a) => Except a -> Cont a -> a -> a -> Result
mul f k n m = mulPred n m (/=0) f k
stringCont :: (Show a) => a -> Result
stringCont = Right . show
opSequence :: Int -> Int -> Except Int -> Int -> Result
opSequence a b f scale = add f (mul f stringCont scale) a b
main :: IO ()
main = do
let res = [tryIt 1 (opSequence 1 2) exceptionCatch
, tryIt 2 (opSequence 1 2) exceptionCatch
, tryIt 0 (opSequence 1 2) exceptionCatch
, tryIt 1 (opSequence 1 (-1)) exceptionCatch]
putStrLn $ show res
You will notice that we define all of our operations in continuation passing style. This is necessary for all operations. Our final operation (stringCont) is our terminal operation. That is, it is the final operation that executes upon a successful computation.
In summary, our tryIt function takes a single value to be passed into our function, our actual continuation, and, finally, our exception handler (i.e. the failure case). Focusing on the opSequence method, you will notice that results are computed from the outside-in (opposite of typical function composition in Haskell). That is because we compute a result and then pass it into the next function.
Conclusion
This ends the first part of our discussion on Continuation Passing Style. Now that you have seen it a bit, it provides us with a framework for discussing more interesting use cases in the future. That said, I admit that these cases– while useful for explanation of the technique– are relatively contrived. The examples provided are usually more easily handled in other ways. In any case, we will dive a little deeper next time. That is, we will discuss using CPS in a more useful fashion on different styles of problems.
comments powered by Disqus