On continuation-passing style and the factorial function
Tags: cps, continuations, elm
Published: 2023-12-14 19:58:03

---
title: On continuation-passing style and the factorial function
published: true
description: It explains how a special representation of continuations leads to the iterative version of the factorial function.
tags: cps, continuations, elm
# cover_image: https://direct_url_to_image.jpg
# Use a ratio of 100:42 for best results.
# published_at: 2023-12-14 19:45 +0000
---

[Factorial](https://en.wikipedia.org/wiki/Factorial) can be implemented in Elm as follows:

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

The JavaScript produced by this implementation looks like:

```js
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](https://mitp-content-server.mit.edu/books/content/sectbyfn/books_pres_0/6515/sicp.zip/full-text/book/book-Z-H-11.html#%_sec_1.2), `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:

```elm
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](https://en.wikipedia.org/wiki/Tail_call), which [Elm does](https://jfmengels.net/tail-call-optimization/).

```js
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](https://en.wikipedia.org/wiki/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](https://guide.elm-lang.org/types/custom_types.html) or functions.

## Factorial using CPS (custom types)

```elm
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)

```elm
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:

```elm
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:

```elm
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](https://mitpress.mit.edu/9780262062794/essentials-of-programming-languages/).