std::find() 是坏的¶

标题：Warning: std::find() is Broken!

日期：2022/05/29

作者：Sean Parent

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

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

备注：标题党，聊的事情太深奥了没看完。

好的，非常欢迎大家来到 CppCon 2021 的最后一场会议。我没有什么要宣布的，但我有一件重要的事情要做，那就是我要感谢 Sean，他成为了我们这套摇头娃娃中第四个的模型。

谢谢你。非常感谢。

让我看看，我的麦克风开了吗？你们能听到我吗？

让我看看。好的，这应该可以。

欢迎大家。我是 Sean Parent。我是 Adobe 的一名高级首席科学家。直到最近，我的头衔上还写着 Photoshop 团队，但最近改成了软件技术实验室，这个实验室是和 Dave Abrahams 一起负责的，他可能就在这里，就在这儿。所以 Dave 和我正在 Adobe 重启软件技术实验室。

我把这个标题放在幻灯片上，“警告：std::find 已损坏”。这是我的“标题党”。我刚刚让你们坐下来听了 90 分钟关于形式方法的轻松介绍。所以感谢你们的到来。

为了理解 std::find 是如何损坏的，我们必须先对我们如何对软件进行推理有一点了解。

所以，几年以前，哦不，是超过 25 年前了，我在苹果公司工作。当我刚被苹果录用时，我的任务是修复一个 bug。我着手修复了那个 bug。然后我把我的修复方案拿给我的导师做代码审查。当时我的导师是 Darren Adler。你们中有些人可能认识他。Darren 对我说，这是个很棒的修复。这的确是个很棒的修复。但你还没做完。我希望你回去想一想，我们能做些什么来防止其他人犯同样的错误。

那个问题让我重新思考了我对编写软件的看法，对吧？你如何开发出健壮、有弹性、不会失败的系统？于是我花了很多时间思考和研究这个问题。

几年后，我把这个一模一样的故事转述给了 Alex Stepanov。这是他的原话。他说，“理解软件为何失败固然重要，但真正的挑战是理解软件为何能正常工作。” 这句话里蕴含着非常深刻的道理。乍一看，这两件事似乎是等价的。但我希望在这次演讲的过程中，我能说服你们，它们并不等价。这背后有更深层的信息。在近 20 年的时间里，这一点一直驱动着我思考如何编写软件。

形式化推理的基础¶

那么，我们如何思考软件是如何工作的呢？这要追溯到 1967 年的一篇论文。这是 Bob Floyd 写的一篇论文。这里是 Bob 的照片，论文标题是《赋予程序意义》（Assigning Meaning to Programs）。Bob 在这篇论文中所做的，是开始建立一种形式化的方法，让我们能够对代码进行推理，判断代码是否正确。他设想我们可以拥有自动化的验证系统，这些系统能够检查我们的代码并验证其正确性。

其工作方式是，他将逻辑命题赋予操作，作为对先行条件（antecedents）和后继结果（consequences）的验证条件。基本上，就是这个操作需要什么条件才能工作，以及这个操作执行后会发生什么。这实际上是在机器层面看待问题，对吧？他关注的是计算机上的指令做了什么。

这项工作在 1969 年被 Tony Hoare 进一步发展。在这篇名为《计算机程序设计的公理化基础》（An Axiomatic Basis for Computer Programming）的论文中，Tony Hoare 所做的，是把他 Bob Floyd 的工作成果拿来，并围绕它建立了一套演算体系，对吧？一个关于我们如何对你机器上的代码进行推理的形式体系。其结果就是所谓的霍尔逻辑（Hoare logic），为了体现 Bob 的贡献，它也被称为弗洛伊德-霍尔逻辑（Floyd-Hoare logic）。

它将计算描述为一个霍尔三元组（Hoare triple），看起来像这样：{P} Q {R}。P 是前置条件（precondition）。Q 是一个操作（operation），而 R 是一个后置条件（postcondition）。所以我们有两个谓词（predicate），P 和 R，中间夹着某个操作。

像这样的语句可以被组合起来。在论文中，他描述了如何处理赋值（assignment）、推论（consequence）、组合（composition）和迭代（iteration）的规则。我不会在这里详细讲解整篇论文。但其中一个关键部分是组合。你如何构建系统？他是从内到外构建系统的。他关注的是执行机器中某条给定指令需要什么条件，以及该指令的后置条件是什么，然后将这些组合起来，从而得出函数的规则。

然后，就像 Bob 的工作一样，只要你能保证一个操作的后置条件能够保证后续操作的前置条件，以此类推，你的程序在某种程度上就是正确的。不过，这种正确性的模型与我们通常使用的“符合规范”（matching specification）有所不同，对吧？我们通常说，如果代码符合规范，它就是正确的。而这里更多的是指“它是否会无故障地执行？”

在我们继续之前，我想介绍几个数学符号，以免产生混淆。

∀ (倒A)：对于所有（for all）。
∃ (反E)：存在（there exists）。这些被称为全称量词和存在量词。
∈ (小写e)：属于（in），例如一个元素属于一个集合。
| 或 st: 使得（such that），这里用反向的 ∋ 表示。
¬ (小钩)：否定（negation） 或 非（not）。
⇒ (右箭头)：蕴含（implies）。
⇔ (双向粗箭头)：当且仅当（if and only if），也写作 IFF。不要和 C++ 的宇宙飞船运算符搞混了。
∧ 和 ∨：逻辑与（and）和逻辑或（or）。

现在你们看到我为什么要介绍这些了。这些是整数加法的性质，对吧？我们用 Z 这个集合来表示整数。我们在这里构建了它的性质。我不会逐一讲解，但我会读一下倒数第二条，这样你们就能明白它是如何运作的。这里写的是：∃ 0 ∈ Z | ∀ a ∈ Z, a + 0 = a。

OK？这就是加法单位元。所以，要成为一个整数，它必须有一个零。我们可以把这个零加到集合中的任何值上，然后得到我们输入的相同的值。

但是，集合 Z 不等于计算机中的 int 类型。对吧？具体来说，当有符号整数溢出或下溢时，其行为是未定义的（undefined）。我们不能那样做。所以在霍尔逻辑中，这可以用一个额外的公理来表示。比如这样：¬∃ x ∈ int | x > max_int。

由此，我们可以推导出一个霍尔三元组，看起来像：{A + B ≤ max_int} int n = A + B; {n ≤ max_int}。

为了让这个成立，A + B 的计算必须在 int 的领域之外进行。这些是 Z 域中的数学运算。对吧？我们正在使用数学来形式化地定义和验证我们的操作。

你可以看到，这仅仅是处理了上溢。我还没有处理下溢，也没有处理所有其他的算术运算以及它们之间是如何关联的。所以 Tony Hoare 在他的论文中写了这么一句话：“即使是整数算术的特性描述也远未完成。” 他不是说这特别困难，他只是说没人坐下来完成这项工作。这是一项浩大的工作，他们在发表这篇论文之前没有费心去做，因为他们认识到这是一件复杂的事情。

尽管如此，这是一个极其强大的工具。静态分析器就是这么做的。这是一张 Clang 静态分析器的截图，它分析了一个小程序，这个函数的作用是，给定一个指向序列中某个位置的指针，它会返回下一个元素，而不是下一个位置。它返回序列中的下一个元素。

这里发生的情况是，在第 9 步，也就是中间那部分，我们得到了一个未定义或垃圾值，因为我们刚刚走出了数组的末尾，对吧？Clang 静态分析器能够发现这一点，并检查所有函数，因为它正在从每个操作的前置和后置条件开始，使用每个函数的组合规则建立一个模型，从而构建一套规则，使其能够对代码进行推理，并告诉你：“嘿，这是你违反操作前置条件的完整路径。”

契约式设计与海勒姆定律¶

