On the Continuation-Passing Style and its role in FP

In Functional Programming, We tend to use Recursion instead of an imperative loop. One tiny problem is that Recursion is normally a stack exploder. For this reason, in practice, we use Tail-recursion form to avoid that. Tail-recursion is a way we write recursive calls in which the “caller” function value does not depend upon the “return value of callee”.

For example, consider these two different definitions of a factorial function.

f = (x) => x == 0 ? 1 : x*f(x-1);

tailF = (x, acc) => x == 0 ? acc : tailF(x-1, acc*x)

The execution chains for 3! can be shown as follows:

The image illustrates call-chains comparison recursion vs tail-recursion.

The pinks indicate calls, the blue indicates return value. Tail-call normally accumulates values and pass them to the next call. As a side note, Stack overflow errors are caused by the length of this chain becomes too long.

Note: Tail-call is not exactly the same thing as Tail-recursion. Tail-recursion employs Tail-call. We see they appear together just because a recursion is an obvious application of Tail-call.

In reality, the call chain of Tail-recursion may or may not be as shown. It depends on the language support of a Tail-call optimization. If it isn’t, the stack will still be used.

How is that related to our topic, Continuation-Passing Style(CPS)? The answer is every call in CPS must be Tail-call. The difference is that instead of passing an accumulator, we pass a continuation to the next call.

Consider the following scenario, suppose we want to make a call to a function by the following order:

f() --> g() --> h()

In the imperative programming, this is easy:

a = f()
b = g() + a
c = h() + b

This is called a direct-style, as opposed to CPS. This program rely upon global variables, which is not a functional way of doing it i.e. it introduces a state to our program. It assumed that between a = f() and b = g() + a there is nothing else, which might not be true in the case of concurrent programming. How about h(g(f()))? Well, it is not Tail-call.

CPS

Let’s get back to the factorial example, how do we make that CPS? One trick to turn thing to CPS is “there shall be no return”. The tailF has a return statement. It returns acc at the base-case.

tailF = (x, acc) => x == 0 ? acc : tailF(x-1, acc*x);

make it CPS, we will get:

cpsF = (x, cont) => x == 0 ? cont(1) : cpsF(x-1, y=>cont(x*y));

To see how is it different to the accumulator version, we must try to execute it. We define id = x => x as an identity function to extract final result. It will be substituted last to not make the evaluation too complicated. First, let’s try with something trivial:

cpsF(0, id)
--> id(1)         // by definition
--> (x => x)(1)   // expand id
--> (1)           // substitute x and reduce it
==> 1 // Result

Let’s try with 3!

cpsF(3, id)
--> cpsF(3-1, y=>id(3*y))
--> cpsF(2, y'=>id(3*y'))                 // reduce and rename it
--> cpsF(2-1, y=>(y'=>id(3*y'))(2*y))     // applied next call
--> cpsF(1, y''=>(y'=>id(3*y'))(2*y''))   // reduce and rename
--> cpsF(1-1, y=>(y''=>(y'=>id(3*y'))(2*y''))(1*y))
--> cpsF(0, y'''=>(y''=>(y'=>id(3*y'))(2*y''))(1*y'''))
--> (y'''=>(y''=>(y'=>id(3*y'))(2*y''))(1*y'''))(1)
--> (y''=>(y'=>id(3*y'))(2*y''))(1*1)
--> (y'=>id(3*y'))(2*(1*1)))
--> id(3*(2*(1*1))))
--> (x=>x)(3*(2*(1*1))))
--> (x=>x)(6)
--> (6)
==> 6 // Result

You may observed that the execution can be divided into two phases. The expansion and the folding back. This is the main difference to accumulator style. The real computation does not happen until it finishes the expansion.

The function we send in can be an arbitrary function. It acts as the result taker and perform its own execution afterward. One major drawback we can see is it may hurt your brain.

CPS eliminates the requirement of the call stack and return statement. Instead of extract a value back, you send in your function to continue(or terminate) a program. It used to create explicit control flows in functional programming. And since it does not rely on stack value, any values will be captured inside of the continuation. We can make even more than one continuation to execute on a different execution path or even on the different CPU with no problem with mutable state. As a result, working with a concurrent program will be innately supported.

More on CPS:
#1 http://2ality.com/2012/06/continuation-passing-style.html
#2 https://en.wikipedia.org/wiki/Continuation-passing_style