浅谈C++元编程

(Updated: )
科普读物 › C++
,

注意， 这是一篇摘抄文

原文出处浅谈C++元编程

元编程

什么是元编程

元编程(Metaprogramming)通过操作程序实体(program entity), 在编译时**(compile time)计算出运行时(runtime)需要的常数, 类型, 代码的方法.

一般的编程是通过直接编写程序(program), 通过编译器编译(compile), 产生目标代码, 并用于运行时执行. 与普通的编程不同, 元编程则是借助语言提供的模板(template)机制, 通过编译器推导(deduce), 在编译时生成程序. 元编程通过编译器推到得到的程序, 再进一步通过编译器编译, 产生最终的目标代码.

因此, 元编程又被称为两级编程(two-level programming), 生成式编程(generative programming)或模板元编程(template metaprogramming).

元编程在C++中的位置

C++语言 = C语言的超集 + 抽象机制 + 标准库

C++的抽象机制(abstraction mechanisms)主要有两种: 面向对象编程(object-oriented programming)和模板编程(template programming).

为了实现面向对象编程, C++提供了类(class), 用C++的已有类型(type)构造出新的类型. 而在模板编程方面, C++提供了模板(template), 以一种直观的方式表示**通用概念(general concept).

模板编程的应用主要有两种: 泛型编程(gerneric grogramming)和元编程(meta-programming). 前者注重通用概念的抽象, 设计通用的类型或算法(algorithm), 不需要过于关心编译器如何生成具体的代码; 而后者注重于设计模板推导时的选择(selection)和迭代(iteration), 通过模板技巧设计程序

元编程的语言支持

C++的元编程主要依赖于语言提供的模板机制. 除了模板, 现代C++还允许使用constexpr函数进行常量计算. 由于constexpr函数的功能有限, 递归调用层数和计算次数还受编译器限制, 而且编译性能较差, 所以模板的元飙车程序主要基于模板, 这一部分主要总结C++模板机制相关的语言基础, 包括狭义的模板和泛型lambda表达式.

狭义的模板

目前最新的C++将模板分成了4类: 类模板(class template), 函数模板(function template), 别名模板(alias template)和变量模板(variable template). 前两者能产生新的类型, 属于类型构造器(type constructor); 而后两者是C++为前两者补充的简化记法, 属于语法糖(syntactic sugar).

类模板和函数模板分别用于定义具有相似功能的类和函数(function), 是泛型中对类型和算法的抽象. 在标准库中, 容器(container)和函数都是类模板和函数模板的应用.

别名模板和变量模板分别在C++11和C++14引入, 分别提供了具有模板特性的类型别名(type alias)和常量(constant)的简记方法. 前者类模板的嵌套类等方法实现, 后者则可以通过constexpr函数, 类模板的静态成员, 函数模板的返回值等方法实现. 例如, C++14中的别名模板. std::enable_if_t 等价于 typename std::enable_if::type，C++ 17 中的变量模板std::is_same<T, U> 等价于 std::is_same<T, U>::value。尽管这两类模板不是必须的，但一方面可以增加程序的可读性（§ 4.1），另一方面可以提高模板的编译性能

C++中的模板参数(template parameter/argument)可以分为三种: 值参数, 类型参数, 模板参数。从 C++ 11 开始, C++ 支持了变长模板(variadic template): 模板参数的个数可以不确定, 变长参数折叠一个参数包(parameter pack), 使用时通过编译时迭代, 遍历各个参数. 标准库中的元组(tuple)–std::tuple就是变长模板的一个应用(元组的类型参数是不定长的, 可以用template<typename… Ts>匹配).

尽管模板参数也可以当作一般的类型参数进行传递(模板也是一个类型), 但之所以单独提出来, 是因为它可以实现对传入模板的参数匹配.

特化(specialization)类似于函数的重载(overload), 即给出全部模板参数取值(完全特化)或部分模板参数取值(部分特化)的模板实现. 实例化(instantiation)类似于函数的绑定(binding), 是编译器根据参数的个数和类型, 判断使用哪个重载的过程. 由于函数和模板的重载具有相似性, 所以它们的参数重载规则**(overloading rule)也是类似的.

