发现面向用户的概念

标题：Discovering a User-Facing Concept

日期：2022/01/15

作者：Christopher Di Bella

链接：https://www.youtube.com/watch?v=_rVmJIfPlqI

注意：此为 AI 翻译生成 的中文转录稿，详细说明请参阅仓库中的 README 文件。

备注：换了新电脑，whisper 暂时还没装上，先直接用油管字幕处理，后续有空替换。

简介与背景

大家好，我是 Christopher Di Bella，欢迎收看《发现面向用户的概念》（Discovering a User-Facing Concept）。

几年以来，我一直对使用和编写 C++ 概念（Concepts）非常感兴趣。大概是在 2016 年左右，我开始对它们产生浓厚的兴趣。曾有一段时间，我以为自己已经理解了应该如何编写概念。直到 2018 年，Eric Niebler 在推特上发了这样一段话，彻底颠覆了我对编写概念的思考方式。他说：“虽然概念是对类型的约束，但你不能通过观察系统中的类型来找到它们；你需要通过研究算法来发现它们。”

从那时起，我真正改变了自己关于如何编写概念的思维方式。但在我和人们交谈时，他们提出的问题表明他们仍然有些困惑。因此我想，既然概念（Concepts）作为语言特性加入标准 C++ 已经有一段时间了，我们确实应该做一个演讲，探讨如何有效地使用这个语言特性。

这意味着，本演讲不是一个教你如何使用“概念”这个语言特性的教程——你应该已经知道该语言特性在 C++ 中是如何工作的了。如果你对概念的语法还不熟悉，请去观看 Andrew Sutton 的演讲《60分钟掌握概念：你需要知道的一切以及你不需要知道的》（Concepts in 60: Everything you need to know about concepts and nothing you don’t）。这可能是迄今为止我见过的最好的关于概念的演讲。原因之一在于，它深入探讨了恰当的使用方法，而没有陷入该语言特性那些晦涩难懂的复杂细节中。Andrew 是 Concepts TS（技术规范）的主要作者之一，他大力倡导了最终进入 C++20 的内容，并且他也是撰写那篇促成 Eric Niebler 在 C++20 中发起 Ranges 运动的前身论文的作者之一。

这是一个关于 泛型编程（Generic Programming） 的演讲，这意味着我们将花大量时间来思考、分析算法，并研究它们的需求。如果你不熟悉什么是泛型编程，或者你需要泛型编程的入门知识，请观看 Sean Parent 在 Pacific C++ 大会上的关于泛型编程历史的演讲，标题就叫《泛型编程》（Generic Programming）。每当我在本次会议中提到 Sean 的主题演讲时，我绝对是指 Sean 在 2018 年 Pacific C++ 上的那次演讲，而不是他即将在这周五发表的那次。

有很多人为我提供了帮助，我在此想向他们致谢。幻灯片上列出的人员，都以某种形式提供了反馈，或者为我能够站在这里发表这个演讲提供了支持。

本次演讲基本上分为三幕，如果时间允许，后面还会有一个尾声。我将在第一幕和第二幕结束时接受提问，然后根据是否还有时间进行尾声部分，来决定是否在第三幕结束时接受提问。

第一幕：什么是算法与概念

让我们开始吧。我们要绕回到 Eric 的那条推特，他提到要“通过研究算法来发现概念”。

现在有人对我说：“Chris，我不一定会使用 STL 算法啊”或者“如果我想编写某种定义了一类类型的概念，我该怎么写呢？”因此，让我们先从弄清楚 “什么是算法” 开始。

对于“算法”一词，我从两本非常受欢迎的相关大学教材中提取了两种不同的定义。但基本上它们都在说： 算法是针对某个问题的解决方案，它包含某种计算过程，接收一个输入并给出输出。 就这么简单。我真正想强调的是，“算法”这个词并不局限于 <algorithm> 和 <numeric> 头文件中的那些函数。

这意味着，如果你写了一个计算最大公约数（GCD）的函数，或者一个 A* 寻路算法，即使它们不一定是基于范围（range-based）的，它们仍然算作算法。它们只是通过计算来解决某种问题的函数而已。这就是你需要了解的关于“算法”一词的全部内容。

在本次演讲中，我们将研究一个基于范围的算法，因为那是我的背景所在。但这并不意味着你必须拥有一个基于范围的算法。事实上，文献中深入探讨非基于范围内容的情况，远远多于最初关于基于范围的内容。

接下来我们进入人们经常问的第二个问题：这对类型意味着什么？我们可以编写一个 Container（容器）或者 Number（数字）概念吗？

请千万不要这样做。

概念（Concepts）不是 Java 和 C# 中 interface（接口）关键字在 C++ 中的等价物。我们不使用它们来定义一个类型应该具有哪些属性。而且退一步讲，即使我们这样做了，这也会给我们实现一个功能完备的算法带来很多问题。因为算法并不一定总是会使用接口提供的所有内容。例如，cppreference 上的 Container 具名要求（named requirement）中有一个名为 max_size 的成员函数。但至少在我的经验中，它的使用频率非常非常低。

因此，概念并不是对其他语言中 interface 关键字的映射，那是一种完全不同的语言特性，只是两者之间有少量的重叠而已。

