20世纪60年代末，人们就在讨论验证其他程序正确性的那些验证程序的前景了。不幸的是，到今天这几十年间，除了屈指可数的几个例外，自动验证系统依然还是纸上谈兵。尽管以前的预期落空了，对程序验证所进行的研究还是给我们提供了很有价值的东西——对计算机编程的基本理解，这比一个吞入程序，然后闪现“好”或“坏”的黑匣子要好得多。

本章的目的是阐述这些基本理解如何帮助实际程序员编写正确的程序。一位读者将大多数程序员习以为常的方法形象地归纳为“编写代码，然后丢给另一个部门，由QA（质量保证）或QT（质量测试）来处理错误”。本章描述一种不同的方法。在开始讨论之前，我们必须正确地认识到：编程技巧仅仅是编写正确程序的很小一部分，大部分内容还是前面三章讨论过的主题：问题定义、算法设计以及数据结构选择。如果这些步骤都完成得很好，那么编写正确的程序通常是很容易的。

4.1　二分搜索的挑战

即使有了最好的程序设计，程序员也常常要编写巧妙的代码。本章讨论一个需要特别仔细地编写代码的问题：二分搜索。在回顾这个问题并简介其算法之后，我们将使用验证原则来编写程序。

我们首次遇到这个问题是在2.2节。我们需要确定排序后的数组

中是否包含目标元素t。[1]准确地说，已知

且

，当n=0时数组为空。t与x中元素的数据类型相同。无论是整型、浮点型还是字符串型，伪代码都必须同样地正确运行。答案存储在整数p中（记录位置）：当p为-1时，目标t不在数组

中；否则

，且

。

二分搜索通过持续跟踪数组中包含元素t的范围（如果t存在于数组的话）来解决问题。一开始，这个范围是整个数组；然后通过将t与数组的中间项进行比较并抛弃一半的范围来缩小范围。该过程持续进行，直到在数组中找到t或确定包含t的范围为空时为止。在有n个元素的表中，二分搜索大约需要执行

次比较操作。

多数程序员都认为有了上述描述在手，编写代码是轻而易举的事。但是他们错了。相信这一点的唯一办法就是马上放下书，然后自己编写这段程序。试试看。

我在给专业程序员上课时布置过该问题。学生们有数小时的时间将上面的描述转换成程序。可以使用任何一种编程语言，高级伪代码也可以。规定的时间到了的时候，几乎所有的程序员都报告说自己完成了该任务的正确代码。然后，我们用30分钟时间来检查这些程序员已经用测试实例检验过了的代码。在几个课堂里对一百多名程序员的检查结果大同小异：90%的程序员都在他们的程序中发现了错误（并且我不相信那些没有发现错误的程序就一定是正确的）。

我很惊诧：提供充足的时间，竟然仅有约10%的专业程序员能够将这个小程序编写正确。但是他们不是唯一一批发现这个任务困难的人：Knuth在其The Art of Computer Programming, Volume 3: Sorting and Searching的6.2.1节的历史部分中指出，虽然第一篇二分搜索论文在1946年就发表了，但是第一个没有错误的二分搜索程序却直到1962年才出现。

4.2　编写程序

二分搜索的关键思想是如果t在

中，那么它就一定存在于x的某个特定范围之内。这里使用mustbe(range)来表示：如果t在数组中，那么它一定在range中。使用这个定义可以将上面描述的二分搜索转换成下面的程序框架：

initialize range to 0..n-1 loop { invariant: mustbe(range) } if range is empty, break and report that t is not in the array compute m, the middle of the range use m as a probe to shrink the range if t is found during the shrinking process, break and report its position

该程序的最重要部分是大括号内的循环不变式（loop invariant）。之所以把这种关于程序状态的断言（assertion）称为不变式（invariant），是因为在每次循环迭代之前和之后，该断言都为真。这个名称将前面已有的直观概念形式化了。

现在进一步完善程序，并确保所有的操作都遵循该不变式。我们面对的第一个问题就是范围（range）的表示方式：这里使用两个下标l和u（对应下限lower和上限upper）来表示范围l..u。（9.3节的二分搜索函数使用起始位置和长度来表示范围）。逻辑函数mustbe(l, u)是说：如果t在数组中，t就一定在（闭区间）范围x[l..u]之内。

下一步的工作是初始化。l和u应该为何值，才能使mustbe(l, u)为真？显而易见的选择是0和n-1：mustbe(0, n-1)是说如果t在x中，那么t就一定在x[0..n-1]中；而这恰好就是我们在程序一开始就知道的事实。于是，初始化由赋值语句l=0和u=n-1组成。