接下来我要谈论的下一个基础性工作叫做契约式设计（Design by Contract）。这篇论文是我能找到的最早的副本，来自 1992 年。还有一篇更早的、来自 1986 年的论文，标题就叫《契约式设计》。这是 Bertrand Meyer 的工作。今天早些时候，我发了封邮件问他是否有原始论文的副本，但他还没回复。所以如果有人有副本，我很想得到一份。

那么，什么是契约式设计？契约式设计将这个概念在某种程度上进行了反转。现在我们从外部的一个函数开始，为该函数定义一组前置条件和后置条件。

Bertrand 的工作是在一种叫做 Eiffel 的语言中进行的。我不知道你们有多少人听说过 Eiffel。三十年前，它曾引起了不小的轰动。这是一个来自 Eiffel 类的 SetMinutes 方法，它接受一个整数 M，这是接口的一部分，而不是实现的一部分。它有一个 require 子句，这个需求被命名为 valid_argument_for_minute，如果你想做错误报告，这非常有用。它要求 M 在 0 到 59 的范围内。然后它确保一个后置条件。这个名为 minute_set 的后置条件是，在这次调用之后，这个类中名为 minute 的成员将等于 M。这是一个非常简单的前置和后置条件。

Bertrand 还在这个概念中引入了类不变式（class invariants）。我们之前有过不变式。我们有循环不变式。还有其他重要的不变式类型，但这里特别处理的是类不变式。所以，类不变式是一个适用于类的所有公共成员的后置条件。因此，从类的外部看，这些后置条件对于该类的任何值都始终成立。所以在这里，不变式是 minute_is_valid，意味着 minute 在 0 到 59 之间。

由于这些是所有成员的后置条件，通过引申，它们也成为了任何接受这些对象之一的操作的保证。任何其他操作，如果接受这个（无论是什么）时间类的对象，都会知道 minutes 在 0 到 59 之间。

现在，契约在实现上有一些限制。断言必须能用代码表达。运行时检查的断言的复杂性是有限的。一个在常量时间操作上的线性时间断言，可能会把一个原本是 O(n) 的操作变成 O(n*m) 或 O(n^2)，如果你真的去检查它，可能会导致你的程序无法终止。如果没有一个逻辑验证系统叠加在上面，你无法用它来验证全称量词或存在量词。

然而，这里的关键贡献不在于实现，而在于思想。从根本上说，这通过反转过程简化了形式方法。我们不再是审视每一个操作然后从那里向外构建，试图确定发生了什么。相反，我们从描述函数开始，结果证明，证明函数内的操作在满足前置条件的情况下能够满足函数的后置条件，这个过程要容易得多。

我们可以这样做。这些思想，好的，并不受限于实现的约束。我们可以在文档中写下完整的语义。我们可以写下“必须对所有…成立”或“必须存在…”。现在我们可以手动地对我们的函数进行推理，但我们可以把它写进我们的规范里。所以它给了我们一种方式来描述我们的函数到底在做什么。这里的关键点是，这使得形式方法成为在座各位在日常写代码时就能做的事情。你可以坐下来，然后说，我的函数有什么要求？即使没有任何语言支持，你也可以把它们写在文档里。我的函数的后置条件是什么？然后在使用它们的时候，你可以在脑海里尽量确保，这个操作的后置条件是否满足那个操作的前置条件？如果满足，那么你就能保证你的函数会做它应该做的事。

但这有一个问题。这是我们故事中的反派。这是 Hiram Wright。Hiram 本人没什么问题，我挺喜欢 Hiram 的。但他在这里是我们的反派。他观察到：

“对于一个 API，当用户数量足够多时，你在契约中承诺了什么都无所谓。你系统的所有可观察行为都会被某些人所依赖。”

他这里特别提到的“契约”，就是 Bertrand Meyer 的契约式设计思想中的契约。

这个引言被称为海勒姆定律（Hiram’s Law），而“海勒姆定律”这个词是 Titus Winters 创造的。

让我们来看一个实际的例子。我们有一个 vector，一个值的序列。我们要写一段代码，它的作用是从 vector 中移除第一个奇数。我们想，嗯，我们要用 remove_if，然后写一个谓词。

（走到白板前）我们写一个谓词，它会记录我们见过的奇数数量 odd_count。如果一个数是奇数，并且它是我们看到的第一个，那么我们就返回 true，这样它就会被移除。

C++

// 移除第一个奇数
std::vector<int> v = {0, 2, 1, 4, 3, 6};

auto p = [count = 0](int i) mutable {
    if (i % 2 != 0) {
        if (count == 0) {
            count++;
            return true;
        }
    }
    return false;
};

v.erase(std::remove_if(v.begin(), v.end(), p), v.end());

现在，如果你了解 remove，它实际上不会缩短我们的 vector，它只是告诉我们最后一个未被移除的元素的位置，所以我们从那个位置擦除到末尾。然后我们显示我们的 vector，写这个的工程师运行了代码，然后它打印出这个结果：0 2 4 6。

有人看出什么问题了吗？3 也不见了，对吧？它把 1 和 3 都删了。

写这个的工程师挠着头，看着他的代码。他心想，我不觉得我把计数搞错了。我代码里的一切看起来都合情合理。但它移除了前两个奇数。于是，他把这段代码发给他的一个同事，他的同事拿了代码，用他的编译器编译，在他的系统上运行，然后回复说，“我不知道你在说什么，我得到的是正确答案。”

好吧，到底发生了什么？

嗯，这里是 remove_if 的一种可能实现：

C++

template<class ForwardIt, class UnaryPredicate>
ForwardIt remove_if(ForwardIt first, ForwardIt last, UnaryPredicate p) {
    first = std::find_if(first, last, p); // 第一次使用 p
    if (first != last) {
        for (ForwardIt i = first; ++i != last; ) {
            if (!p(*i)) { // 第二次使用 p
                *first++ = std::move(*i);
            }
        }
    }
    return first;
}

我不记得了，我本该记下来的，但是两大开源 C++ 标准库中的一个就是这么做的。另一个不是。所以你得到的结果取决于你用的是 libstdc++ 还是 libc++。选一个，你会得到其中一种行为。

这里发生了什么？我们的谓词通过值传递被传入 find_if，以找到我们要移除的第一个东西。当它找到时，谓词内部的计数器会增加。但是之后，那个谓词的副本就被丢弃了。然后我们回到谓词的原始副本，继续迭代，此时计数器重置为零。于是我们把第二个也移除了。所以这最终会移除前两个元素。

于是，写这段代码的工程师看了实现，明白了发生了什么，然后说：“啊，我知道怎么修了。”

C++

// 移除第一个奇数的（看似）修正版
std::vector<int> v = {0, 2, 1, 4, 3, 6};
int count = 0;

auto p = [&count](int i) {
    if (i % 2 != 0) {
        if (count == 0) {
            count++;
            return true;
        }
    }
    return false;
};

v.erase(std::remove_if(v.begin(), v.end(), p), v.end());

这次我要做的，是把我的 count 从 lambda 表达式中提出来，然后通过引用来捕获它。这样在实现中，当它创建我的 lambda 的副本时，它不会也创建我的 count 的副本，我只有一个 count，count 会随着我的处理递增，然后我就会移除第一个奇数。

他执行了代码，成功了，他很高兴，然后发给他的朋友，他的朋友也得到了同样的答案，他们又发给了更多的人，用更多版本的标准库尝试，在他们尝试的每一个标准库版本上，它都有效。

它正确吗？房间里有人吗？你们觉得它正确吗？不。那是“不”还是“是”？不。它不正确。为什么不正确？

嗯，标准里有这么一行关于谓词的规定。非常复杂的一行，讲的是 U 的 glvalue，但基本上它的意思是，如果我用一个值 U 来调用我的谓词，或者我用解引用迭代器得到的值来调用它，只要这些东西指向同一个对象，我的谓词就必须返回相同的值。我把计数器放在里面违反了这一点。一个更强的表述是要求谓词是一个纯函数（regular function），这意味着如果我们给它相等的值，它应该返回相同的东西，这和纯函数（pure function）的概念非常相关，只不过纯函数不能有任何副作用。我们可以有副作用，只是它们不能是对这个函数可见的副作用。

但是，海勒姆定律，对吧？我刚展示的代码很可能已经在某个地方部署了。我为什么这么想？因为整个这个对话是在 Twitter 上出现的。这意味着如果有人在 Twitter 上问这个问题，就说明有人在代码里这么干了。

安全性与正确性¶

现在让我们稍微离题一下，谈谈安全性和正确性，因为这个领域有很多混淆。Dave 和我花了很多时间讨论安全性和正确性。我在之前的演讲中给过安全的定义，它与我将在这里给出的定义不同，但并不矛盾。我们一直试图提出一个清晰、明确的安全定义，它既要符合文献中对安全的使用（比如内存安全和线程安全这类特定安全），又要与 C++ 吻合，也要与我自己的编码哲学吻合。

这是我们的定义： 一个操作是安全的，如果它不会导致未定义行为（undefined behavior）。 句号。这就是一个操作安全的定义。

我说“导致”时，指的是直接或间接的。即使操作的前置条件被违反了也一样。这就是安全操作的含义。

那么一个不安全（unsafe）的操作，如果其前置条件被违反，就可能导致未定义行为。无论是直接的，还是在后续操作中，无论后续操作安全与否。所以一旦我做了一个不安全的操作，我可能会得到一个我们称之为“有毒”的值，然后我可以把这个值传给一个本来安全的操作，但这可能会以一种导致未定义行为的方式违反那个操作的前置条件。

现在，违反前置条件的代码是不正确的（incorrect）。好的？所以让我们谈谈软件的要求。这差不多就是我们对软件正确性的定义。不是完整的定义，因为你还必须满足后置条件，但如果你违反了前置条件，你就是不正确的。

所以安全性是关于有 bug 可能带来的后果。是关于当事情脱轨时，情况有多糟糕。

让我们谈谈代码正确性的要求。一个正确实现的操作保证，如果前置条件被满足，那么操作将：

成功，并且结果符合契约中的后置条件；
或者，操作报告一个失败。

这是另一个容易混淆的点。对吧？有时候你无法满足保证。但这并不是 bug，只要你返回某种类型的错误来表明你无法满足操作的后置条件。任何被该操作修改的对象，必须被置于一个——这是 Bertrand 的术语——已知的或可确定的状态（known or determinable state）。这意味着如果我正在修改一个对象的中途，那个操作无法满足其后置条件。所以如果我收到一个错误信号，我可能有一个以某种方式损坏的对象，我需要至少能够知道它的状态，要么是因为规范说如果我得到这个错误信息，我的对象就在这个状态，要么我需要能够检查并确定它处于什么状态。

所以这需要某种方式来基本保持我的应用程序运行，在我得到错误时弄清楚发生了什么。这是一个比“有效”（valid）更弱的要求。“有效”是指满足类的不变式。所以这是一个比“有效”更弱的条件。

现在，如果一个前置条件未被满足：

如果操作是安全的，结果是未指明的（unspecified）。 未指明行为（unspecified behavior）不同于未定义行为（undefined behavior）。这两个在 C++ 中都是术语。未指明行为可能包括失败（返回错误、抛出异常、设置 errno 等）。它可能包括捕获（trapping）或终止应用程序。它可能包括将被操作修改的对象置于一个未指明的、可能无效的状态。

在我离开这个话题之前，Dave 在午餐时有一个很棒的观察，那就是我们真的应该有一个 强安全（strong safety） 的概念。强安全的概念是，你能保证如果违反了前置条件，程序就会终止或陷入陷阱（trap）。它会立刻停在那里，而不会对你的系统造成任何额外的损害。我认为这是一个有趣的想法。这是我们正在探索的东西，我只是想在这里提一下。

如果操作是不安全的，行为是未定义的（undefined）。 句号。不仅仅是这个操作的行为，而是你的整个应用程序的行为在此时都是未定义的。如果操作碰巧返回了，任何后续的操作也都是未定义的。未定义行为可能包括写入任意内存、执行任意函数、损坏硬件、发射导弹、撞毁汽车、杀死你家的狗，任何事情。编译器可以自由地假设未定义行为不会发生。而且它们确实这么做了。

让我们看一个例子。这是一个有点做作的例子，但它源于我在审查真实代码时看到的东西。有人在他们的真实代码中有一个类，带有一堆成员函数，在每个函数内部，他们都在检查 this 是否为 nullptr。所以每个成员函数的开头都有一个检查：if (this == nullptr)。如果为真，就抛出异常，代码是这么写的。我说，嗯，这很有趣。我说，你明白这实际上什么也做不了吗？他说，哦不，这可能会发生，因为有人可能解引用一个指向我对象的空指针然后调用我的对象，那样的话 this 就会是 nullptr。

为了调用你的对象的成员函数，你必须已经解引用了那个指针。这和传递一个引用非常类似。所以如果我们这里有一个引用，我们可以取它的地址，然后看那个地址是不是 nullptr。

C++

void f(const T& t) {
    if (&t == nullptr) { // 检查引用是否为空
        // ...
    }
}

T* p = nullptr;
f(*p); // 这里发生了未定义行为

在下面这里，我们声明一个指针 p 是空指针。然后我们调用我们的函数 f(*p)。那么，这会打印“空引用”还是“有效”？“有效”。它打印“有效”。为什么？

嗯，在顶部的那个检查，编译器知道如果你解引用一个空指针，那就是未定义行为。所以，下面这里的 f(*p)，就是未定义行为发生的地方。因为编译器可以假设你不能解引用空指针，所以编译器可以自由地假设一个引用永远不可能是 nullptr。因为得到它的唯一方法就是解引用一个空指针。因此，整个测试都是无效的。整个测试被剥离掉了。唯一剩下的就是打印“有效”的语句。整个东西都被去掉了。

现在，根据你使用的编译器，在 Clang 上，你实际上会得到一个警告，说“这不可能发生，这段代码正在被剥离”。GCC 只是默默地剥离它。它从你的应用中消失了。

强前置条件 vs. 弱前置条件¶

所以，有一种趋势，一种愿望，是说也许答案是我们需要更弱的前置条件。我们想做的是，如果我们的前置条件很强，那会有点麻烦，我们会遇到海勒姆定律。所以也许我们想做的是削弱我们的前置条件，也许尝试让我们所有的操作都没有前置条件。我们会把它们一路削弱到底。我们会指定所有的行为。

一个给定的实现可能会在违反前置条件时做一些可指定且安全的事情。所以，在这种情况下，为了防止海勒姆定律影响我们的代码，削弱前置条件以说明实现的实际行为是很诱人的。但我们应该这样做吗？这是好事吗？

用 Kate Gregory 的话说，这很复杂。

让我们来看一个相对简单的东西：有符号整数类型 vs. 无符号整数类型。在 C++ 中，有符号整数类型比无符号类型有更多的前置条件。有符号类型的上溢或下溢是未定义行为。但无符号类型被定义为模 2 的比特数次方。所以它们会在其空间内回绕。无符号类型仍然有前置条件。C++ 中几乎所有类型都有某种前置条件。其中一个前置条件是你在初始化之前不能从中读取。所以，仅仅是 unsigned int i = i; 这样的简单赋值就是未定义行为。

太棒了。那么让我们在一个算法中使用有符号整数类型吧。这是 Bresenham 画线算法。有多少人熟悉这个算法？哦，很好，相当多的人。

