In our last episode, we built the foundation of boolean logic in lambda calculus using a limited subset of JavaScript. (Read that entry first.) Now, let's build numbers and do some math. There are several ways one could choose to represent numbers using functions, but the most typical method is called Church numerals. That's what we'll use.

A "number" will be a function that applies some other function that many times to some value. In JavaScript, this looks like number(fn)(value). So, the number "zero" is a function that takes some other function and a value, applies the other function zero times to the value, and then returns the result — the original value. The number "one" applies that function once, like fn(value). The number "two" applies that function twice, like fn(fn(value)). Because JavaScript doesn't allow identifiers to start with a digit, we'll prefix number values with N. Here are a few examples:

var N0 = f => x => x;              // apply "f" zero times; N0(f)(x) == x
var N1 = f => x => f(x);           // apply "f" once;       N1(f)(x) == f(x)
var N2 = f => x => f(f(x));        // apply "f" twice;      N2(f)(x) == f(f(x))
var N3 = f => x => f(f(f(x)));     // and so on.
var N4 = f => x => f(f(f(f(x))));

This might seem like a weird way to define a number, but it turns out to be both convenient and useful in a land where everything is a function.

If we cheat for a moment, imagine a function, wrap(str), that wraps its argument in angle brackets and returns the new string; calling wrap("x") would produce <x>. We could use our number functions to wrap a string that many times: N3(wrap)("x") would produce <<<x>>>, and N0(wrap)("x") would produce x.

The simplest math we can do with a number is to add one (called "increment" in programming and "successor" in mathematics). A successor function should return a number one higher than the number given. Given our definition of numbers, our successor function should produce a new function which takes some function (f) and some value (x) and applies that function one additional time to that value. For example, the successor of two is three — the successor of "a function which applies another function twice" is "a function which applies another function three times".

This is also the point at which we first see a difference between "take a bunch of arguments all at once" like normal JavaScript (f(a, b, c, d)) and "take one argument and then produce a new function to take the next one" seen in lambda calculus (f(a)(b)(c)(d)). Because a number is a function that eventually takes two arguments (the function to apply and the value on which it should operate), any operation we do with numbers should ultimately return a number — a function that takes those same two arguments. Therefore, some of these functions, like the successor function, look like they take more arguments than they should; they're returning a "number", a thing that takes two arguments, and there's no difference between doing that and taking those arguments immediately.

At last, here's the successor function:

var SUCC   = n => f => x => f(n(f)(x));
//                \-- "new number" --/

Imagine it as taking a single argument, n, the number to increment. It returns a new number — a thing that takes f and x and returns something. In this case, though, the "number" it returns has different guts than our normal numbers that we defined above. Instead of simply applying f to x some number of times, when it's finally invoked, it applies f to x exactly n times (by calling n(f)(x), since that's exactly what a number function does). Then, it applies f one additional time, by simply just passing the previous result to f(...). So, it's a number that applies f one more time than n would have on its own.

In a very similar way, we can implement addition. Addition is an operation that takes two numbers and produces the sum of those numbers. In lambda calculus terms, our addition function needs to take two numbers ("functions that apply some other function some number of times to some value") and invoke them, making sure they both use the same "other function" and operate on the same value. To achieve this, it needs to take the two numbers to "add", m and n, and produce a new number (a function that takes f and x) which applies f to x that many times:

var PLUS   = m => n => f => x => m(f)(n(f)(x));
//                     \---- "new number" ---/

The guts of our addition function applies f() n times (n(f)(x)), and then applies f() again m times to the result (m(f)(...)).

Multiplication becomes slightly more complicated. This time, instead of applying f() n times and then m times, we need to apply n itself m times. That is, instead of having to increase zero by one n times and then by one m times, we need to repeat the whole operation of "increase zero by n" itself m times. This is written as follows:

var MULT   = m => n => f => x => m(n(f))(x);
// or, equivalently,
var MULT   = m => n => f =>      m(n(f));

Finally, exponentiation takes the process one step further; the act of applying the base (b) itself becomes the "other function" used by the exponent (e), building a new "number" function unrelated to the other arguments f and x. It then uses that new number function to apply the original f to x the appropriate number of times:

var POW    = b => e => f => x => e(b)(f)(x);
// or, equivalently,
var POW    = b => e =>           e(b);

To demonstrate these functions, we first need a way to turn lambda calculus numbers back into real numbers:

function l2js_uint(uint) {
  return uint(x => x+1)(0);
}

This function takes one number function (uint, since our integers are unsigned) and asks it to apply "add one" to 0 that many times.

Then:

output(["n","succ","plus","mult","pow"].join("\t")+"\n");
[N0, N1, N2, N3, N4].forEach(function(n){
  output([
    l2js_uint(n),
    l2js_uint(SUCC(n)),
    l2js_uint(PLUS(n)(n)),
    l2js_uint(MULT(n)(n)),
    l2js_uint(POW(n)(n)),
  ].join("\t")+"\n");
});

This produces:

n       succ    plus    mult    pow
0       1       0       0       1
1       2       2       1       1
2       3       4       4       4
3       4       6       9       27
4       5       8       16      256

Predecessor (subtract one) and full subtraction are much simpler if we take a quick detour, so we'll pause for a moment to cover data structures next.