泛型lambda表达式

由于C++不允许在函数内定义模板, 有时候为了实现函数内的局部特殊功能, 需要在函数外专门定义一个模板. 一方面, 这导致了代码结构松散, 不易于维护; 另一方面, 使用模板是, 需要传递特定的上下文(context), 不易于复用. (类似于C语言里的回调机制, 不能在函数内定义回调函数, 需要通过参数传递上下文.)

为此, C++14引入了泛型lambda表达式(generic lambda expression): 一方面, 能像C++ 11引入的lambda表达式一样, 在函数内构造闭包(closure), 避免在函数外定义函数内使用的局部功能; 另一方面, 能实现函数模板的功能, 允许传递任意类型的参数.

元编程的基本演算

C++的模板机制仅仅提供了纯函数(pure functional)的方法, 即不支持变量, 且所有的推导必须在编译时完成. 但是C++中提供的模板是图灵必备(turing complete)的, 所以可以使用模板实现完整的元编程.

元编程的基本演算规则(calculus rule)有两种: 编译时测试(compile-time test)和编译时迭代(compile-time iteration), 分别实现了控制结构(control structure)中的选择(selection)和迭代(iteration). 基于这两种基本你的演算方法, 可以完成更负载的演算.

另外, 元编程中还常用模板参数传递不同的策略(policy), 从而实现依赖注入(dependency injection)/控制反转(Inversion of Control). 例如，std::vector<typename T, typename Allocator = std::allocator> 允许传递 Allocator 实现自定义内存分配。

编译时测试

编译时测试相当于面向过程编程中的选择语句(selection statement), 可以实现if-else/switch的选择逻辑.

在C++ 17 之前, 编译时测试是通过模板的实例化和特化实现的—每次找到最特殊的模板进行匹配; 而c++17提出了使用constexpr-if的编译时测试方法.

测试表达式

类似于静态断言(static assert), 编译时测试的对象是常量表达式(constexpr), 即编译时能得出结果的表达式. 以不同的常量表达式作为参数, 可以构造各种需要的模板重载. 例如, 下面代码演示了如何构造谓词(predicate)isZero, 编译时判断Val是不是0.

1
2
3
4
5
6
7
8
9
10
11
12
13
template <unsigned Val> struct _isZero {
    constexpr static bool value = false;    
};

template <> struct _isZero <0>{
    constexpr static bool value = true;    
};

template <unsigned Val>
constexpr bool isZero = _isZero<Val>::value;

static_assert (!isZero<1>, "compile error");
static_assert (!isZero<0>, "compile error");

测试类型

在元编程的很多应用场景中, 需要对类型进行测试, 即对不同的类型实现不同的功能. 而常见的测试类型又分为两种.

  • 判断一个类型是否为特定的类型:
    • 可以通过对模板的特化直接实现
  • 判断一个类型是否满足某些条件
    • 可以通过替换失败不是错误SFINAE(substitution Failure Is nOT aN Error)规则进行最优匹配.
    • 还能通过标签转发(tag dispatch)匹配可枚举的有限情况(例如, std::advance 根据 std::iterator_traits::iterator_category选择迭代器类型Iter支持的实现方式)

为了更好的支持SFINAE, C++11的type_traits除了提供类型检查的谓语模板is_*/has_*, 还提供了两个重要的辅助模板:

  1. std::enable_if 将对条件的判断转化为常量表达式, 类似测试表达式实现从重载的选择(但需要添加一个冗余的函数参数/函数返回值/模板参数);
  2. std::void_t直接检查依赖的成员/函数是否存在, 不存在则无法重载(可以用于构造谓词, 再通过std::enable_if判断条件.)

是否为特定的类型的判断, 类似于上面的代码, 将unsigned Val改为typename Type; 并把传入的模板参数由值参数改为类型参数, 根据最优原则匹配重载.