概念的根基来源于泛型编程。在《从数学到泛型编程》（From Mathematics to Generic Programming）一书中，作者将泛型编程定义为：“一种专注于设计算法和数据结构的方法，使得它们能在最通用的环境下工作，而不会损失效率。”

书中接着提到，使用 STL 的人会开始质疑，像模板元编程（Template Metaprogramming）这样的东西算不算是泛型编程的一部分？作者指出，那是在 C++ 中促成泛型编程的手段，但它本身并不真正属于泛型编程。

这一点很重要，因为归根结底，泛型编程是一种对待编程的态度，而不是 C++ 中的某种特定事物。我在这里将其与面向对象编程（OOP）做了一个类比：模板和元编程与泛型编程的关系，就像类和成员函数与面向对象编程的关系一样。换句话说，它们是实现工具，但完全不代表其本质。你不是为了写一个类而去进行面向对象编程，你是通过使用类来对程序设计做些什么。泛型编程在对待模板方面也是非常相似的。

泛型编程也与 抽象代数（Abstract Algebra） 有着非常紧密的联系，它确实脱胎于抽象代数。Wolfram MathWorld 将抽象代数定义为：“处理抽象代数结构而不是我们日常生活中处理的常规数字系统的一组主题。”

《从数学到泛型编程》中写道：抽象代数的一个显著特点是，我们可以为一个结构（比如群 Group）证明各种结果，而无需了解群里的具体元素是什么，也无需了解其操作是什么。如果你不熟悉“群”，Steve Downey 在他的演讲中非常出色地讲解了群，你应该去看看那个视频。简单来说，它是一种数学描述，描述了某个对象集合以及遵循某组规则的操作。

我想在这个段落上多花一点时间，带着强调的语气给你们重读一遍： “抽象代数的一个显著特点是，我们可以为一个结构（比如群）证明各种结果，而无需了解群里的具体元素是什么，也无需了解其操作是什么。”

现在我要把这个关联拉回到泛型编程上。这是我对这段话做的一点微调： “泛型编程的一个显著特点是，我们可以为一个概念（比如范围 Range）证明各种结果，而无需了解范围里的具体元素是什么，也无需了解其操作是什么。”

让我们在幻灯片上来回切换一下，这样你就能看到视觉上的差异。并没有太大的改变，我只是修改了几个名词，但句子的完整逻辑依然成立。

所以我喜欢这样思考这种联系：泛型编程是连接理论上的抽象代数与编程（在当前语境下是 C++）之间的桥梁。因为我一直在谈论抽象代数，你可能会担心自己需要有抽象代数的背景才能听懂这次演讲，但其实你不需要。只要你能看懂第一段代码，并明白它是如何转换成第二段代码的，且它们对于 int 来说含义相同，但第二段代码还涵盖了描述完全相同上下文的更多情况，那你就完全没问题了。

我不是经过科班训练的数学家，我在大学里确实挂了不少数学课，通过的那些也是勉强及格。所以我真心希望这张幻灯片能给你一点信心，你不需要成为一名正式的数学家就能理解我们将要在本节课讨论的所有内容。

让我们回顾一下，因为这是一个关于概念（Concepts）的演讲，而我还没有真正谈到什么是概念。

概念实际上只是针对某些算法或数据结构的一组具名要求（named requirements）。这些要求以三种密不可分的形式出现。我的意思是，在概念的工作机制中，你通常会在发现其中一种要求时，自然而然地发现另外两种同时出现。

基本上有三种不同的要求：

  1. 语法要求（Syntax requirements）：通俗地称为约束（constraints）。约束的例子比如：要求迭代器支持 ++i 的语法。

  2. 语义要求（Semantic requirements）：通俗地称为公理（axioms）。公理的例子比如：++i 会使迭代器移动到下一个元素。

  3. 复杂度要求（Complexity requirements）：它没有一个花哨的别名，但复杂度要求的例子比如：++i 操作必须在常数时间（constant time）内完成。

这就是所有三种要求介入的地方，在整个演讲中我们还会反复回到这一点。

接下来要说明的是，本演讲的标题最初是《设计一个面向用户的概念》（Designing a User-Facing Concept）。但是当我和 Eric Niebler 讨论同步我们的演讲内容时（因为我不确定是否会有重叠，结果证明并没有），他指出：我们并不“设计”我们的概念，我们设计我们的算法，然后通过研究算法来“发现”我们的概念。

就像植物、动物和数学一样，它们只是客观存在着。有些人甚至假设，即使没有物质和能量，数学依然可以存在。我们只是发明了符号来描述数学，但我们并没有发明数学的规则。同样，我们也不设计对象之间的关系，我们只是观察并报告它们。概念描述了类型和对象之间的关系，这就是为什么我们是“发现”它们，而不是“设计”它们。

Eric 和我想表达的核心观点是： 在开始考虑编写概念之前，我们必须、始终、永远要考虑用例（use cases）。 永远需要思考用例。

这标志着第一幕的结束。我将暂停大约一分半钟，解答任何开放的问题。

(在此期间没有看到聊天中有任何问题，所以让我们进入第二幕。)

第二幕：分析与抽象用例

正如我承诺的，我们需要考虑观察用例，所以这里有一些用例。 这有点像一个互动环节——我在屏幕上放了六个例子，给你们一点时间阅读它们。能有人告诉我，你们认为这六个算法在描述什么吗？

