前言
最近由于在项目中用到了一些模板技巧如SFINAE之类，突然对这类“屠龙之技”产生了浓厚的兴趣。换而言之就是，既然有机会在正常的C艹工程里面使用函数式的技巧，总会让人忍不住拿更复杂的东西练练手。于是在拜读了某位大神的《Brainfuck Compile Time Evaluator》之后，决定自己写几个简单的玩具，比如求解一些经典的递归问题之类，就先从汉诺塔开始吧。
基本实现
这里就不再赘述正常的递归版本实现了，要把它转化成模板，我们首先定义存储目标结果的结构如下：
:::C++
template <typename T, T a, T b>
struct pair {
static constexpr auto first = a;
static constexpr auto second = b;
};
接下来，我们定义一个用于存储结果的序列：
:::C++
template <typename... Args>
struct sequence {};
然后定义一个连接两个sequence生成一个新sequence的方法：
:::C++
template <typename... Args1, typename... Args2>
struct concat<sequence<Args1...>, sequence<Args2...>> {
using type = sequence<Args1..., Args2...>;
};
有了基本的序列存储和连接操作，我们就可以定义汉诺塔的递归求解操作了，如下所示：
:::C++
template <int, typename T, T a, T b, T c>
struct hanoi;
template <typename T, T a, T b, T c>
struct hanoi<1, T, a, b, c> {
using type = sequence<pair<T, a, c>>;
};
template <int n, typename T, T a, T b, T c>
struct hanoi {
using type = typename concat<
typename concat<typename hanoi<n - 1, T, a, c, b>::type,
sequence<pair<T, a, c>>
>::type,
typename hanoi<n - 1, T, b, a, c>::type
>::type;
};
这里我们实际上是先声明模板接口，然后定义两个实例，分别是正常的递归版本，以及递归终止时的偏特化版本。这样编译器就可以正确求解这个问题了。
最后的问题在于如何输出我们的结果，这里同样采取递归的方式来解开参数包：
:::C++
// here we use T for type "sequence<>"
template <typename T>
void print(T) {}
template <typename T, typename... Args>
void print(sequence<T, Args...>) {
std::cout << T::first << "->" << T::second << std::endl;
print(sequence<Args...>());
}
int main(int, const char*[]) {
print(typename hanoi<3, char, 'A', 'B', 'C'>::type());
}
注意到在上述汉诺塔实现中，我们只要保证模板参数a, b, c具有相同的类型，并且都重载了流输出运算符即可。看起来是一种很不错的泛型抽象。完整代码见这里。
编译命令为：g++ hanoi.cpp -std=c++14 -O2 -o hanoi。
优化I
Clang对C++模板推导的最大递归深度有限制，因此默认情况下程序的汉诺塔层数最大只能设置为8，输出结果是255次移动操作。而当我们这样编译程序以后，会发现程序体积达到了惊人的216KB(Clang 8.0, macOS 10.12)。然而，这种静态编译器推导，理想情况下的体积占用应该与我们直接“打表”生成的程序体积相当，即正比于输出结果的长度。只编码输出结果的话绝不应该有这么大。用objdump瞄一眼到底生成了什么，我们会发现里面有255个不同参数类型的print函数。由于每个函数的符号名中都包含了完整的类型名称sequence<...>，而且它的长度随着参数包展开而慢慢变短，所以这巨长的符号名就要占用不少体积，确切滴说空间复杂度是多项式级别的。于是果断用strip去掉这些无用的符号，重新看下体积，会发现减小为80KB。但问题在于，虽然长长的符号名去掉了，但是生成的这几百个函数体还在，所以还是有不小的空间占用。
优化II
接下来我们尝试从代码的层面予以优化。既然这样递归展开参数包导致了过长的参数名，我们可以考虑换一种方式，如果编译期间直接把所有结果推导为静态字符串，最后一起输出呢？这里我们使用std::integer_sequence来解决这个问题，首先定义一个向序列前面追加元素的方法：
:::C++
template <typename seq, typename seq::value_type...>
struct prepend;
template <typename T, T... x1, T... x2>
struct prepend<std::integer_sequence<T, x1...>, x2...> {
using type = std::integer_sequence<T, x2..., x1...>;
};
然后我们就可以定义一个将先前的sequence格式化为std::integer_sequence的方法：
:::C++
template <typename T>
struct seq2str {};
template <typename T>
struct seq2str<sequence<T>> {
using type = std::integer_sequence<typename T::type,
T::first, '-', '>', T::second, '\n'>;
};
template <typename T, typename... Args>
struct seq2str<sequence<T, Args...>> {
using type = typename prepend<
typename seq2str<sequence<Args...>>::type,
T::first, '-', '>', T::second, '\n'
>::type;
};
最后，只要把我们的std::integer_sequence打印出来即可：
:::C++
template <typename T, T... xs>
void print_seq(std::integer_sequence<T, xs...>) {
bool Do[] = { (std::cout << xs, true)... };
(void)Do;
}
int main(int, const char*[]) {
print_seq(typename seq2str<
typename hanoi<8, char, 'A', 'B', 'C'>
::type
>::type ());
}
这样编译出来的程序体积只要48KB，又有了明显的提升。完整的代码在这里。
优化III
上述代码有一个明显的问题，就是失去了泛型的抽象特性。如果我们把hanoi<3, char, 'A', 'B', 'C'>换成hanoi<3, int, 1, 2, 3>，会发现输出结果彻底不正常，用于格式化的箭头等等也被作为int类型来输出了。并且，如果我们查看一下生成的二进制，会发现生成了一个参数类型巨长的，并且函数体也很复杂的print_seq函数，这个函数会调用很多次std::cout。确切滴说，函数符号名的长度以及调用cout的次数与结果字符串中字符的数量相当。所以虽然这样的程序体积已经正比于输出长度了，但其实还应该有进一步优化的空间。
再考察一下我们对pair的定义，会发现我们只要在这里加上一个静态的print()方法就足够了：
:::C++
template <typename T, T a, T b>
struct pair {
static constexpr auto first = a;
static constexpr auto second = b;
static void print() { std::cout << first << "->" << second << std::endl; }
};
然后在打印输出的时候没必要如此麻烦地转成静态字符串，完全可以直接展开类型包调用其print()方法：
:::C++
template <typename... Args>
void print_seq(sequence<Args...>) {
bool Do[] = { (Args::print(), true)... };
(void)Do;
}
int main(int, const char*[]) {
print_seq(typename hanoi<8, char, 'A', 'B', 'C'>::type());
}
这样的话我们会发现，该版本不会失去泛型特性，并且编译后二进制体积也控制得足够好，仅有16KB大小。完整代码在这里。
总结
为什么最后这个版本就有效地控制了二进制体积呢？还是操起objdump，我们会发现它的二进制中仅仅包含\(A^2_3 = 6\)个pair::print()方法，显然是在编译过程中所有出现过的类型排列将pair特化成了这仅有的几个实例；而在函数print_seq中，包含的是255次对这些不同pair::print()方法的直接调用，每一次调用只占5字节。所以，这个版本几乎完全等价于打表，甚至可以说优于打表，也就不难理解为何二进制体积如此之小了。
另外，有人可能会好奇，这类模板技巧主要有哪些用途呢？其实答案是……毫无卵用😂😂😂