是否满足某些条件的判断, 在下面的代码中, 展示了如何将C语言的基本类型数据, 转换为std::string的函数ToString. 代码具体分为三个部分:

  1. 首先定义三个变量模板IsNum/isStr/isBad, 分别对应了三个类型条件的谓词(使用了中的std::is_arithmetic和std::is_same);
  2. 然后根据SFINAE规则, 使用std::enable_if重载函数ToString, 分别对应了数值, C风格字符串和非法类型;
  3. 在前两个重载中,分别调用std::to_string和std::string构造函数; 在最后一个重载中,静态断言直接报错.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
template <typename T>
constexpr bool isNum = std::is_arithmetic<T>::value;

template <typename T>
constexpr bool isStr = std::is_same<T, const char *>::value;

template <typename T>
constexpr bool isBad = !isNum<T> && !isStr<T>;

template <typename T>
std::enable_if_t<isNum<T>, std::string> ToString (T num) {
    return std::to_string (num);
}

template <typename T>
std::enable_if_t<isStr<T>, std::string> ToString (T str) {
    return std::string (str);
}

template <typename T>
std::enable_if_t<isBad<T>, std::string> ToString (T bad) {
    static_assert (sizeof (T) == 0, "neither Num nor Str");
}

auto a = ToString (1);  // std::to_string (num);
auto b = ToString (1.0);  // std::to_string (num);
auto c = ToString ("0x0");  // std::string (str);
auto d = ToString (std::string {});  // not compile :-(

根据两阶段名称查找(two-phase name lookup)的规定: 如果直接使用static_assert(false)断言, 会在模板还没实例化的第一阶段编译失败; 所以需要借助类型依赖(type-dependent)d false表达式(一般依赖于参数T)进行失败的静态断言.

类似的, 可以通过定义一个变量模板template <typename…> constexpr bool false_v = false;, 并使用false_v替换sizeof(T)==0.

使用if进行编译时的测试

对于初次接触元编程的人, 往往会使用if语句进行编译时测试, 下面代码就是一个错误的写法, 很代表性的体现了元编程和普通编程的不同之处.

1
2
3
4
5
6
template <typename T>
std::string ToString (T val) {
    if (isNum<T>) return std::to_string (val);
    else if (isStr<T>) return std::string (val);
    else static_assert (!isBad<T>, "neither Num nor Str");
}

这段代码的错误在于: 编译代码的函数ToString时, 对于给定的类型T, 需要进行两次函数绑定—val作为参数分别调用std::to_string(val)和std::string(val), 再进行一次静态断言—判断!isBad是否为true. 这会导致: 两次绑定中, 会有一次失败. 假设调用ToString(“str”), 再编译这段代码时, std::string(const char* ) 可以正确重载, 但是std::to_string(const char *)并不能找到正确的重载, 导致编译失败.

假设是脚本语言, 这段代码是没有问题的: 因为脚本语言没有编译的概念, 所有函数的绑定都在运行时完成的; 而静态语言的函数绑定是在编译时完成的. 为了使得上述代码的风格用于元编程, C++17引入了constexpr-if—只需要把以上代码的if改为if constexpr 就可以编译了.

constexpr-if的引入让模板测试更加直观, 提高了模板代码的可读性. 下面代码展示了如何使用constexpr-if解决编译时选择的问题; 而且最后的**兜底(catch-all)**语句, 不再需要IsBad谓语模板, 可以使用类型依赖的false表达式进行静态断言(但也不能使用static_assert(false)断言).

1
2
3
4
5
6
template <typename T>
std::string ToString (T val) {
    if constexpr (isNum<T>) return std::to_string (val);
    else if constexpr (isStr<T>) return std::string (val);
    else static_assert (false_v<T>, "neither Num nor Str");
}

然而, constexpr-if背后的思路早在vs2012已出现. 其引入了__if_exists语句, 用于编译时测试标识符是否存在.

编译时迭代

编译时迭代和面向过程编程中的循环语句(loop statement)类似, 用于实现与for/while/do雷士的循环逻辑.

