# Doing numbers without the numbers

Numbers are abstractions invented by humans to aid with various activities, mainly counting, and sometimes recreation. While the “three” might be the number of coins in my pocket right now, the number “three” is in itself an abstract entity, worthy of study in its own right. It is defined as the successor to the integer “two”. It is, in general, really hard to define what data is. According to one definition, we define data in terms of operations possible on it, and certain constraints on these operations, like an axiomatic system. Note that under this scheme, the actual representation of the data object in question is irrelevant: only the external operations on it and a set of properties obeyed by those operations is enough.

For example, let’s consider natural numbers (0, 1, 2, 3..) as data objects. No matter how we represent these numbers on a computer, we would like basic arithmetic properties of numbers to hold, like addition and multiplication of natural numbers behaving normally, the presence of a total ordering among the numbers, etc.

On most computers, these numbers are simply represented in their binary form,
usually as 32 or 64 bits. However, like I mentioned above, as long as the
expected operations on natural numbers are available and obey certain
properties, the representation does not matter. One cool way of encoding numbers
is the Church encoding, due to Alonzo Church. In the simplest form, **we
encode a number as the number of applications of a given function $f$**. For
example, $0$ is encoded as *no* application, $1$ is encoded as just one
application of $f$, while an arbitrary natural number $n$ is encoded as the
function composition $f^n$. Let’s try this out in some Perl 6 code:

So, for example, `two($foo)`

is a function that, when called with some parameter
`$x`

, will apply `$foo`

twice, i.e., compute `$f($f($x))`

.

Of course we don’t want to write out all numbers as functions, so we just define
`zero`

, and a successor function, which transforms a Church encoded natural
number to the next higher natural number.

The key here is the bit `$f($n($f)($x))`

, which is where the “increment” happens
by applying `$f`

one more time:

- The expression
`$n($f)`

is a function that when called with`$x`

, will apply`$f`

for`$n`

times, to compute $f^n\left(x\right)$ - i.e.,
`$n($f)($x)`

*is*the result of applying the composition obtained by repeating`$f`

for`$n`

times to`$x`

. - Next, we simply add another
`$f`

call to the chain, thus ending up with`$f($n($f)($x))`

.

Note that the returned value is still a function that takes a function `$f`

, and
returns another function of the variable `$x`

, which in turn applies `$f`

for
$n+1$ times to `$x`

. This is consistent with the interface we have for `zero`

,
and more importantly, demonstrates the use of closures: the function of `$x`

*captures* its environment, which contains `$f`

. Also, the function of `$f`

(the
outer lambda returned by `successor`

) captures the function `$n`

as it was when
provided as an argument to `successor`

.

To make it even clearer, let’s try to come up with a mechanism to convert from
the Church representation to normal Perl 6 numbers. We want to invent a function
`$g`

and a value `$a`

, that when used with any of our Church encoded numbers,
give us the corresponding integers. Concretely, we want:

One choice could be to use `$g = { $_ + 1 }`

, i.e., the increment function, with
`$a = 0`

:

Once we understand this function, the rest of the operations are easy to derive:

The predecessor function, however, is a bit more involved: given a numeral $n$,
that applies $f$ for $n$ times to an initial value $x$, we want to derive a
function that applies $f$ *one less time*. While there are multiple ways of
doing this, the easiest to understand for me was to apply $n$ to *transformed*
versions of $f$ and $x$. Let’s first define a function $g$ that takes a *pair*
$\left(a, b\right)$ and if $a=0$, returns $\left(0, f(a)\right)$, and if $a=1$,
returns $\left(0, a\right)$. In essence, the first element of the pair tells $g$
if it should *skip* applying $f$ to the second element. Here’s $g$:

Note that if $g$ is composed for $n$ times and applied to a pair $\left(1, x\right)$, we will in the end have the pair $\left(0, f^{n-1}\left(x\right)\right)$!

e.g.,

Now Perl 6 of course has lists which we could use to represent our pairs, but
let’s use an alternate representation in the spirit of this post. A pair is
a data object that stores two other objects, and provides the two functions
`first`

and `second`

for accessing those objects. This can be implemented like
so:

To take things even further, let’s also encode the boolean type, and implement a conditional function:

Now let’s implement the predecessor function, finally: