Implement Compile Time Peano Numbers – A Primer in C++ Template Metaprogramming

Like Love Haha Wow Sad Angry

Fundamentals

Function on Types

We all know that C++ templates can receive types as “parameters”. In the same spirit we could can “return values”s, so that we can form a function. The basic paradigm is the following:

template<class T>
struct Computed {
  using type = T;
}

In this way we constructed a type level function named Computed, with one parameter and result the parameter itself. We use the function as Computed<float>::type, the result being float itself.

Why an extra structwrapper instead of directly defining the “function”? That’s because partialization on using is not allowed. Such codes are invalid:

template <class T>
using computed<T> = T;

template<>
using computed<int> = double;

As of why this isn’t supported by C++, I’m not sure.

Partialization

What is partialization? You can take it as “pattern matching” in Haskell.

template<class T>
struct Computed {
  using type = T;
}

template<>
struct Computed<int> {
  using type = double;
}

Thus, Computed<bool>::type would become bool, while Computed<int>::type would (specially) be double. Certainly, there are a set of rules for the matching process. E.g. the most “specific” case gets matched first. This is somewhat from Haskell, where the first-defined case comes first. The equivalent code in Haskell is:

data Type = Bool | Double | Int

computed :: Type -> Type
computed Int = Double
computed t = t

With this correspondence in mind, if you are familiar with the implementation of Peano numbers in Haskell, then you are ready to do it in C++. If you aren’t, don’t worry. We are going to explore the Peano numbers next.

Peano numbers

What are the Peano numbers? They are natural numbers defined with “induction”. More precisely, it would be a system of axioms that behaves like the “natural” numbers in naive intuition, a.k.a. a possible axiomatization of the natural numbers. There are only two symbols in this system, a Zero for 0, and a Succ for the successive. Thus 1 would be Succ<Zero>, 2 would be Succ<Succ<Zero>>, and so on. This is but the heuristic demonstration of “induction”.

We can represent the two symbols in C++ as follows:

struct Peano {};
struct Zero: Peano {};
template<class T>
struct Succ: Peano {};

Then what is “addition”? Starting from an example. We are need to define a template (type level function) with two parameters:

template<class T1, class T2>
struct Add {
  using type = ???;
}

satisfying the laws in intuition, such as 2+1=3, or Add<Succ<Succ<Zero>>, Succ<Zero>>::type = Succ<Succ<Succ<Zero>>>. Certainly the latter expression is not valid C++, since there is no equality operator for types. Instead, we should use the std::is_same<T1, T2> function, which is predefined in <type_traits>. Or you can implement it yourself, again using partialization. This is a possible implementation:

template<class T, class U>
struct is_same {
  static constexpr bool value = false;
};
 
template<class T>
struct is_same<T, T> {
  static constexpr bool value = true;
};

Then how do we actually implement the addition? We can certainly implement a partialization for each specific case. An example is:

template<>
struct Add<Succ<Succ<Zero>>, Succ<Zero>> {
  using type = Succ<Succ<Succ<Zero>>>;
}

Such exhaustion could actually work, since most C++ compilers only allow a finite level of nested templates (255 for clang by default). But such a “solution” is too silly to accept. Indeed, addition can be covered with only 2 rules: 0 + b = b, (Succ a) + b = Succ (a + b). In C++ they are:

template<class T1, class T2>
struct Add;

template<class T>
struct Add<Zero, T> {
  using type = T;
};

template<class T1, class T2>
struct Add<Succ<T1>, T2> {
  using type = Succ<typename Add<T1, T2>::type>
};

Notice that typename — the compiler doesn’t know whether the ::type is a member type or a member variable, so we need this keyword as a hint.

Hereby we’ve finished the definition of addition. We can do some test to verify if std::is_same<Add<Succ<Succ<Zero>>, Succ<Zero>>::type, Succ<Succ<Succ<Zero>>>>::value == true or so. Such nesting of Succ is somewhat hard to read, so you can simply write a template to generate Peano types from integers:

template<int v>
struct peano {
  using type = Succ<typename peano<v - 1>::type>;
};

template<>
struct peano<0> {
  using type = Zero;
};

Then you can simplify it to Add<peano<2>::type, peano<1>::type>::type and peano<3>::type. The other opeartions like subtraction, multiplication and division can be similarly implemented, which are left as exercises.

Exercises:

Finish the exercises for arithmetic, comparison and parity at Peano numbers | Codewars and pass the tests.

Afterwords

We can further “prove” the assertions in our intuition, such addition is commutative, multiplication is distributive over addition, and so on. We may talk about this later.

Read by: 1,652