在C++17之前, 和普通的编程不同, 元编程的演算规则是纯函数的, 不能通过变量迭代实现编译时迭代, 只能用递归(recursion)和特化的组合实现. 一般思路是: 提供两类重载–一类接受任意参数, 内部递归调用自己; 另一类是前者的模板特化或函数重载, 直接返回结果, 相当于递归终止条件, 它们的重载条件可以是表达式或类型.

而C++17提出了**折叠表达式(fold expression)的语法, 化简了迭代的写法.

定长模板的迭代

下面代码展示了如何使用编译时迭代实现编译时计算阶层(N!). 函数_Factor有两个重载: 一个是对任意非负整数的, 一个是对0为参数的. 前者利用递归产生结果, 后者直接返回结果. 当调用_Factor<2>时, 编译器会展开为2 * _Factor<1>, 然后_Factor<1>再展开1*_Factor<0>, 然后_Factor<0>直接匹配到参数为0的重载.

“””
template
constexpr unsigned _Factor () { return N * _Factor<N - 1> (); }

template <>
constexpr unsigned _Factor<0> () { return 1; }

template
constexpr unsigned Factor = _Factor ();

static_assert (Factor<0> == 1, “compile error”);
static_assert (Factor<1> == 1, “compile error”);
static_assert (Factor<4> == 24, “compile error”);
“””

变长模板的迭代

为了遍历变长模板的每个参数, 可以使用编译时迭代实现循环遍历. 下面代码实现了对所有参数求和的功能. 函数Sum有两个重载: 一个是对没有函数参数的情况, 一个是对函数参数个数至少为1的情况. 和定长模板迭代类似, 这里也是通过递归调用实现参数遍历.

1
2
3
4
5
6
7
8
9
10
11
12
template <typename T>
constexpr auto Sum () {
    return T (0);
}

template <typename T, typename... Ts>
constexpr auto Sum (T arg, Ts... args) {
    return arg + Sum<T> (args...);
}

static_assert (Sum () == 0, "compile error");
static_assert (Sum (1, 2.0, 3) == 6, "compile error");

使用折叠表达式简化编译时迭代

在c++11引入变长模板时, 就支持了在模板内直接展开参数包的语法; 但该语法仅支持对参数包里每个参数进行一元操作(unary operation); 为了实现参数见的二元操作(binary operation), 必须借助额外的模板实现(例如, 上面代码定义了两个Sum函数模板, 其中一个展开参数包进行递归调用).

而C++17引入了折叠表达式, 允许直接遍历参数包里的各个参数, 对其应用二元运算符(binary operator)进行左折叠(left fold)或右折叠(right fold). 下面代码使用初值为0的左折叠表达式, 对上面代码进行改进.

1
2
3
4
5
6
7
template <typename... Ts>
constexpr auto Sum (Ts... args) {
    return (0 + ... + args);
}

static_assert (Sum () == 0, "compile error");
static_assert (Sum (1, 2.0, 3) == 6, "compile error");

元编程的基本应用

利用元编程, 可以很方便的设计出类型安全(type safe), 运行时高效(runtime effective)的程序.

尽管元编程的应用场景各不相同，但都是三类基本应用的组合：数值计算(numeric computation)、类型推导(type deduction)和代码生成(code generation)。例如，在 BOT Man 设计的对象关系映射ORM (object-relation mapping) 中，主要使用了类型推导和代码生成的功能。根据对象(object) 在 C++ 中的类型，推导出对应数据库关系(relation) 中元组各个字段的类型；将对 C++ 对象的操作，映射到对应的数据库语句上，并生成相应的代码

数值计算

作为元编程的最早的应用, 数值计算可以用于编译时常数计算和优化时表达式计算.

编译时常数计算能让程序员使用程序设计语言, 写编译时确定的常量; 而不是直接写常数(迷之数字(magic number))或在运行时计算这些常数.

类型推导