(互动结束) 没错，它们都是左折叠（Left Folds）。如果你不熟悉左折叠的概念，基本上就是：我们从某个累加器（accumulator）开始，遍历元素，将它们从某种元素序列（有点像向量）收集（合并）成一个标量。

这些操作在很多地方都会出现。数学中的求和或求积运算就是左折叠的一种形式；许多 STL 算法实际上也是左折叠，Conor Hoekstra 在他的一些演讲中对此进行了详细介绍。中间的两个例子我认为是 all_of 和 any_of，而右下角的那一个是 max_element 的实现。

这些都是左折叠自然而然地出现在其他算法中的例子。

Barry Revzin 为 C++23 撰写了一份名为《Ranges fold for C++23》的提案（P2322）。在第二幕中，我们将慢慢梳理该提案中提出的内容。我需要说明的是，Barry 在这方面投入了大量的工作，我非常感谢他的付出。我还需要指出，P2322 是一个提案，这并不能保证它最终会成为标准 C++。任何被标准化的内容都可能与我们在本次会议中讨论的内容有所不同。这是一个提案，而不是承诺，我谈论的内容与之相关，但我不保证我们最终会得到这些功能。

我们需要做的第一件事是规范化代码。你可能已经注意到，我给出的例子采用了三种不同的格式。当我们要概括一个算法，将其从具体的用例变成某种抽象算法时，我们真的需要让它们处于相同的格式，这样才能更容易地证明这些算法是相同的，它们都是在解决同一个问题，只是稍微调整了一些细节。

所以我们要做的第一件事，是将这种复合操作转换为中缀（infix）操作。这使它们与逻辑与（AND）和逻辑或（OR）的例子格式一致了。但这仍然不够好，因为它是中缀操作，而在 C++ 中，我们的大多数操作希望以前缀（prefix）模式进行：函数名在前面，两个参数在括号里面。目前的格式并非如此，所以我们需要再次对其进行规范化。

最终，我们将那四个中缀示例转变成了函数调用的语法格式（逻辑或操作我也写了，只是屏幕上放不下，但它也遵循这个格式）。一旦我们把它变成了这种最终格式，我们现在就可以开始思考它的属性了。我们可以指出这些属性并说：“这些就是我们在通用设置中想要讨论的东西。”

我会给你们一点时间消化我们通过肉眼观察能发现的属性，但我会先给出我观察到的第一个属性，让你们了解我在谈论什么： 那就是，我们正在迭代一个序列，这意味着该算法使用了一个范围（Range）。

好的，下一件事是，我们会读取我们正在迭代的内容。在这两种情况下（求和与求最大值），我们都将 *i 作为参数传递给 plus 和 max，这意味着我们实际上是在读取它。因此，我们拥有一个所谓的可读范围（Readable Range）。

然后我注意到的下一件事是，我们从不回头看之前的元素，我们总是处理当前元素，然后移动到下一个元素，从不回头。这意味着它是所谓的单趟算法（Single-pass Algorithm）。我们永远只考虑当前元素。这将在稍后发挥作用。

我们的操作接受两个参数作为输入，所以它是一个二元操作（Binary Operation）。

最后，操作返回的结果会直接赋值给我们的累加器。在第一种情况下，累加器是 sum；在第二种情况下，它是 max。

好，现在让我们将算法参数化，也就是对其进行模板化，并应用一些属于“容易摘到的果子”类别的概念。我们将要应用的概念是 input_iterator（输入迭代器）和 sentinel_for（哨兵）。如果你对这些不熟悉，Kristen Brindle 在 CppCon 2019 上对 Ranges 术语做了非常精彩的阐述。

这两个是最容易添加的约束要求，它们源自我们通过观察看到的前三个属性。我们在这里看到的代码很容易让人想起 std::accumulate，但我们还可以改进它。

现在屏幕上是另一个具体的用例，我们在其中拼接字符串。这可能不是拼接字符串的最佳方式，但这是我为了传达我想表达的内容而能使用的最快方式。在保留左折叠操作的同时，我们如何改进这段代码呢？

我的想法是，由于我们保留了左折叠操作，必须明白一点：我们正在从 spaceless_sentence 中读取数据，然后立即又写回其中。所以我们永远不需要对读出的内容使用超过一次。这意味着我们可以将 spaceless_sentence 移动（move） 到拼接操作中，而 spaceless_sentence 获取返回的任何内容都将成为它的新值。

这就是我们想要做的改进。现在我们可以将其应用于我们的抽象算法，以便在那些因拷贝和直接赋值给刚刚读取的对象而可能导致性能受阻的情况下，利用这一特性。

现在我们的算法变成了这样，我们终于可以开始分析一些更深层的需求了。

我们首先来看算法的主要部分，即操作的调用（invocation）。但在那之前，我们要先考虑初始值。因为我们将初始值作为第一个参数移动到操作中，我们必须说明它是可移动构造的（move_constructible）。并且由于我们又要把结果拿回来赋值给它，我们需要它也是可移动赋值的（move_assignable）。当我们同时有这两个要求时，我们称其需要是可移动的（movable）。

这就是我们可以针对算法得出的第一点：类型 T 现在需要是 movable。