解释一下它的工作原理，我们在画一条线。我们关注的是第一个八分之一象限。通过反射，我们可以得到围绕一个圆的所有其他象限。我们在一个光栅显示器上画线。所以我们会从这个函数得到什么呢，我们传入这个 fout 函数，它会用 x 和 y 坐标调用 fout，我们可以把这些坐标画出来，它就会画出一条光栅线。

作为输入，它接受两个增量，也就是距离。一个 dx，我们的线在 x 坐标上有多长，和一个 dy，有多高。这就给了我们线的斜率。

现在，我们有一些非常复杂的断言在这里，用来检查我们是否会溢出，因为我们不想遇到未定义行为。最复杂的部分在下面这里，我们要确保 dy 加到 dx 上不会超过 int_max。所以我们得稍微思考一下如何表达这个。

我可以运行这段代码，然后我会得到一条像那样的线。这是一段好代码。

让我们看看内部，来感受一下它是如何工作的。好的，这是算法的关键部分。我们有一个 a，是我们的累加器（accumulator）。我们把 dy 加到 a 上。每当 a 超过 dx，我们就从 a 中减去 dx。所以你可以把 dx 看作是极限，它会像这样回绕。每当它回绕一次，我们就会把我们的 y 坐标加一。你可以把回绕的量看作是多出来的部分，对吧？所以我们像是在积累，我们会在我们的线上停留一会儿，直到我们积累到足够多，y 坐标需要增加。在那个点，我们只能增加一个整数单位。还会有一些余量。那个余量留在我们的累加器里。我们继续前进。我们的线就会随着我们的行进而建立起来。

这个小东西就是模加法（modulo addition），对吧？我们做的是将 a 和 dy 相加，得到一个模 dx 的结果。所以这是模 dx 的加法。

啊哈。无符号整数，其整数算术是模 2 的比特数次方的。这也等于模无符号值的最大值加一。我们只是在做模运算。那么，如果我们不以 dx 为模，而是以 max_value + 1 为模呢？我们能做到吗？当然可以。我们只需要把我们线的斜率一直投射到我们无符号值的最大值加一。

那么我们怎么做呢？我们必须这么做。我们有一个斜率 dy / dx。我们需要的是一个 dy' / (max_value + 1)。我们可以解出 dy'。这很简单。

所以现在我们可以用无符号整数来编码这个。这里发生了什么？首先，我们的断言简化了，因为我们不需要处理溢出，因为这正是我们的意图。我们在这里回绕。我们仍然有一个断言。我们不能处理完全对角线的线，即 dx 等于 dy 的情况。为什么？因为我们无法将其与零的情况区分开。

计算我们的 dy' 有点棘手。因为我们需要一个比我们最大无符号整数大一的值。做到这一点的方法是，我们把所有东西都转换成 double，通过把它加上 1.0。然后我们乘以 dy 除以 dx，然后我们会把结果截断回 dy。我们想截断而不是四舍五入的原因是，我们实际上不想超过 dy。我们永远不想向上取整。

但是看看我们循环体里发生了什么。a += dy。这是我们的累加器。但它自然地回绕。我们可以通过检查 a 是否小于 dy 来判断它是否回绕了。所以如果 a 小于 dy，那么它就回绕了，我们继续，把我们的 y 坐标加一。

即使我们那里有一个比较操作，也没有分支。右边的注释是这段代码至少在 x86 上会生成的指令。我们有一个 add 指令和一个 adc（add with carry）指令。什么是带进位的加法？嗯，如果你做加法并且回绕了，你需要进一位。这正是我们在这里做的。我们做的是无符号值的加法。它回绕了，我们把 1 加上去。之前有一个关于无分支编程的演讲。这是一种做无分支编程的方法。

结果是，这段代码本身就比带有 if 条件的版本快大约 15%。而且因为它没有分支，这意味着你可以很容易地将其向量化。所以你可以用你机器上的 SIMD 单元执行相同的算法，获得 8 倍或 16 倍的加速。这是一个相当显著的加速。如果我们运行它，你看它能工作。我们得到一条线。我们不会得到和原始 Bresenham 算法完全相同的线，因为当我们在做投射和截断时会有一点误差。但它们会几乎相同，我们实际上可以——我不会在这里做——但有一个几何证明可以表明它们总是会在正确的起始和结束位置。变化的只是中间的小阶梯。

所以，无符号 vs. 有符号整数。

用模运算更容易检测溢出。
模运算的性质可以被利用。我们可以做一些很酷的事情，比如画快速的 Bresenham 线，如果我们知道我们的数会回绕。

这些都很好。但通常，数学是在模拟 Z 的一个子集，一个数学整数的子集，或者自然数的一个子集。有符号数学为分析器提供了更多机会来检测可能的溢出。大多数时候，如果你让一个数溢出，不管是有符号还是无符号，那都不是故意的。那是你代码里的一个 bug。那是一个错误。如果我们把之前代码里的 assert 去掉，然后用 UB sanitizer 来运行它，并给它一些确实会导致溢出的输入，它会捕捉到并停止我们的程序。

所以，理想情况下，我们希望能够指定我们想要的行为。有我们想要做的模运算，它会回绕。有陷阱算术（trapping arithmetic），我们希望它能直接停止我们的程序，即强安全保证。有饱和算术（saturating arithmetic），这在做图形处理时非常有用，它会固定在最大值，不再增加。然后是我们现在有的……嗯，然后是未指明行为，它可以是以上任何一种。我们现在拥有的是未定义行为，也就是发射导弹和杀死你的狗。我有点怀疑我们是否需要未定义行为。我明白在某些情况下，编译器能够利用未定义行为进行优化以获得实际的性能提升，但也许仅仅有未指明行为就足够了。

好的。这些可以封装在不同的类型中，就像 Rust 对这类算术所做的那样，或者封装在不同的操作中，就像 Swift 所做的那样。

强前置条件的优点是它们为我的实现提供了灵活性。如果我有强前置条件，那给了我在函数内部有更多机会……该怎么说呢？在边界上利用一些东西。这个说法不好。我会想个别的。有了强前置条件，我们可以赋予一个操作意义和意图。我的意思是，当我有了一个强前置条件，我可以说，如果你满足这个强前置条件，那么这个东西就会做一些有意义的事情，并满足那个强的后置条件。我们不想陷入的情况——而且有这种趋势——是说，嗯，你知道，如果我们削弱前置条件，如果那些较弱的前置条件被满足，它会做一些无意义的事情，但我们把那个无意义的事情写下来了。这都简化了我们对代码进行推理的能力。强前置条件使我们更容易对代码进行推理。

如果我们做的是 Tony Hoare 做的事情，也就是仅仅审视所有单个的操作，然后将它们组合成调用这个函数所需的最小要求，并且不引发未定义行为，不让机器崩溃，那么结果是，这真的很难做。而且那些描述会变得非常复杂和庞大。

但这里也有缺点。就像我们在有符号和无符号整数中看到的那样，我们能够利用无符号整数具有较弱前置条件这一事实，并用它做一些有用的事情。但我们也看到，这允许了不同实现之间的行为差异。这就是我们在 remove_if 操作中遇到的情况，对吧？我们看到 remove_if，我们超出了前置条件的范围。一个实现做一件事。另一个实现做另一件事。更强的前置条件为海勒姆定律打开了一个漏洞。

这就是我们所面临的情况。尽管如此，我仍然站在无符号阵营。无符号队。

泛型编程与概念¶

现在，我们得稍微往回说一点。我们有点超前了。因为这个故事还有后续。你们中有些人可能听说过泛型编程（generic programming）。这个词是由这两个人创造的，Dave Masser 和 Alex Stepanov。这是 1989 年发表的论文，泛型编程这个词就在这里被创造出来。从一开始，泛型编程的一个关键部分就是所谓的要求（requirements）和保证（guarantees）。

这些在 1992 年由 James Dennert 和 Alex Stepanov 发表的一篇论文中被更加形式化了。这是 James 的照片。也就是在这里，概念（concepts） 这个词被创造出来。所以早在 92 年，概念这个词就被创造了。我们终于在 C++20 中有了一些对概念的语言支持。所以花了一点时间。

这是他们最初介绍概念这个概念的方式。“我们称一个数据类型和其上的一组操作所满足的公理集合为一个概念。” 这是泛型编程的基础。

所以，概念。概念本身是一个命名的需求集合。这里的“命名”很重要。它们包括一组指定操作语义的公理。所以当我们之前看相等性时，我们说相等性必须是自反的、对称的、可传递的。这些是等价操作的语义。它们还封装了操作的前置条件和后置条件。这些是契约性要求。最后，这也是一个有点独特的观点，概念实际上捕捉了复杂度要求。它们告诉你为了满足后置条件并保证操作的某个复杂度，操作的复杂度需要达到什么要求。

现在，C++20 的概念将一组有文档记录的语义、契约和复杂度要求与一个名字和一组语法要求关联起来。C++20 的概念没有任何方式来描述语义、契约或复杂度要求到底是什么，除了通过你的文档和规范。它们只捕捉语法要求。这表面上看起来相当弱，但这是一个非常强大的思想。我们说的是，我们把某物的所有语义要求与一个名字，一个操作的名字关联起来。这就是我们说话时做的事情。这就是我们互相交流的方式。这就是语言的思想。

所以，如果我们有一个例子，比如标准库中的 equality_comparable，它要求定义了 operator==，并且其结果可以转换为 bool。这是语法要求。它要求 operator== 是一个等价关系（equivalence relationship）。这是语义要求。但这些词没有出现在语言中。它们出现在标准文档里。operator== 的参数必须在操作的定义域内。这是契约性要求。operator== 在与对象面积成正比的时间内执行。这会是复杂度要求。

现在，我撒了点谎。最后两个要点实际上没有被放进标准里。它们实际上不是 equality_comparable 所要求的。但它们应该是。所以它们缺失了。

概念将语义和复杂度与语法关联起来。它们允许我们定义一个组件，这个组件可以与任何满足这些要求的类型一起工作。这使我们能够为一个无边界的操作集合赋予意义。我们可以有一个像 find 这样的操作，我们可以在 vector 中查找整数。我们可以在 deque 或其他序列中查找员工。这使我们能够混合搭配，把东西组合在一起，并且仍然能构建一个我们可以推理的系统。这是一个极其强大的思想。

我们说，一个组件的参数被要求满足一个概念。作为回报，一个数据类型，一个特定的实例，比如 int、vector<int>，可以保证它能够满足一个概念。这种要求和保证的概念极其重要。

所以让我们稍微谈谈这个。

要求（Requirement） 适用于一个参数化类型或一个操作的参数。
保证（Guarantee） 适用于一个对象或对象的实例。

一个保证是在断言这样一个实例满足一个要求，或者我们也会说它 建模（models） 一个概念。

所以如果我们看一个像 distance(f, l) 这样的函数，它要求什么？它要求 F 和 L 满足 输入迭代器（input iterator） 的概念。输入迭代器要求有前置自增 ++i、后置自增 i++，以及解引用 \*i。这有一个前置条件，即 i 不能等于 L，对吧？我们要自增或解引用的迭代器不能等于范围中的最后一个元素。F 和 L 还必须满足一个 平凡迭代器（trivial iterator） 的所有要求。那就是 F 和 L 必须满足它是可赋值的、可相等比较的、可默认析构的。可相等比较有前置条件，即参数在 == 的定义域内。我不能比较任何两个任意的迭代器。它们必须在同一个序列中。这是我们输入迭代器的前置条件。最后，我们有一个前置条件，即 [f, l) 是一个有效范围。

我们这里省略了很多东西，因为我没有深究可赋值的含义或者可默认构造的含义。所以，为一组要求命名是一个巨大的简化。这是巨大的，对吧？std::input_iterator 这个概念封装了这一大堆语法和语义要求。只有语法要求是由编译器强制执行的，但分析器和清理器可以，并希望会，做更多的工作，验证一些语义要求。

所以，标准中的概念是对库组件参数的要求。再次重申，标准类型通常被描述为保证它们满足某个概念。我之所以想再重复一遍，是因为我看到了巨大的混淆，即使在标准委员会的成员中也是如此。在座有多少人是标准委员会的？好的，有几个。在座有多少人曾认为标准中的要求表，就像是对实现者关于他们必须如何实现 vector 的要求？那不是它们真正的含义。它们是关于你可以把什么类型插入到一个容器或算法中的要求，我们只是碰巧记录了标准库中一些特定类型的保证，说它们满足那些要求，对吧？所以这与微软是否这样做无关。那不是标准里的意思。

这些命名的要求是从一组相关的组件中提炼出来的。当你试图弄清楚要求是什么时，你是在看一组算法、容器、类型等等，或者不管是什么，一组东西和一组通用的模型，对吧？所以随机访问迭代器的想法是，嗯，我们有像指针一样的东西，比如语言指针和类指针的东西，它们以这种方式行为，而在另一端，我们有输入流，那些会是输入迭代器的好模型。我们有像链表这样的容器，我们会用只向前或双向的迭代器来遍历它们，这取决于它是单向还是双向链表。所以你想去看看，然后说，好的，我有一个算法，这个算法要求这些东西。我有一组我认为可以放进去的模型。通过这种方式，它们为我们创造了一种简单的方式来匹配我们的对象和我们的组件，把两者放在一起。它们避免了这样的问题：如果我想排序，我必须谈论，我是要排序一个列表，还是一个 vector，或者我到底在排序什么？它们避免了这种 n * m 的复杂性，使其变成了 n + m。

对于一个特定的组件，其要求可能比实现实际需要的更强。如果你回头看，我给了一个 distance 要求的例子。distance 的一个要求是它接受输入迭代器，而输入迭代器被要求是可解引用的，但 distance 永远不会解引用迭代器。那不是坏事。那允许我们建立一个心智框架，以便我们可以把这些东西组合起来并对代码进行推理。其目的不是为了指定实现，而是为了指定代码的意义。这就是概念的目的。

std::find 的问题¶

现在我们有了足够的材料，可以真正地看一下 std::find 了。std::find 做什么？它接受一对迭代器，first 和 last，以及一个值。它要做的是在 first 到 last 的范围内找到第一个等于该值的元素，并返回那个东西的位置，如果那个东西不存在，它就返回 last。这就是 find 所做的。

好的？那么，我们的值等于序列中的某个元素是什么意思？嗯，我们需要定义我们所说的相等是什么意思。两个对象相等当且仅当它们代表同一个实体，这是一个非常哲学和抽象的事情，但这就是相等的含义。它们有相同的值。它们意味着同样的事情。由此我们推导出，相等是一个等价关系，意味着它是自反的（reflexive）、对称的（symmetric）和可传递的（transitive）。

相等也需要与你类型上的其他操作保持一致。为什么？因为我们是根据相等来定义那些操作的，对吧？所以，复制一个东西是什么意思？意思是在复制之后，这些东西是相等的。有一个全序关系，可以进行小于比较，是什么意思？其定义的一部分意味着我们得到了排中律，对吧？这种根据相等来定义事物的概念非常基础。它被称为等式推理（equational reasoning）。这就是我们理解宇宙的方式。我们可以用别的东西来描述一个东西。

