TheLazy.Dev
Portfolio GitHub

Blog

cps |continuations |elm

On continuation-passing style and the factorial function

dwayne

Dwayne Crooks

Posted on December 14, 2023

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)
Enter fullscreen mode Exit fullscreen mode

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));
};
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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);
};
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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.

💖 💪 🙅 🚩
dwayne
Dwayne Crooks

Posted on December 14, 2023

Join Our Newsletter. No Spam, Only the good stuff.

Sign up to receive the latest update from our blog.

Related

On continuation-passing style and the factorial function
cps On continuation-passing style and the factorial function

December 14, 2023