Computing a Factorial with Church Numerals
Hello, friends!
There are plenty of articles about the lambda calculus, Church numerals and related topics, so I won't be discovering anything new here. Instead, we're going to write one useless and extremely inefficient program.
To keep things from getting too easy, we'll limit ourselves to a tiny subset of JavaScript: anonymous functions of one argument. We won't need anything else (well, almost).
Let's start with the usual definition of factorial and see what we'll need along the way:
var fact = function (n) {
if (n === 0) return 1;
return n * fact(n - 1);
};So we need booleans (for the result of comparing with zero), a conditional, multiplication, subtracting one, and a recursive call.
Ready?
Booleans and If
Let's start with the simple stuff: True, False, and If. True and False are curried functions of two arguments that pick one of them. True picks the first, False picks the second. If takes three arguments: a boolean, a then branch and an else branch.
var True = function (x) {
return function (y) {
return x;
};
};
var False = function (x) {
return function (y) {
return y;
};
};
var If = function (p) {
return function (t) {
return function (e) {
return p(t)(e);
};
};
};You can play with them in the console:
console.log(If(True)("foo")("bar")); // => foo
console.log(If(False)("foo")("bar")); // => barNumbers
Next we need numbers. You can build all the natural numbers from just two things: ZERO and a PLUS_ONE operation. Roughly speaking, a Church numeral is a function of two arguments that applies the first argument to the second n times, where n is the number it stands for.
var Zero = function (f) {
return function (x) {
return x;
};
};
var Succ = function (n) {
return function (f) {
return function (x) {
return f(n(f)(x));
};
};
};Factorial needs a zero check, so let's also define a predicate for that. It returns False if the function passed to the number was applied at least once.
var IsZero = function (n) {
return n(function (x) {
return False;
})(True);
};Let's check that the numbers work:
console.log(
Succ(Succ(Succ(Zero)))(function (x) {
return x + 1;
})(0),
); // => 3
console.log(If(IsZero(Zero))("zero")("not zero")); // => zero
console.log(If(IsZero(Succ(Zero)))("zero")("not zero")); // => not zeroAs you can see, one was added to zero three times, and the predicate recognizes its argument correctly.
Multiplication
Now that we have all the natural numbers, let's define multiplication. The product of n and m is a function that applies its argument m times, n times over.
var Mul = function (n) {
return function (m) {
return function (f) {
return n(m(f));
};
};
};Subtracting one
All that's left is subtracting one. This one is a bit trickier. The idea is to build the pair (n, n − 1) and take its second element. So we need a pair constructor and functions that return the first and second elements. Then we can define the predecessor function.
var Pair = function (a) {
return function (b) {
return function (t) {
return t(a)(b);
};
};
};
var Fst = function (p) {
return p(True);
};
var Snd = function (p) {
return p(False);
};
var Pred = function (n) {
return function (s) {
return function (z) {
return Snd(
n(function (p) {
return Pair(s(Fst(p)))(Fst(p));
})(Pair(z)(z)),
);
};
};
};Let's play with pairs and subtraction:
Fst(Pair("foo")("bar")); // => "foo"
Snd(Pair("foo")("bar")); // => "bar"
Pred(Succ(Succ(Zero)))(function (x) {
return x + 1;
})(0); // => 1Factorial
It looks like we have everything, so let's write the factorial:
var fact = function (n) {
return If(IsZero(n))(Succ(Zero))(Mul(n)(fact(Pred(n))));
};But there are two problems. The first is that JavaScript is an applicative-order language (arguments are evaluated eagerly), so the recursive call is made even when n is zero. Our factorial never stops recursing and dies with Maximum call stack size exceeded. That's easy to fix: we can defer the recursive call by wrapping it in an anonymous function.
var fact = function (n) {
return If(IsZero(n))(Succ(Zero))(function (x) {
return Mul(n)(fact(Pred(n)))(x);
});
};Now the function works:
fact(Succ(Succ(Succ(Zero))))(function (x) {
return x + 1;
})(0); // => 6Getting rid of the name
One problem left. I promised to use only anonymous functions, but here we have a recursive call by the name fact. We need to get rid of it, and the fixed-point combinator will help us. I won't explain how it works, there's plenty written about that already. I recommend this blog post, for example. In an eagerly evaluated language the Y combinator looks like this (strictly speaking, this version is called the Z combinator, but everybody calls it Y anyway):
var Y = function (f) {
return (function (x) {
return x(x);
})(function (x) {
return function (y) {
return f(x(x))(y);
};
});
};You can check that it works like this:
Y(function (f) {
return function (n) {
return If(IsZero(n))(Succ(Zero))(function (x) {
return Mul(n)(f(Pred(n)))(x);
});
};
})(Succ(Succ(Succ(Zero))))(function (x) {
return x + 1;
})(0); // => 6Now let's substitute the factorial into the Y combinator and get the next version:
var fact = (function (x) {
return x(x);
})(function (x) {
return function (y) {
return (function (f) {
return function (n) {
return If(IsZero(n))(Succ(Zero))(function (x) {
return Mul(n)(f(Pred(n)))(x);
});
};
})(x(x))(y);
};
});To make experimenting easier, let's define NatToChurch and ChurchToNat. These are just debugging helpers, not part of the factorial itself, so they use regular JavaScript syntax:
var NatToChurch = function (n) {
return n === 0 ? Zero : Succ(NatToChurch(n - 1));
};
var ChurchToNat = function (n) {
return n(function (x) {
return x + 1;
})(0);
};Now we can experiment in the console:
ChurchToNat(fact(NatToChurch(5))); // => 120The final function
The last step is to inline everything and get the final function:
Careful, lots of functions
var fact = (function (x) {
return x(x);
})(function (x) {
return function (y) {
return (function (f) {
return function (n) {
return (function (p) {
return function (t) {
return function (e) {
return p(t)(e);
};
};
})(
(function (n) {
return n(function (x) {
return function (x) {
return function (y) {
return y;
};
};
})(function (x) {
return function (y) {
return x;
};
});
})(n),
)(
(function (n) {
return function (f) {
return function (x) {
return f(n(f)(x));
};
};
})(function (f) {
return function (x) {
return x;
};
}),
)(function (x) {
return (function (n) {
return function (m) {
return function (f) {
return n(m(f));
};
};
})(n)(
f(
(function (n) {
return function (s) {
return function (z) {
return (function (p) {
return p(function (x) {
return function (y) {
return y;
};
});
})(
n(function (p) {
return (function (a) {
return function (b) {
return function (t) {
return t(a)(b);
};
};
})(
s(
(function (p) {
return p(function (x) {
return function (y) {
return x;
};
});
})(p),
),
)(
(function (p) {
return p(function (x) {
return function (y) {
return x;
};
});
})(p),
);
})(
(function (a) {
return function (b) {
return function (t) {
return t(a)(b);
};
};
})(z)(z),
),
);
};
};
})(n),
),
)(x);
});
};
})(x(x))(y);
};
});Now we're left with the question: "Why would anyone do this?" Honestly, I don't have an answer.
Take care, everyone!