12/26/2019 trivial-languages

# 第 0 节 - 前言

# 为什么要写这个？

近日沉迷实现一个类型安全的 EventEmitter (opens new window)

alt

某日晚上突然顿悟了一些东西，想要写下来。

什么？可能看不懂？~~0.5 分警告~~

前排提示：这套文章十分主观，绝大部分都来自于笔者自己的编码经验。所以，如果你不喜欢，~~那你来打我啊，反正我也不会改。~~

# 前言

本文假设读者已经有如下的 C++ 语言基础:

class/struct/template 等关键字的拼写
知道啥是模版，啥是继承，啥是多态
有一个支持 C++11/14/17 的编译器（不用 clang 的都踢了）
爱思考，会谷歌，能面向 StackOverflow 编程（用百度的都踢了）
没了

# 计划的内容

模板基础知识
模板类型推导
模板匹配规则
模板元编程中的函数式思想
编译期计算
模板类型擦除
写出优雅的模板元编程代码（很重要！！！）
实战项目包括
- 编译期斐波那契数列
- 实现一个最 naive 的 std::any
- 编译期快速排序
- 类型列表
- Event Emitter

按照预期设想：这些内容会被均匀（可能？）分散在每个文章中，她们之中蕴含的思想将会贯穿本系列的所有文章。

# 作者联系方式

邮箱 imkiva@icloud.com
漂流瓶 (opens new window)

# 致谢

感谢好友 mikecovlee (opens new window) 不厌其烦回答我的问题
感谢好友 newNcy (opens new window) 问了上面截图的那个问题

# 模版元编程是什么？有什么用？

断句：模版/元编程

所谓「元编程」，就是一种「抽象的编程」。我认为，对程序的抽象其实就是找出程序之间的相似之处，然后用统一的逻辑将其表示出来，而对于程序之间的不同之处，我们用一种手段将他们隐藏起来。在 C++ 中，这种手段就叫做「模版」，表示统一的逻辑的方式就叫「元编程」。

C++ 标准库是「泛型编程（Generic Programming）」的实践，这意味着数据和算法是分开的。算法最终需要的不过就是数据的比大小而已，所以我们需要用模版将算法的逻辑「抽象化」，比如我们知道标准库里有这样的算法:

template <class T>
const T& min(const T& a, const T& b)
{
    return a < b ? a : b;
}

这里的 T 我们不用管是什么，我们只要知道，这个算法会返回二者中较小的一个，而至于怎么比较 a 和 b，那跟我 min 有什么关系？

所以在我的理解中，「模版」给了我们抽象算法的能力，算法是通用的，但仅仅只靠「模版」来抽象具体类型却不足以帮助我们写出通用的算法逻辑，我们还需要更强大的功能，来帮我们设计出更通用、更友好、更健壮、错误信息更可读的代码，于是就有了「元编程」。

# 花费大量时间学习模版元编程，值得吗？

不值得，你可以关掉这个页面了。

那我为什么要学？我只是觉得好玩罢了。

# 为什么歧视 MSVC？

我不是，我没有，你不要乱说啊。

# 模版参数命名约定

模版参数是指 template <typename T> 里的 T，其定义域为所有类型。给这个参数取个好名字跟禁用 Windows 自动更新一样重要。

所以对于特定的一些模版参数，我的习惯是这样

普通的类型: T, U, A, B, C, From, To, ...
Callable 类型 (opens new window): F, Callable, Handler, ...
函数参数类型: Args, ArgsT, ...
函数返回值类型: R, RetType, ReturnType, ...
变长参数: Ts..., As..., Xs..., ...
~~其他的看心情~~

# 暴论一：模版元编程是另一门编程语言

模版元编程是借助了 C++ 语法的另一门运行在编译期的编程语言，它的作用是辅助 C++ 程序设计。

说 TMP (Template MetaProgramming, 模版元编程) 是另一门编程语言，是因为你可以在 TMP 中见到一些好康的语法，以及神似函数式语言的一些写法。

# 暴论二：类型即数值