下一步的任务是检查空范围并计算新的中间点m。当l > u时范围l..u为空，在这种情况下，将特殊值-1赋给p并终止循环，程序如下：

if l > u p = -1; break

break语句终止了外层的loop。下面的语句计算范围的中间点m：

m = (l + u) / 2

“/”运算符实现整数除法：6/2等于3，7/2也等于3。至此，扩展的程序如下：

l = 0; u = n-1 loop { invariant; mustbe(l, u) } if l > u p=-1; break m = (l + u) / 2 use m as a probe to shrink the range l..u if t is found during the shrinking process, break and note its position

为了完善循环体中的后三行，需要比较t和x[m]，并采取合适的操作来保持不变式成立。因此代码的一般形式为：

case x[m] < t: action a x[m] == t: action b x[m] > t: action c

对于操作b，由于t在位置m，所以将p设为m并终止循环。由于另外两种情况是对称的，这里集中讨论第一种情况并认为对最后一种情况的讨论可以根据对称性得到（这也是在下一节中我们必须精确验证代码正确性的一部分原因）。

如果x[m]<t,那么x[0]

x[1]

…

x[m]<t。因此，t不可能存在于x[0..m]中的任何位置。将该结论与已知条件“t不在x[l..u]之外”相结合，可知t一定在x[m+1..u]之内，记为mustbe(m+1, u)。然后，通过将l设为m+1可以再次确立不变式mustbe(l, u)。将这些情况放入前面的代码框架中，就获得了最终的函数。

l = 0; u = n-1 loop { mustbe(l, u) } if l > u p = -1; break m = (l + u) / 2 case x[m] < t: l = m+1 x[m] == t: P = m; break x[m] > t: u = m-1

这是一个简短的程序：只有9行代码和一个不变式断言。程序验证的基本技术（精确定义不变式并在编写每一行代码时随时保持不变式的成立）在我们将算法框架转化成伪代码时起到了很大的作用。该过程使我们对程序的正确性树立了一些信心。但是这并不意味着该程序就一定是正确的。在继续往下阅读之前，请花几分钟时间确定该代码的功能是否与所描述的一致。

4.3　理解程序

当面对复杂的编程问题的时候，我总是试图得到如同上面那样详细的程序代码，然后使用验证方法来增强自己对程序正确性的信心。本书中的第9章、第11章和第14章也将在这个层面上使用验证技术。

本节我们将在近乎吹毛求疵的细节层面上研究对二分搜索程序所进行的验证分析，实践中我很少做这么多正式的分析。下一页的程序大量使用断言进行注释，从而形式化了最初编写代码时所用的直观概念。

代码的开发是自上而下进行的（从一般思想开始，将其完善为独立的代码行），该正确性分析则是自下而上进行的：从每个独立的代码行开始，检查它们是如何协同运作并解决问题的。

我们从第1行至第3行开始讨论。mustbe的定义如下：如果t在数组中，那么它一定在x[0..n-1]中。由此可知，第1行的断言mustbe(0, n-1)为真。于是，根据第2行的赋值语句l=0和u=n-1可以得到第3行的断言：mustbe(l, u)。

下面讨论困难的部分：第4行至第27行的循环。关于其正确性的讨论分为3个部分，每部分都与循环不变式密切相关。

• 初始化。循环初次执行的时候不变式为真。
• 保持。如果在某次迭代开始的时候以及循环体执行的时候，不变式都为真，那么，循环体执行完毕的时候不变式依然为真。
• 终止。循环能够终止，并且可以得到期望的结果（在本例中，期望的结果是p得到正确的值）。为说明这一点需要用到不变式所确立的事实。

对于初始化，我们注意到第3行的断言与第5行的相同。为确立其他两条性质，对第5行至第27行进行分析。讨论第9行和第21行（break语句）时，将确立终止性质。如果持续下去，直至第27行，就可以得到保持性质，因为这又与第5行相同。

1． { mustbe(0, n-1) } 2． l = 0; u= n-1 3． { mustbe(l, u) } 4． loop 5． { mustbe(l, u) } 6． if l > u 7． { l > u && mustbe(l, u) } 8． { t is not in the array } 9． p = -1; break 10． { mustbe(l, u) && l <= u } 11． m = (l + u) / 2 12． { mustbe(l, u) && l <= m <= u } 13． case 14． x[m] < t: 15． { mustbe(l, u) && cantbe(0, m) } 16． { mustbe(m+l, u) } 17． l = m+1 18． { mustbe(l, u) } 19． x[m] == t: 20． { x[m] == t } 21． p = m; break 22． x[m] > t: 23． { mustbe(l, u) && cantbe(m, n-1) } 24． { mustbe(l, m-1) } 25． u = m-1 26． { mustbe(l, u) } 27． { mustbe(l, u) }