解决了 T 的问题后，我们可以开始考虑我们的 操作（operation） 了。 我们想在这里说明的是，操作（op）是一个可调用的对象（invocable），其第一个参数是类型 T，第二个参数是迭代器的引用类型（iterator’s reference type）。明确了这三点信息后，我们可以说：在涉及 T 和迭代器引用类型时，op 满足 invocable 概念。我们可以将其作为我们的第二个约束要求应用上去。

由于我们将调用的结果赋值给我们的累加器（即初始值），而调用的结果类型可能与实际的类型 T 不同，因此我们还要说明调用的结果是可赋值的：即它能被赋值给类型 T（assignable_from）。

最后，因为某些我现在记不清的原因，我们还希望 op 是可拷贝的（copyable）。

这样，我们就确立了描述 T、可调用对象以及迭代器引用类型之间关系的约束要求。这里包含的信息非常多，并不是很容易消化。我和 Sy Brand 明天在我们的文档主题演讲中会深入探讨代码的可读性/易消化性。但正因为它不容易消化，我们想要将它抽象到一个被称为 “细节概念”（Detail Concept） 中去。

细节概念是面向内部的，不是面向用户的，这意味着它不符合本次演讲标题的标准。它的结构安排是为了能给我们提供尽可能好的诊断信息，并以编译器能够理解的方式描述这些约束。你在前一页幻灯片上看到的和现在看到的，实际上只是这一点的区别。除此以外没有真正的结构变化，我们只是让算法的接口变得更容易理解一点。

至此，这差不多就是带有一些约束的 std::accumulate 在 C++20 中的样子。

但是接着有人带着一个新的用例走过来。他们想要将一组数字相加，在这个例子中，数字是 1.0、0.75 和 0.25。当他们传入初始值 0.0 时，他们得到了返回值 2。这很棒，因为这是正确答案。但当他们传入初始值 0（整数零）时，他们没有得到正确答案，他们得到的是 1。

问题在于，我们在上一张幻灯片上的代码会导致这样的情况：我们本质上有一个 int 类型的 sum，多亏了 double 到 int 的转换，1.75 会被截断为 1，随后的 1.25 也会被截断为 1。所以最终结果实际只有 1 而不是 2。

因此，Barry 在提案中提出了一个修复方案（屏幕上所示）。它解决了我们刚刚展示的用例：我们可能想传入一个整数作为初始值，但依然能得到正确的理论答案 2 而不是 1。为了让理论与实践同步，我们采用的方法是：取我们刚才谈论的操作调用的结果类型（它可能与 T 是或不是同一种类型），并将其用作左折叠新的返回类型。

屏幕上变灰的部分是我们已经考虑过且不需要重新考虑的内容。问题在于，我们刚刚看到的算法已经不再满足我们原本设定的约束条件了。特别是底部的两个约束已经与我们屏幕上的现有代码脱节了。

所以我们首先引入第二个细节概念，以提高我们原本的细节概念 indirectly_left_foldable 的可读性。因为如果我们不使用第二个细节概念，过一会儿它就会变得非常庞大且难以处理。

我们阅读这个名为 indirectly_left_foldable_impl 的细节概念的方式是：前三个参数与 indirectly_left_foldable 完全相同（操作、T 和迭代器）；然后我们还有个叫 raw_result 的东西，这是调用实际产生的结果类型；接着我们有 decayed_result，它是调用结果类型衰变（decay）后的类型。我们会在后面的幻灯片中说明为什么衰变很重要。但现在关键是要注意，第 4 行屏幕上显示的 decayed_result 和类型 R 描述的是同一个东西。

让我们继续往下看新的表达式。我们要考虑三个新的表达式。

先从最简单的一个开始：如果范围为空，我们在基础情况（base case）下要返回的东西。我们只需将初始值转换为 R 返回。我们在这里所做的是将 T 转换为 R，这意味着 T 必须能够转换为 decayed_result（convertible_to）。这是第一个要求。

第二个要求是有一个新的调用表达式，我们需要考虑它。我们要说明的是，当我们调用 op 时，第一个参数现在的类型是 R（因为那是我们新的累加器对象），而第二个参数仍然是迭代器的引用类型。这意味着，操作必须能用 decayed_result 和迭代器的引用类型来进行调用（invocable）。

如果此时回头看，我们发现这个表达式其实和最开始累加器是 init 时是一样的，只不过现在换成了 accum。这意味着 decayed_result 也需要像 U 一样是可移动的（movable）。同样地，使用新累加器和第一个元素的值（迭代器指向的值）来调用 op 的结果类型，可能与累加器本身的类型不同。所以我们需要确保调用结果能够赋回给 accum。我们因此得到了底部这句非常长的话，准确地描述了这个要求。

最后，我们来说明为什么类型衰变（decay）很重要。操作可能返回类似引用的东西，但根据 auto 的规则，类型在声明时会发生衰变。所以我们要在这里指明：原始的返回类型（raw_result）可以转换为衰变后的返回类型（decayed_result）。

讲到这里，我已经向你们抛出了一大堆不同的约束要求，所以我准备把它们打包在一起，放入这个 indirectly_left_foldable 的实现中。我们又看到了两个细节概念。再次强调，这些不是我们感兴趣的面向用户的概念。