作为一门编程语言，那么就有这门语言操作的数据。在 C++ 中我们操作的数据有各种类型，比如 int, float, std::string；类似的，在 TMP 中，我们操作的数据就是上面提到的那些类型，比如下面的代码：

template <typename T>
using S = std::remove_reference_t<T>;

这里先解释一下，上面这段代码的意思是：

S 是一个类型，T 也是一个类型，并且 S 取决于 T

如果 T 是任意一个类型 U 的引用类型 U & (即 T == U &)，则 S 为 U

如果不是，则 S 为 T。

举几个更直观的例子，

T	S
int &	int
const int &	const int
...	...
U &	U

这个像不像我们小学二年级时学过的函数值表？

不妨更深入一步，之前已经说过 TMP 是一门编程语言，那么我们就可以认为上面那个 S 是一个函数，S 需要一个参数 T，其返回值记为 S<T>。

写成伪代码的形式就是这样

S<T> {
    return std::remove_reference_t<T>;
}

或者写作

S<T> {
    if (T == U &) {
        return U;
    } else {
        return T;
    }
}

~~有内味了，有内味了。~~

（什么？你说要把尖括号换成圆括号你才看得出这是个函数？踢了！

在一些资料书中，上面的模版 S 也被叫做元函数 (metafunction)，可见我的暴论都没说错。

但是在后续的文章中，我依然会把类型和数值分开称呼（原因就在下面），但你得知道 TMP 是能把类型当作数值一样来做运算的。

那么 TMP 能不能操作 C++ 里的那些 int, flaot... 呢？当然可以！比如：

/* 接受一堆类型作为参数 */
template <typename ... Ts>
struct T {};

/* 接受一堆 int 作为参数 */
template <int ... Is>
struct I {};

void foo() {
    using t1 = I<1, 2, 3, 4>;
    using t2 = T<int, char, short>;
}

怎么样？现在看出那个 typename 的意思了吗？是不是相当于「类型的类型」呢？

怎么样？那个 using 是不是觉得很微妙？像不像是在定义一个「常量」？（using 定义出来的是类型，which is immutable）

# 暴论三：TMP 没有停机性检查

啥叫停机性检查？我们写个代码来看看：

template <size_t A, size_t B>
struct Add {
    static constexpr size_t result = Add<A + 1, B - 1>::result;
};

template <size_t A>
struct Add<A, 0> {
    static constexpr size_t result = A;
};

Add<A, B> 可以在编译期计算 A + B，比如

static_assert(Add<1, 2>  ::result == 3,   "You wrote a bug");
static_assert(Add<50, 99>::result == 149, "You wrote a bug");

但是如果你试着把终止条件去掉，让 Add<A, B> 成为一个死循环，让代码长这样：

template <size_t A, size_t B>
struct Add {
    static constexpr size_t result = Add<A + 1, B - 1>::result;
};

我们再试着运行同样的代码，编译器会给出这样的错误：

fatal error: recursive template instantiation exceeded maximum depth of 1024

看到没？C++ 编译器不会检查上面的代码是否能停机，而是限制模版展开次数。

事实上，从错误信息可以看出，就算终止条件存在，当 Add<A, B> 展开次数超过 1024 次时，编译器一样会报错。

这也限制了一些特定的需求用 TMP 是无法完成的。（后文会详细讨论）但这也让一些骚操作成为可能。

# 暴论四：TMP 是 duck-typing

啥是 duck-typing（鸭子类型）？~~你 tnd 不会谷歌吗？~~

简单的说，如果有这样的代码

template <typename Duck>
void meow(Dock &&duck) {
    duck->meow();
}

相信大家都能看出来，不管这个 Duck 在实例化的时候被替换成了什么类型，只要这个类型提供了 meow() 的成员方法，这段代码就能通过编译。

这就是所谓的

当看到一只鸟走起来像鸭子、游泳起来像鸭子、叫起来也像鸭子，那么这只鸟就可以被称为鸭子

# 暴论五：TMP 是动态类型和静态类型的混合语言

举个例子就行啦:

template <typename T>
struct happy {
    using type = int;
};

template <>
struct happy<float> {
    static constexpr int type = 1;
};

