Numbers in Computer Scientist's Eye

The fundation of modern mathmatics is the set theory. If you have gone through some mathmatics course, you would find that every definition comes from set directly or indirectly. For example, one possible way of defining natural numbers is to define by powerset.

Firstly, we define that $0$ is the empty set, i.e.,

$$
0 = \emptyset
$$

Then we define the successive relationship by

$$
S(n) = \text{the power set of }n
$$

which means, $1$ is defined by $\{\emptyset, \{\emptyset\}\}$, $2$ is defined by $\{\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}\}$. Such kind of definition is quite beautiful indeed.

However, this is not the only definition, computer scientists also came up with their own languages: the church numerals. This was introduced by Alonzo Church with the lambda calculus. But in this post we are going to introduce in C++.

Suppose that there is some type T. We certainly have functions of this type,

1
2
template<typename T>
using nat = std::function<T(std::function<T(T)>, T)>;

which takes a function of type T->T(in the following context, we would denote the type of functions as (T1, T2, .., Tn) -> Tr, where Ti are the type of the parameters and Tr is the type of return) and a value of T, finally returns a value of T. The type of itself can be noted as (T->T, T)->T.

Now, we are going to define that, functions of this types are natural numbers! Firstly, we are going to define zero as below,

1
2
3
4
template<typename T>
T zero(std::function<T(T)> f, T _) {
return _;
}

which looks like a identity fucntion, and has nothing to do with the f. Then we are going to define one,

1
2
3
4
template<typename T>
T one(std::function<T(T)> f, T _) {
return f(_);
}

See it? One is simply call the function f once before the return. I think you can guess the definition of two,

1
2
3
4
template<typename T>
T two(std::function<T(T)> f, T _) {
return f(f(_));
}

Ahh, we just called the function f twice! Now we can give the definition of successor:

1
2
3
4
5
6
template<typename T>
nat<T> succ(nat<T> n) {
return [n](std::function<T(T)> f, T _) {
return one(f, n(f, _));
};
}

Literally, a successor wraps f around its predecessor exactly once. Then, we can now define summation!

1
2
3
4
5
6
template<typename T>
nat<T> sum(nat<T> n, nat<T> m) {
return [n, m](std::function<T(T)> f, T _) {
n(f, m(f, _));
};
}

If you understand the definition of successor, then you should understand this easily: wraps f around m for n times.

Previous definition is somewhat straightforward, and we didn’t find the need for type generalization, right? But we would find it necessary if we want to define multiplication and exponential. First let us deal with multiplication.

From our knowledge of math, multiplication of m and n, is add n by m times. Translated into our words, it is wrapping n around something for m times. How can we achieve this without the invocation of iteration? The point is, we can pass n into m in the place of f.

1
2
3
4
5
6
7
8
template<typename T>
nat<T> product(nat<T> n, nat<T> m) {
return [m,n](std::function<T(T)> f, T _) {
return m([n, f](T _) {
return n(f, _);
}, _);
};
}

and the answer to the exponential is left for readers as an exercise: The code is presented, but the meaning of it is left to you.

1
2
3
4
5
6
7
8
9
10
template<typename T>
nat<T> exponential(nat<T> n, nat<std::function<T(T)>> m) {
return [n, m](std::function<T(T)> f, T _) {
return m([n](std::function<T(T)> f) {
return [n, f](T _) {
return n(f, _);
};
}, f)(_);
};
}
Share