Let's talk about numbers. Not about the "regular" numbers we all know, but about another representation of numbers – numbers in Church Encoding.
Church Encoding is a way of representing natural numbers as Higher‐Order Functions. Higher‐order function (HOF) is a function that receives functions as an input or returns a function as an output. They are functions that operate on functions.
Now that we understand what higher‐order functions are, let's define our encoding:
The encoding will match each natural number to a function, named , which works in this way:
receives two parameters: The first is a function name , which maps some element of type to some element of type . The second parameter is a value of type , named .
The function will return the outcome of operating on times in a chain. I.e. – the first iteration will run on , the next iteration will run on and so on, times overall. If we want to write it formally, we will write it this way:
To make things less abstract, let's look at some examples.
Let's choose as , and so, in the next examples, the type we mentioned earlier, will be the Real Numbers ().
- is the function that will be matched, by Church Encoding, to the natural number . The result of is . Why? Because we applied to zero times overall, I.e., we didn’t apply at all, and therefore we stayed with the original value, . Generally speaking, the function returns its second parameter for any function and any type .
- The result of is .
- The result of is .
We now understand how the encoding maps a natural number to a HOF. Let's mark the function which maps a natural number to its corresponding HOF, as (E stands for encoding). We should now define the inverted mapping, from a HOF (that is guaranteed to represent a natural number in Church Encoding) to a natural number. Fortunately, the opposite direction is way simpler. We have a function named . We know it represents some natural number , but we don't know which number is. Therefore, we will calculate for as , and as . is going to apply to , times overall, and therefore our result will be as a result!
The mapping works in both directions! 🥳
We will name a HOF that was returned by a Church function, this is not a formal term, but it will make my sentences much shorter. 🙃 The inverted function, which maps a Church function to its original natural number, will be named (D stands for decoding).
Now, let's define addition and multiplication on Church Numbers. The operations should preserve the encoding. That means, we want to fulfill this equation:
The notations here are a bit tricky:
The plus sign on the left side represents an addition between two natural numbers. The sum of this addition is mapped to a Church function by .
On the right side, we apply to each number and separately, and then sum the results – the Church functions that represent and . The addition on the right hand isn't the regular addition for natural numbers; it's an addition between Church functions. Therefore, we'll define it as follows:
The result of should be the function , the Church function which takes two parameters, and , and returns applied to , times. Similarly, we will define the multiplication between Church functions: the result of will be .
In my opinion, this is a beautiful way to represents the natural numbers. The thing that Alonzo Church wants to show in this encoding is that we can solve any computable problem by using only functions as primitive types.
We shouldn't use this representation in practice, as it is much cheaper to represent numbers in memory as bits than as functions.
But it isn't going to stop us from doing so, as it will help us understand how the addition and the multiplication, which we defined earlier, actually work.
We are going to model our encoding in Haskell, which is an excellent language for this purpose since functions are primitive types in it, and it is straightforward to use it for writing functions which operate on functions.
Let's create a new type, named
CNumber to hold a Church function. It's not actually a new type, but a wrapper for a higher‐order function that receives two parameters: a function which maps value from to a value from , and a value of . This can be any type, so is a generic parameter (or a type parameter) of this wrapped function. This is the way to write that in Haskell:
The first line allows us to use the keyword
forall, for defining an advanced generic function. On the second line, we define
CNumber, saying its constructor is named
Nr and that it receives a higher‐order generic function (which its generic parameter is
t), of the kind we mentioned earlier.
I will remind you that in Haskell, the type
a -> b -> c represents a function that takes a value of type
a and a value of type
b as its parameters and returns a value of type
The type we have created above,
CNumber, is a container for a Church function. Please note that it doesn’t mean that every value of type
CNumber is a Church function; it merely means that the container will match every HOF that receives a function and a value and returns a value.
Let's define , and :
As we said earlier, , or
zero, doesn’t apply
x at all, and returns the . , or
one returns the result of applying
x once, and
two returns the result of applying
x twice in chain.
Assuming we have a
CNumber that is guaranteed to hold a Church function, how can we recover the natural number it represents? We've already figured that out earlier, let's write it in Haskell:
We used the function that the
CNumber holds to apply
(+1) – which corresponds to that we talked about earlier – and
0, and so, we received the natural number that this Church function represents.
Now we'll define the addition function,
but before we do that, let's define a simpler function, named
succ, that will help us implement the
succ increases any
succ zero returns
CNumber that represents ),
succ one returns
two, and so on.
succ receives a
CNumber that represents ,
we define the result as a new function, which takes a function
f and a value
The new function is going to use
a (the function that the given
CNumber holds) to apply
x times, and then apply
f to the result once again. And so, we get the
CNumber that represents .
An aside note: if you want this code to compile, you should replace
import Prelude – which usually appears on the top of the code – with
import Prelude hiding (succ), so the built-in function named
succ doesn't collide with ours.
Now, it will be much easier to define addition! We want a function named
add that receives two values of type
CNumber and returns a
CNumber that represents the addition of the Church functions that the parameters hold.
We assume that
b are Church functions that represents and , respectively. The function we wrote will use
b to apply
x times, and then use
a to apply
f to the result more times. Overall, the result function applies
x times, as we aimed to.
But we can do better! We have the function
a, which knows to apply a certain function times. Let's use it more smartly. We can apply
Nr b (the
CNumber that holds a Church function that represents ) times, and so, we will get the
CNumber that holds a Church function that represents .
Yet there is an even a shorter way to write it, using partial applying:
However, we aren’t trying to make our code shorter, but readable and simpler. 😊
All we have left to do is to define the multiplication function! Note that it's a great exercise, and in my honest opinion, it is worthwhile for you to solve it by yourself. Of course, if you prefer, you can go on and read my solution 🙃
We want to use
a, in the same way we used it earlier, for calculating the result of the product of
Nr a and
Again, we assume that
b are Church functions that represents and , respectively. The value of
add (Nr b) is a function that receives a
CNumber and adds
Nr b to it. We use
a to add
Nr b to
zero, times overall. As
b is a Church function which represents , the total result will be a
CNumber that holds a Church function which represents .
In the same way we can implement a power of Church functions!
And we can go and define Tetration, but I think you get the idea. 😊