On Continuation-Passing Style

In this post, I would like to explain continuation-passing style (CPS) and few of interesting applications.

Firstly, to understand continuation-passing style, we need to understand what is continuation.

Compuatations are happended in some order, for example, to compute the value of 1+2+3 in a certain programming languages, say Racket, we have the following expression:

(+ 1 (+ 2 3))

Clearly, we have to compute the value of (+ 2 3), and then compute the value of (+ 1 5) where 5 is the result from the preceding continuation. We can not do anything to (+ 1 ...) before we have the value of (+ 2 3).

So we say that the ... in expression (+ 1 ...) is a hole, an expression with a hole is a continuation. A continuation needs something to fill up this hole so that to proceed. More formally speaking, a continuation is an evaluation context around certain computation.

Continuations are connected. One continuation also contains another continuation, which is the next thing we need to do after current continuation. We can think that a continuation is a pair of expression with hole and another continuation. Only when the current expression is filled up with some value and evaluated to a value, the control will be transferred to next continuation. There is a special continuation called halt which do nothing and immediately stop the computational procedure.

For instance,

(+ 1 (+ 2 (+ 3 4)))

The continuation of (+ 3 4) is [(+ 2 ...), cont1], where cont1 is [(+ 1 ...), halt].

So, the CPS is a programming style that exposes continuations explicitly to programmers. The continuation in CPS are usually represented as functions, where the (formal) argument of the function is the hole of continuation. When we apply this function with some value, is acutually filling up this continuation.

The above code (+ 1 (+ 2 (+ 3 4))) can be easily transformed to CPS form. Though plus operation + is primitive, we can still come up with a variant plus operator with continuation called +/k. Also we need to have a identity continuation id to represent halt.

(define +/k (lambda (x y k) (k (+ x y))))
(define id (lambda (x) x))
(+/k 2 3 (lambda (five) (+/k 1 five id)))

As saying about call/cc which is often confusing to many learners, is not a part of pure CPS. call/cc is a control operator provided by the language that used for capturing current continuation. So call/cc exposes current continuation explicitly to programmers even you are programming not in a continuation-passing style. We can also use call/cc to implement the above code:

(+ 1 (call/cc (lambda (k) (k (+ 2 3)))))

So, the variable k is the current continuation of (+ 2 3) which is (+ 1 ...). By capturing the current continuation, programmers obtain the computations going to happen after now, therefore we may have ability to do something interesting, for example, save k and use it later. call/cc is a powerful function that can be used to implement a lot of fancy things, like non-deterministic operator amb and lightweight concurrency coroutines.

The minimum form of CPS only needs lambda and function application, so all the function applications in CPS are tail recursion. Let’s take function map as an example. A normal map can be implemented in this way:

(define (map f xs)
  (if (empty? xs) '()
      (cons (f (first xs)) (map f (rest xs)))))
(map (λ (x) (+ x 1)) '(1 2 3))

But here, the call of map at line 3 is not a tail call. Because of after have the result of (map f (rest xs)) we still need to cons it with the value of (f (first xs)). However, a CPS version of map is like this:

(define (map-k f xs k)
  (if (empty? xs) (k '())
      (f (first xs) (λ (v) (map-k f (rest xs)
                                  (λ (rest-v) (k (cons v rest-v))))))))
(map-k (λ (x k) (k (+ x 1))) '(1 2 3) (λ (x) x))

We can see that in map-k, all function applications are in tail position, which means that there is no stack consumption on these recursive call (in a language with tail-call optimization).

CPS is a commonly used intermediate representation (IR) of functional languages since 80s, and also has many applictions in compilers and static analysis. For example, in control flow analysis, continuations are exposed in lexical scope, and any forms of control flow transfer are represented by a continuation, thus extremely simpilied the analysis. Also, when doing partial evaluation, the results are even better in CPS.

But the problem of CPS is it is too difficult for a human to read and understand it when the code grown. Another IR simpler but equivalent to CPS is A-Normal Form(ANF), where the A-normalize transformation is equivalent to CPS convert -> Beta normalize -> un-CPS convert. The paper The Essence of Compiling with Continuation is a good reference to ANF.

Interestingly, CPS is also equivalent to Static Single Assignment (SSA). In CPS, each variable is introduced by a lambda term, and the mutation of a variable is also implemented by a continuation in lambda form; where in SSA, each variable only can be assigned with a value exactly once, and the definition dominates the following use of this variable, and the Phi node is SSA is equivalent to passing different value to the same continuation. The paper A correspondence between Continuation Passing Style and Static Single Assignment Form is worth to read about this part.

Haskell programmers may farmilar with continuation monad. In theory, CPS also has a correspondence with monad and for any monad there is a equivalent form in CPS. In Philip Wadler’s seminal paper The Essence of Functional Programming he also demostrated this point.