第6行的成功测试将得到第7行的断言：如果t在数组中，那么它就必定在位置l和u之间，且l > u。这些事实就意味着第8行的断言成立：t不在数组中。于是在第9行设定p为-1后，就可以正确地终止循环。

如果第6行的测试失败，就进入到第10行。不变式依然为真（我们没有对其做任何改动），并且由于测试失败，可得l

u。第11行将m设为l和u的平均值，向下取整为最接近的整数。由于平均值总是位于两个值之间并且取整不会使之小于l，所以得到第12行的断言。

从第13行至第27行的case语句考虑到了所有3种可能。最容易分析的一个分支是位于第19行的第二个分支。由第20行的断言，我们将p设定为m并终止循环是正确的。这是第二处终止循环的地方（一共两处），由于两次对循环的终止都是正确的，于是我们确立了循环终止的正确性。

下面讨论case语句中的两个对称分支。由于在编写代码的时候，我们把精力集中在第一个分支上，现在我们将注意力转移到第22行～第26行。考虑第23行的断言。第一个子句是不变式，循环并没有对其进行改变。由于t < x[m]

x[m+1]

x[n-1]，第二个子句亦为真，于是我们可以知道t不在数组中任何高于m-1的位置，使用简短记法表示为cantbe(m, n-1)。逻辑告诉我们，如果t一定在l和u之间，而且不等于或高于m，那么t就一定在l和m-1之间（前提是t在x中），于是得到第24行。第24行为真时执行第25行可得第26行为真——这是赋值的定义。case语句的这个分支也就再次确立了第27行的不变式。

第14行至第18行的讨论具有完全相同的形式，至此，我们完成了对case语句所有三个分支的分析。一个正确地终止了循环，其他两个则保持了不变式。

该代码分析表明，如果循环能够终止，那么就可以得到正确的p值。但是，程序中仍有可能包含死循环；事实上，这正是那些专业程序员编写该程序时所犯的最常见的错误。

我们的停机证明从另一个角度对范围l..u进行了考虑。初始范围为某一有限大小（n），第6行至第9行确保当范围中的元素少于一个时终止循环。因此，要证明终止，我们必须证明在循环的每次迭代后范围都缩小了。第12行告诉我们，m总处于当前范围内。case语句中不终止循环的两个分支（第14行和第22行）都排除了范围中位置m处的值，由此将范围大小至少缩小1。因此，程序必会终止。

有了这些背景分析，我对我们进一步讨论这个函数更有信心了。下一章涵盖了以下主题：用C来实现该函数，然后进行测试以确保程序正确而且高效。

4.4　原理

本章的练习展示了程序验证的诸多优势：问题很重要，需要认真地编写代码；程序的开发需要遵循验证思想；可以使用一般性的工具进行程序的正确性分析。该练习的主要缺点在于其细节层面：在实践中不需要这么正式。幸运的是，这些细节阐述了许多一般性的原理，包括以下原理。

断言。输入、程序变量和输出之间的关系勾勒出了程序的“状态”，断言使得程序员可以准确阐述这些关系。这些断言在程序生命周期中的角色在下一节中论述。

顺序控制结构。控制程序的最简单的结构莫过于采用“执行这条语句然后执行下一条语句”的形式。可以通过在语句之间添加断言并分别分析程序执行的每一步来理解这样的结构。

选择控制结构。这些结构包括不同形式的if和case语句；在程序运行过程中，多个分支中的一个被选择执行。我们通过分别分析每一个分支说明了该结构的正确性。一定会选择某个分支的事实允许我们使用断言来证明。例如，如果执行了语句if i >j，那么我们就可以断言i >j并且使用这个事实来推导出下一个相关的断言。

迭代控制结构。要证明循环的正确性就必须为其确立3个性质：

我们首先讨论由初始化确立的循环不变式，然后证明每次迭代都保持该不变式为真。由数学归纳法可知这两步就证明了在循环的每次迭代之前和之后该不变式都为真。第三步是证明无论循环在何时终止执行，所得到的结果都是正确的。综合这些步骤可知：只要循环能停止运行，那么其结果就是正确的。因此我们还必须用其他方法证明循环一定能终止（二分搜索的停机证明所使用的方法是比较常见的）。