上面的例子里，我们为 happy 特化（下一章会讲）了 float 类型，于是只有 happy<float>::type 本身是一个值，而不是一个类型，其余的 happy<...>::type 都是一个类型。

那么现在我们有一个元函数如下定义:

template <typename T>
using get_happy = typename happy<T>::type;

乍一看没什么问题，但当你把 float 作为参数传递给 get_happy 的时候，编译器无疑会抛出一个编译错误。

error: no type named 'type' in 'struct happy<float>'

这个问题的原因我们会在后续的文章中慢慢解释...这里只能说是因为：每个特化的分支中的定义是独立的。

其次还能从此处需要手动指定 typename 看出来，如果编译器能从 happy 的泛化版本中推断出 happy<...>::type 是类型而不是值，那么在 get_happy 中就不需要手动指定了，因为泛化版本中的 type 和特化版本中的 type 应该是同样的东西（都是类型或者都是值），但实际上并不是。所以我们可以知道：TMP 在对待类型参数上跟动态类型类似（实际上就是）。

那么静态类型表现在何处呢？

自然是直接将数值作为模板参数传递的时候啊！

# 技巧一：using 可以少打一按一堆键盘

这也是 C++ STL 里广泛采用的方法，我们知道 std::remove_reference 要这样用:

using type = typename std::remove_reference<T>::type;

着看着很不爽，因为 typename 和 ::type 完全就是多余的，体现不出核心要素，所以我们可以为这个函数写一个额外的辅助函数，比如:

template <typename T>
using remove_reference_t = typename std::remove_reference<T>::type;

这样就可以直接:

using type = remove_reference_t<T>;

同理，如果是值，我们可以这样:

template <typename T, typename U>
static constexpr bool is_same_v = std::is_same<T, U>::value;

秒啊！

切记，请保持「一致性」：

如果为类型取别名，请使用 _t 后缀
如果为值取别名，请使用 _v 后缀

# 技巧二：统一「返回值」的名字

就像上面的 std::remove_reference 一样，它的返回值的名字叫做 type：

template <typename T>
struct identity {
    using type = T;
};

这里 identity 函数返回的是一个类型，所以我们给返回值取名叫做 type，同理，如果我们有一个函数返回的是一个值，我们一般给它取名 value：

template <typename T, T t>
struct identity_value {
    static constexpr T value = t;
};

所以，这里也需要保持「一致性」

如果返回的是一个类型，请使用 type 作为名字
如果返回的是一个值，请使用 value 作为名字

我最不推荐使用那种有歧义的名字，比如 result，因为 TMP 是动态类型的语言，而 result 这个词太过于笼统，不能从名字看出返回的东西到底是个类型还是一个值。

~~不过嘛，你要想用，我也没办法啊。我总不能顺着网线去打你吧！~~

# 总结

在与 TMP 打交道的过程中，请一定要记住这几点暴论，尤其是「类型即数值」，这点真的很！重！要！

# 参考文献

[1] wuye9036, CppTemplateTutorial (opens new window)
[2] Wikipedia, Duck Typing (opens new window)

# 第 1 节 - 「泛化」和「特化」

# 泛化

我们有一个做除法的静态成员函数(~~别问我为什么是静态成员函数而不是全剧函数~~)：

class Div {
    static double doit(double lhs, double rhs) {
        return lhs / rhs;
    }
}

但是这个函数只能对 double 类型做除法，现在我们需要将其中的算法逻辑抽象出来，让它能对所有类型都做除法，于是我们引入模版参数 T，来代表一个任意类型。

template <typename T>
class Div {
    static T doit(T lhs, T rhs) {
        return lhs / rhs;
    }
}

好了，现在我们的 Div::doit 就能应用到任意支持「除法」运算的类型上了。（这里强调支持「除法」运算是因为如果 T 不是原始数据类型并且也没有重载正确的 operator/ 时，编译器会报错）。

如你所见，上面的过程就叫做「泛化」。我们说泛化后的模版类 Div 是「原型」，也叫 Div 的「泛化版本」。