这是旧的 SGI STL 关于 Find 的文档。它接受输入迭代器和一个 EqualityComparable 的值，并且它要求在 EqualityComparable 类型的对象（也就是我们的值）和输入迭代器的值类型的对象之间定义了相等性（equality）。它说的是相等性被定义了。它没说 operator== 被定义了。它说的是相等性被定义了。它还有一个前置条件，即 [first, last) 是一个有效范围，意味着如果我们从 first 开始并递增，最终我们会到达 last。然后它告诉我们复杂度的保证是什么，也就是在这个序列中最多会发生 last - first 次相等性比较。

如果我们看一下文档中 EqualityComparable 的定义，我们也会在这里找到一个相等的定义。它意味着两个东西相等，如果表达式 x == y 是一个有效的表达式，其前置条件是 x 和 y 在 == 的 定义域（domain） 内。我们还有一组不变式，看起来和我们在数学里的一模一样，也就是自反性、对称性、传递性，我们还加了一条，说如果它们是同一个对象，意味着它们有相同的地址，那也意味着它们相等。

现在让我们看一下 C++20 规范中 std::find 的定义。我们会注意到的第一件事是，它接受一对输入迭代器，就像前一个一样，但现在对 value 的要求只是某个类 T。这里没有提到 EqualityComparable。然后我们用一种有点绕的方式说，表达式 *i == value，嗯，我们会说，这个函数将返回范围 [first, last) 中的第一个迭代器 i，即表达式 *i == value 为 true 的位置。否则它将返回 last。所以它会一路调用我们的 == 运算符，并返回最后的结果。

C++20 标准确实包含了 equality_comparable 的概念。实际上它包含了两个。我只包含了旧版本，也就是 Cpp17EqualityComparable，因为那是适用于这里的。新版本被用在 ranges 算法中，但两个定义实际上是相同的。我们要求表达式 a == b 可转换为 bool，并且它是一个等价关系。然后我们过一遍我们的定义，对于所有的 a，它是自反的、对称的、可传递的。但我们并没有在 find 的定义中实际使用它。那部分被省略了。

所以我们开始看到问题了。这里是 NaN。NaN（Not a Number）通常由浮点数中零除以零产生。NaN == NaN 是 false，它是非自反的。最近有个很棒的笑话，说 NaN 代表 Not a NaN（不是一个 NaN），因为它们不是 NaN。

好的。所以 NaN 不满足 EqualityComparable 或 Cpp17EqualityComparable 的要求，无论是旧的还是新的。所以如果我拿这个 double 数组，它包含一个 NaN，然后我用 std::find 在上面寻找 NaN，然后输出“找到”或“未找到”，它会打印什么？有人知道吗？未找到？是的。它打印“未找到”，对吧？因为 NaN 不等于 NaN，所以它找不到 NaN。

好的。那么，如果我稍微改一下，让它寻找 3 呢？找到还是未找到？好的。那会打印我们找到了 3。这似乎很合理。

嗯，我们真的找到 3 了吗？我的意思是，在数学里，如果我在这里寻找 3，然后我把 3 和 NaN 比较，那是不确定的。我不知道。也许是，也许不是。也许这是正确的答案。也许不是。

你可能会想，这里的修复应该超级简单。我们去标准里找到 std::find，然后我们把要求改成 std::find 应该要求 Cpp17EqualityComparable。但如果我们真的那么做了，那么这段代码 std::find(c.begin(), c.end(), 3.0) 就会是未定义行为了，即使这里没有 NaN。

好的。但是这段代码在旧的 SGI STL 中是完全定义好的。所以这里到底发生了什么？有一个关键的部分缺失了。

这个短语。“x 和 y 在 == 的定义域内”。这个短语来自旧的 SGI STL。我经常使用这个术语，但这个术语并没有出现在 equality_comparable 的定义中。这个术语，“操作的定义域”，在整个标准中只在一个情况下为 == 的定义域出现，那就是对于输入迭代器。

所以当我们看这里的要求时，这是 C++20 中“对于所有”（for all）。对于所有什么？对吧？这通常被解读为“对于该类型的所有值”。标准委员会就是这么解释“对于所有”的。然后他们说，嗯，现在我们甚至在没有 NaN 的情况下也无法在我们的序列中找到一个值，因为 double 类型因为 NaN 的存在而不满足 equality_comparable。

那么我们该如何定义“操作的定义域”这个术语呢？实际上在标准中有非常类似的措辞，定义了输入迭代器的 == 的定义域。那是从 Alex 在 STL 上的旧工作中拿来的。但“操作的定义域”这个术语在旧的 STL 中被广泛使用。现在它在标准中几乎无处可见。就像我说的，只在输入迭代器上，并且只针对输入迭代器上的 ==。

这是“操作的定义域”的定义。我要读一下这个，因为它很重要：

“术语‘操作的定义域’（domain of the operation）在普通的数学意义上使用，表示一个操作被要求（因为我们正在谈论要求）在其上定义的值的集合。这个集合可以随时间改变。每个组件可能对操作的定义域施加额外的要求。”

好的。暂停一下。随时间改变。我们说的这是什么意思？嗯，最简单的思考方式是，如果我们看输入迭代器，对吧？我只能在两个输入迭代器在同一个范围内时比较它们的相等性。但是什么是“同一个范围”是随时间改变的。我可以缩短一个范围，一个迭代器可能会掉出范围的末端。然后用相等性比较就不再有效了。所以，我什么时候能实际使用相等性是可以随着我的程序执行而改变的。每个组件都可以对究竟何时我需要相等性以及在什么条件下施加额外的要求。

“通常，这些要求可以从组件对该操作的使用中推断出来，并且通常被限制在那些通过操作参数可访问的值。”

所以当我们调用 find 时，我们传递了一对迭代器 first 和 last。那个序列中的所有元素，都是通过我们操作的参数可访问的。

所以，一个操作的定义域不是参数的类型。我们经常想，哦，一个函数接受一个 T 类型的东西。那就是操作的定义域。当我们在数学中这样做并说，我们有一个关于自然数的函数，那和类型有点不同，Z 代表一个值的集合。某个类型 T 也代表一个值的集合，但我们可以谈论其中的不同值的集合，而不必给它一个单独的符号。

那么，对于一个类型 T 满足某个要求 P 的要求是什么呢？如果我们想说对于所有的 A，某个属性 P 成立，T 意味着什么？T 只需要保证什么？T 只需要保证存在某个元素 A 在 T 中使得 P 成立。这才是实际的要求。对 double 的要求不是所有的 double 都是可相等比较的。而是至少有一个是。这就是满足 equality_comparable 的要求。

double 和 float 满足旧的 equality_comparable。它们应该满足新的 equality_comparable。只要 NaN 不在被比较的集合中。是 NaN 这个值处于定义域之外。

所以，在 find 的序列中没有 NaN 是 equality_comparable 的一个前置条件。所以如果我真的把 NaN 作为我要搜索的值，或者作为我序列中的一个值，然后我调用 std::find，那应该违反了那个操作的前置条件。因为 find 在我这么做的时候找不到。

std::find 将返回第一个使谓词为 true 的元素。人们很想看一个实现然后说，嗯，我可以用 find_if 来实现 find。find_if 只是接受一个返回 true 的谓词。所以这似乎是 find 的一个有效实现。我可以从内到外地推导出它的要求是什么。但那不是我应该看问题的方式。我应该从外到内地看。find 要找到东西是什么意思？在这里，是这个相等性施加了额外的要求。额外的要求随着 operator== 的使用而来，因为我们试图交流，因为词语有意义。否则，find 的意义和相等的意义都被削弱了。我们对代码进行推理的能力也被削弱了。甚至在这里，我都搞错了。如果你看到，之前我写的是 value == e，它需要是 e == value。为什么？因为标准里甚至没有要求 == 是对称的。没有对对称性的要求。

