编程的修炼（中英对照）

《编程的修炼（中英对照）》写于20世纪70年代中后期，但其对编程技术领域的开发、编程语言发展和程序理论研究的深刻影响持续至今。

《编程的修炼（中英对照）》为图灵奖获得者Edsger W.Dijkstra所著，是编程领域里经典著作中的经典。作者基于其敏锐的洞察力和长期的实际编程经验，对基本顺序程序的描述和开发中的许多关键问题做了独到的总结和开发。《编程的修炼（中英对照）》中讨论了顺序程序的本质特征、程序描述和对程序行为（正确性）的推理，并通过一系列从简单到复杂的程序的思考和开发范例，阐释了基于严格的逻辑推理开发正确可靠程序的过程。

艾兹赫尔·戴克斯特拉（Edsger W. Dijkstra，1930年5月11日－2002年8月6日），生于荷兰鹿特丹，自喻为荷兰第一个以程序设计作为职业的人。他早年积极推动结构化程序设计，一生致力于将计算（computing）发展为一门科学，在计算机科学技术的诸多领域有开拓性建树，并由于在程序设计基础研究中的卓越贡献获得1972年图灵奖。

在本书中，作者以其习惯的文字风格，详尽地描述了他对计算机编程的基本性质的激进的新见解。基于这些见解，作者开发了一套编程方法以及与之相适应的记法工具，并用一大批优雅而且高效的实例展示和检验了它们。本书将注定成为在计算机编程的智力修炼领域发展中最杰出的成就之一。
——C.A.R.Hoare

序
前言
第0章 执行抽象
第1章 编程语言的作用
第2章 状态及其特征
第3章 语义的性质
第4章 一种编程语言的语义特征
第5章 两个定理
第6章 论完满终止结构的设计
第7章 再论欧几里得算法
第8章 几个小例子的形式化处理
第9章 论受限的非确定性
第10章 有关记法的短论："变量的作用域"
第11章 数组变量
第12章 线性检索定理
第13章 下一个排列
第14章 荷兰国旗问题
第15章 更新顺序文件
第16章 再论归并
第17章 来自R.W.HAMMING的一个练习
第18章 模式匹配问题
第19章 将一个数写成两个平方之和
第20章 大数的最小素因子问题
第21章 最孤立村庄问题
第22章 最短子支撑树问题
第23章 记录等价类的REM算法
第24章 三维空间的凸包问题
第25章 有向图的最大强连通分支
第26章 论手册和实现
第27章 跋