这把我们带到了第二幕的结尾。我在这里给你们留下一个问题：我们能更快地计算这些操作吗？我们会在第三幕中讨论。

(现在第二幕结束了，我将花大约一分钟回答问题。)

问题： left_foldable 这个概念看起来像是一个专门为单一算法设计的概念。

回答： 没错！你预判了我在尾声部分本打算回答的一个问题，这很好。基本上，是的，这就是为什么它是一个“细节概念”（detail concept）。它只是一个内部细节，因为它仅仅、且专门针对一个非常特定的算法。我们接下来要讨论的是更加通用的东西，它适用于更广泛的范围，并且不会被放在 detail 命名空间中。这样回答解答你的疑问了吗？

问题： 是否存在一个规定了返回类型的 invocable 概念？

回答： 很遗憾，没有。我认为我们需要去寻找如何对那一点建模的方法，但目前的 invocable 并不能解决具有特定返回类型的需求。我们需要将返回类型作为单独的要求来讨论。

好了，我把剩下的问题推迟到演讲结束。我们的时间把控得很好，我想我们能进入尾声环节。

第三幕：推导面向用户的概念

第三幕的标题是：归约为一个面向用户的概念。

在第二幕的最后，我问了一个问题：我们能更快地计算这些操作吗？ 答案是：也许可以。

有一种技术叫循环展开（Loop Unrolling）。我们或者编译器可以分析循环，看看能做些什么来执行更多的操作，并利用指令级并行（instruction level parallelism）。我不会深入讲解指令级并行，但我在演讲最后提供了一些资源，如果你对这个主题感兴趣，可以去深入了解。

如果我们为获取最大值（max_element）的示例手动展开循环，我们可以发现在 GCC 上，fold_left 的速度要比我为循环展开版的折叠写的基准测试慢得多。顺便提一句，我们将这个展开后的折叠称为 reduce，稍后我会详细说明。

原因在于，fold_left 所做的是依次考虑序列中的每一个元素。它只是把它们组合在一起，严格从左到右按顺序执行。但在循环展开中，我们可以同时（并行）考虑多个元素。一旦我们在同一时间或几乎同一时间执行了那些操作，我们就可以将它们合并成一个新的结果，然后再将该结果合并到累加中，接着循环回去并继续这样做，直到元素耗尽。

这就是循环展开能实现的优化。但在我们继续之前，我需要强调的是：在你试图手动优化代码之前，必须始终对其进行基准测试（benchmark）。

如果你去看上面那个乘积计算的例子，它产生了非常不同的结果。对于 GCC 来说，未展开的左折叠的乘积运算确实比展开的慢；但是当我切换到 Clang 时，我发现单纯的平铺 for 循环版的乘积运算，比它的 reduce 对应版本快得多。

这让我很惊讶，所以我与一位编译器优化专家朋友聊了聊。他们说： 每当程序员试图自作聪明地超越优化器时，优化器通常就会退居二线了。 我原以为在最坏的情况下它们至少表现相当，但事实证明并非必然如此。所以，在你们试图在自己的算法中进行循环展开之前，请务必同时对朴素（naive）的实现和“程序员觉得聪明”的实现进行基准测试。

尽管如此，我们还是要继续看看 fold_left 展开后的版本，因为它确实引入了一些有趣的想法。

在 C++ 中，fold_left 的展开版本被称为 reduce。因为 std::reduce 身上附带了一些额外的约束要求，这些要求允许我们在指令级别，以及（如果可能的话）在数据级别利用并行性。这里我们只着眼于能利用指令级并行的部分，但如果你做更深入的分析，这些要求同样适用于数据级别的并行。这就是我们把这个新算法称为 reduce 的原因。这意味着我们本质上脱离了“左折叠”，我们明白左折叠会产生一个非常特定的结果，但我们想做得更多并加以利用。

让我们来看看 ranges::reduce。这个算法的某些结构在感觉上至少有一小部分和左折叠是一样的。我把这两种操作之间非常常见的部分置灰了。通过展开，我们这里所做的本质上还是左折叠，但在至少有四个元素的情况下，我们展开了一部分循环。（顺便说一下，这是 libstdc++ 中 std::reduce 实现所采用的一种方式。）而在元素少于四个时，我们将回退到 fold_left 算法。

这意味着，fold_left 的所有约束要求现在固有地成为了 reduce 的约束要求，因为我们在底层使用了 fold_left。这意味着 fold_left 的要求构成了 reduce 的基础。这是第一个要求。

现在让我们像分析第二版 fold_left 时那样，来看看 reduce 中的新表达式。 我们有六个新表达式。我们可以通过观察新的迭代器要求，直接解决其中三个。

第一个要求是，我们希望能够表达 last - first。这是一个语法要求。我们还希望这个表达式能够计算 first 迭代器和 last 迭代器（或哨兵）之间元素的距离。这是语义要求（这个范围内有多少个元素）。最后，我们希望这个操作在常数时间（constant time）内发生。否则的话，我们还不如直接遍历并计算它们，那就没有任何优化机会了。所以这就是表达式 last - first 的三个要求。

接着我们有 first += 4。在这里我们表达的是，我们不想顺序遍历每个元素，我们希望能够跳过任意数量的元素，并且要在常数时间内完成。

