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:
-
endContmultiplies its value by1, becauseendCont = \val -> 1 * val. - If
nextKmultiplies its value bymthenfactNCont n nextKmultiples its value bym * 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.
Top comments (1)
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.