On continuation-passing style and the factorial function

Factorial can be implemented in Elm as follows:

fact : Int -> Int
fact n =
    if n <= 1 then
        1
    else
        n * fact (n - 1)

The JavaScript produced by this implementation looks like:

var $author$project$Main$fact = function (n) {
    return (n <= 1) ? 1 : (n * $author$project$Main$fact(n - 1));
};

So the recursive Elm implementation produced a recursive JavaScript implementation. In the terminology of SICP: Procedures and the Processes They Generate, fact can be described as a recursive function that generates a recursive process.

Experienced functional programmers know we can write the following version of the factorial function:

factIter : Int -> Int
factIter n =
    factIterHelper n 1

factIterHelper : Int -> Int -> Int
factIterHelper n acc =
    if n <= 1 then
        acc
    else
        factIterHelper (n - 1) (acc * n)

And the JavaScript produced by this implementation will produce a while loop if the language implements tail-call optimization, which Elm does.

var $author$project$Main$factIterHelper = F2(
    function (n, acc) {
        factIterHelper:
        while (true) {
            if (n <= 1) {
                return acc;
            } else {
                var $temp$n = n - 1,
                    $temp$acc = acc * n;
                n = $temp$n;
                acc = $temp$acc;
                continue factIterHelper;
            }
        }
    });
var $author$project$Main$factIter = function (n) {
    return A2($author$project$Main$factIterHelper, n, 1);
};

As a result, factIter is a recursive function that generates an iterative process. This is much better since looping tends to be faster than making function calls.

Anyway, what I wanted to share today was something I recently learned about continuation-passing style and factIter.

Continuation-passing style (CPS)

Continuation-passing style (CPS) is a style of programming which allows you to transform functions such that all function calls end up as tail calls.

We do this by adding an extra argument to each function. The extra argument is called a continuation. The function you're transforming returns by "calling the continuation". In Elm, the continuation can be implemented using custom types or functions.

Factorial using CPS (custom types)

fact : Int -> Int
fact n =
    factK n endCont

factK : Int -> Continuation -> Int
factK n k =
    if n <= 1 then
        applyContinuation k 1

    else
        factK (n - 1) (factNCont n k)

type Continuation
    = EndCont
    | FactNCont Int Continuation

endCont : Continuation
endCont =
    EndCont

factNCont : Int -> Continuation -> Continuation
factNCont =
    FactNCont

applyContinuation : Continuation -> Int -> Int
applyContinuation k val =
    case k of
        EndCont ->
            val

        FactNCont n nextK ->
            applyContinuation nextK (n * val)

Factorial using CPS (functions)

fact : Int -> Int
fact n =
    factK n endCont

factK : Int -> Continuation -> Int
factK n k =
    if n <= 1 then
        applyContinuation k 1

    else
        factK (n - 1) (factNCont n k)

type alias Continuation = Int -> Int

endCont : Continuation
endCont =
    \val ->
        val

factNCont : Int -> Continuation -> Continuation
factNCont n nextK =
    \val ->
        applyContinuation nextK (n * val)

applyContinuation : Continuation -> Int -> Int
applyContinuation k val =
    k val

Towards a clever representation of continuations

Sometimes we can find clever representations of continuations. If we notice the following about the previous representation:

1. endCont multiplies its value by 1, because endCont = \val -> 1 * val.
2. If nextK multiplies its value by m then factNCont n nextK multiples its value by m * n.

Then, we will see that both continuations are of the form \val -> m * val for some m. It means we can represent such a continuation by the multiplier m. Doing that we get:

fact : Int -> Int
fact n =
    factK n endCont

factK : Int -> Continuation -> Int
factK n k =
    if n <= 1 then
        applyContinuation k 1

    else
        factK (n - 1) (factNCont n k)

type alias Continuation = Int

endCont : Continuation
endCont =
    1

factNCont : Int -> Continuation -> Continuation
factNCont n nextK =
    applyContinuation nextK n

applyContinuation : Continuation -> Int -> Int
applyContinuation k val =
    k * val

Finally, if we inline endCont, factNCont, and applyContinuation and get rid of the Continuation type alias, we end up with the following implementation:

fact : Int -> Int
fact n =
    -- factK n endCont
    -- =
    factK n 1

factK : Int -> Int -> Int
factK n k =
    if n <= 1 then
        -- applyContinuation k 1
        -- = k * 1
        -- =
        k

    else
        -- factK (n - 1) (factNCont n k)
        -- = factK (n - 1) (applyContinuation k n)
        -- =
        factK (n - 1) (k * n)

Isn't that cool? It's equivalent to the factIter we started off with.

An accumulating parameter is often just a representation of a continuation.

If this blew your mind and piqued your interests then I'd highly recommend you to read section 6.1 Writing Programs in Continuation-Passing Style from the book Essentials of Programming Languages, 3rd Edition.

Comments

[John Pavlick]

I finally understand "continuation passing" - this is outstanding.

Seriously - I have tried to understand this for many, many years; and it turns out that I have understood it, in a sense; I've been advocating for defunctionalization everywhere that it fits for a minute now, but this is another level.

Appreciate it.