P0557r1 Good Concepts 阅读报告

• 1. A bit of background
• 2. Generic Programming
• 3. Using Concepts
  • 3.1 Specifying template interfaces
  • 3.2 A short-hand notation
• 4. Defining concepts
• 5. Designing with concepts
  • 5.1 Type/concept accidental match
  • 5.2 Semantics
  • 5.3 Ideals for concept design
  • 5.4 Constraints
  • 5.5 Matching types to concepts
  • 5.6 Gradual introduction of concepts
• 6. Concept overloading
• 7. The short-form notations
  • 7.1 auto arguments
  • 7.2 Readability
• 8. Language design questions

闲来无事，前段时间看了一个有关 C++20 ranges library 的网页，里面推荐了这篇 paper P0557r1（鼻祖），正好早想了解一下 concepts 了，于是就花点时间读一下写点报告吧。
Download link: http://www.stroustrup.com/good_concepts.pdf

1. A bit of background

关于背景这块，我了解的是比较少的，因为平时也没有开发过什么较大或较难的 C++ 项目，对模板这块理解还是不够。当然，有机会还是会回去读 C++ Templates 的。
传统的 C++，无法提供很好的、对模板参数的限制，换句话说就是无法保证模板参数的正确。1987年，paper 的作者想要设计满足下列三项的模板：

• Full generality/expressiveness
• Zero overhead compared to hand coding
• Well-specified interfaces

但是实际从设计中的代码中得到的反馈，有一下三个问题是：

• Turing completeness
• Better than hand-coding performance
• Lousy interfaces (basically compile-time duck typing)

图灵完备我不是很懂，性能和编译期鸭子类型稍微可以理解一点。

于是作者和另外两位大佬在 2009 开始起草设计 concepts。一波三折之后，concepts 作为 ISO Technical Specification 加入了 C++15.

2. Generic Programming

这里需要说明一下泛型编程的诞生过程：

// 传统代码
double sqrt(double d);    // C++84: 接受任何一个以 double 型的 d

double d = 7;
double d2 = sqrt(d);     // fine: d is a double

vector<string> vs = {"Good", "old", "templates"};
double d3 = sqrt(vs);    // error: vs is not a double

看他这个意思应该是 80s 还没有函数模板？

// 1990s style generic code:
template<class T> void sort(T& c)
{
    // 排序的算法代码
    // 但是可能会依赖 T 类型的，比如 [], < 操作符
}

vector<string> vs = {"Good", "old", "templates"};
sort(vs);      // fine

double d = 7;
sort(d);   // error: d 没有 [] 操作符

这里会遇到不少问题：

• sort(d) 的错误提醒是冗长、给的建议不精确，简单说就是废话连篇。这个真的是平时写 C++ 遇到过最恶心的事情了，深有体会，我也不赘述了。
• 函数模板的声明和定义必须要写一起。严重破坏代码结构。
• 参数类型对 sort 是隐藏的。
• 错误信息只会在 sort 模板完成实例化后才会出现，而且调试上会遇到麻烦。
• template<typename T> 非常冗长、受限制。

了解到这些问题之后，他们就想设计一种方案，类似：

void sort(Sortable& c);

这样的代码的优点：

• simple 的泛型代码和非泛型代码一样 simple。
• advanced 的泛型代码构建起来会比原来容易太多。

3. Using Concepts

concept 是一个编译期谓词，换句话说它会 yields 一个布尔值。比如一个 concept C，使用 C<T> 这样的表达式表示“true if T 满足 C 的需求，false otherwise”。而且这还不一定是一个一元谓词，比如可以有个 concept 类似 Mergeable<In1, In2, Out>。这种谓词相比传统的模板元编程解决方案要方便太多（这些元编程技术在 STL 中演变出来的就是 traits 技术了，噩梦）。
当然，我们可以定义自己的 concept，而且也会有 concepts 库这种东西。

3.1 Specifying template interfaces

首先看下怎么用 concepts 去修饰 std::find() 的变体：