第1 章
编程语言的作用
在“执行抽象”一章中，我非形式化地描述了计算两个（不太大的）正整数的最大公因子的几种不同“机器”的设计。其中一部机器采用在纸板上移动石子的方式；另一部机器基于两个半拉石子，而且它们都在坐标轴上移动；最后一个基于两个寄存器，每个里面可以保存一个（直至某个上限的）整数值。从物理上说，这三台“机器”大相径庭；而从数学上看，它们却很类似，做出这一论断的主要原因是，三者都能计算最大公因子，这是三者的共性。由于这三台机器只不过是同样一组“游戏规则”中不同的具体实现，而实际上，这组规则才是一个发明的核心，该发明就是大名鼎鼎的“欧几里得算法”。
在前一章里，欧几里得算法是用一种相当非形式化的方式描述的。有人会提出，由于与之对应的可能计算的数目如此之大，因此，我们必须要有一个关于其正确性的证明。如果一个算法只是以非形式化的方式给出，它就不容易作为一种形式化处理的对象。为了形式化地处理，我们就需要用某种适当的形式化的记法来做算法的描述。
这样一种形式化记述技术的可能优势有许多方面。任何记述技术都蕴涵着一个事实：它所实际表述的任何东西都是它有可能描述的那个对象集合（通常是一个无穷集合）的一个特定成员。我们的记述技术当然应该能给出欧几里得算法的一个优雅而简洁的描述，而一旦做好了这件事，也就是把它表示成了一个包含各种算法的巨大的类中的一个成员。而在描述该类中的其他算法时，我们可能期望发现自己所用的记述技术的一些更有趣的应用。对于欧几里得算法，可能会有人说因为它如此简单，用一个非形式化的描述就能对付了。形式化记法的威力应该表现在一些没有它就绝不可能做到的成就方面。
形式化记述技术的第二个优势是，它使我们有可能将算法作为一种数学对象来研究，算法的形式化描述将成为我们的智力收获的抓手，使我们能证明一些有关算法类的定理，例如，由于算法所采用的描述而使之共有的一些结构性的性质。
最后，这样一种记述技术将使我们能毫无歧义地定义算法，这样，给定了用它描述的一个算法，并给定一组实际参数（输入），有关与之对应的答案（输出）应该是什么，将没有任何疑义或者非确定性。可以断言，相应的计算完全可以用一部自动机器完成：给它该算法（的形式化描述）和相应的实际参数，它就能产生出相应的答案，完全无须进一步的人工干预。这样一种能对付这种相互对应的算法和实际参数的自动机器已经造出来了，它就是人们说的“自动计算机”。为能在计算机上自动执行而写出的算法称为“程序”，而自20世纪50年代后期以来，用于写程序的形式化记述技术就被称为“编程语言”。（与程序的记述技术有关的术语“语言”的引入已受到多方面关注。一方面，现有的语言理论为相关讨论提供了一种很自然的框架和一套有用的术语，如“文法”、“语法”、“语义”等。另一方面，我们也必须注意到，与现存的“自然语言”的类似性也造成了许多误导，因为各种自然语言，无论怎样做形式化，其弱点和威力都来自它们的非明确性和非精确性。）
从历史情况看，这最后一个方面，即各种编程语言可以用作指挥现有的自动计算机的媒介，这个事实已经在很长时期里成为它们最重要的属性。现有的自动计算机执行某种特定语言写出的程序的效率，也成为评判该语言的质量的最重要标准。这种情况导致了一个令人遗憾的后果：不难看到，现有计算机的许多很反常的特性都被忠实地反映在现有的编程语言里，为此付出的代价是，用这样一个语言描述的程序是很难用智力去把握的（实际上，即使没有这种情况，编程的工作也已经非常困难了！）。在下面将要提出的方法中，我们将试着重新考虑这方面的平衡。按我们的认识，写出的程序需要实际地由一台计算机执行，这只是由于偶然性而导致的一种实际情况，它不应该居于我们考虑问题的中心。（在最近的一本培养PL/I程序员的教材里，可以看到作者强烈建议尽可能避免过程调用，理由是“因为它们会大大影响程序的效率”。由于过程是PL/I中描述结构的最重要的工具，上述建议实在太可怕了，以至于我完全无法把这本书看作真的能“用于教育”。如果你确信过程是一种有用的概念，而在你的工作环境中，过程机制的实现带来的开销却令人难以忍受，那么应该诅咒的是这些不适当的实现，而不应该是把它们的表现作为一种标准！这方面的权衡确实应该重新做！）
我把一种编程语言看作是一种工作媒介，用于描述（可能非常复杂的）抽象机制。正如在有关“抽象执行”一章里可以看到的，算法最突出的优点就在于对它们能够做出的论证的简洁性。我们对于有关机制的信心也是基于这个事实。如果失去了这种简洁性，算法就失去了其（存在的权利）中很大一部分，因此，我们将把保持这种简洁性作为始终如一的目标。另外，我们对所有编程语言的选择也将直面这一目标。

……