~~（其实我非常不想扯名词的，但后文需要，没办法~~

# 特化

在上面的例子中，当 T 是 int 的时候，而 rhs 又恰好为 0，那么上面的代码就会出现运行时异常。

所以我们可以为 int 类型特化 Div 来处理这种特殊情况：

template <>
class Div<int> {        /* 为 int 类型特化 */
    static int doit(int lhs, int rhs) { 
        if (rhs == 0) {
            printf("Divide by zero\n");
            return 0;
        }
        return lhs / rhs;
    }
}

void foo() {
    Div<int>::doit(1, 0);    /* Divide by zero */
    Div<double>::doit(1, 2); /* 0.5            */
}

等等！那个 template <> 是什么玩意？！ ~~你哪来这么多问题！~~，在模版匹配规则的地方会详细讲这个东西。

现在可以理解为 「Div 在为 int 特化后，不再需要额外的模版参数」，那既然不需要模版参数了，那能不能去掉这一行呢？

答案是不行，因为这个特化依赖于原型。关键字 template 相当于告诉编译器：这是一个模版类的特化版本，不是独立存在的一个类。

让「原型」在遇到不同的类型时执行不同的代码，从而做到处理特殊情况。这种方法就叫做「特化」，更准确的说，

特化（specialization）是根据一个或多个特殊的整数或类型，给出模板实例化时的一个指定内容。

特化，就是处理特例。我们在数学中学过「斐波那契数列」，这个数列满足下面的关系：

F(0) = 1
F(1) = 1
F(n) = F(n - 1) + F(n - 2), n >= 2

它有两个特例，当 n == 0 或 n == 1 时，F(n) 的值恒为 1。

显然, F(0) 和 F(1) 就是在处理斐波那契数列中的特例，这就是「特化」。

# 实战：编译期斐波那契数列

~~真就说什么来什么~~，我们来整一个利用 TMP 特性实现的编译期斐波那契数列。

我们先把一般情况写出来，也就是「原型」：

/* 这里有疑惑的自觉看上一章 */
template <int N>
struct Fib {
    /* 递归调用元函数 Fib 计算第 N 项的值 */
    /* constexpr 会「请求」编译器在编译期试着对这个值求值 */
    static constexpr int value = 
        Fib<N - 1>::value + Fib<N - 2>::value;
};

然后再处理 N 为 1 和 2 时的特殊情况，注意！！！我要特化了！！！

处理 $F_{0} = 1$

template <>
struct Fib<0> {
    static constexpr int value = 1;
};

处理 $F_{1} = 1$

template <>
struct Fib<1> {
    static constexpr int value = 1;
};

然后我们来测试一下：

static_assert(Fib<20>::value == 10946, "You wrote a bug");

嗯！我没写出 bug！

# 偏特化

后面讲到模版匹配规则的时候会再详细来说。可以先看参考文献里的资料。

# 参考文献

[1] wuye9036, CppTemplateTutorial (opens new window)
[2] en.cppreference.com, constexpr specifier (since C++11) (opens new window)
[3] en.cppreference.com, partial template specialization (opens new window)

# 第 2 节 - 模板匹配规则

# 导入

上篇里讲到了特化，那么这里我们就从特化的更多应用开始吧~

比如我们需要实现这样的一个功能，我们需要为类型编号. 即将类型映射到一个整数上，比如 int 类型编号为 0，float 类型编号为 1， double 类型编号为 2，指针类型编号为 3 ...

看下面的代码:

template <typename T>
struct id;

这是我们简单的 id 函数，现在它还没有实现。但别担心，下一步我们就要为我们支持的类型进行特化了。

比如，将 int 类型编号为 0

template <>
struct id<int> {
    static constexpr size_t value = 0;
};

以此类推，我们能特化更多:

template <>
struct id<float> {
    static constexpr size_t value = 1;
};

template <>
struct id<double> {
    static constexpr size_t value = 2;
};

这时候，你可能就问了，如果我要映射 int * 怎么办？好说！特它！

template <>
struct id<int *> {
    static constexpr size_t value = 3;
};

问题似乎解决了。

