This article was originally published at 47deg.com on January 7, 2021.
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.
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 –
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
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
false 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 == 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
notfunction on Booleans?
const not = (a) => if(a) false else true
// 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)
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
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
x to the original number
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
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!