除了基本的数值计算之外, 还可以利用元编程进行任意类型之间的互相推导, 例如, 在领域特定语言(domain-specific language)和C++语言原生结合时, 类型推导可以实现将这些语言中的类型, 转化为C++的类型, 并保证类型安全.

BOT Man提出了一种能编译时进行SQL语言元组类型推导的方法. C++所有的数据类型都不能为NULL; 而SQL的字段是允许为NULL的, 所以在C++中使用std::optional容器存储可以为空的字段. 通过SQL中outer-join拼接得到的元组的所有字段都可以为NULL, 所以ORM需要一种方法: 把字段可能是std::optional或T的元组, 转化为全部字段都是std::optional的新元组.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template <typename T> struct TypeToNullable {
    using type = std::optional<T>;
};
template <typename T> struct TypeToNullable <std::optional<T>> {
    using type = std::optional<T>;
};

template <typename... Args>
auto TupleToNullable (const std::tuple<Args...> &) {
    return std::tuple<typename TypeToNullable<Args>::type...> {};
}

auto t1 = std::make_tuple (std::optional<int> {}, int {});
auto t2 = TupleToNullable (t1);
static_assert (!std::is_same<
               std::tuple_element_t<0, decltype (t1)>,
               std::tuple_element_t<1, decltype (t1)>
>::value, "compile error");
static_assert (std::is_same<
               std::tuple_element_t<0, decltype (t2)>,
               std::tuple_element_t<1, decltype (t2)>
>::value, "compile error");

上面代码展示了这个功能:

  1. 定义 TypeToNullable，并对 std::optional 进行特化，作用是将 std::optional 和 T 自动转换为 std::optional；
  2. 定义 TupleToNullable，拆解元组中的所有类型，转化为参数包，再把参数包中所有类型分别传入 TypeToNullable，最后得到的结果重新组装为新的元组。

代码生成

和泛型编程一样, 元编程也常常被用于代码的生成. 但是和简单的泛型编程不同, 元编程生成的代码往往是通过编译时测试和编译时迭代的演算推导出来的

在实际项目中，我们往往需要将 C++ 数据结构，和实际业务逻辑相关的领域模型(domain model) 相互转化。例如，将承载着领域模型的 JSON 字符串反序列化(deserialize) 为 C++ 对象，再做进一步的业务逻辑处理，然后将处理后的 C++ 对象序列化(serialize) 变为 JSON 字符串。而这些序列化/反序列化的代码，一般不需要手动编写，可以自动生成。

BOT Man 提出了一种基于编译时多态(compile-time polymorphism) 的方法，定义领域模型的模式(schema)，自动生成领域模型和 C++ 对象的序列化/反序列化的代码。[27] 这样，业务逻辑的处理者可以更专注于如何处理业务逻辑，而不需要关注如何做底层的数据结构转换。

元编程的主要难点

复杂性

由于元编程的语言层面上的限制较大， 所以许多的元编程使用了很多的编译时测试和编译时迭代技巧， 可读性(readability)都比较差. 另外, 由于巧妙的设计出编译时能完成的演算也是很困难的, 相较于一般的C++程序, 元编程的可写性(writabilirty)也不是很好.

现代C++也不断地增加语言的特性, 致力于降低元编程的复杂性:

  • C++11的别名模板提供了对模板中的类型的简记方法
  • C++14的变量模板提供了对模板中常量的简记方法
  • C++17的constexpr-uf提供了编译时测试的新写法
  • C++17的折叠表达式降低了编译时迭代的编写难度

基于c++14的泛型lambda表达式, 其核心思想是: 只需要使用c++14的泛型lambda表达式和c++11的constexpr/decltype, 就开业快速实现元编程的基本演算了.

实例化错误

模板的实例化和函数的绑定不同: 再编译前, 前者对传入的参数是什么, 没有太多的限制; 而后者则根据函数的声明, 确定了应该传入参数的类型. 而对于模板实参内容的检查, 则是再实例化的过程中完成的. 所以, 程序的设计者再编译前, 很难法线https://bot-man-jl.github.io/articles/?post=2017/Cpp-Metaprogramming实例化可能产生的错误.