但你有一天忘记了你的具体实现，你只记得你曾经写过一个元函数，可以将类型映射为整数，于是你写下了 id<double *>::value 这样的代码。最后你得到了这样的错误

error: no member named 'value' in 'id<double *>'

你一看~原来是没有为 double * 特化实现，于是你又写下了这样的代码

template <>
struct id<double *> {
    static constexpr size_t value = 3;
};

然后你仔细一想，发现事情不简单：难道我要为所有指针类型都手动特化吗？

当然不用！还记得之前我们说过 所有类型 这一概念吗？没错，这可以用一个模板参数来表达！此处不妨命名为 P 吧（P 表示 pointer），于是你拿起键盘，手起刀落，写下这样的代码:

template <>
struct id<P *> {
    static constexpr size_t value = 3;
};

嗯！我们为所有类型 P 的指针类型 P * 特化了 id 函数，让 id 函数对所有指针类型的参数都返回 3.

但是...编译器可不这么认为:

error: 'P' was not declared in this scope

嗯？P 没有定义是什么回事？难道编译器不知道这个 P 表示所有类型吗？

你想的没错，编译器还真不知道！

在这里，编译器认为这个 P 应该是某个实际存在的类型，比如 struct P {} 这样的。但是我们的意思是让 P 表示所有类型，所以我们需要这里的 P 是类型参数，which 我们必须手动告诉编译器，就像这样:

template <typename P>
struct id<P *> {
    static constexpr size_t value = 3;
};

在上面的 template 里面加上一条 typename P 就行了，这就像在做一个声明：我这里需要用到一个参数 P，这个 P 是一个类型名。

然后我们再把代码放一起来看:

template <typename T>
struct id;

template <>
struct id<int *> {
    static constexpr size_t value = 3;
};

template <typename P>
struct id<P *> {
    static constexpr size_t value = 3;
};

然后我们再写一点测试代码

static_assert(id<int *>::value == 3);      /* ok */
static_assert(id<char *>::value == 3);     /* ok */
static_assert(id<double *>::value == 3);   /* ok */

嗯，都正确。

现在问题又来了，如果我想细化指针类型的 id 怎么办呢？比如现在我们需要这样操作，让 id = id + 100，即下面这样的断言恒真（伪代码）:

static_assert(id<P *>::value == id<P>::value + 100, "FUCK");

要解决这个问题，我们需要先明白模板匹配规则。

# 模板匹配规则

注意看上面的那个对指针类型的特化，我们说 P 是一个类型名，然而诸如像 int *, double * 之类的都是类型名。那么为什么还会匹配到 P * 呢？或者说，用 P * 匹配了 double * 后，P 是什么呢？

我们不妨试一试

template <typename T>
struct what;

template <typename P>
struct what<P *> {
    using type = P;
};

template <typename T>
using what_t = typename what<T>::type;

然后再写一个辅助函数用来打印类型的名字:

template <typename T>
struct show {
    show() = delete;
};

然后我们来看看 P 到底是个什么鬼:

show<what_t<double *>>();

编译这段代码，我们能从编译错误信息中看到这样一句:

[with T = 'double']

所以，我们尝试用 P * 去匹配 double *，如果匹配成功，那么 P 就变成了 double。有没有觉得像什么？模式匹配！

没错，模板匹配规则，就是模式匹配。

# 元编程中的模式匹配

上面已经有了一个很生动的例子，用 P * 匹配 double *，所以 P 是 double。那么能不能说的更笼统一点呢？

~~当然可以，不然我还能自己把自己问死了？~~

Pattern Matching：compare something with its construction form 模式匹配：将一个东西，按照其「构造的方式」进行对比

当然上面这个版本需要进一步阐述：

# 1. 构造？

比如你有一个基本类型 int，我们就可以这个类型的基础上构造出 int * 类型。

这里可以说 * 是一个构造器，它接受一个类型，返回一个新类型。不妨用 Star 来代替 *，于是就可以说：Star 接受一个类型 T，返回新的类型 Star(T)。用伪代码表示如下：

Type Star(T) {
    return T *;
}