最后，我们希望能够对任意元素进行索引（在常数时间内）。同样，这是为了让我们不必先跳过它们再解引用，我们可以全在一个漂亮的语法包中完成。

在 C++ 中，只有一个概念能描述所有这些要求（同时也是基础概念），那就是 random_access_iterator（随机访问迭代器）。所以我们在说，对于几分钟前在屏幕上展示的那个特定实现，我们需要一个随机访问迭代器。知道了这一点，我们就可以进入更有趣的概念了。

首先，我们的操作现在被要求：当迭代器的引用类型同时作为第一个和第二个参数时，它是可调用的（invocable）。这是一个重要的问题，因为我们实际上调用了两次操作。如果由于第一个参数和第三个参数相等，第二和第四个参数也相等，但是当我们把它们作为元素传给操作时，却得到了不同的答案，那将是非常令人沮丧的。

对于 left_fold 来说这是可以容忍的，因为它超级通用；但对于像 reduce 这样通常用于数值计算的东西，或者仅仅因为我们现在在并行执行操作，我们希望这些结果是相同的。试想一下，如果 first[0] 和 first[2] 的值是 100，first[1] 和 first[3] 的值是 50，我们的操作是加法，结果我们在第一次调用时得到了 150，第二次调用时得到了 300，这简直太扯了，根本不符合我们的要求。

所以我们要说的是，我们将把 invocable 要求加强或细化为 regular_invocable（正则可调用）。regular_invocable 意味着：我们不仅可以用这些参数调用它，而且我们不允许修改输入参数，也不允许修改正在被调用的对象本身，并且相同的输入必须始终产生相同的输出。

这就是 regular_invocable 的含义：对于某个函数，相等的输入产生相等的输出。所以对于调用操作的地方，现在的约束要求将变成 regular_invocable。

然后，因为我们将操作返回的结果大量地赋值/转换为 R，我们需要声明调用的结果可以转换为 R（我们的返回类型）。

这就结束了那些非常“普通”的约束要求部分（我在说“普通”时加了引号）。我的意思是，我们一直停留在 C++ 的范畴内，还没有涉足抽象代数。所以现在，我们将走进数学的领域，查看一些定义，并根据我们对于该算法的要求，将这些定义引入 C++ 的世界中。

第一件事，我们需要思考 “操作”（Operation） 这个词。我们在数学中非常宽泛地使用它，指代我们调用的某种东西。根据维基百科，“操作”是一个函数，它接受若干个值作为输入（参数或操作数），并返回一个明确定义的输出值。

它具有所谓的域（Domain，即定义域集）和陪域（Codomain，即到达域集）。域是其输入的可能值的集合，陪域是其输出的可能值的集合。

但真正让我们感兴趣的不一定是整个定义域，而是严格定义域（Domain of definition）。实质上，严格定义域是定义了操作的域的子集。如果我们以实数空间中的平方根操作为例，我们可以看到，域是全体实数的集合，但严格定义域将是非负实数的集合。这意味着，在实数空间中，-1 的平方根是无效的。

如果在编程中，我们不向操作传递位于严格定义域内的东西，我们就不一定能得到合理的结果。我们可以得到有意义的结果，也可能得到完全无意义的东西。在 C++ 中，根据具体上下文，这实际上分为三种不同的类别：

  • 未定义行为（Undefined Behavior, UB）：关于这点已经有很多讨论了。

  • 格式错误且无需诊断（Ill-formed no diagnostic required, NDR）：这是 Titus 和 Chandler 在 CppCon 2019 的视频《What is C++》中谈论到的那个非常诡异的东西。

  • 未指定行为（Unspecified Behavior）。

根据情况，如果你超出了严格定义域，你可能会落入这三个类别中的任何一个，或者你可能会得到某种定义良好的行为，比如抛出异常。这也是为什么浮点数被认为是全序的（totally ordered），尽管我们无法比较 NaN（非数字）的值，因为 NaN 不在实数空间中，它们也不在浮点数运算的“可比较对象”空间中。由于那些特定的值不在严格定义域内（它们不可比较），所以我们无所谓，我们在泛型编程中不关心这部分。

现在我们已经涵盖了什么是“操作”的定义，以及严格定义域的定义，我们可以开始思考一个 二元操作概念（Binary Operation Concept） 了。

在这个上下文中，二元操作有三个约束：

  1. 它必须是 regular_invocable，因为它与归约（reduction）算法相关。

  2. 结果类型必须能作为参数构造传递给 R。

  3. 它还需要可以被赋值给一个类型为 R 的对象。 后面这两个要求正是为了防止我们返回某种极其任意的东西，并且也防止我们得到一个返回 void 的操作。

这个二元操作还有一些相关的公理（Axioms）。 第一点是，类型 T 和 U 代表了操作的定义域。当一位审阅我幻灯片的数学家介入时，他们担心 T 和 U 会把一切都限制在某一个特定的集合里，而不允许任何跨集合或跨类型的操作。情况并非如此。我们不仅可以有不同类型的输入参数，还可以有不同的集合。所以这个二元操作概念应该能适用于，比如，标量与向量的乘法（scalar-vector multiplication）。 第二个要求是，类型 R 代表操作的陪域。同样，它允许是一个不同于 T 和 U 的集合与类型。 最后，调用返回的值必须是操作陪域中的一个元素。它不能（比如在实数的加法上）返回一个 NaN 值，那超出了操作的严格陪域（你可能也知道这叫值域/Range，这在思考 C++ Ranges 时容易引起混淆）。