译者序
图灵奖获得者Edsger W. Dijkstra（1930.5.11—2002.8.6）是每个在计算机领域
中学习和工作的人都应该了解和尊重的先驱者，其思想和技术遗产散布在计算机科学技术的众多领域。刚开始学习编程的人们都听过结构化编程的基本思想，在专业学习的早期就会遇到查找图中最短路径的Dijkstra 算法，在学习并发程序技术时更是无处不见Dijkstra 的思想和技术贡献。
Dijkstra 是20 世纪70 年代前后程序理论研究领域最重要的开拓者之一，也是那个时代的技术英雄。1968 年，Dijkstra 给CACM 的一篇投稿引起结构化编程的倡导者们与维护goto 的保守人士的大辩论，最终成就了结构化编程的革命，这是软件开发从个人技艺走向技术和科学的伟大的第一步。Dijkstra 与Tony Hoare 和Ole-Johan Dahl 的专著Structured Programming 以其三位作者分别获得图灵奖而永远不可能被超越。其中，Dijkstra 撰写的“Notes on Structured Programming”提出了软件设计的许多指导原则，其深刻影响覆盖了从基础计算机教育直到复杂软件系统设计的广泛领域。Dijkstra 的另一重大贡献是作为最主要奠基人参与了并发程序理论和技术基础的开发。他基于自己的并发编程实践提出了许多概念，开发了许多技术。这里的许多术语出自他的思考，包括互斥、同步、竞态条件、死锁、非确定性、自稳定等。他提出的信号量、P/V 操作、临界区等是今天所有并发机制的基础。他还留给我们许多并发程序范例，如读者/作者问题、生产者/消费者问题、就餐的哲学家问题等，有些是他上课时留给学生的练习。他开发的THE 多道程序系统为操作系统的理论和实现竖起了第一根标杆。Dijkstra 在程序正确性领域
也做出了极为重要的贡献，这是20 世纪70 年代之后他最关注的领域，本书就是
他一段工作的最重要的总结，下面将详细讨论。有关Dijkstra 的更多贡献可以参考介绍他的WiKi 页和纪念网页。
本书的英文书名是A Discipline of Prograamming，是Dijkstra 有关程序理论和编程技术的最重要的著作。本书是一本非常独特的编程技术专著。首先，编程教科书通常要选一种流行语言作为示例的载体，而本书却没用任何可以由计算机执行的语言，所有示例程序都没运行过，但其正确性却有保证。
作者也没用“伪代码”形式，因为那样做会带来不可避免的歧义性，而且伪代码无力作为严格的形式化推理工具。本书中的程序用作者自己设计的一种小语言描述，该语言反映了顺序（非并行）编程语言最本质的性质，还有许多重要特性将在下面讨论。其次，虽然本书也给出了一系列编程实例，但采用的方式却与其他书籍大相径庭。作者在给出了要解决问题的陈述之后，总是很详细地描述了从问题出发，通过细致的分析思考，逐步深入工作，最后做出所需程序的整个过程。作者通过这种过程反复展示了在编程中应该怎样思考问题，提出合适的概念，规划处理流程，通过自上而下的设计和开发逐步做出程序框架，分析解决遇到的具体问题并做出各部分细节，直至完成完整的程序。作者还特别强调了“关注点分离”的重要性，强调在一个阶段解决一个问题。在一些复杂程序开发完成后还给出了细致的回顾性分析。作者在书中特别注意开发过程的真实性，并不回避其间提出过的错误概念和走过的弯路。这种真实的实践很难在其他编程著作中看到。虽然上面两点已明显表现出本书的与众不同，但它们还不是本书最重要的特点。Dijsktra 在本书中最重要的关注点是程序的正确性，是关于程序和程序意义的“数学推导”和“证明”。他在前言中写到，我们的目标应该是“设计出具有高度信任水平的程序，而不仅仅是……一些胡乱涂抹出来的，随时准备被第一个反例推翻的程序正文”。他认为构造过程的目标应该是直接得到正确的程序，而不是得到一些“大致能用”的代码。目前的编程工作都表示这样，人们在开发中反复测试半成品或成品，找出其中缺陷并予以更正，直至作品或工作过程满足了某些外在“评价标准”，或者由于时间、金钱、人力限制而不得不结束工作。到最后开发者也不敢断定给出的就是所需要的“那个”程序。
有关如何开发出正确的程序，书中强调了多方面的问题。首先是大家都熟悉的问题分析，需要在动手编程之前把问题弄清楚，严格定义好，这件事怎么强调都不过分。这里不过多地讨论，书中有许多具体例子可供参考。更重要的是，Dijkstra认为保证程序正确的主要武器就是数学意义上的严格描述和推导，他通过一大批示例展示了严格推导在编程领域里的威力。Dijkstra认为程序语言（无论哪种语言）本身是一种形式化的严格定义的描述形式，用它们写出的一个程序具有确定的语义。具体计算机运行该程序是实现它的语义，但其语义并不依赖于运行它的计算机，因此需要独立考虑和表达。为此，Dijkstra基于状态和断言的概念提出了最弱前条件的思想，用谓词转换器作为程序语义的落脚点。由于常规语言不能完美地支持他的想法，他自己开发了一种语言，其中最重要的新概念是卫式命令，语言里的选择和重复结构都基于卫式命令定义。Dijkstra用书中的实例展示了通过严格推理直接开发出正确程序的过程，展示了不变式、最弱前条件、谓词转换器等重要概念和严格的逻辑推理怎样在程序开发中发挥作用，帮助开发者（这里的实践者是Dijkstra本人）理清程序的线索，逐步推导出正确的程序。作者在这里提出的最弱前条件、谓词转换器、非确定性等概念对程序理论和实践的发展都产生了重要影响。
显然，并不是每个人都赞同Dijkstra的这种想法，未来世界中所有的程序也未必都采用他的这种理想主义的方式开发。对于数学和逻辑究竟能在编程世界里起多大作用，怀疑者们还在不断地提出各种质疑，而倡导此道的研究者们也在持续不断地工作。可以看到，他们的工作成果正在不断地被纳入越来越多的主要软件公司的开发过程，变成流行软件工具的有机组成部分。从另一个角度看，在流行的编程书籍中，也能越来越多地看到讨论状态、断言、前后条件、不变式、基于协约的编程等内容。这些趋势说明，作为一种复杂的智力劳动，由于其工作成果将变成当前和未来的工业化、信息化社会中所有基础设施的最关键支柱，编程和软件开发工作必将越来越强烈地关注其产品的正确性和可信任问题。本书作者在三十多年前的呼喊并没有过时，也不会被遗忘，他提出的想法和技术在未来软件开发中必定会起越来越重要的作用。原因无二，正如作者在另一处所言：“我早已对计算领域的实践活动有个总结：在那里乱搞的自由度太大，因此，数学的优美绝不是一种可有可无的奢侈，它关系到生命和死亡”。
本书出版于1976年，20世纪80年代曾被影印并在国内计算机科学界流传，当时书名被译为《程序设计训练》，但很奇怪的是没出版过中文译本。20世纪90年代后期，国内计算机领域开始迅猛发展，而这一经典著作却销声匿迹，不为人知，确实很令人遗憾。这次电子工业出版社引进本书是做了一件绝大的好事。我接手时，出版社曾计划以《编程的法则》为书名，我对此有疑。Dijkstra在本书最后专门讨论了一个科学（或其他）领域的形成，以及其参与者智力活动的情况和性质。本书序言作者（图灵奖获得者TonyHoare）将编程与音乐、诗词等领域相提并论，讨论其卓越成就者对后人的启迪和引领。作为一种智力活动的学习和实践者，既需要获取他人经验，也需要内省和自我总结，将其说成是学一些“法则”当然不妥。作为领域专家的Dijkstra虽然锋芒毕露，但其实他是一个谦虚的人，原书名用不定冠词“A”开头，表示这只是他认为在编程领域里有道理的一套智力修炼，未必就是终极和唯一的“那一套”。由于以《编程的一种修炼》作为中文书名很别扭，我选了目前这个名字，还好，它也没有强加于人的意味。翻译本书就像是在倾听作者缓缓道出其深邃的思考，感觉非常有趣并到处受到启发（虽然我原来已经看过几遍），但是也感到非常累。要想把这本书翻译好确实非常困难，术语是最简单的问题（但也颇费琢磨），更重要的是，既要准确反映原文的字面意思，还要尽可能反映作者的意图和想法。在此基础上还要尽量符合汉语的习惯，语言流畅并容易理解。要把本书译到满意，我觉得至少还需要一两年时间。但出版社不能等，因此，我只能把目前的版本呈献给读者。我当然要对书中的所有缺陷负责，并为这些缺陷表示歉意。裘宗燕
北京大学数学学院信息科学系