## Church Numbers

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 $n$ to a function, named $C_n$, which works in this way:

$C_n$ receives two parameters: The first is a function name $f$, which maps some element of type $T$ to some element of type $T$. The second parameter is a value of type $T$, named $x$.

The function $C_n$ will return the outcome of operating $f$ on $x$ $n$ times in a chain. I.e. – the first iteration will run $f$ on $x$, the next iteration will run $f$ on $f(x)$ and so on, $n$ 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 $f(x)=2*x$ as $f$, and so, in the next examples, the type $T$ we mentioned earlier, will be the Real Numbers ($\R$).

- $C_0$ is the function that will be matched, by Church Encoding, to the natural number $0$. The result of $C_0(f,3)$ is $3$. Why? Because we applied $f$ to $3$ zero times overall, I.e., we didn’t apply $f$ at all, and therefore we stayed with the original value, $3$. Generally speaking, the function $C_0$ returns its second parameter for any function $f$ and any type $T$.
- The result of $C_1(f,3)$ is $f(3)=2*3=6$.
- The result of $C_2(f,3)$ is $f(f(3))=f(2*3)=2*(2*3)=12$.

We now understand how the encoding maps a natural number to a HOF. Let's mark the function which maps a natural number $n$ to its corresponding $C_n$ HOF, as $C_E$ (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 $C_h$. We know it represents some natural number $h$, but we don't know which number $h$ is. Therefore, we will calculate $C_h(f,x)$ for $f(x)=x+1$ as $f$, and $0$ as $x$. $C_h$ is going to apply $x+1$ to $0$, $h$ times overall, and therefore our result will be $1*h=h$ as a result!

The mapping works in both directions! 🥳

We will name a HOF that was returned by $C_E$ 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 $C_D$ (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:
$C_E(n+m)=C_E(n)+C_E(m)$.
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 $C_E$.

On the right side, we apply $C_E$ to each number $n$ and $m$ separately, and then sum the results – the Church functions that represent $n$ and $m$. 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 $C_n+C_m$ should be the function $C_{n+m}$, the Church function which takes two parameters, $f$ and $x$, and returns $f$ applied to $x$, $n+m$ times. Similarly, we will define the multiplication between Church functions: the result of $C_n*C_m$ will be $C_{n*m}$.

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 $T$ to a value from $T$, and a value of $T$. This $T$ can be any type, so $T$ 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 `c`

.

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 $C_0$, $C_1$ and $C_2$:

As we said earlier, $C_0$, or `zero`

, doesn’t apply `f`

to `x`

at all, and returns the $x$. $C_1$, or `one`

returns the result of applying `f`

to `x`

once, and `two`

returns the result of applying `f`

to `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 $f(x)=x+1$ 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 `add`

function.
`succ`

increases any `CNumber`

by `one`

. I.e., `succ zero`

returns `one`

(the `CNumber`

that represents $1$), `succ one`

returns `two`

, and so on.

Given that `succ`

receives a `CNumber`

that represents $n$,
we define the result as a new function, which takes a function `f`

and a value `x`

.
The new function is going to use `a`

(the function that the given `CNumber`

holds) to apply `f`

to `x`

$n$ times, and then apply `f`

to the result once again. And so, we get the `CNumber`

that represents $n+1$.

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 `a`

and `b`

are Church functions that represents $n$ and $m$, respectively. The function we wrote will use `b`

to apply `f`

to `x`

$m$ times, and then use `a`

to apply `f`

to the result $n$ more times. Overall, the result function applies `f`

to `x`

$n+m$ times, as we aimed to.

But we can do better! We have the function `a`

, which knows to apply a certain function $n$ times. Let's use it more smartly. We can apply `succ`

to `Nr b`

(the `CNumber`

that holds a Church function that represents $m$) $n$ times, and so, we will get the `CNumber`

that holds a Church function that represents $n+m$.

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 `Nr b`

.

Again, we assume that `a`

and `b`

are Church functions that represents $n$ and $m$, 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`

, $n$ times overall. As `b`

is a Church function which represents $m$, the total result will be a `CNumber`

that holds a Church function which represents $n*m$.

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. 😊