所以 std::find 并不要求 T 中存在任何可相等比较的值。std::find 不保证它能找到 value，即使 value 存在于序列中。std::find 的意义被降级为“按实现的方式工作”（works as implemented）。

幸运的是，很容易证明，当且仅当 operator== 建模了旧的 equality_comparable，并且序列中的所有值和被寻找的值都在 == 的定义域内，那么 std::find 才会真的找到。

好的。现在，幸运的是，这很简单，但是当你在写一段代码时，你不想对每个操作都这样做。如果你试图对一个函数进行推理，你不想去看然后说，这些东西能不能一起用？这就是我们为什么有概念。我们有概念，所以我知道，嘿，这个东西保证它是 equality_comparable。这个东西要求 equality_comparable。我可以把它们插在一起。它会找到。好的？那个能力被拿走了。

结论与启示¶

所以这把我们带回到最初的那句话。我希望我已经说服了你们这句话的深刻性。理解软件为什么会失败，这很重要。当我们谈论安全性时，我们谈论的是我们的软件在失败时会造成多大的损害。试图弄清楚我们如何防止软件脱轨是非常重要的，但理解软件为什么能工作要重要得多。以及我们如何构建能工作的软件。

我们想要的是在不正确的代码和正确的代码之间有一条清晰、坚实的界线。一条我们能看到的东西。一条可见的东西。当我们削弱我们的要求时，我们打开了海勒姆的洞（Hiram’s hole）。这是所有碰巧能工作的代码掉进去的地方。

Titus Winters 有这么一句话：“我与非常优秀的程序员一起工作，我看到大量的‘碰巧能工作’的代码，而很少有‘真正正确’的代码。”他说的正是所有掉进海勒姆洞里的代码。

所以你从这里能带走什么？嗯，当你在写一段代码时，我懂。你经历了一系列的试错。你在谷歌上搜索。你在 Stack Overflow 上搜索。你试图弄清楚，我只需要让这个东西工作，做点什么。你终于得到了足够的信息。它编译了。它运行了。哇哦！非常兴奋。你还没完。现在你必须花时间去理解你刚刚做了什么。你写了一段代码。你调用了一些函数。你调用了一些运算符。它做了些事情。

所以，花点时间坐下来，真正地去查一下那些东西是什么。学会阅读规范。C++ 规范。CppReference 网站相当不错。不完美。可读性强一些。无论你在看什么语言。无论你用什么库。去读文档。查找任何你不清楚的东西。如果你在读规范，不要只是扫一眼然后说，哦，这个东西要求这个东西是 equality_comparable。好的。你知道 equality_comparable 是什么意思吗？去读它。向专家提问。

如果你在耍小聪明，如果你试图利用数据的某些边界特性，好的，这需要额外的勤奋。这需要在你自己的代码中有额外的规范和额外的文档。我不是说永远不要那么做，但是如果你在做，花点时间。我们看到了这在加速 Bresenham 算法时有多么强大。我们在利用特性。我们也看到了这在用 remove_if 时有多么危险。如果我们不理解规范，我们现在就违反了前置条件，我们进入了未定义行为的领域。即使它在我们尝试的每个人的机器上，每个标准库的实现上都有效，那也不意味着它明天还会有效。它被标准明确排除为无效。

所以思考你代码的语义的意义。你的代码是什么意思？确保你的使用反映了隐含的语义。因为你知道读者不会总是去查找所有细节。这就是为什么我们能够依赖惯例是很重要的。我觉得 std::find 实际上不要求 equality_comparable 很令人惊讶。如果我在读一段代码，我会期望 std::find 真的在寻找。如果一个工程师利用了 std::find 在我把一个 NaN 放到序列里时会做某件事这个事实，我在代码审查时不会预料到这一点。所以那是一个棘手的用法。根据标准它是有效的。永远不要那么做。

所以，确保你的名字反映了它们所代表的语义。所以仔细思考你给操作起什么名字。正如我之前说的，我们用名字作为语言。它们传达信息。标准给了我们一个相当广泛的词汇和一组名字。所以如果你在寻找什么，叫它 find。如果你在搜索什么，叫它 search。它们在标准中有细微的差别。不要创造一个新的词汇表。一个很好的例子，有一次，这是几年前了。我有一个工程师走进我的办公室，他说，我在写一个类，我需要能复制它，所以我应该叫那个复制的成员函数什么？我说，嗯，那应该是你的拷贝构造函数。他说，哦，不，我的拷贝构造函数已经用作别的东西了。

好的，这就像我说，嗯，当我们在我家时，我要把苹果叫做香蕉，我要把香蕉叫做 fizzle。我仍然可以指代苹果和香蕉，因为我造了一个词，我的集合仍然是完整的，但你会非常困惑，对吧？你会超级困惑。你根本不知道我要一个 fizzle 是什么意思。如果我要一个苹果，你会在我递给你一个香蕉时非常惊讶。

所以，用规范、概念和约束来指定你的前置条件。将语义与你的概念关联起来。它们不仅仅是一组语法要求，即使那是语言能为我们提供的所有设施。断言你能断言的。我们不能断言所有事情，但断言你能断言的，以及编译器和工具做不到的。

而做这些尽职调查的责任，如果你是一个库的作者，会成倍增加，我希望在座的几乎每个人都是。我总是告诉人们，你应该像写库一样写你所有的代码，因为它会被重用，所以你不如从那里开始。但委员会成员也一样。我偶然发现这个问题，是因为我长期以来对 std::move 的后置条件，即一个被移动过的对象的后置条件有抱怨。John Lakos 让我在他的书里就此写几页。所以如果你拿到他刚出版的新书，你会看到我的那几页。但当我真正通读时，导致这个问题的是从标准中剥离了“操作的定义域”这个术语。我们在标准中甚至没有任何方式来谈论析构和赋值的操作定义域是什么。那才是缺失的东西。

所以我的最后一个想法给你们，对吧？ 失败的代码和正确的代码之间的鸿沟是巨大的。这就是海勒姆的洞。 不幸的是，它太大了。所有碰巧能工作的代码都在其中。所有那些不正确，但能运行并做点什么的代码。所以，当你写代码时，努力去写正确的代码。你可能不会总是做到完全正确，但我保证如果你这么做，你会写出更好的代码。

这就是我的结束语。

最后一条评论。正如我之前提到的，我在 Adobe 工作。Adobe 正在招聘。我们有大量的空缺职位。这是我们职业网站的链接。下面那个是一个 bitly 链接，指向我们一些招聘人员专门为招聘 C++ 人员而建的网站。所以你们可能想去看看。

谢谢。我接受提问。

问答环节 (Q&A)¶

观众 1 (John Lakos): 感谢这次演讲。和往常一样精彩。你提到类型不一定能表达我们想在操作定义域方面表达的很多东西。显然有一些语言具有更强的类型概念，在那些语言中这是可以表达的，甚至包括形式化可证明的语言。但人们不使用那些语言，因为，你知道，很多经验已经表明了这一点。你认为这种差距实际上是由于人们无法持续遵循你在这场演讲中提出的那种观念所固有的吗？比如，一个能够做到你所要求的事情的人，他们能舒适地用那些语言之一来写代码吗？还是你认为这里有更多的事情在发生？

Sean Parent: 不，我认为这里肯定有更多的事情在发生，那就是当我们谈论编程语言中的一个类型时，我们真正谈论的是机器中某个值集合的一种表示。对。对。对。对。那才是重要的部分。当我们有一种表示时，开始谈论那个表示内部的子集、部分子集等等就变得极其困难。然后还要有某种方式来实现对那之上的强制执行。所以，是的，我认为如果你遵循这个，你在 TLA+ 或者其他那些围绕形式方法和表达事物设计的语言中会更自在一些，但不会太多。你最终还是在试图让计算机做某件事，并生活在那个局限性之中。坦白说，在那些其他语言中，甚至很难表达那个到硬件的映射是什么。而那是我们所做工作的一个重要部分。

