(中文) 【C++ 模板元编程入门】在编译期实现 Peano 数

Извините, этот техт доступен только в “中文” и “Американский Английский”. For the sake of viewer convenience, the content is shown below in this site default language. You may click one of the links to switch the site language to another available language.

基本知识

类型的函数

我们都知道模板可以接受类型作为「参数」。同样地我们也可以有「返回值」，从而构造类型的函数。基本的范式是：

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

这就构造了一个名为 Computed 的，接收一个类型参数，返回这个类型本身的函数，用法如 Computed<float>::type，这个类型应当还是 `float`。
为什么要包一层 struct？这是因为 C++ 不支持对 using 的特化。这样的代码是不行的：

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

template<>
using computed<int> = double;

至于为什么不支持，我没有了解。

特化

什么是特化？你可以理解为模式匹配，就像 Haskell 中的写法一样。

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

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

这样当你调用 Computed<bool>::type 时，得到的结果是 bool，而调用Computed<int>::type得到的结果却是double。当然这种匹配是遵循一定规则的，比如更「具体」的特化优先匹配，这跟 Haskell 谁在前谁先试着匹配不太一样。在 Haskell 中就好比：

data Type = Bool | Double | Int

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

实际上有了这层对应，如果你知道怎么在 Haskell 中实现 Peano 数，那么 C++ 中的实现基本就是无脑翻译了。如果你不知道怎么在 Haskell 中实现 Peano 数，那你知道 Peano 数是什么，也能大差不差知道答案了。

Peano 数

Peano 数是什么？Peano 数是归纳定义的自然数，准确地说应该是一个表现形如直觉中「自然数」的公理系统，也就是「自然数」的形式化。这个系统里只有两个符号，Zero——表示 0，以及 Succ——表示后继。那么 1 就是 Succ<Zero>，2 就是 Succ<Succ<Zero>>，以此类推（归纳，其实就是「以此类推」的形式化）。
我们可以在 C++ 中如此表述：

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

那么加法又是什么呢？从例子出发，我们需要定义一个两个类型参数的模板：

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

满足直觉中的运算规律，比如 2+1=3，翻译成 C++ 就是 Add<Succ<Succ<Zero>>, Succ<Zero>>::type = Succ<Succ<Succ<Zero>>>。当然类型之间没有等于号，准确地说应该用 std::is_same<T1, T2>，这其实也是通过特化实现的，比如（示意，非官方实现）：

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;
};

那么如何定义加法呢？对于有限的元素，我们当然可以为每一个实例做特化，比如：

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

也就是打表。C++ 编译器的模板深度一般都是有限的，所以这理论上是可以在实际操作中覆盖所有用例的。但是这明显太傻了。其实加法的定义只需要两条规则就可以覆盖：0 + b = b, (Succ a) + b = Succ (a + b)。翻译成 C++ 就是：

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>
};

注意那个 typename，gcc 并不知道后面那个 ::type 成员是类型还是变量，所以需要 typename关键字的提示。
这就算写完了，你可以测试看看，是不是满足 std::is_same<Add<Succ<Succ<Zero>>, Succ<Zero>>::type, Succ<Succ<Succ<Zero>>>>::value == true（需要 <type_traits> 头文件，或者上面自己写的那个模板（那就不用加 std::）。这么嵌套着写 Succ 太繁琐了，也不方便看，你可以简单地写一个模板来从整数生成类型：

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

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

然后就可以去验证 Add<<peano<2>::type, peano<1>::type>::type 是不是等于 peano<3>::type 了。
至于加减乘除的其他运算，比较啊奇偶性啊其他的函数，只要你懂得了加法，恐怕就不难了。

练习：

在 Peano numbers | Codewars 完成加减乘除、奇偶性和比较大小的撰写，并通过测试。

后记

当然我们还可以进一步「证明」我们印象中的结论，比如加法是满足交换律的，加法和乘法是满足分配率的，等等。这就是后话了。