template<typename S, typename T>
        requires Sequence<S> && Equality_comparable<Value_type<S>, T>
Iterator_of<S> find(S& seq, const T& value);

这里的两个 concepts 简单到顾名思义了：Sequence<S> 表示需要 S 类型满足“有 begin() 和 end() 成员函数”；Equality_comparable<Value_type<S>, T> 则是要求 Value_type<S> 与 T 之间要能“用 ==进行比较”。
另外是比较简单的 alias templates：

template<typename X> using Value_type<X> = X::value_type;
template<typename X> using Iterator_of<X> = X::iterator;

3.2 A short-hand notation

template<Sequence Seq>
void algo(Seq& s);

这样的语法总结一下就是：

template<C T>

就是

template<typename T>
        requires C<T>

的意思。

4. Defining concepts

直接看语法，以 Equality_comparable 为例：

template<typename T>
concept bool Equality_comparable = 
        requires (T a, T b) {
            { a == b } -> bool;
            { a != b } -> bool;
        };

意思是 T 类型必须提供返回 bool 类型的 == 和 !=（这里说准确一点是返回可转换为 bool 型的类型）。
requires 表达式不会实际执行，但是它可以左右编译器的行为。
再看稍微复杂一点的：

template<typename T>
concept bool Sequence =
        requires(T t) {
            typename Value_type<T>;
            typename Iterator_of<T>;

            { begin(t) } -> Iterator_of<T>;
            { end(t) } -> Iterator_of<T>;

            requires Input_iterator<Iterator_of<T>>;
            requires Same_type<Value_type<T>, Value_type<Iterator_of<T>>>;
        };

这里很明显是在说明 typename 声明关联类型和 requires 嵌套的语法。

template<typename T>
concept bool Sortable =
        Sequence<T> &&
        Random_access_iterator<Iterator_of<T>> &&
        Less_than_comparable<Value_type<T>>;

这里说明了 concepts 可以使用 && 操作符连接（我记得没错的话 || 也可以）。
然后要注意一下双参数的 Equality_comparable concept：

template<typename T, typename U>
concept bool Equality_comparable = 
        requires (T a, U b) {
            { a == b } -> bool;
            { a != b } -> bool;
            { b == a } -> bool;
            { b != a } -> bool;
        };

这个比较要是双向的。

5. Designing with concepts

paper 中提到的“本 paper 中最重要的部分”：有关如何设计 good concepts。

5.1 Type/concept accidental match

让 concept 提供一些基础概念——如操作符和成员类型。原文中举了两个反例：
第一个：

template<typename T>
concept bool Drawable = requires(T t) { t.draw(); };

这个 Drawable 是用来解决 OO 问题的。我们想表达的意思是：T 是一个能“绘画(draw)的”某物。但是很糟糕的是，能“拉、吸引(draw)的”的某物也被包含了进来。这是一种 concept 和 type 的范围的不匹配。
第二个：

template<typename T>
concept bool Addable = requires(T a, T b) { { a+b } -> T; };

可加的。对于普通的数字来说确实没错，但是对于 string 而言，虽然它有对 operator+() 重载，但是表达的是“字符串拼接”的意思，而并不是“加法”的意思。这是另一种 concept 和 type 的不匹配。

于是这个部分想告诉我们的：不要让你的设计受到自然语言的影响了，大概意思就是，不要因为以自然语言命名的 concept 产生歧义，这是一种对设计的破坏。

5.2 Semantics

要从语义学角度出发设计 concepts。这个我不是很懂，但是文中列举了几个用处：

• C/C++ 内置类型的 concepts（换句话这里应该可以说 POD）：算术运算、字面值、浮点。（然后这里提到了一句前面的 C 不是多余的，C 也有 concepts）。
• STL 中的 concepts，比如迭代器、容器。
• 数学 concepts，比如半幺群（monoid）、群（group）、环（ring）、域（field）。
• 图论 concepts，比如边、节点；图、DAG 等等。

