第四章 结构化编程

1930年，Edsger Wybe Dijkstra出生于鹿特丹，他在二战时期的鹿特丹爆炸中幸存下来，当时德国人占领了荷兰。他于1948年从高中毕业，在数学，物理，化学，生物学等方面拥有最高的分数。 1952年3月，21岁（也就是我出生前的9个月）的Dijkstra在阿姆斯特丹数学中心找到了一份工作，成为了荷兰的第一个程序员。

1955年，作为一名程序员三年，仍然是一名学生，Dijkstra总结说，编程的对智力要求比理论物理对智力的要求更大。因此，他选择编程作为他的长期职业。Dijkstra于1957年与Maria Debets结婚。当时，你必须把你的职业作为荷兰婚礼的一部分。荷兰当局不愿接受“程序员”作为Dijkstra的职业;他们从来没有听说过这样的行业。为了满足他们，Dijkstra决定以“理论物理学家”作为他的职位。

把编程作为职业生涯的一部分，Dijkstra和他的老板Adriaan van Wijngaarden进行了交流。Dijkstra感到担心的是，没有人确定编程的学科或科学性，因此他并不被重视。他的老板回答说，Dijkstra很可能是发现这样的学科的人之一，进而可以将软件演变成一门科学。

在真空管的时代，Dijkstra开始了他的职业生涯，当时电脑巨大，脆弱，缓慢，不可靠，（按照当今的标准）非常受限。在最初几年，程序是用二进制编写的，或者是非常粗糙的汇编语言。输入采取了纸带或打孔卡的物理形式。编写/编译/测试循环是几个小时 - 如果不是几天。

Dijkstra在这个相当原始的环境中创造了伟大的发现。

证明

Dijkstra在早期就认识到编程困难和程序员难以处理的问题。任何复杂的程序都包含了太多的细节，人类的大脑在没有帮助的情况下难以处理。如果只看一个小细节的结果，程序似乎能运行，但这样往往造成出其不意的失败。

Dijkstra的解决方案是运用数学证明原理。他的愿景是建立一个欧几里德式的等式规则，定理，推论和引理。 Dijkstra认为程序员可以像数学家那样使用这个层次结构。换句话说，程序员将使用经过验证的结构，并将它们与代码绑定在一起，然后自行证明它们是正确的。

当然，为了实现这一目标，Dijkstra意识到他将不得不演示用于编写简单算法的基本证明的技巧。他发现这是相当具有挑战性的。

在他的研究中，Dijkstra发现goto语句的某些用法会阻止模块递归地分解成越来越小的单元，从而阻止使用分而治之的方法来进行合理的证明。

但是，goto语句的其他用法没有这个问题。 Dijkstra意识到goto的这些“良好”用法对应于简单的选择和迭代控制结构，如if / then / else和do / while。只使用这些类型的控制结构的模块可以递归地细分为可证明的单元。

Dijkstra知道，这些控制结构与顺序执行相结合是非常特殊的。他们在两年前被Böhm and Jacopini发现，他们证明了所有的程序都可以由三种结构构成：顺序，选择和迭代。

这一发现是意义重大：构成模块的这三种控制结构是可以构建所有程序的最小控制结构集合。因此结构化编程诞生了。

Dijkstra表明，通过简单的枚举可以证明顺序语句是正确的。该技术用数学方法追溯序列的输入到序列的输出的整个过程。这种方法与任何正常的数学证明没有什么不同。

Dijkstra通过又应用枚举来解决选择问题。通过选择的每个路径都被枚举。如果两条路径最终都产生了合适的数学结果，那么证明是可信的。

迭代有点不同。为了证明迭代是正确的，Dijkstra得使用数学归纳法。他通过枚举证明了1的情况。然后他证明了如果N被假定正确的话，N +1是正确的，这里也用了枚举。他还通过枚举证明了迭代的起始和终止的正确性。

这样的证明是费力和复杂的，但它们是证据，随着他们的发展，可以构建欧几里德定理层次的思想似乎是可行的。

有害的传言

1968年，Dijkstra写了一封信给CACM的编辑，这封信在CACM的3月号出版。这封信的标题是“Go To语句是有害的”。这篇文章概述了他在三种控制结构上的立场。

编程世界沸腾了。当时我们没有互联网，要不然人们会张贴Dijkstra这讨厌的模因¹，在网上攻击他。但是他们可以，而且也是写信给许多出版刊物的编辑。

那些信件不都是有礼貌的。有些人强烈否定;其他人表示强烈支持他的立场。战斗就这样加入了，最终持续了大约十年。