同理，用 Const 代替 const 关键字，我们说：Const 接受一个类型 T，返回新的类型 Const(T)。用伪代码表示如下：

Type Const(T) {
    return const T;
}

这就是构造。~~我真的只能解释成这样了，呜哇啊啊啊啊啊啊啊啊~~

# 2. 匹配？

我们有一个值/类型 T，我们可以尝试用一个「表达式」(表达式中可以包含类型) 去跟 T 的「构造形式」做对比，这就叫「匹配」。匹配过程中，尽可能地让 T 的「构造形式」中没有被被匹配的部分最少。

于是，我们就可以用 P * 尝试去匹配尽可能符合条件的 P。

类型	P
int *	int
int **	int *
int ****	int ***
int(*)(int)	int(int)

用上面的 Const 和 Star 举例子，如果写成伪代码：

match (T) { /* 对 T 进行匹配 */
    case Star(U)  => /* T 是 U * */
    case Const(U) => /* T 是 const U */
    case _        => /* T 两种都不是 */
}

这就是匹配。~~我真的只能解释成这样了，呜哇啊啊啊啊啊啊啊啊~~

# 具体例子？

光说概念可能不好理解，我们直接上代码来看。

我们知道，C++ 中的模板类并不是类型，而是类型构造器（即：模板类本身不能作为对象的类型，只有在实例化以后才可以）。就是这样:

/* 错误，std::vector 不是类型，而是类型构造器 */
std::vector v1;

/* 正确，std::vector 接受一个类型参数 int，构造出(实例化)了类型 std::vector<int> */
std::vector<int> v2;

所以我们这里就可以看出，std::vector 是类似于上面的 Star, Const 之类的构造器。于是我们就可以进行模式匹配:

template <typename V>
struct vector_value_type;

template <typename ValueType>
struct vector_value_type<std::vector<ValueType>> {
/*                       ^^^^^^^^^^^^^^^^^^^^^^   */
    using type = ValueType;
};

注意看代码中标出来的地方，这里我们用跟上面一样的伪代码写出来就是这样:

match (V) {
    case std::vector<ValueType> => return ValueType;
    case _                      => fuck;
}

快！自己理解！~~我真的只能解释成这样了，呜哇啊啊啊啊啊啊啊啊~~

# 来吧！解决问题！

问题是啥来着？

现在问题又来了，如果我想细化指针类型的 id 怎么办呢？比如现在我们需要这样操作，让 id = id + 100，即下面这样的断言恒真（伪代码）:
static_assert(id::value == id::value + 100, "FUCK");

很简单啊：

template <typename P>
struct id<P *> {
    static constexpr size_t value = 100 + id<P>::value;
};

~~你说是吧？~~

# 实战：Function Parser

我们要从一个 Callable 的类型中，解析出返回类型，和参数类型。 Callable 类型就是可以支持「函数调用语法」的类型，比如本身就是个函数，或者重载了 operator()（即 Functor 类型）。

我们不妨先参照上面的伪代码，写出 Function Parser 的伪代码:

/* 模式匹配 Callable 类型 */
match (Callable) {
    case R(Args...)             => /* 是函数，或者类静态函数 */
    case R(Class::*)(Args...)   => /* 是成员函数 */

    /* 不是函数/函数指针，那么是 Functor 吗？*/
    case _ => match (decltype(&Callable::operator())) {
                  case R(Class::*)(Args...) => /* 是 Functor */
                  case _                    => /* 不是，滚    */
              }
}

# 分析

TMP 的常用套路之一就是：先实现一个通用版本，然后在这个通用版本的基础上进行特化。

template <typename Callable>
struct function_parser {
    /* 什么都不做 */
};

接着看上面的第一个匹配式子: case R(Args...)，我们这样匹配它

template <typename R, typename ...Args>
struct function_parser<R(Args...)> {
    using return_type = R;
    using arg_types = TypeList::List<Args...>;
    using function_type = std::function<R(Args...)>;
};

再强调一次，特化处的 template <typename R, typename ...Args> 是用于声明需要用到哪些参数的，也就是声明模式匹配表达式 case R(Args...) 里的 R 和 Args。

