Question

写一个程序的所有要点就是让计算机做有用的事情。作为程序员，我们该如何应对无法检测程序是否正确工作这个事实呢？

拒绝是一个吸引人的选择：忽略整个问题。如果能自动校验程序行为当然好，但我们不能，所以只是期望做到最好，而永远不要检查一个程序在正确地完成它的工作。

但这属于反应过度，因为情况没有听起来那么坏。Rice 定理并不意味着分析程序不可能，而只是我们不可能写出一个不平凡的总是停机并产生正确答案的分析器。就像我们在 8.3.1 节看到的，没有什么可以阻止我们写一个工具来为某些程序给出正确答案，只是我们得承认总是会存在其他程序要么给出错误答案要么永远循环不返回任何东西。

不考虑不可判定性，下面是一些分析和预测程序行为的实用方法。

· 问一些不可判定的问题，但如果找不到答案就放弃。例如，为了检查一个程序是否会输 出特定的字符串，我们可以运行程序然后等待；如果在特定的时间（比如 10 秒）内没有输出那个字符串，我们就结束程序并假设它没有用。我们有可能会扔掉一个 11 秒之后才产生期望输出的程序，但在很多情况下，这种风险是可以接受的，特别是从自身来说我们不需要运行缓慢的程序。

· 把所问的几个小问题答案汇总起来，就能为一个更大的问题提供经验性的证据。在执行自动化验收测试时，我们通常不能为每一个可能的输入检查程序是否做了正确的事情，但我们可以尝试为有限的输入样本运行这个程序来看会发生什么。每一个测试运行都对那个特例程序如何运行给出了信息，并且我们可以使用这个信息提高对程序通常可能行为的信心。有可能还有未测试的输入，这会引起完全不同的行为，但只要测试用例为大多数现实输入的表示完成了工作，我们就可以坦然生活。这个方法的另一个例子是单元测试的使用，单元测试是为了验证小段程序行为，而不是把程序作为整体来验证。一个良好分离的单元测试专注于简单单元代码的性质，并通过把程序的其他部分表示成测试替代物（存根和模拟对象）来做出假设。使用小段容易理解代码的单个单元测试可能会简单而且快速，把任何一个将会永远运行或者给出误导答案的测试风险最小化。

通过这种方式对程序的所有片段进行单元测试，我们可以建立一个类似数学证明的假设和影响链：“如果片段 A 工作，那么片段 B 能工作，而如果片段 B 工作，那么片段 C能工作。”判定所有这些假设是否正当是人类推理的责任而不是自动化校验的责任。当然，集成和验收测试可以提高我们对整个系统做应做之事的自信。

· 问可判定的问题，在必要的时候要保守一些。上面的建议通过实际运行一个程序的很多部分来看发生了什么，它总是会引入无限循环的风险，但有的问题可以只通过静态检查源代码就能回答。最明显的例子是：“这个程序含有任何的语法错误吗？”但万一真正的答案是不可判定的，我们也准备接受近似安全的话，就可以回答更有意思的问题。

一个常规分析就是浏览程序的源代码看它是否含有计算出来的值从来不用的死代码（dead code），或者含有从来不会被求值的不可达代码（unreachable code）。我们不可能总能说出是否代码是真正的死代码或者不可达代码，因此只能保守一些，假设它不是，但存在明显是的情况：在某些语言里，我们知道赋值给一个永远不再使用的局部变量肯定是死的，一个紧跟在 return 后边的语句必是不可达的。21 像 GCC 这样优化的编译器就是使用这个技术识别和去除不必要的代码，让程序更小更快而且不会影响程序的行为。

· 通过把程序转换成更简单的东西来近似它，然后问关于近似的可判定问题。这个重要的思想是下一章的主题。

21Java 语言规范要求编译器拒绝任何含有不可达代码的程序。参见http://docs.oracle.com/javase/specs/jls/se7/html/jls-14.html#jls-14.21，其中有 Java 编译器如何不运行程序就判定一个程序哪一部分有可能不可达的冗长解释。