函数。要验证一个函数，首先需要使用两个断言来陈述其目的。前置条件（precon- dition）是在调用该函数之前就应该成立的状态，后置条件（postcondition）的正确性由函数在终止执行时保证。如此可以得到C语言二分搜索函数如下：

int bsearch(int t, int x[], int n) /* precondition: x[0] <= x[1] <= ... <= x[n-1] postcondition: result == -1 => t not present in x 0 <= result < n => x[result] == t */

这些条件与其说是事实陈述不如说是一个契约：如果在前置条件满足的情况下调用函数，那么函数的执行将确立后置条件。一旦证明函数体具有该性质，在以后的应用中就可以直接使用前置条件和后置条件之间的关系而不再需要考虑其实现。该方法在软件开发中通常称为“契约编程”。

4.5　程序验证的角色

当一个程序员想要让别人相信某段代码正确的时候，首选的工具通常就是使用测试用例：运行程序并手动输入数据。这是很有效的：适用于检测程序的错误、易于使用并且很容易理解。然而，程序员明显对程序有更深的理解——如果他们做不到这一点的话，就不可能编写出第一手程序。程序验证的一个主要好处就是为程序员提供一种语言，用来表达他们对程序的理解。

本书的后续部分（特别是第9章、第11章和第14章）将会使用验证技术进行复杂程序的开发。在编写每一行代码的时候都使用验证语言来解释，这对概括每个循环的不变式特别有用。程序文本中重要的解释以断言的形式结束；而确定在实际软件中应包含哪些断言则是一门艺术，只能在实践中学习。

验证语言常用于程序代码初次编写完成以后，在进行初次模拟的时候开始使用。测试过程中，违反断言语句的那些情况指明了程序的错误所在，而对相应情况形式的分析则指出了在不引入新错误的情况下如何修正程序中的错误。调试过程中，需要同时修正错误代码和错误的断言：总是保持对代码的正确理解，不要理会那种“只要能让程序工作，怎么改都行”的催促。第5章将介绍程序验证在程序的测试和调试过程中所扮演的几种重要角色。断言在程序维护过程中至关重要：当你拿到一段你从未见过而且多年来也没有其他人见过的代码时，有关该程序状态的断言对于理解程序是很有帮助的。

这些仅是编写正确程序的很小一部分技术。编写简单的代码通常是得到正确程序的关键。另一方面，几个熟悉这些验证技术的专业程序员曾经对我讲述了一段在我自己编程时也常遇到的经历：当他们编写程序的时候，“困难”的部分第一次就可以正确运行，而那些“容易”的部分往往会出毛病。当开始编写困难的部分时，他们会坐下来仔细编程并成功地使用强大的正规技术。在编写容易的部分时，他们又返回到自己的编程老路上来了，结果当然是旧病复发了。在亲身经历之前，我也并不相信会有这种现象，这种尴尬的现象是经常使用验证技术的良好动力。

本文摘自：《编程珠玑》第2版。[美] 乔恩·本特利（Jon Bentley） 著，黄倩，钱丽艳 译。

• 经典算法和数据结构习题精粹，计算机科学领域20余年畅销不衰的不朽经典
• 程序员案头常备，融深邃思想、实战技术与趣味轶事于一炉的奇书
• 带你真正领略计算机科学之美

多年以来，当让程序员推选喜爱的计算机图书时，《编程珠玑》总是位于前列。正如自然界里珍珠出自细沙对牡蛎的磨砺，计算机科学大师乔恩·本特利以其独有的洞察力和创造力，从磨砺程序员的实际问题中凝结出一篇篇编程“珠玑”，成为世界计算机界名刊《ACM通讯》历史上*受欢迎的专栏，*终结集为两部计算机科学经典名著，影响和激励着一代又一代程序员和计算机科学工作者。本书为第一卷，主要讨论计算机科学中*本质的问题：如何正确选择和高效地实现算法。 
在书中，作者选取许多具有典型意义的复杂编程和算法问题，生动描绘了历史上大师们在探索解决方案中发生的轶事、走过的弯路和不断精益求精的历程，引导读者像真正的程序员和软件工程师那样富于创新性地思考，并透彻阐述和总结了许多独特而精妙的设计原则、思考和解决问题的方法以及实用程序设计技巧。解决方案的代码均以C/C++语言编写，不仅有趣，而且有很大的实战示范意义。每章后所附习题极具挑战性和启发性，书末给出了简洁的解答。