同样的，设计这些 concepts 需要考究能匹配一个领域概念的完整（必须且足够的，说中文就是不多不少）的属性（包括操作符、类型等）集合。

5.3 Ideals for concept design

这里提到的是一个叫 “plug compatible” 的概念，说人话就是：

• 我们想到写出来的算法支持的类型的更多变体
• 我们想要定义的类型支持的算法的更多变体

注意，这里不是说支持“更多的”类型和“更多的”算法。接下来我将介绍为什么要这么说。

举个例子，比如一个简化版的 accumulate：

template<Forward_iterator Iter, typename Val>
        requires Incrementable<Val, Value_type<Iter>>
Val sum(Iter first, Iter last, Val acc)
{
    while (first != last) {
        acc += *first;
        ++first;
    }
    return acc;
}

很好，这里使用了 Incrementable concept 来请求 += 操作符的支持。但是：

• 我们并没有考虑 Val 类型是否 copyable 且/或 movable.
• 我们不能对一个只提供 + 和 = 而不提供 += 的 Val 使用 sum.

这也就是上面不说“更多的”的原因。我们的 ideal，是不是要满足“最小化的需求”，而是“使得需求正好够用”。

5.4 Constraints

这部分依旧是在说 concept 设计完整性的，大段英文我没有读懂。
如果一个 concept 对于广泛用途设计的过于 simple 了且/或确认简明的语义，则可以用于为更完整的 concept 添砖加瓦。有时候我们就说这些过于简单或者不完整的 concepts “constraints”，用于与 “real concepts” 相区分。

5.5 Matching types to concepts

这一部分教我们怎么判断一个 type 是否匹配一个 concept。

class My_number { /*...*/ };
static_assert(Number<My_number>);

C++11 引入了一个新的类函数的关键字 static_assert 用于静态断言。
同样作为断言，std::assert() 用于一个布尔值断言，运行时执行；static_assert 用于一个谓词，编译期由编译器判定。

5.6 Gradual introduction of concepts

template<Sortable S>
void sort(S& s);

我们的 sort 需要参数 s 是 sortable 的，但是我们并不知道 std::sort 需要什么，即使我们有仔细阅读标准，但是也可能漏掉 requirements；再进一步，在调用处，我们并不知道某一个函数的实现中是不是有一些 facilities 是我们没有 required 到的；再进一步，函数的实现随时可能改变，需求也随时在改变。
但是这并没有什么太担心的，因为我们在 requires 中提供的新添加的需求，也只不过是把报错信息提前了而已。

另外这里提到的是编译器、平台与 concepts 的兼容问题。比如我们在使用一个老款的编译器或者在编译器参数上设定使用老版本编译，我们有关 requires 的代码就不能使用了。这里有一个非常容易且使用的技术——宏。

#ifdef GOOD_COMPILER
#define REQUIRES requires
#elseif
#define REQUIRES //
#endif

对于 short-hand concepts，我们可以：

#ifdef GOOD_COMPILER
#define SORTABLE Sortable
#define ITERATOR Iterator
#elseif
#define SORTABLE auto
#define ITERATOR auto
#endif

当然，也可以写更复杂的代码让老版本也能进行一定的 concepts 判定，比如使用 enable_if，在这里就不赘述了。

6. Concept overloading

举个例子：

template<typename Iter> void advance(Iter p, int n);

对于这样一个 advance() 模板，我们想到对于不同的迭代器执行不同的行为：

• 基本的 forward iterators 就使用循环进行逐次自增。
• random-access iterators 可以直接使用 += 进行位移。

我们知道，这是可以使用 traits 中的 std::true_type 和 std::false_type 配合 iterator category 使用，也就是 SFINAE。但是作者他们本身创造 concepts 就是为了希望“simple 的泛型代码和非泛型代码一样 simple”（见本 md 文件 L68），于是他们希望，concepts 也能帮助函数进行重载，比如像这样：

