书名：编程的修炼
本书由人民邮电出版社发行数字版。版权所有，侵权必究。
您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。
我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。
如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。
著 ［荷兰］艾兹格·W. 迪杰斯特拉（Edsger W. Dijkstra）
译 裘宗燕
责任编辑 吴晋瑜
人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
网址 http://www.ptpress.com.cn
读者服务热线：(010)81055410
反盗版热线：(010)81055315
Authorized translation from the English language edition, entitled A Discipline of Programming, by Edsger W. Dijkstra, published by Pearson Education, Inc, publishing as Microsoft Press, Copyright © 1976.
All rights reserved. No part of this book may be reproduced or transmitted in any form or by any means, electronic or mechanical,including photocopying, recording or by any information storage retrieval system, without permission from Pearson Education, Inc.
CHINESE SIMPLIFIED language edition published by POSTS ＆ TELECOM PRESS Co.,LTD, Copyright © 2020.
本书中文简体版由Pearson Education,Inc授权人民邮电出版社出版。未经出版者书面许可，不得以任何方式或任何手段复制和抄袭本书内容。
本书封面贴有Pearson Education（培生教育出版集团）激光防伪标签，无标签者不得销售。
版权所有，侵权必究。
本书为图灵奖获得者Edsqer W. Dijkstra最重要的著作，也是编程领域里经典著作中的经典。作者基于其敏锐的洞察力和长期的实际编程经验，对基本顺序程序的描述和开发中的许多关键问题做了独到的总结和开发。书中讨论了基本顺序程序的本质特征、程序的描述和对程序行为（正确性）的推理，并通过从简单到复杂的一系列程序的思考和开发范例，阐释了基于严格的逻辑推理开发正确而可靠的程序的过程。
本书写于20世纪70年代后期，但其对于编程领域的技术开发，对于编程语言的发展和程序理论研究的深刻影响持续至今。本书值得每一个关注计算机科学技术的本质，冀求在程序和软件领域有长远发展的计算机工作者、教师和学生阅读。
图灵奖获得者Edsqer 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的更多贡献，读者可以参考介绍他的维基百科页和下面的纪念网页
http://www.utexas.edu/faculty/council/2002-2003/memorials/Dijkstra/dijkstra.html。
本书原名为A Discipline of Programming，是Dijkstra有关程序理论和编程技术的最重要的著作。本书是一本非常独特的编程技术专著。
首先，常见编程教科书都要选一种流行语言作为示例的载体，而本书却没用任何可以由计算机执行的语言，所有示例程序都没运行过，但它们的正确性却有保证。作者也没采用“伪代码”，因为伪代码会带来不可避免的歧义性，也无法作为严格的形式化推理的基础。书中的程序采用作者自己设计的一种小语言描述，该语言反映了顺序（非并行）编程语言最本质的性质，还有许多重要特性将在下面讨论。
其次，书中给出了一大批编程实例，采用的方式与其他书籍大相径庭。作者在给出要解决问题的描述之后，总是非常详尽地描述了从问题出发，通过细致的分析思考，逐步深入工作，最后做出所需程序的整个过程。通过这种过程，作者反复展示了在编程中应该怎样思考问题，提出合适的概念，规划处理流程，通过自上而下的设计和开发逐步做出程序框架，分析、解决遇到的具体问题，填充各部分细节，直至做出完整的程序。作者还特别强调了“关注点分离”的重要性，强调在一个阶段解决一个问题。在一些复杂程序的开发完成后，还给出了细致的回顾性分析。作者在书中特别注意开发过程的真实性，并不回避提出过的错误概念和走过的弯路。在其他编程著作中，很难看到这种真实的实践。
虽然上面两点已明显表现出本书的与众不同，但它们还不是本书最重要的特点。Dijsktra在本书中最重要的关注点是程序正确性，是关于程序及其意义的“数学推导”和“证明”。作者在前言中写到，我们的目标应该是“做出高度可信的程序，而不仅是……一些胡乱涂抹出来的，……，随时准备被第一个反例推翻的程序文本”。他认为编程工作的目标应该是直接得到正确程序，而不是得到一些“大致能用”的代码。令人遗憾的是，目前的编程工作大都并不如作者所愿，人们在开发中反复测试开发出的半成品或成品，找出其中缺陷并予以更正，直至其作品或工作过程满足了某些外在“评价标准”，或由于时间、金钱、人力限制而不得不强行结束。到了工作完成时，开发者们也不敢断定给出的就是所需要的“那个”程序。
有关如何开发出正确的程序，书中强调了许多方面的问题。首先是大家熟悉的问题分析，在着手编程前先把问题弄清楚，写出尽可能严格的定义，这件事怎么强调都不过分。书中有许多具体示例可供参考。更重要的是，Dijkstra认为保证程序正确的主要武器是数学意义上的严格描述和推导。他在本书中给出了一大批示例，展示了严格推导在编程领域里的威力。Dijkstra认为程序语言（无论哪种语言）本身就是一种形式化的严格定义的描述形式，用它们写出的程序具有确切的语义。用具体计算机运行程序就是实现其语义，但程序的语义并不依赖于运行它的计算机，可以独立地思考和表达。从这种认识出发，Dijkstra基于状态和断言的概念提出了最弱前条件的思想，用谓词转换器作为程序语义的落脚点。由于常规语言不能完美地支持这种想法，他自己开发了一种语言，其中最重要的新概念是卫式命令，选择和重复结构都基于卫式命令定义。Dijkstra用实例展示了通过严格推导，直接开发出正确程序的过程，展示了不变式、最弱前条件、谓词转换器等重要概念和严格的逻辑推理怎样在程序开发中发挥作用，帮助开发者（这里的实践者是Dijkstra本人）理清程序的线索，逐步推导出正确的程序。作者提出的最弱前条件、谓词转换器、非确定性等概念，对程序理论和实践的发展都产生了重要影响。
当然，并不是每个人都赞同Dijkstra的想法，即使在未来世界中，也未必所有程序都采用他的理想主义的方式开发。对于数学和逻辑究竟能在编程世界里起多大作用，怀疑者们还在不断地提出质疑，而信仰此道的研究者们也一直在努力工作，在有关领域的研究取得了许多成果，这些成果正在不断被纳入越来越多的重要软件公司的开发过程，变成流行软件工具的有机组成部分。另一方面，在流行的专业编程书籍中，我们也越来越多地看到有关状态、断言、前后条件、不变式、基于协约的编程等内容的讨论。这些趋势说明，编程作为一种复杂的智力劳动，由于许多工作成果将变成当前和未来的工业化、信息化社会中所有基础设施中最关键的支柱，人们必将越来越强烈地关注其产品的正确性和可信问题。本书作者在三十多年前的呼喊并没有过时，也不会被遗忘，他提出的想法和技术在未来软件开发中必定会起到越来越重要的作用。原因无二，正如作者在另一处所言，“我早已对计算领域的实践活动有个总结：在那里乱搞的自由度太大，因此，数学的优美绝不是可有可无的奢侈，它关系到生命和死亡”。
原著出版于1976年，20世纪80年代曾被影印并在国内计算机科学界流传，当时书名被译为《程序设计训练》。但是很奇怪，这本书没出版过中文译本。20世纪90年代后期以来，国内计算机领域迅猛发展，而这一经典却销声匿迹不为人知，非常令人遗憾。电子工业出版社引进本书，是做了一件绝大的好事。我接手时，出版社曾计划以《编程的法则》为书名，我对此有疑。Dijkstra在本书最后专门讨论了一个科学（或其他）领域的形成，及其参与者的智力活动的情况和性质。本书序的作者（图灵奖获得者Tony Hoare）将编程与音乐、诗词等领域相提并论，讨论一个领域中的卓越成就者对后人的启迪和引领。作为一种智力活动的学习和实践者，既需要获取他人经验，也需要内省和自我总结，把这种获得说成是学习“法则”，当然不妥。作为领域专家的Dijkstra虽然锋芒毕露，但其实也是一个谦虚的人。原书名用不定冠词“A”开头，表示这只是他认为的在编程领域里有道理的一套智力修炼方法，未必就是终极和唯一的“那一套”。由于以《编程的一种修炼》作为中文书名很别扭，我选了目前这个名字，还好，它也没有强加于人的意味。
翻译本书，就像是在倾听作者缓缓道出的深邃思考，非常有趣，不断地受到启发（虽然我原来已经看过几遍），但也非常累。想把这本书翻译好，确实很困难，术语是最简单的问题（但也颇费琢磨），更重要的是既要准确反映原文的字面意思，还要尽可能反映作者的意图和想法。在此基础上还要尽量符合汉语的习惯，使语言流畅容易理解。要把本书译到满意，我觉得至少还需要一两年时间。但是出版社不能等，因此，我只能把目前的版本呈献给读者。我当然要对书中所有的缺陷负责，并对它们的存在表示歉意。我将在www.math.pku.edu.cn/teachers/qiuzy/为本书建一个专门页面，做些后续的弥补工作。最后，我要衷心感谢出版社的编辑，他们通过认真工作找出了译文里的一些错误。
裘宗燕
北京大学数学学院信息科学系
由于一些情况，本书将由人民邮电出版社重新出版。作为译者，我首先对出版社和陈冀康编辑表示感谢，他们的付出保证了这本书能在国内持续存在，使一批计算机工作者可以从中获益。为了这次出版，我重新检查了全部译文，做了一些力所能及的修改。希望修改后的版本意义更清晰准确，能更好地满足读者学习的需要。
译者注，2020年
在诗歌、音乐、艺术和科学等历史更悠久的智力领域，历史学家们都把颂词献给那里最卓越的实践者，因为他们的成就拓展了其赞美者的体验和理解，也启迪和提升了其追随者们的才华。他们的创新基于通过实践积累的卓越技艺，结合了他们对领域基础理论的敏锐洞见。在很多情况下，他们的影响还由于其广博的文化积淀，以及他们在表达上的力量和透彻性，而得到了进一步提升。
在本书中，作者以其惯用的文字风格，详尽描述了他对计算机编程的基本性质的激进的新见解。基于这些见解，作者开发了一套编程方法以及与之适应的记法工具，并用一大批优雅而且高效的实例展示和检验了它们。本书注定会成为在计算机编程的智力领域的发展中最杰出的成就之一。
C.A.R.Hoare
很久以来，我一直想写一本基本上是按照本书线索的书，原因是：一方面，我知道程序可以有迷人的形态和深刻的逻辑之美；另一方面，我又不得不接受这样的事实，即绝大部分程序是用一种只适合机器执行的方式表达的，完全没有美感，也不适合人来欣赏。这种不满意还有第二个原因，那就是，各种算法通常总是以一种完成了的产品形式发表，而在设计过程中起着最重要作用的，以及成为证明所完成程序的最终形式的正当性的各种思考的主要部分，通常都完全没有提及。我最初的想法是以读者能欣赏到它们之美的方式发表一系列优美的算法。对于如何做这件事，我当时的想法是描述一些实际的和想象中的设计过程，每个过程最终都得到了所需的程序。我在一定程度上实现了最初的想法。作为这本专著的核心部分是一系列章节，每一章处理并解决一个新问题。但在另一方面，最终写出的这本书与我早前的期望又有很大不同。由于我特别希望用一种自然而且方便的方式来展现这些内容，由于这种追求而强加给自己的任务变成了一种重要责任。我将永远为自己完成了这一工作而感到欣慰。
在开始写一本像本书这样的著作时，人们立刻会面临一个问题：“我准备使用哪一种编程语言？”而实际上这并不仅仅是一个有关展示形式的问题！任何工具的一个最重要的（而且也是最难琢磨的）方面，就是它对被训练而且将使用它的人们的工作习惯的影响，这种影响——无论我们是否喜欢——是对我们的思考习惯的影响。在尽可能地分析了这种影响的各方面情况之后，我得出了一个结论：没有一种现存的编程语言，也没有一个它们的子集适合我的目标。另外，我也知道自己完全没有为设计一种新编程语言做好准备，因此，我曾发誓在随后的五年里不做这件事。而且我有一种非常清晰的感觉：这个时期还没有过去！（但还有一个前提，就是除了其他事情外，这本书必须要写。）我试着化解这一矛盾的方式是设计了一个适合我的具体目标的小型语言，只做出一些看起来不可能避免而且其正当性也得到了充分证实的承诺。
这种犹豫和自我强加的约束，如果被错误地理解，有可能使本书的许多潜在读者对它感到失望。那些把编程的困难等同于老练地利用精细而花哨的称为“高级编程语言”的工具，或者（更糟糕的！）“编程系统”的困难的人们，注定会对这本书不满意。如果因为我忽略了所有那些诱人的花哨玩意儿而使他们感到受了骗，我只能回答说：“你真能确定所有那些诱人的花哨玩意儿，以及那些你所谓‘强大的’编程语言的美妙功能确实属于解的集合，而不属于问题的集合吗？”我只是希望，即便用的是一种小型语言，他们也能看看这本书。在读完之后，他们有可能同意，虽然没有那些诱人的花哨玩意儿，仍然有非常丰富的问题需要讨论。因此，是否一开始就介绍大量的花哨玩意儿，确实是应该质疑的。还有，对于那些明显对编程语言的设计有兴趣的读者，我只能表示歉意。正如我已经做的那样，我没办法在这个问题上做出更清晰的事情。但在另一方面，我也希望随着时间的推移，这一专著会对他们有所启示，而且能帮助他们避免一些因为没有读过它而有可能犯的错误。
在写作过程中——它持续不断地让我感到惊喜和激动——逐渐呈现的文本与我初始时头脑中的想象大不相同。我一开始设想以一种（易理解的）方式去展示程序的开发过程，带上比我在（引论）课程中更多一点的形式化设施，其中以直观方式介绍所使用的语义，有关正确性的论证采用通常的严格论述，手工编排，再加上有说服力的文字。在为更形式化的方法建立了必要的基础后，我得到了两个惊喜。第一个惊喜就是所谓的“谓词转换器”，作为我选用的工具，它提供了一种方法，使我们可以直接定义初始状态与最终状态之间的关系，并不需要参考程序实际执行中可能经历的中间状态。我对这种情况感到非常欣慰，因为这清晰地区分了程序员的两个主要关注点：数学的正确性（即程序是否定义了所需要的初始状态与最终状态之间的正确关系——谓词转换器是我们研究这一问题的一种形式化工具，研究中不需要考虑实际计算进程），以及工程上对于效率的关注（现在也很清楚，这件事只与实现有关）。这已经成为一种最有帮助的发现，因为同一个程序正文总是有两种相当互补的解释：它可以解释为一个谓词转换器的编码，这样做，看起来更适合我们的需要；它也可以解释为可执行代码，我宁愿把这种解释留给机器去做。第二个惊喜是，我能够想象到的最自然而且最系统化的“谓词转换器的编码”，在被看作“可执行代码”时，将要求一种非确定性的实现。有一段时间，我对于把非确定性引进单道编程感到不寒而栗（对于它给多道编程带来的复杂性，我知道得太多了！），直到我认识到，将程序正文解释为一个谓词转换器的编码有其自身的存在理由。（回顾往事，我们可以看到，过去提出的有关多道编程的许多问题并不是别的什么，只不过是不适当地过分强调了确定性的重要性而带来的后果。）我最终认识到，应该把非确定性看作正常情况，这样，确定性就将变成一种——并不非常有趣的——特例了。
在打好了有关的基础之后，我将所有时间都投入到想做的事情上，也就是说，去解决一系列问题。做这件事使我得到了未曾预料的快乐。与我以前的工作方式相比，形式化设施使我能更稳固地把握所做的工作。我很高兴地发现，明确地关注终止性问题能带来许多富于启发性的看法，以至于使我觉得，偏向于考虑部分正确性的观点如此常见是非常令人遗憾的。然而，最大的快乐是，对于大部分我原来做过的问题，这次都得到了更漂亮的解答！这是非常令人鼓舞的事情，我将它看作一种指示剂，说明我开发的方法确实提升了我的编程能力。
应该怎样学习这部专著呢？我能给出的最佳建议就是，一旦看完了问题的描述，就停止阅读，转去试着自己解决它。尝试自己解决问题，是你能自己认识和评价问题的困难程度的唯一方法，它也使你有机会去比较你的解和我给出的解，还给你得到满足的机会，即看到你给出的解比我给出的更好。这里还是要先说一下，当你发现这里的内容远不是那么容易读的时候，请不要沮丧。研读过这部专著的人都觉得它的内容通常是很难的（但收获也同样很多！）。然而，每次我们分析遇到的困难时，得到的结论都是：应该把这种困难“归咎于”实际讨论的问题，而不是有关的文字本身（即它的表达方式）。这一认识的寓意是，一个非平凡的算法本身就是非平凡的，与论证其设计的正确性的思考相比，在一种编程语言里做出的算法描述是高度紧凑的，不应该受最后的程序正文长度的误导！我的一个助理给出的建议——也是我忠实地采纳的，因为它可以很有价值——是让学生分为一些小组一起学习这本书。（在这里，我必须对书中正文的“困难程度”加一点附带说明。我本人科学生涯中的许多年一直在致力于弄清楚程序员的任务，目标是设法使它成为智力上可以管理的工作。从事了多年的这种澄清性的工作之后，我感到很好玩，也很吃惊地发现，反复出现的回馈是“我把编程弄得更困难了”。但困难始终在那里，只有将其变为明显可见的，我们才有希望设计出具有高度信任水平的程序，而不仅是做出了一些“胡乱涂抹出的代码”，即那种基于一些根本无法得到支持的假设，随时准备被第一个反例推翻的程序正文。不用说，本书的任何一个程序都没有在机器上测试过。）
我还要给读者解释为什么我把这里的小型语言弄得这么小，小到没有包含过程和递归。由于任何一点儿语言扩充都会给这本书增加几章内容，并因此使它相应地变得更贵，所以对于大部分可能的扩充（例如多道编程），我都不需要更多的解释。而过程总是在编程中居于核心地位，递归对于计算科学而言也是最受学术界重视的标志，因此，我必须给出一些解释。
首先，这本专著不是为新手写的，因此，我期望本书的读者熟悉那些概念。其次，本书不是某种特殊编程语言的引论教材，缺乏这些结构和使用它们的例子，不会被解释为我不能或者不希望使用它们，也不会被作为是建议，希望那些有能力使用那些结构的人不要用它们。这里的关键是，我觉得在传递本书想给出的信息时并不需要那些结构。我想讨论的是，应该非常仔细地分离各种关注，以及为什么从各个方面看这种做法都是设计出高质量程序的最重要的基础。以这里的小型语言作为一种有节制的工具，对于给出各种非平凡而且非常令人满意的设计而言，已经能给我们足够的行动自由了。
前面的解释，虽然已经很充分，但还不是故事的全部。实际上，我觉得把重复结构本身作为语言中的一种结构是不得已的事情，因为在我看来这种表达方式是有些过度了。当编程语言诞生时，其赋值语句的“动态”性质看起来与传统数学的“静态”性质很不吻合。由于没有合适的理论，数学家很不喜欢它。而且，由于重复结构是需要变量赋值的最根本原因，数学家也很不喜欢重复结构。当人们开发出没有赋值，也没有重复结构的编程语言——例如，纯LISP——时，许多人都大大地松了一口气。这使他们又可以回到自己熟悉的场地，看到了一点希望的微光：有可能将编程变成一种具有坚实的而且得到广泛尊重的数学基础的活动。（直到目前，在更偏向于理论的计算科学家中仍然有一种广泛存在的感觉，认为递归程序比基于重复结构的程序“来得更自然”。）
另一种角度，是为“重复结构”和“给变量赋值”提供一种可靠的而且可用的数学基础，为此，我们又必须等待另一个十年。正如在这部专著里阐释的，这方面研究的成果是，一个重复结构的语义可以基于谓词之间的一个递归关系定义，而一个广义递归的语义定义则需要基于谓词转换器之间的一个递归关系。这一点很清楚地说明，为什么我认为广义递归的复杂性比重复结构高一个数量级。因此，我很害怕看到把下面这样重复结构的语义：
定义为调用
其中的whiledo是如下定义的递归过程（用ALGOL 60的语法描述）：
虽然这样做不错，但它却伤到我了，因为我不喜欢用一把大锤去敲一个鸡蛋，无论用大锤做这件事是多么有效。对于在20世纪60年代涉足这一问题的那一代理论计算科学家来说，上面的定义常常不仅是“自然的那一个”，而且是“真正的那一个”。应该看到下面的事实：如果不诉诸重复的概念，我们甚至无法定义图灵机能够做什么。这说明需要重新做一些权衡。
对于没有参考文献的问题，我不准备解释，也不表示歉意。
致谢：下列人士对本书有直接影响，他们或者是就本书的拟议中的内容提出过期望，或是为本书（或其中一些部分）写过评论，他们是C. Bron、R.M. Burstall、W.H.J. Feijen、C.A.R. Hoare、D.E. Knuth、M. Rem、J.C. Reynolds、D.T. Ross、C.S. Scholten、G. Seegmüller、N. Wirth和M. Woodger。对于他们的合作，我很荣幸能在此表示谢意。我还要特别感谢Burroughs公司为我提供了机会和各方面的便利，感谢我妻子不断的支持和鼓励。
艾兹格·W.迪杰斯特拉
荷兰纽南
本书由异步社区出品，社区（https://www.epubit.com/）为您提供相关资源和后续服务。
作者和编辑尽最大努力来确保书中内容的准确性，但难免会存在疏漏。欢迎您将发现的问题反馈给我们，帮助我们提升图书的质量。
当您发现错误时，请登录异步社区，按书名搜索，进入本书页面，单击“提交勘误”，输入勘误信息，单击“提交”按钮即可。本书的作者和编辑会对您提交的勘误进行审核，确认并接受后，将赠予您异步社区的100积分（积分可用于在异步社区兑换优惠券、样书或奖品）。
我们的联系邮箱是contact@epubit.com.cn。
如果您对本书有任何疑问或建议，请您发邮件给我们，并请在邮件标题中注明本书书名，以便我们更高效地做出反馈。
如果您有兴趣出版图书、录制教学视频，或者参与图书翻译、技术审校等工作，可以发邮件给我们；有意出版图书的作者也可以到异步社区在线提交投稿（直接访问www.epubit.com/selfpublish/submission即可）。
如果您来自学校、培训机构或企业，想批量购买本书或异步社区出版的其他图书，也可以发邮件给我们。
如果您在网上发现有针对异步社区出品图书的各种形式的盗版行为，包括对图书全部或部分内容的非授权传播，请您将怀疑有侵权行为的链接发邮件给我们。您的这一举动是对作者权益的保护，也是我们持续为广大读者提供有价值的内容的动力之源。
“异步社区”是人民邮电出版社旗下IT专业图书社区，致力于出版精品IT技术图书和相关学习产品，为作译者提供优质出版服务。异步社区创办于2015年8月，提供大量精品IT技术图书和电子书，以及高品质技术文章和视频课程。更多详情请访问异步社区官网https://www.epubit.com。
“异步图书”是由异步社区编辑团队策划出版的精品IT专业图书的品牌，依托于人民邮电出版社近30年的计算机图书出版积累和专业编辑团队，相关图书在封面上印有异步图书的LOGO。异步图书的出版领域包括软件开发、大数据、AI、测试、前端、网络技术等。
异步社区
微信服务号
执行抽象对于“算法”的整体概念而言如此基础，以至于人们经常默认它而并不提及。执行抽象的作用是使不同计算可以相互映射，或者换句话说，它使我们可以在思考中把握住一个特定的计算，采用的方式是将其看作一大类不同计算中的一个成员。这就使我们有可能抽象掉这一类计算中各成员的相互差异，以便能基于这个类的整体定义，写出对其所有成员都适用的断言，从而也把握了我们希望考虑那一个特定的计算。
为了把我们所说的“一个计算”的意义讲透，我先描述一种非计算的设备，它“产生出”（在此避免使用术语“计算出”），例如，111和259的最大公因子。这一设备由两张纸板组成，一张放在另一张的上面，位于上面的一张上写着“GCD(111, 259) =”，这是要求该设备产生出一个解答。我们拿起上面的纸板，并将其放在下面一张的左边，立刻就能从下面纸板读出“37”。
这一卡片设备的最大优点是简单，但它的两个缺陷却使这一优点黯然失色，其中一个是主要的，而另一个是次要的。其次要缺陷是，虽然这一设备确实能产生出111和259的最大公因子，但除此之外完全无用。而其主要缺陷则在于，无论多么仔细地考察这一设备的构造，我们对它确实能产生出正确结果的信心只能基于我们对其制造者的信任。实际上，其制造者完全可能出错，或是在设计该设备的时候，或者是在专门为我们制造这一具体设备的时候。
为了克服上面的次要质疑，我们可以考虑一部巨型的纸板设备，其形式是一个很大的二维矩形网格，具有满足0 ＜ x 
500，0 ＜ y 500的整数坐标x和y的网格点。对所有具有正坐标的点 (x, y)，即除去位于坐标轴上那些点之外，在每个点写上GCD(x, y) 的值。这样就是构造了一个包含250,000个项的二维表格。从可用性的观点看，这是一个很大的改进：原来的设备只能为一对整数提供最大公因子，现在我们有了一台能为250,000对不同整数提供最大公因子的“设备”。何其妙哉！但是我们却不能太过兴奋，因为还有前面提出的第二个缺陷，即“我们怎么能相信这个设备给出的是正确回答呢？”这一质疑现在也被放大了250,000倍！我们必须250,000倍地信任该设备的制造者！
由于这些情况，让我们考虑另一种设备。其形式仍是带有同样网格的纸板，但只在坐标轴上写了从1到500的数。我们还在纸板上画出下面直线：
1．竖线（对应于等式x = 常数）；
2．横线（对应于等式y = 常数）；
3．对角斜线（对应于等式x + y = 常数）；
4．“答案线”（对应于等式x = y）。
在操作这一机器时，我们应该按下面的指令工作（“按下面的规则玩这个游戏”）。当需要找两个值X和Y的最大公因子时，我们先把（机器制造者提供的）一颗小石子放在坐标点x = X和y = Y处。只要石子没有在答案线上，我们就考虑满足下面要求的最小等腰直角三角形：其直角位于石子处，一个锐角在一条坐标轴上。该三角形可能在石子的下面或左边，由于石子不在答案线上，因此这个三角形只能有一个锐角在坐标轴上。这时我们就把石子移到对应该三角形另一个锐角的网格点上。只要石子没有移到答案线，就重复进行上述操作；如果它到达了答案线，这时的x-坐标（或者y-坐标）就是所需要的答案。
如果我们想让自己相信这一机器总能产生正确答案，该怎么办呢？第一，如果 (x, y) 是任意不在答案线上的249,500个点之一，而 (x', y') 是按上面游戏规则将石子移到的下一个点，那么就有或者x' = x且y' = y – x，或者x' = x – y且y' = y。不难证明，GCD(x, y) = GCD(x', y')。最重要的是，这一论断适用于所有249,500个可能步骤中的每一个！第二点也不困难，我们可以证明对任何一个点 (x, y)，如果x = y，也就是说，对答案线上的那500个点，我们都有GCD(x, y) = x。最重要的情况同样是，第二个论断对答案线上500个点中的每一个都完全适用。第三点仍然不困难，我们还能证明对任意初始点 (X, Y )，经过有限步，石子就能被移到答案线上。而且，最重要的观察是，这一论断对于250,000个初始位置中的每一个都适用。这三项简单论断的长度与网格点的个数无关，它们很清晰地表现出数学有可能为我们做的事情。用 (x, y) 表示任意一次这种游戏开始时石子的位置 (X, Y )，上面第一个定理使我们可以得出结论，在这一游戏过程中，关系
GCD(x, y) = GCD(X, Y)
总是成立的，或者按行话说就是“保持不变”。第二个定理告诉我们，可以将石子最终位置的x坐标当作所需要的结果；而第三个定理告诉我们最终位置的存在性，也就是说，我们能在有限的步骤内到达那里。这样，我们就完成了对这种可以称为是“我们的抽象机器”的设备的分析。
我们的下一个任务，是验证由设备制造者提供的这种纸板确实是一种良好的模型。为此，我们必须检查沿着坐标轴写数的过程，并确认各种直线都可以正确画出。这件事有点别扭，因为需要检查的事项数目与N成正比，这里的N（在上面的例子中是500）对应于正方形一边的长度。但这毕竟要好于N2，即在这里可能出现的不同计算的数目。
另一种机器也可能工作。它不是一块大纸板，而是两个能保存9位二进制代码的寄存器，每个都足以保存0～500的任一个整数。我们用一个寄存器保存“当前石子位置”的x-坐标值，用另一个保存其y-坐标值。与移动石子对应的是将一个寄存器的值减去另一寄存器的内容。我们可以自己做这种算术，如果有机器帮我们做当然更好。这时，如果我们要让自己相信答案，就要让自己相信机器能正确完成数值的比较和减法。在一个更小尺度上历史又出现了重复：我们只需为所有事情做一次推导。也就是说，为所有n位整数对推导出有关减法器的等式，而后证明物理机器是这种二进制位减法器的良好模型，能使我们满意。
如果这里用的是并行减法器，所涉及的验证数目正比于部件及其相互间交互数量，即正比于n = log2N。在顺序机器上相对于部件数的时间代价更大一点。
现在让我试着阐释一下从这个例子中得到的启示，至少是对我自己的启发。
我们不是去考虑如何计算GCD(111, 259) 这一个别问题，而是将其推广，把它看作如何计算GCD(X, Y) 这一更广泛的问题类的具体实例。值得指出的是，我们完全可以按照不同方式去推广计算GCD(111, 259) 的问题。例如，可以把这项工作看作下面这个同样很广泛问题的实例：计算GCD(111, 259)、SCM(111, 259)、111 × 259、111 + 259、111/259、111 – 259、111259、公元前259年的第111天，等等。这样考虑实际上是要求做一个“111和259处理器”，而要令它产生出原来考虑的那个答案，我们应该给出需求“计算GCD”作为其输入。而上面提出的则是做一台“GCD计算机”，将数对“111，259”作为输入，它就产生出前面问题的答案。这是两台非常不同的机器！
换一种说法，如果被要求产生出一个或几个结果，通常的方法是推广这个问题，将这些结果看作一个更广泛问题的具体实例。把任何问题都说成是另一个更广泛问题的特殊实例，显然不是一种好想法！如果我们希望按这种思路前进，就要承担两项义务。
1．我们必须在如何推广上采用特殊的选择。也就是说，需要仔细考虑所选的更广泛的问题类，并明确地定义它，因为随后的论断要能适用于整个类。
2．我们必须选择（你也可以称之为“发明”）一种推广，它真的能对我们的目标有所帮助。
对前面这个例子，我当然更喜欢“GCD计算机”，而不是“111和259处理器”。对这两种机器做一个比较，我们有可能得到一些线索，帮助说明哪些特点可能使一个推广“对我们的目标有帮助”。一台可以根据各种需求产生111和259的各种可笑函数值作为结果的机器，随着这种汇集中的函数个数增加，其验证也会变得越来越困难。这与我们“GCD计算机”的情况形成了鲜明对比。
如果把GCD计算机做成一个包含250,000个项的表，每个项都是直接给出答案，那么它的情况也同样糟糕。前面机器的独特之处就在于它能通过一组很简洁的“游戏规则”给出，只要按这组规则行事，就能产生出所需答案。
这里最大的收获在于，只需要给出一套适用于这些规则的论证，就能证明一些对任何具体的游戏都适用的重要断言。在这里我们也付出了一些代价：把这些规则应用于250,000个特定情况之一时，我们不能“立刻”得到结果，每次游戏时都必须按照规则一步步地做。
我们能给出一套简洁规则来形式化这一游戏，使得通过一套论证就能得出有关所有可能的具体游戏的结论，这一事实还与对250,000个网格点的系统化安排有紧密的内在联系。如果纸板被设计为无特定形状的混沌式的、没有任何系统化结构的点云，我们就会变得无能为力了。然而，我们确实可以把那颗石子切成两颗“半拉石子”，把一颗半拉石子下移，直至它遇到横坐标轴，把另一颗半拉石子左移，直至它碰到纵坐标轴。这时操作的就不再是具有250,000个可能位置的一颗石子，而是两颗半拉石子，每个只有500个可能位置，总计1000个可能位置。我们前面的那250,000个可能状态，可以通过一颗半拉石子的500个可能位置和另一颗半拉石子的500个可能位置的组合构造出来：未切分石子的可能位置的个数，等于切分后的两颗半拉石子的可能位置之乘积。按行话说就是，“整个状态空间是变量x和y的状态空间的笛卡儿积”。
将一颗石子在二维空间中的位置自由度替换为两颗半拉石子各自在一维空间里的位置自由度，这种替换的自由选择在前面提出的两个寄存器机器中也得到体现。从技术的观点看，这种替换很有吸引力：你只需构造能区分500种不同情况（不同“值”）的寄存器，组合起两个这种寄存器，所有不同情况的数目就平方了。这种乘法规则对我们很有帮助：只需用不多个组件，每个组件只有不多的可能状态，就可以模拟巨大数量的可能状态。通过增加这样的组件，状态空间呈指数式增长。当然还要记住，只有在保证仍然能非常简洁地对整个装置进行论证的前提下，我们才能这样做。如果论证的时间也呈指数式地增长，这样设计的机器就毫无价值了。
注 一项迄今已有10个世纪以上历史的发明可以看作上面讨论的完美具现：十进制数系统！该系统确实具有令人惊叹的性质，即所需数字个数的增长正比于可以表示的数的对数。二进制数系统也就是你忘掉每只手有5个手指之后得到的东西。
上面我们只考虑了许多问题的一个方面，即最大可能的石子位置（= 可能状态）。还有一个类似的乘法性质，即可以按照我们的规则去做的不同游戏（= 计算）的最大个数，一个游戏恰好对应着一种初始位置。我们有关游戏的规则是非常一般的，它能应用于任何初始状态。我们还强调游戏规则需要一种简洁的有关正当性的论证，这实际上也意味着游戏规则本身必须非常简洁。对我们的示例，这件事是通过下面的方式做到的：这里不是简单地列举出“做这个，做那个”，我们给出游戏规则的方式是给出几条执行“一步动作”的规则，同时还给出了一种准则，来判断是否还要再执行“下一步动作”。（也就是说，这种动作步必须反复执行，直至到达一个状态，这种动作步在那里不再有定义。）换句话说，通过反复应用同一组“子规则”，就可以解决任何一个具体游戏。
这是一种威力强大的机制。一个算法具现了一类计算的一个设计，在其控制下可以呈现出这些计算。这里做的是一个“动作步”的有条件反复，隶属于这个类的不同具体计算，在长度上可能有很大差异。这也解释了为什么一个很短的算法有可能导致一台机器繁忙很长一段时间。换个角度，我们也可以将它看作需要极端快速的机器的第一个理由。
如果想象着欧几里得正在背后看着我写这一章，那将是多么迷人的事情啊。
在第0章里，我非形式地描述了计算两个（不太大的）正整数的最大公因子的几种不同的“机器”设计。其中一部机器采用在纸板上移动石子的方式；另一部机器基于两颗半拉石子，而且它们都在坐标轴上移动；最后一部基于两个寄存器，每个里面可以保存一个（直至某个上限的）整数值。从物理上说，这三台“机器”大相径庭；而从数学上看，它们却很类似。做出这一论断的主要原因是，三者都能计算最大公因子，这是三者的共性。这三台机器只不过是同样一组“游戏规则”的不同具体实现，而实际上，这组规则才是一项发明的核心，该发明就是大名鼎鼎的“欧几里得算法”。
在前一章里，欧几里得算法是用一种相当非形式化的方式描述的。有人会提出，由于与之对应的可能计算的数目如此之大，因此，我们必须要有一个关于其正确性的证明。如果一个算法只是以非形式化的方式给出，它就不容易作为一种形式化处理的对象。为了形式化地处理，我们就需要用某种适当的形式化的记法来做算法的描述。
这样一种形式化记述技术的可能优势有许多方面。任何记述技术都蕴涵着一个事实：它所实际表述的任何东西都是它有可能描述的那个对象集合（通常是一个无穷集合）的一个特定成员。我们的记述技术当然应该能给出欧几里得算法的一个优雅而简洁的描述，而一旦做好了这件事，也就是把它表示成了一个包含各种算法的巨大的类中的一个成员。而在描述该类中的其他算法时，我们可能期望发现自己所用的记述技术的一些更有趣的应用。对于欧几里得算法，可能会有人说因为它如此简单，用一个非形式化的描述就能对付了。形式化记法的威力应该表现在一些没有它就绝不可能做到的成就方面。
形式化记述技术的第二个优势是，它使我们有可能把算法作为一种数学对象来研究，算法的形式化描述将成为我们的智力收获的抓手，使我们能证明一些有关算法类的定理，例如，由于算法所采用的描述而使之共有的一些结构性的性质。
最后，这样一种记述技术将使我们能毫无歧义地定义算法，这样，给定了用它描述的一个算法，并给定一组实际参数（输入），有关与之对应的答案（输出）应该是什么，将没有任何疑义或者非确定性。可以断言，相应的计算完全可以用一部自动机器完成：给它该算法（的形式化描述）和相应的实际参数，它就能产生出相应的答案，完全不需要进一步的人工干预。一种能对付这种相互呼应的算法和实际参数的自动机器已经造出来了，它就是人们说的“自动计算机”。为能在计算机上自动执行而写出的算法称为“程序”，而自20世纪50年代后期以来，用于写程序的形式化记述技术就被称为“编程语言”。（与程序的记述技术有关的术语“语言”的引入，已经受到多方面的关注。一方面，现有的语言理论为相关讨论提供了一种自然的框架和一套很有用的术语，如“文法”“语法”“语义”等。另一方面，我们也必须注意到，与现存的（现在大家都说的）“自然语言”的类似性也造成了许多误导，因为各种自然语言，无论怎样做形式化，其弱点和威力都来自它们的非明确性和非精确性。）
按照历史的观点，上述最后一个方面，即各种编程语言可以用作指挥现有的自动计算机的媒介，这个事实已经在很长时期里成为它们最重要的属性。现有的自动计算机执行以某种特定语言写出的程序的效率，也成为评判该语言的质量的最重要标准。这种情况导致了一个令人遗憾的后果：不难看到，现有计算机的许多很反常的特性都被忠实地反映到编程语言里，为此付出的代价是，用这样一个语言描述的程序是很难用智力去把握的。（实际上，即使没有这种情况，编程工作也已经非常困难了！）在下面将要提出的方法中，我们将试着重新考虑这里的利弊权衡。按我们的认识，写出的程序需要由一台计算机实际执行，只是由于偶然性而导致的一种情况，它不应该居于我们考虑问题的中心。（在最近的一本培养PL/I程序员的教材里，可以看到作者强烈建议尽可能避免过程调用，理由是“它们会大大影响程序的效率”。过程是PL/I中描述结构的最重要的工具，上述建议实在太可怕了，以至于我完全无法把这本书看作真的能“用于教育”。如果你确信过程是一种有用的概念，而在你的工作环境中，过程机制的实现带来的开销却令人难以忍受，那么应该诅咒的是那些不适当的实现，而不应该把它们的表现作为一种标准！这方面的权衡确实应该重新做！）
我把一种编程语言看作一种工作媒介，用于描述（可能非常复杂的）抽象机制。正如在第0章里可以看到的，算法最突出的优点，就在于对它们能做出非常简洁的论证。我们对于有关机制的信念也是基于这个事实。如果失去了这种简洁性，算法就失去了其很大一部分意义（存在的权利），因此，我们将把保持这种简洁性作为始终如一的目标。我们对编程语言的选择，也将直面这一目标。
