概述
模板元编程可在编译时完成一些计算,说它是屠龙之技,是因为模板元编程
- 似乎很厉害的样子。
- 似乎没有地方可以用上。
假如只从实际工程出发,没有太大必要研究模板元编程。只是我还是想写写这个主题,感叹一下模板居然可以做这种事情。
本文假设大家知道 C++ 模板元编程、编译期计算等概念。先上完整代码:
可以对照着代码看下文。代码中,首先用 C++ 模板来模拟 Scheme 的常用函数。再将 Scheme 代码改写成 C++ 模板,实现一些计算。基本上任何 Scheme 代码都可以按照这种方式改写。
代码中包含一些元编程例子。简单例子是计算阶乘、计算平方根。复杂点的例子是,求解八皇后、huffman 编码。
编程语言特性
假如将模板当成一门全新的编程语言。一门编程语言最少应该具有什么特性呢?
- 需要有基本的数据类型,比如数字、字符串、布尔值等。
- 需要某种方法,将基础类型组合起来,表达更高级的概念。比如 C 语言中的 struct, 就是一种组合方法。数组和字典也是组合方法。
- 需要流程控制。典型的是顺序、分支、循环。
- 需要输入和输出。
还需要什么语言特性呢?已经没有了,具备上述的特性,基本就可写出任何程序。
下面按照这个顺序,描述一下模板元编程。
基本数据类型
数字
数字可分为整数和小数。怎么用模板类型表示整数呢?大概这样
template <int N>
struct number {
static const int value = N;
};
这样每个整数都对应一种类型。那小数呢?C++ 的模板参数不可以是
double
, 下面的语法是错误的
template <double N>
struct number {
static const double value = N;
};
但是我们可以将小数表示成分数,有分子和分母。于是数字可以表示为
template <int64_t N, int64_t D = 1>
struct number {
static const int64_t numer = N;
static const int64_t denom = D;
};
当分母为 1 时,其实就是整数。当然我们需要简化分子和分母,在编译期实现
gcd
(求最大公约数)算法。
布尔值
布尔值其实可归类为数字。但经常将布尔值单独拆分出来,用于条件判断。布尔值可表达为如下的模板类型。
template <bool flag>
struct boolean {
static const bool value = flag;
};
字符串
接下来是用模板类型来表示字符串。C++ 的模板参数只能是整数,不能是
const char*
。但是我们可以将字符串的字符分拆开,这样每个字符都是整数。
比如字符串 hello
对应于类型
String<'h', 'e', 'l', 'l', 'o'>
。
有些编程语言,会将实际上的字符串,再分拆成两种类型。
- 符号(Symbol)
- 字符串(String)
符号是不可修改的,放在全局唯一的符号表。要判断符号是否相同,只需要判断符号对应的指针或者索引是否相同。而字符串是可以被修改的。
Scheme 区分了符号和字符串。为跟 Scheme 对应(我们在用 C++ 模板来模拟 Scheme),我们将在编译期不可变的字符串,叫做符号。符号的类型为
template <char... C>
struct Symbol {
static constexpr char const value[sizeof...(C) + 1] = {C..., '\0'};
};
为了方便编写代码。提供了一个宏 symbol
symbol("hello") // 生成 Symbol<'h', 'e', 'l', 'l', 'o'>
将基础类型组合起来
cons
有了基础类型,现在需要将基础类型组合起来。最简单的组合方式,就是将两个类型放在一起。
template <typename T, typename U>
struct pair {
using car_ = T;
using cdr_ = U;
};
第一个类型是 car
,第二个类型是
cdr
。另外我们用 cons
函数,将两个类型粘到一起。于是有
template <typename x>
struct car {
using type = typename x::car_;
};
template <typename x>
struct cdr {
using type = typename x::cdr_;
};
template <typename T, typename U>
struct cons : public pair<T, U> {};
car
、cdr
、cons
都是 Scheme
的叫法。现在就可以用 cons
组合两个基本类型,也可以用
car
或 cdr
访问类型
using p = cons<number<1>, number<2>>
using num1 = car<p>;
using num2 = cdr<p>;
假如要组合三个类型,可以嵌套 cons
。
using p = cons<number<1>, cons<number<2>, number<3>>>
list
现在我们用 cons
嵌套来表示线性结构,引入
list
。类似链表,将多个节点串连在一起。为达到这个目标,还需要引入一个结束类型。
struct null {
};
比如
using lst0 = list<number<1>, number<2>, number<3>>; // 等价于下面
using lst1 = cons<number<1>, cons<number<2>, cons<number<3>, null>>>;
list
的实现使用了模板偏特化
template <typename... T>
struct list;
template <typename T>
struct list<T> : public pair<T, null> {};
template <typename T, typename... X>
struct list<T, X...> : public pair<T, list<X...>> {};
字典
好了,有了基本类型和 list
操作(其实是 cons
的嵌套),我们就可以表达任意更高级的概念。比如字典
a: 1
b: 2
就可以表达为
list<symbol("*table*"),
cons<symbol("a"), number<1>>,
cons<symbol("b"), number<1>>>
类型 tag
我们有了
number
、symbol
、null
、pair
、boolean
这些类型。现在我们想判断类型,比如有一些
is_null
、is_number
等实用函数。用于对应 Scheme
的 null?
、`pair?
等函数。
这可以用经典的模板编程技术 traits
来解决。定义好一个
tag,再在基本类型中嵌入 tag
。比如
struct boolean_tag {
static const bool is_pair = false;
static const bool is_null = false;
static const bool is_number = false;
static const bool is_boolean = true;
static const bool is_symbol = false;
};
struct number_tag {
static const bool is_pair = false;
static const bool is_null = false;
static const bool is_number = true;
static const bool is_boolean = false;
static const bool is_symbol = false;
};
template <bool flag>
struct boolean {
using tag = boolean_tag;
static const bool value = flag;
};
template <int64_t N, int64_t D = 1>
struct number {
using tag = number_tag;
static const int64_t numer = impl::rat_reduce<(N == 0 || D == 0), N, D>::numer;
static const int64_t denom = impl::rat_reduce<(N == 0 || D == 0), N, D>::denom;
};
这里 tag 就是类型标识。每个类型都有了 tag,就可以编写判断函数
template <typename T>
using is_null = boolean<T::tag::is_null>;
template <typename T>
using is_pair = boolean<T::tag::is_pair>;
template <typename T>
using is_number = boolean<T::tag::is_number>;
template <typename T>
using is_boolean = boolean<T::tag::is_boolean>;
template <typename T>
using is_symbol = boolean<T::tag::is_symbol>;
流程控制
顺序
顺序是是简单的,一个个写下去就行。比如
using lst0 = list<number<1>, number<2>, number<3>>;
using lst1 = cons<number<1>, cons<number<2>, cons<number<3>, null>>>;
display<lst0>();
display<lst1>();
分支
在 C++ 模板中,分支使用偏特化来实现
template <typename Flag, typename True, typename False>
struct if_else_impl : public True {};
template <typename True, typename False>
struct if_else_impl<boolean<false>, True, False> : public False {};
template <typename Flag, typename True, typename False>
struct if_else : public if_else_impl<typename Flag::type, True, False> {};
if_else
有三个参数,第一个是条件,条件成立就做
True
分支,不成立就走 False
分支。
循环
模板元编程,没有直接的循环语法。但我们可以用递归来实现。
if_else
例子
上面我们定义了 list
, 但还不能操作
list
。现在我们已经有了分支和递归,可以编写一些函数。其中
length
计算 list
的长度,list_ref
用于访问元素。
template <typename items>
struct length {
using type = typename if_else<is_null<items>,
number<0>,
add<number<1>, length<cdr<items>>>>::type;
using tag = typename type::tag;
};
template <typename items, typename n>
struct list_ref {
using type = typename if_else<is_equal<n, number<0>>,
car<items>,
list_ref<cdr<items>, sub<n, number<1>>>>::type;
using tag = typename type::tag;
};
上面的定义看起来很复杂的样子。但上面的模板代码,完全等价于下面的 Scheme 代码
(define (list-ref items n)
(if (= n 0)
(car items)
(list-ref (cdr items) (- n 1))))
(define (length items)
(if (null? items)
0
(+ 1 (length (cdr items)))))
来到这样,应该意识到,我们是用 C++ 的模板语法来写 Scheme。基本上 Scheme 的任何代码,都可以按照这种方式改写。
拿 struct length
来说,其中类型名 length
可以对应于 Scheme 的一个函数名。typename items
可以对应于
Scheme 的函数参数。using type
对应于函数返回结果。using tag
是返回结果的类型。
类型 type
我们统一用 T::type
来获取返回结果。T::tag
获取返回类型。为了达到这种统一,在所有的类型中,都定义 type
和 tag
这两个字段。
特别地,在基础类型中,也添加 type 字段。于是基础类型,就演变成
template <int64_t N, int64_t D = 1>
struct number {
using type = number<N, D>;
using tag = number_tag;
static const int64_t numer = impl::rat_reduce<(N == 0 || D == 0), N, D>::numer;
static const int64_t denom = impl::rat_reduce<(N == 0 || D == 0), N, D>::denom;
};
template <bool flag>
struct boolean {
using tag = boolean_tag;
using type = boolean<flag>;
static const bool value = flag;
};
输入输出
模板元编程,可以使用模板参数作为输入。现在我们再编写一个
display
的输出函数。
template <typename T>
struct display_impl {
static std::ostream &display(std::ostream &os, bool showBracket, number_tag) {
...
}
static std::ostream &display(std::ostream &os, bool showBracket, symbol_tag) {
...
}
static std::ostream &display(std::ostream &os, bool showBracket, boolean_tag) {
...
}
static std::ostream &display(std::ostream &os, bool showBracket, null_tag) {
...
}
static std::ostream &display(std::ostream &os, bool showBracket, pair_tag) {
...
}
static std::ostream &display(std::ostream &os, bool showBracket) {
return display(os, showBracket, typename T::tag());
}
};
template <typename T>
void display(std::ostream &os = std::cout) {
display_impl<T>::display(os, true) << std::endl;
};
使用类型 tag
对函数进行分派。这也是模板元编程的一种常见方法。
using lst = list<symbol("*table*"),
cons<symbol("a"), number<1>>,
cons<symbol("b"), number<1>>>;
display<lst>();
输出
(*table* (a . 1) (b . 1))
结束
现在我们用 C++
模板表达出,基础类型、组合类型、流程控制、输入输出。在上面的基础上,再编写一批基础函数,比如
add
、sub
、mul
、div
。也可以编写一些高阶函数,比如
filter
、map
。
实际上,我们已经用模板实现了 Scheme
的一个子集,只是语法不同。Scheme
的嵌套原括号(),变成了模板语法的嵌套尖括号<>。模板语法写起来更麻烦,更难以阅读,但思路是一样的。
之后再阅读 SICP 这本书,看看如何用最简单的 Scheme 特性写出复杂的程序。再用 C++ 模板语法进行一点改写。看起来就很厉害的样子了。