通用版本里的模板参数声明的意义与特化中的完全不同，千万不要弄混淆了！！

然后是第二个匹配表达式: case R(Class::*)(Args...)

template <typename Class, typename R, typename ...Args>
struct function_parser<R(Class::*)(Args...)> {
    using return_type = R;
    using arg_types = TypeList::List<Class&, Args...>;
    using class_type = Class;
    using function_type = std::function<R(Class&, Args...)>;
};

注意这里的 arg_types 和 function_type，他们的第一个参数都多了一个 Class &，这是因为，现在匹配的是成员函数，而成员函数都需要一个 this，这个 this 自然就是 Class &.

现在我们已经完成了前两个模式匹配了，但第三个是一个通配符（即前两个都没匹配到），那么在 TMP 里应该怎么对应呢？

没错，就是我们一开始写的那个通用版本，我们再搬出来看看:

template <typename Callable>
struct function_parser {
};

我们需要在这个地方对 decltype(&Callable::operator()) 再进行一次模式匹配，所以现在我就要祭出 TMP 中常用的第二个法宝：继承。

这里我们应该进行的模式匹配中，也会包含 case R(Class::*)(Args...) 这个模式，而这个模式的处理我们已经实现过了，所以我们让 function_parser 的通用版本继承自己的某个特化版本，这样，在所有模式都匹配不到的时候，重新匹配第二次，这样不就行了嘛？

template <typename Callable>
struct function_parser : public function_parser<decltype(&Callable::operator())> {
};

这样，就完成了整个模式匹配的过程。但值得一提的是，上面这样的写法存在不足之处：匹配到 lambda 表达式 的具体类型无法转换。比如:

auto lambda = []() { printf("yes"); };
using FT = typename function_parser<decltype(lambda)>::function_type;
FT f = lambda; /* error! */

为啥呢？

这就要讲一下 Functor 和一般的成员函数的不同了。 Functor 是重载了 operator() 的对象，而这个函数正好是个成员函数，所以我们直接匹配 Callable::operator() 这个函数的类型的时候，我们一定会进入到 R(Class::*)(Args...) 这个分支中，但是这个分支中，我们必须让参数列表的第一个参数是 this，但 Functor 是不需要的，这便是冲突的原因。

那怎么解决呢？

很简单，我们单独为 Functor 做一个 Functor Parser 就行了。

template <typename F>
struct functor_parser : public functor_parser<decltype(&F::operator())> {
};

template <typename Class, typename R, typename ...Args>
struct functor_parser<R(Class::*)(Args...)> {
    using function_type = FunctionAlias<R(Args...)>;
    using return_type = R;
    using class_type = Class;
};

然后我们让 Function Parser 的通用版本继承自 Functor Parser:

template <typename Callable>
struct function_parser : public functor_parser<Callable> {
};

大功告成！

# 工业化版本

实际的版本中，需要考虑的情况还有 const 和函数指针，由于本篇文章只是讲解核心部分，所以这些不那么重要的就忽略了。