观众 2: 所以这让我开始思考。我在思考安全性，以及通常来说，每当我们调用 API 时，你都是从一组契约开始的。然后那个 API 可能会调用其他 API，理想情况下，这些 API 会缩小那组契约。所以我这里有一个两层的问题，一个是，我们应该把被调用 API 的契约向上冒泡多远？我们什么时候这样做，什么时候不这样做？比如基于控制流，我可能很少调用一个会缩小契约的 API，以至于把那个契约应用到顶层函数几乎永远不为真。

Sean Parent: 是的。是的。我认为，基本上我之前说的是，你想从外到内构建，也就是从定义“我希望这个操作做什么？”和“我希望后置条件是什么？”开始。在实现中，你可能会发现一些你之前没意识到的关于这些关系的事情。但那是你想开始的地方，而不是暴露实现。泛型编程的一个关键思想是，你总是可以过来，比如一旦我有了 find，我总是可以为分段迭代器实现一个更快的 find，因为理论上我应该能做精化（refinement）。我们实际上不能用 C++ 恰当地做精化，但那，你知道，那应该是目标。所以从外部开始。我们为像迭代器层次结构这样的东西内置了一些精化。

在线提问 1: 我们能为像 float 和 double 这样的类型提供一个“部分相等”的概念吗？

Sean Parent: 一个部分相等的概念？不。不。NaN 是在那个定义域之外的。所以这真的就像类型本身是可相等比较的，但这排除了 NaN 这个值一样简单。所以，你知道，如果你想说，“我只想创建一个没有 NaN 的类型”，那会非常困难。那么你就真的不能在里面做除法了。

在线提问 2 (后续): 为什么不直接移除浮点数的 == 和 != 呢，既然它们没有意义？

Sean Parent: 我不同意这一点。我认为，比如 JavaScript 的所有东西都几乎是 double，没有它就没法工作了。在很多概念中，== 有着巨大的意义。但是，是的，你知道，正确地处理浮点数，有正确的精度等等，是一件棘手的事情。人们确实会滥用它，但我肯定不会移除它们。

观众 3: 我基本上有两个问题。一个是你是否可以真的使用像 Clang sanitizers 这样的工具来定义未定义行为，如果你传入的迭代器指向包含 double 的东西？第二个是……我想我忘了我第二个问题了。

Sean Parent: 好的。让我回答你的。然后我想回到那个在线问题，因为我刚对那个有了个想法。是的，希望如此，我的意思是，如果我们有更强的概念，在 std::find 上施加了实际相等性的要求，那么是的，你可以让 Clang Tidy 或者未定义行为清理器或者别的什么东西。你可以教它那些规则，让它挑出你的 NaN 并告诉你。所以，我的意思是，这当然是可行的。你知道，你能用那些工具做什么是有极限的，但在这种情况下，你可以。

我想回到为什么在浮点类型上有 == 很重要。部分原因是因为我们是根据相等来定义复制的。所以如果我复制一个东西，那个副本必须等于原始的。所以如果你从你的浮点数中剥离掉相等性，那实际上会让你很难验证你是否得到了一个正确的副本。

观众 3 (续): 我记起我最后一个问题了。你所说的 std::find 带有迭代器指针或迭代器值是未定义的，这是否也意味着 ranges::std::find 也是未定义行为，如果你传入一个在 range 里有 NaN 的东西？

Sean Parent: 我没有，你知道，深究过所有那些操作的所有要求。要澄清一下，我不是说 std::find 的实现版本在有 NaN 的情况下是未定义行为，因为它只要求 == 做某件事，并且它是在一个类型 T 上定义的。它实际上不要求它是 equality_comparable 的。我知道有一个 std::equality_comparable 概念，它被用在一些算法中。取决于它被用在哪些算法里，你可能会陷入那种情况。

观众 4: 你正在鼓励一种软件方法论，即人们非常仔细地审视你正在调用的函数的语义，并确保它与你正在写的函数相匹配。通读所有文档，深入思考。我想每个人都会同意，作为一个理想，这很棒。你会如何回应这样的反对意见：在商业环境中，这种编程方法论没有竞争力？

Sean Parent: 你知道，我认为发布有缺陷的软件会很快搞垮一家公司，你知道，有高缺陷率。所以你要么不做，要么尝试在测试中发现一些问题，这又回到了那个老论点，即你在前期花的时间越多，你在后端试图验证东西时花的时间就越少。通常这被证明是节省成本的。关于这类事情有大量的研究。它确实与“快速行动，打破常规”的心态有点相悖。但我认为总的来说，即使只是你个人，即使这不是公司的强制规定或命令，如果你花时间这样做，你会发现你能比不花时间这样做更快地写出更好的代码。

观众 5: 好的，Sean，这将是最后一个问题。我的问题是关于你最后一张幻灯片，关于我们能做什么来写出正确的代码？既然你提出了问题是什么以及你如何推导出写出正确的代码，你可能想提出一些理论框架，一些数学推理，说明为什么那些方法应该能产生正确的代码。有时候把一段代码看作一个沙箱是很常见的，它有一些输入、一些输出和一些副作用。所以你对所有这些东西施加约束和条件，并试图推导出输出和副作用，并确保在这段特定代码的执行中不会发生坏事。这也是为什么函数式语言，计算机函数式语言，在知道你写的代码是正确的方面做得这么好的原因，对吧？

Sean Parent: 嗯，是的，这里有点不同，那种正确性是 Tony Hoare 和 Bob Floyd 意义上的正确性，也就是说它不会引发未定义行为。它不会杀死你的狗。但它不一定做你打算做的事，因为你从未在外部陈述你打算让它做什么，对吧？所以我认为，那是 Bertrand Meyer 在契约式设计中的天才之处，就是你实际上必须陈述你打算让这个东西做什么。

观众 5 (续): 是的，这就是函数式语言和过程式语言的区别，在过程式语言中，你必须通过指定告诉计算机你想做什么来编码。我认为，函数式语言在商业上也不是那么广泛使用的原因之一是，总有一些副作用，那就是性能。所以你的代码在机器上执行的时间是副作用的一部分。你需要考虑到这一点，特别是如果你有一些时间约束。

Sean Parent: 对。所以你真正触及的，这不是一个正确性问题，甚至不是一个方法问题。而是大多数函数式语言保证了安全性。它们做到这一点的方式是，如果你所有的基本原语都是安全的，那么你用它们构建出来的所有东西都将是安全的。所以如果你从一个安全的基础开始，你就会有一个安全的系统。问题是，保证一个安全的基础是有代价的。所以那会影响你的性能。对。对。而且，安全性与正确性不同。对。安全性是关于你的代码脱轨时你造成多大的损害。所以你的函数式程序仍然会脱轨。只是损害被控制住了。我通常的说法是，如果你的语言是图灵完备的，那么在你的语言内部，我可以实现一个 C 语言虚拟机，我可以写出完全相同的所有 bug。唯一的区别是，我能造成的所有损害都被隔离在我构建的 C 语言虚拟机的边界内，这其实说明不了什么。

观众 5 (续): 是的。我正试图说明，所有这些都是与性能的权衡。我发现自己经常陷入这种情况，这是聪明的事情，但比如说你需要专门验证，特别是试图做一些性能更好的事情时。并且超越了过早优化的范围，试图写一些算法，特别是在并发中，大部分都是“碰巧能工作”。最成问题的“碰巧能工作”的事情是那些与并发问题相关的事情。是的。谢谢。

Sean Parent: 我同意。我的意思是，“碰巧能工作”在一个并发系统中会变成“有时候碰巧能工作”。而那真的非常糟糕。是的。好的。好的。我想，我想我们结束了。谢谢。谢谢。