好，现在我们有了二元操作（Binary Operation）概念的定义。我们将利用它来构建一个叫作 原群（Magma） 的东西。Steve 在他之前的演讲中谈到了原群，但是如果你对抽象代数没有很深的理解，我最好再重申一下：本质上，原群是某种二元操作，它的定义域和陪域是相同的。就这么简单。 它非常通用，事实上对大多数有趣的用例来说过于通用了，所以我们把它做成了另一个“细节概念”。

我们要说明的是：作为输入，针对某些类型 T 和 U，它们必须能够以任何 T 和 U 的排列顺序作为参数类型。这就构成了原群（Magma）的含义：我们有四种不同的二元操作，涉及 T 和 U 参数的不同顺序组合，并且返回类型保持一致。

然后我们有一些公理，说起来有点啰嗦，但希望应该不难理解： 给定操作的某个实例，以及 T 类型的 t1、t2，和 U 类型的 u1、u2。操作的定义域和陪域必须相同，这符合原群的定义。 并且，因为我们这里有一个跨类型操作，我们要表达的是这些类型都代表同一个定义域（这继承自二元操作概念）。但我们还需要指出，如果 t1 == u1 且 t2 == u2，只要那个“1号”变量在左侧，“2号”变量在右侧，操作将总是返回相同的结果。这意味着当我们应用 t1 和 t2 进行操作时，它的结果等于应用 t1 和 u2 进行操作的结果，其他排列组合同样成立。 这就是原群（Magma）在 C++ 概念形式下的定义。

接下来，我们来看看一条你可能会忽视的公理。 屏幕上有我们在归约算法中的三个表达式。我们来考虑一个包含 1, 2, 3, 4 的范围。如果我们做加法，我们有：

  • x = 1 + 2 = 3，

  • y = 3 + 4 = 7，

  • 所以 z = x + y = 10。

现在如果我们改变做加法的顺序：

  • x = 2 + 3 = 5，

  • y = 1 + x = 6，

  • z = y + 4 = 10。

这两个结果是相同的，我们实际所做的仅仅是改变了加法的顺序。

现在让我们把操作从加法换成减法。我们有：

  • 1 - 2 = -1，令其为 x。

  • 令 y = 3 - 4 = -1。

  • z = x - y = 0。

我们的结果会不同，因为我们做了不同的操作，这很自然。并且我们计算操作的顺序符合加法例子左侧的情况。

现在让我们用减法操作考虑加法例子右侧的情况。我们再次移动运算顺序。

  • x = 2 - 3 = -1。到目前为止一切顺利，与初次减法的 x 相吻合。

  • 然后 y = 1 - x = 2。这与左侧不再相同。

  • 最后，当我们计算 z = y - 4，也就是 2 - 4 时，我们得到 -2。

这些结果是不一样的。这意味着我们在减法上遇到了不一样的情况。乘法和除法也同样如此（把加法替换为乘法，减法替换为除法）。所以这种情况不仅仅存在于加法和减法之间。

这就是我们所谓的结合律（Associativity）。 通俗地说，结合律意味着：对于相同的一连串操作，我们可以重新安排括号，并且它将产生相同的结果。 如果我们看看我如何在左侧通过加法重新排序括号，我们总是得到 10；但对于减法，我们每次都得到不同的答案。这意味着加法具有结合律，而减法没有结合律。

这对于我们将要讨论的内容非常重要，所以我将更正式地定义它。屏幕上是正式的数学定义。 它大致转化为下面这段 C++ 代码逻辑。我们这里不考虑 C++ 概念层面的具体约束，这仅仅是一个类比，展示这两者看起来应该是什么样。

一旦我们理解了结合律是什么，并认识到这对我们的归约算法很重要，我们就可以开始考虑被称为 半群（Semigroup） 的代数结构了。 半群就是一种原群（Magma），其操作遵循结合律。仅此而已。

现在我们来看看它的代码约束：我们指出，如果一种类型结构可以在将 T 和 U 作为两个参数传入时；并且当我们可以将 T 连同针对 T 和 U 调用的结果作为第二个参数传入时；然后反过来，我们以调用的结果作为第一个参数，将 U 作为第二个参数传入时，它就属于半群（是一个原群）。 我们之所以用这三个约束条件（而不是简单附上一个文字公理说它“必须具备结合律”），是因为我们希望能够实际在代码层面检查它。唯一能检查它的方法就是声明：返回的结果还需要是一个可以继续传递回该操作的对象。

我想在此稍作停顿。 这个特定的概念与我们到目前为止讨论的所有其他东西都有一点不同。其他所有的概念都在 detail（内部细节）命名空间中，但这个不是。它是面向用户的（user-facing），这很重要。 因为这就是我们一直以来的目标概念。它之所以是一个公共概念、是面向用户的（有别于我们考虑的其他所有细节概念），是因为它涵盖了广泛的适用情况。尽管我们没有正式讨论它们，但我同样能推理出它的很多应用场景：例如在这个演讲的语境中，加法和减法都属于半群（当我们未深入讨论一些更强的约束条件时）。这可以广泛适用于这类事物。 正因为它适用于更广泛的事物范围，我们可以说，半群（Semigroup）是一个面向用户的概念。