最终这个争论就消失了。原因很简单：Dijkstra赢了。随着计算机语言的发展，goto语句逐渐退化，直到它消失。大多数现代语言没有goto语句，当然，LISP从来就没有过。

现在我们都是结构化的程序员，虽然不一定选择。只是我们的语言不能让我们选择使用无条件的直接传输控制。有些人可能会指出Java中的命名中断或者类似的异常。事实上，这些结构并不是像Fortran或COBOL这样的老式语言曾经有过的完全无限制的控制转移。事实上，即使是支持goto关键字的语言，也经常会将目标限制在当前函数的范围内。

功能分解

结构化编程允许模块递归分解成可证明的单元，这又意味着模块可以在功能上分解。也就是说，你可以把一个大规模的问题描述分解成多个高层的函数。这些函数中的每一个都可以被分解为更低层的函数，再不断分解下去。而且，这些分解的函数中的每一个都可以用结构化编程的有限多的控制结构来表示。

在此基础上，结构化分析和结构化设计等学科在二十世纪七十年代后期和八十年代开始流行起来。像Ed Yourdon，Larry Constantine，Tom DeMarco和Meilir Page-Jones这样的人在那个时期推广和推广了这些技术。通过遵循这些规则，程序员可以将大型初步的系统分解成一个个模块和组件，这些模块和组件可以进一步分解成一个个微小的可证明的函数。

从无正式的证明

但是证明从来没有出现过。欧几里德定理层次从来没有建立。而程序员从来没有看到通过正式证明每一个小函数正确的艰辛过程的好处。最终，Dijkstra的梦想消失了，终于消失了。今天的程序员很少有人相信正式的证明是生产高质量软件的恰当方式。当然，正式的欧式风格的数学证明并不是证明某件事情正确的唯一策略。另一个非常成功的策略是科学的方法。

修复科学

科学与数学是根本不同的，因为科学的理论和规律不能被证明是正确的。我不能向你证明牛顿的第二运动定律$$F=ma$$或重力定律$$F=Gm_1m_2/r^2$$是正确的。我可以向你展示这些规律，而且我可以进行测量，证明它们精确到许多小数位，但是我不能用数学证明来证明它们。无论我进行了多少次实验，或者收集了多少经验证据，总会有一些实验证明那些运动规律和引力是不正确的。

这就是科学理论和定理的本质：它们是可证伪的，但是不可证明的。

然而，我们每天都要在这些定理上打赌。每当你进入一辆车，你打赌你的生活，$$F=ma$$是一个可靠的描述世界的工作方式。每次你迈出一步之后，你的健康和安全就是$$F=Gm_1m_2/r^2$$是正确的。

科学不是通过证明陈述是正确的，而是通过证明陈述是错误的。那些我们无法证明是虚假的陈述，经过很多努力，我们认为对于我们的目的来说是足够正确的。

当然，并非所有的陈述都是可以证明的。 “这是一个谎言”这个陈述既不是真也不假。这是一个不可证明的陈述的最简单的例子之一。

最终，我们可以说数学是证明可证明陈述是真的规则。相反，科学是证明可证明陈述是假的。

测试

Dijkstra曾经说过：“测试显示了有错误存在，而不是没有错误了”。换句话说，一个程序可以被测试证明是不正确的，但是它不能被证明是正确的。在经过充分的测试后，所有的测试都可以让我们认为程序对我们来说是足够正确的。

这个事实的影响是惊人的。软件开发并不是靠数学的努力，尽管它似乎在操纵数学结构。相反，软件就像一门科学。尽管我们尽了最大的努力，但我们是通过找不到不正确的情况，而说明程序的正确性的。

这种不正确的证据只能用于可证明的程序。一个不可证明的程序（例如，由于无限制地使用goto）不管有多少测试用例，都不能被认为是正确的。

结构化编程迫使我们递归地将一个程序分解成一组小的可证明函数。然后我们可以使用测试来试图证明这些小的可证明的功能是不正确的。如果这些测试不能证明不正确，那么我们认为这些功能对于我们的目的来说是正确的。

小结

正是这种能力来创建可证伪的编程单元，使得今天的结构化编程非常有价值。这就是现代语言通常不支持无限制的goto语句的原因。而且，在架构层面上，这就是为什么我们仍然认为功能分解是我们的最佳实践之一。

从最小的功能到最大的组件，在每一个层面上，软件就像是一门科学，因此是由可证伪性驱动的。软件架构师努力定义易于发现错误（可测试）的模块，组件和服务。为此，他们采用类似于结构化编程的限制性的规则，虽然它们处于更高层。

在之后的章节中，我们将详细研究这些限制性的规则。