Lambda Calculus Through JavaScript, Part 2

This article was originally published at 47deg.com on January 7, 2021.

The previous post in this series introduced the constraints we had to obey to use JavaScript as untyped lambda calculus, and then we relaxed some of those constraints via currying (for functions of more than one argument) and translation (to turn const local variables into a combination of functions). Now, in this post, we are going to continue our journey by looking at conditionals first. Then we’ll introduce Church numerals to encode numbers.

Boolean values

Everything in lambda calculus is a function at the end of the day. This point of view is quite different from looking at Booleans as tiny objects – true or false, high or low voltage. In fact, to reconcile both views, we are going to work with the logic gate analogy.

In our encoding, each Boolean value is thought of as a “gate” with two wires. The output of this gate comes from one of the wires; which one it is depends on the Boolean value. Note that we could reverse the particular choice for true and false; we only need to be consistent.

Those functions can be defined using the blocks of lambda calculus:

const true_  = x => y => x
const false_ = x => y => y

The conditional, which we usually represent as if (cond) a else b, also has to be represented as a function. All that we know at this point is the shape it should have:

const if_ = cond => a => b => ???

Here comes the magic trick! 🪄 We know that cond is going to be one of our true<em> or false</em> Boolean values. This means cond is a function that accepts two arguments; the exact arguments we have! The definition of if_ can then be refined to:

const if_ = cond => a => b => cond(a)(b)

Does this work? Let’s try to compute with both choices of cond:

// cond == true_
if_(true_)(a)(b) = true_(a)(b) = (x => y => x)(a)(b) == a
// cond == false_
if_(false_)(a)(b) = false_(a)(b) = (x => y => y)(a)(b) == b

Victory! We were able to define the Boolean values, and their main operation – conditional choice – using only functions.

Exercise for the reader

Would you be able to write the not function on Booleans?

Solution: If we were to write this function using regular JavaScript, we would end up with something along the lines of the following code block.

const not = (a) => if(a) false else true

Let’s simply replace each of the JavaScript components with those from lambda calculus.

// using our definitions for if_, true_, and false_
const not = (a) => if_(a)(false_)(true_)
// expanding the definitions
const not = (a) => a(false_)(true_)
const not = (a) => a(x => y => y)(x => y => x)

Lambda numbers

That’s a cool name, but the regular name for the representation of numbers in the lambda calculus is Church numerals, named after its creator Alonzo Church. As in the case of Booleans, we are going to use a function of two arguments to represent each number; the trick is to find something that we can somehow iterate.

In our case, this iteration is going to be done by repeatedly applying the same function. Let me show you how the numbers 1 to 3 are represented in this fashion:

const one   = f => x => f(x)
const two   = f => x => f(f(x))
const three = f => x => f(f(f(x)))

You can surely see the pattern here: we have as many nested fs as the number we seek to represent. Pause here for a minute and think how the number 0 would look in this encoding.

Solution: The Church numeral for 0 must apply its argument f no times. In other words, it should return the x untouched.

const zero = f => x => x

One simple operation we can define is the addition of a constant number to a Church numeral. For example, let’s build the function that represents the operation x => x + 1; the idea is that the resulting Church numeral should apply its f argument once more.

const addOne = n => (f => x => f(n(f)(x)))
//                   ---------------------

To understand this code, let’s break it into pieces. addOne is a function that accepts one Church numeral – the n – and gives back another numeral – hence the f => x => in the underlined section. As we said, we need to apply f once more, but we need to remember to still pass f and x to the original number n!

In case you’re not fully convinced, we can work out an example:

addOne(two) = f => x => f(two(f)(x))
            = f => x => f(f(f(x)))
            = three

In the same way that Booleans directly encode conditional choice, Church numerals directly encode repetition. You can use a Boolean as a function to choose between two alternatives, and you can use a number as a function to repeat an operation. This insight allows us to define more complex operations on numbers, like addition.

Think of how you used to add when you were a kid (if you are like me, you may still do it!). You start with a number of fingers up, and then you add one more finger as many times as the second number tells you. More concretely, to perform 2 + 3 you start with 2 fingers up, and add one finger three times. This algorithm is exactly what we are going to follow: repeat the addOne operation as many times as one argument, starting with the other one. The cool trick is that “repeating an operation x times” is exactly the same as “apply the operation as first argument to x”!

const add = a => b => a(addOne)(b)

Once again, does this work? Let’s try our 2 + 3 example:

add(two)(three) = two(addOne)(three)
                = addOne(addOne(three))
                = addOne(addOne(f => x => f(f(f(x)))))
                = f => x => f(f(f(f(f(x)))))

Now that you’ve conquered addition, maybe you feel brave enough to define multiplication!

Enough for today

We are getting closer and closer to a more realistic programming language: at least we have conditionals and bounded loops. However, to define general functions, we need a way to loop, iterate, or recur an unbound number of times. For example, if you try to define factorial only with the tricks you know at this point, you’ll surely fail. Stay tuned for the next post in which we’ll introduce fixed points to solve this issue!