现在，我们把它放进我们最初的算法要求中。我们声明：我们的迭代器现在有 random_access_iterator 要求；我们将要求我们的操作对于 i 引用类型作为第一和第二参数时建模（model）了 semigroup 概念，并且它的返回结果也是一样（对应幻灯片上高亮的第 13 和 14 行）；随后我们还需要说明，该操作及其两个参数的结果类型也要构成半群（对应 16 和 17 行）。

这标志着第三幕的结束。我们终于“发现”了一个面向用户的概念（Semigroup），它依然完美地描述了我们归约算法的需求。

尾声与总结

我们还有时间进行尾声部分，所以我将把所有问题推迟到最后。

我们已经说明了为什么有些概念是公开的，而另一些是私有的，这在第二幕结尾和第三幕中都涉及了。 现在让我们回到最初的问题：我们能编写一个 Container 或 Number 概念吗？ 答案仍然是：不行。

概念不同于接口。对于概念，你需要做的是：勾勒出算法能工作的最小必要集合。你可以用“数字（Number）”做很多事情，但大多数事情并不总是必要的。所以我们不想要一个 Number 概念，因为这对我们的算法来说并不是一个有用的东西。semigroup（半群）、monoid（幺半群）、group（群）之类的东西对于概念是有用的，因为它们描述的是操作，以及我们输入和输出之间可能存在的关系。它们描述的是我们算法的计算过程，而不是在对某个类型的家族进行分类。

关于 Container（容器），我个人觉得一个关注插入元素到范围中的概念，要比某种模糊的、只塞进一大堆“满足容器定义”特征的 Container 概念有用得多。这个领域还没有得到充分的探索，所以关于什么才真正适合放在这个空间里，还有很多开放性的研究空间。如果你有兴趣探索，我很乐意和你探讨，但你不必非得去当推动它的领头人。

最后，这一切又回到了：“我们谈了很多关于算法的内容，那我可以在我的类型上加什么要求呢？” 其实这与我们一直在讨论的算法是相同的：思考一下你的类型仅仅为了存在并参与其关键算法，什么是至关重要的？你可能觉得这肉眼一看就清楚，但情况并非总是如此，有时你确实需要从基本原理推导出来。

作为一项练习，我想提出一个问题： 为什么在 C++20 中，所有的 Range 适配器（adapters）都要求它们所适配的类型符合 input_range 概念？ 至少对我来说，这不是凭直觉就能看出来的。你需要从基本原理出发推导，并真正剖析底层到底在发生什么。

这回答了最初所有的疑问。如果你想了解更多关于泛型编程的知识，《从数学到泛型编程》（From Mathematics to Generic Programming）和《编程的元素》（Elements of Programming）是两本非常好的书。它们是我准备这个演讲的核心参考资料。此外，还有我最初提到的那两个演讲，如果你还没看过，请回去看一看，它们能填补一些知识空白。Alexander Stepanov 的网站（stepanovpapers.com）对于深入了解泛型编程也非常有帮助。最后，我承诺过要提供一些关于指令级并行的资源，这些是我咨询过关于这些主题的三本书。

总结一下，我们在演讲中试图传达的核心要点是：

  • 概念描述的是一个算法的需求，而不是某个类型类别的属性。

  • 具有广泛用途的概念是 面向用户（user-facing） 的，否则它们应该只是实现细节。

  • 我们需要将优化版本与原始朴素的实现进行基准测试。

  • 我们通过研究算法来发现需求。

  • 泛型编程始于具体的用例。

这就是你如何去发现一个面向用户的概念。非常感谢你们的观看，我会在 Gather Town 等候大家。如果你不在会议现场，你可以在 Twitter 或 #include 的 Discord 上找到我。谢谢！

问答环节

观众提问/评论： 其他概念由于未能符合其约束模型，会被暴露给用户，导致算法表现异常。所以用户需要了解并满足这些约束才能（比如）正确地使用 fold。我假设由于你提到这些不作为面向用户的概念，所以它们不会有一个面向用户的命名。但是，不暴露名字真的对用户有帮助吗？通过隐藏名字，我们实际上让查找约束条件变得更难了，因为它们不再有一个广泛可移植的名字。

Christopher Di Bella： 这是一个极好的问题。 我的意思是，这些约束要求仍然需要公开，仍然需要被记录在文档中。我在这里想表达的是，它们不应该作为一个面向用户的概念来提供。面向用户的概念应该是那些供大家通用消费的东西，比如 std::invocable 或 std::regular_invocable。

像 indirectly_left_foldable 这样的东西，是的，我们需要将它记录下来，并在文档中说明它是 fold 的约束要求。但它真的只应仅仅关注 fold 本身，而不是被当作一个覆盖面大得多的通用概念。这样做是为了防止人们错误地以为这个高度特定的概念对他们的普遍应用也有用，而事实上它并没有用。这解答你的问题了吗？

好的，那么我们的演讲就到此结束，我会在 Gather Town 回答后续的其他问题。谢谢大家！