模板元编程

在前一篇文章中介绍了使用lambda calculus构造自然数以及相关运算。在所有的图灵完备的语言中，我们都可以进行类似的行为。之前学习C++的时候，看过一些模板元编程的内容，所以决定用C++重写一遍，作为练习。

说明

模板元编程同样是图灵完备的，例如我们可以用如下的方式构建一个函数

template<typename x>
struct func{
    using ret=x;
 };

尖括号中的x即为输入，func<x>::ret就是我们的返回，不过这里都是类型。在后面我们可以看到非类型的输入和返回。
然而本人才疏学浅，并未找到像lambda演算中返回高阶函数的对应C++代码，所以只能换一种方式。
以下是我们定义0，1，2:

struct zero{
};
template<typename Nat>
struct succ{};  //后继
using one=succ<zero>;
using two=succ<one>;    //succ<succ<zero>>

接下来是加。

template<typename m,typename n>
struct plus;
template<typename Nat0,typename Nat2>
struct plus<succ<Nat0>,Nat2>{
    using ret=typename plus<Nat0,succ<Nat2>>::ret;
};
template<typename Nat>
struct plus<zero,Nat>{
    using ret=Nat;
};

是的，你没有看错其实就是模式匹配。当然这里我们用到的技术叫做模板偏特化和SFINAE。等价Haskell代码如下：

plus :: Nat -> Nat -> Nat
plus zero n = n
plus (succ m) n = plus m (n+1)

减

emplate<typename m,typename n>
struct minus;
template<typename Nat1,typename Nat2>
struct minus<succ<Nat1>,succ<Nat2>>{
    using ret=typename minus<Nat1,Nat2>::ret;
};
template<typename Nat>
struct plus<Nat,zero>{
    using ret=Nat;
};

乘法

template<typename m,typename n>
struct multi;
template<typename Nat0,typename Nat2>
struct multi<succ<Nat0>,Nat2>{
    using ret=typename plus<typename multi<Nat0,Nat2>::ret,Nat2>::ret;
};
template<typename Nat>
struct multi<zero,Nat>{
    using ret=Nat;
};

乘方。

template<typename m,typename n>
struct exp;
template<typename Nat0,typename Nat2>
struct exp<Nat0,succ<Nat2>>{
    using ret=typename multi<typename exp<Nat0,Nat2>::ret,Nat2>::ret;
};
template<typename Nat>
struct exp<Nat,zero>{
    using ret=Nat;
};

更多

之前提到模板参数可以不是类型，例如最经典的阶乘

template<int x>
struct fact
{
    static const int ret=fact<x-1>::ret*(x-1);
};
template<0>
struct fact
{
    static const int ret =1;
};
int x=fib<5>;   //x=120

关于模板元编程还有许多内容，像构造if，while之类的在看了上面的例子之后想必也是手到擒来。等到下次我找到什么新的有意思的内容再来补充。