DEV Community

Dwayne Crooks
Dwayne Crooks

Posted on

On continuation-passing style and the factorial function

#cps #continuations #elm

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.

Top comments (1)

Collapse
 
jmpavlick profile image
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.