这里是一份跑在生产环境的 Function Parser：[libmozart/function.hpp](https://github.com/libmozart/core/blob/bd432a29d9e56cecb4b89e7a8cdb7280981814fc/mozart%2B%2B/mpp_core/function.hpp#L58)

也许会有帮助！

# 第 3 节 - TypeList

# TypeList 是什么？

List 是什么？自然是列表。 TypeList，顾名思义，就是类型列表。只不过列表里的元素不是数据，而是一个个的类型。所以我们需要将类型视为一种数据。

# 可变参数模板

一个列表，里面存放的元素个数可以是任意的，所以我们需要一种「容器」能包装「任意个数」的类型。

这种东西，叫做「可变参数模板」(variadic templates):

template <typename ...Ts>
struct Fuck {};

那么这个 Ts... 就叫做「参数包」(parameter pack)，我们可以用 sizeof...(Ts) 得到参数包中元素的个数。

这里需要提一下参数包的解包规则，当 ... 出现在一个语法单元的末尾时，代表这个表达式中的参数包将按照这个语法单元的格式进行展开。

比如：

template <typename ...Ts>
void fuck(Ts &&...ts) {
    use(std::forward<Ts>(ts)...);
}

所以，当你这样使用 fuck 函数的时候：

T t;
U u;
fuck(t, u);

里面的 use 函数调用处包含一个 std::forward<Ts>(ts) 这样的语法单元，所以这里就会展开成：

use(std::forward<T>(t), std::forward<U>(u));

又比如：

template <typename ...Ts>
class son : public Ts... {};

所以当你这样使用 son 的时候:

son<A, B, C, D>

由于这里包含一个 public Ts 的语法单元，所以这里会展开成

class son : public A, public B, public C, public D {};

Wow, awesome!

# 先来一个容器！

看看上面的可变参数模板，是不是跟我们要的容器很相似？我们要的是这样的：

List<int, bool, char, List<int>, std::string>

是吧？

于是我们有了容器了:

template <typename ...Ts>
struct List {};

但是为了代码的整洁，我们可以考虑把这部分放到一个结构体里去（具体原因后面会体现）:

struct TypeList {
    /* 列表元素的容器 */
    template <typename ...Ts>
    struct List {};

    /* 为了少打几个字，为空列表 List<> 取个别名 */
    /* 这不是显而易见的嘛 ？ */
    using Nil = List<>;
};

# 容器有了，然后呢？

所以你最后的成果就是纯理论的，就像欧氏几何一样，先设定几条简单的不证自明的公理，再在这些公理的基础上推导出整个理论体系。

我们不妨思考一个列表的「最小行为集合」，在这个集合里的操作我们认为是「公理」。然后其他的操作都可以使用这些「公理」实现。

对于一个列表，首先有的必须是往容器中添加内容，所以这个集合里必定包含「cons」。

然后我们需要能对这个列表进行遍历，不然，我要个列表只能存，不能读，那还玩个🔨。

所以，这个集合里还需要包含「head」和「tail」。

head: 取出这个列表的头部元素。

tail: 去除这个列表的头部元素。

那么，足够了吗？足够了。

# 我们先来实现 cons

这里需要用到特化，因为特化可以给我们使用「模式匹配」的能力。

/* I 后缀代表 Implementation（实现）*/
template <typename T, typename L>
struct consI;

template <typename T, typename ...Ts>
struct consI<T, List<Ts...>> {
    using type = List<T, Ts...>;
};

请注意这里的特化形式 consI<T, List<Ts...>>，这里要求我们传给 cons 的第二个参数必须是列表容器，否则这个特化就无法匹配。

同时，还需要注意特化内部的 using type = List<T, Ts...>，这里就完成了添加操作：把 T 添加到了原有列表的头部。

现在我们需要往列表里添加元素，就要这样用：

using my_list = List<int, char>;
using new_list = typename consI<bool, my_list>::type;

淦！typename consI<bool, my_list>::type 这一点都不像在调用一个函数！我们可以多写一步，把后面那个 type 省略掉。

template <typename T, typename L>
using cons = typename consI<T, L>::type;

于是我们就能写:

using new_list = cons<bool, my_list>;

Wow, awesome!

# 然后是 head 和 tail

有了 cons 的实现经验，我们实现 head 和 tail 就很简单了。

先来实现 head:

template <typename L>
struct headI;

template <typename T, typename ...Ts>
struct headI<List<T, Ts...>> {
    using type = T;
};

template <typename L>
using head = typename headI<L>::type;

然后是 tail，这不过就是 head 的另一种情况罢了:

template <typename L>
struct tailI;

template <typename T, typename ...Ts>
struct tailI<List<T, Ts...>> {
    using type = List<Ts...>;
};

template <typename L>
using tail = typename tailI<L>::type;

这里故意没有对 head 和 tail 函数特化空列表，因为，对空列表做 head 和 tail，难道不是非法的吗（笑？

# 其他操作？

其他操作都可以通过 cons, head, tail 三种基本操作组合出来，不信你试试？

# 参考资料

Functional Streams (opens new window)
[libmozart/typelist](