void advance(Forward_iterator p, int n) {
    while(n--)
        ++p;
}
void advance(Random_access_iterator p, int n) {
    p += n;
}

接着我们要为如此的 concept 匹配制定基本规则：

• 如果仅能匹配某一个函数重载的 concept 需求，则调用它
• 如果匹配不到任何一个函数重载的 concept 需求，这个调用就是错误的
• 如果匹配到两个，则需要判定其中一个 requirements 是不是另一个的子集：
  • 如果是，则调用更严格 requirements 的那一个
  • 如果不是，则调用错误（也就是 ambiguous）

其实不管是根据常识，还是 iterator category 的继承关系，我们都很清楚 Random_access_iterator 定是 Forward_iterator 的一个子集，意思就是前者的要求比后者更严苛，于是理所当然，如果能两个都匹配，必会调用 Random_access_iterator 的版本。
但是非常可惜的是，不同于 iterator categories 的继承和多态，concepts 是不支持继承的。希望以后的 C++ 版本能支持。

7. The short-form notations

先行的 C++ 版本中，concepts 是如此使用的：

template<typename Seq>
        requires Sortable<Seq>
void sort(Seq& s);

用 short-hand 写是这样的：

template<Sortable Seq>
void sort(Seq& s);

但是作者希望的是这样的：

void sort(Sortable& s);

我们来看一个稍微复杂一点的 concepts 的使用：

template <Sequence S, typename T>
      requires Equality_comparable<Value_type<S>, T>
Iterator_of<S> find(S& seq, const T& value);

这里面提到了两样东西——“rewrite rule” 和 “the onion principle”。第一个，就是俗称的语法糖了吧，使用更简单的形式去取代一种更复杂但是通用的格式；第二个规则就如洋葱，我们的设计应该优先（default）考虑最简单的形式，如果最简单的形式不能表示，就像剥去洋葱的一层一样，寻找较为复杂但更通用一点的写法，如果找不到，就再剥一层。原文甚至讲了个冷笑话：Each layer gives you more flexibility, and make you cry more(because of the added work and the added opportunities for mistakes)，这个双关语真是绝了。比如我们上面的 Equality_comparable 其实就满足这样的规定：因为很明显这种双参数的 concept 不能使用 short-hand，虽然我们很想用，但是没办法，只能写到 requires 里面了。

7.1 auto arguments

void f(auto x);

这个 auto 算是一个限制最小的 “concept” 了（终于看到一个符合作者想法的 concept 了，泪目），换句话说所有的 concepts 都应该是 auto 的子集。auto 作为参数类型和返回值类型的提案作者早在 01 年就发起了，终于终于终于，C++14 在 lambdas 中支持了。

Tips:
C++11 开始引入的函数返回值后置，使得自动推导函数返回值类型成为可能。但是这个自动的过程需要写手动的推导代码（迷乱）：

auto add(int a, int b) -> decltype(a+b) {
    return a + b;
}

经过测试，g++ 的 -std=c++14 flag 就已经支持下面的代码了：

auto add(auto a, auto b) {
    return a + b;
}

加上 flag -fconcepts-ts 甚至没有 warning。这部分属于 concepts TS，其实也就相当于是私货。
C++17 标准下的 clang++ 是无法编译通过以上的代码，那是因为在 C++17 不开 TS 的情况下，还是不支持 concepts 的。但是，C++20 下编译可以通过。

我们可以定义一个像这样的东西：

concept bool Any = true;
void ff(auto x, auto y);
void gg(Any x, Any y);

相较 ff()，gg() 的限制是两个参数类型必须相同。

7.2 Readability

这一部分跟语言设计有关系，稍微浏览了一下。稍微总结一下，就目前的 concepts 在阅读性上还是存在一些缺陷的，也是亟须修改的问题，作者认为这关系到 concepts 的设计和可维护性。

8. Language design questions

这个部分暂时不读了，跟程序员关系不大。等接触 language design 之时，将会再回来拜读。