为了减少可能产生的错误, Bjarne Stroustrup等人提出了再语言层面上, 给模板上引入概念(concept), 可能对传入的参数加上限制(constraint), 即只有满足特定限制的类型才能作为参数传入模板. 例如, 模板std::max限制接受支持运算符<的类型传入. 但是由于各种原因, 这个语言特性一直没有能正式加入C++标准(可能在C++20中加入). 尽管如此, 编译时仍可以通过编译时测试和静态断言等方法实现检查.

另外, 编译时模板的的实例化出错位置, 在调用层数较深处时, 编译器会提示每一层实例化的状态, 这使得报错信息包含了很多的无用信息, 很难让人较快的法线问题所在. BOT Man提出了一种短路编译(short-circuit compiling)的方法, 能让基于元编程的库(library), 给用户提供更人性化的编译时报错. 具体方法是, 在实现(implementation)调用需要的操作之前, 接口(interface)先检查是传入的参数是否有对应的操作; 如果没有, 就通过的短路的方法, 转到一个用于报错的接口, 然后停止编译并使用静态断言提供的报错信息.

代码膨胀

由于模板会对所有不同模板实参都进行一次实例化, 所以当参数的组合很多的时候, 很可能会发生代码膨胀(code bloat), 即产生体积巨大的代码. 这些代码可以分为两种: 死代码(dead code) 和有效代码(effective code).

在元编程中, 很多时候只关心推导的结果, 而不是过程. 例如, 只关心最后的Factor<4> == 24, 而不需要中间过程中产生的临时模板. 但是在N很大的时候, 编译会残生很多临时模板. 这些临时模板是死代码, 即不被执行的代码. 所以, 编译器会自动优化最终的代码生成, 在链接时(link-time)移除这些无用代码, 使得最终的目标代码不对包含它们. 尽管如此, 如果产生过多的死代码, 会浪费宝贵的编译时间.

另一种情况下, 展开的代码都是有效代码, 即都是呗执行的, 但是又由于需要的参数的类型繁多, 最后的代码体积仍然很大. 编译器很难优化这些岱庙, 送一程序员应该在设计时避免代码膨胀. 一般用薄模板(thin yemplate)减少模板实例体积; 具体思路是: 将不同参数实例化得到的模板的相同部分抽象为共同的基类或函数, 然后将不同参数对应的不同部分继承基类或调用函数, 从而实现代码共享.

例如, 在std::vector的实现中, 对T* 和void* 进行了特化; 然后将所有的T* 的实现继承到void* 的实现上, 并在公开的函数里通过强制类型转换, 进行void* 和 T* 的相互转换; 最后这使得所有的指针的std::vector就可以共享同一份实现, 从而避免了代码膨胀.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <typename T> class vector;       // general
template <typename T> class vector<T *>;  // partial spec
template <> class vector<void *>;         // complete spec

template <typename T>
class vector<T *> : private vector<void *>
{
    using Base = Vector<void∗>;
public:
    T∗& operator[] (int i) {
        return reinterpret_cast<T∗&>(Base::operator[] (i));
    }
    ...
}

编译性能

元编程尽管不会带来额外的允许时开销(runtime overhead), 但如果过度使用, 可能会大大增加编译时间(尤其是在大型项目中). 为了提高元编程的编译性能, 需要使用特色的技巧进行优化.

根据单定义规则(one Definition Rule ODR), 允许一个模板在多个翻译单元(translation unit)中使用下昂同的模板参数实例化, 并在链接时合并在同一个实例. 然而, 每个翻译单元上的模板操作是独立的, 一方面增加了编译时间. 另一方面还会产生过多的中间代码, 因此, 常用显式实例化(explicit instantiation)避免进行多次模板实例化操作; 具体思路是: 在一个翻译翻译中显示定义模板实例, 在其他翻译单元中只需要通过extern声明夏娜沟通的实例. 由于接口于实现分离, 该方法还常用于静态库的模板接口.