本书将演绎方法应用于程序设计，讨论程序与保证它们能正确工作的抽象数学理论之间的联系。书中把理论的规程、基于这些理论写出的算法，以及描述算法性质的引理和定理一起呈现给读者。
追溯数学原理 探求编程原本
STL之父力作，C++之父鼎力推荐
北大数学学院裘宗燕教授倾情献译
编程原本
Elements of Programming
（美）Alexander Stepanov Paul McJones 著 裘宗燕 译
封底：
“要是问一位机械、建筑或电子工程师，如果不依靠坚实的数学基础，他们能走多远。他们会告诉你‘走不了多远’。而所谓的软件工程师在实践其技能时，却常常对他们所做工作的数学基础知之甚少，甚至一无所知。同时我们也很奇怪为什么软件由于不能按时发布并充斥错误而声名狼藉，而其他工程师却能按时完成其桥梁、汽车、各种电子装置等，而且缺陷很少。本书就是想纠正这种不平衡现象。我在Adobe的高级开发团队的成员们，但凡参加了基于同样材料的课程，都觉得付出的时间获益匪浅。初看可能觉得这种高度技术性的文字只是为计算机科学家写的，其实所有从事实际工作的软件工程师都应该来读。”
—— Martin Newell，Adobe 院士
“本书包含一些我所见过的最美的代码。”
—— Bjarne Stroustrup，C++ 设计者
“我很高兴看到Alex课程的内容。担任Silicon Graphics的CTO时，我曾大力支持这一课程的开发和教授，现在这本书已经能被所有程序员阅读了。”
—— Forest Baskett，合伙人，New Enterprise Associates
“Paul的耐心和在体系结构方面的经验帮助把Alex的数学方法组织成为一套高度结构化的大厦——功德无量！”
—— Robert W. Taylor，Xerox PARC CSL和DEC系统研究中心创始人
前：
本书提供了有关编程的一种与众不同的理解。其主旨是，实际的编程也应像其他科学和工程领域一样基于坚实的数学基础。本书展示了在实际编程语言（如C++）中实现的算法如何在最一般的数学背景中操作。例如，如何定义快速求幂算法，使之能使用任何可交换运算。使用抽象算法将能得到更高效、可靠、安全和经济的软件。
这不是一本很容易读的书，它也不是能提升你的编程技能的秘诀和技巧汇编。本书的价值是更具根本性的，其终极目标是提升你对编程的洞察力。要想从中大获裨益，你需要从头到尾认真学习：阅读代码，证明引理，完成练习。最终，你将看到如何把这里讨论的演绎方法应用到你的程序中，保证你开发的软件部件能一起工作，并表现出它们所应该表现的行为。
书中给出的算法和需求针对某些被操作的类型。有关这些描述的代码（也可以通过Web得到）采用C++的一个小子集书写，这样做是为了让所有有经验的程序员都能理解。这个小子集可以看做一种特殊语言，是由Sean Parent和Bjarne Stroustrup一起设计的。
无论你是一位软件开发者，还是以编程作为一项重要活动的其他专业人员，或者是一名在校的学生，你都会逐渐理解本书的经验丰富的作者多年来一直在教授和阐释的道理：数学对于编程是绝好的东西，理论对于实际是绝好的东西。
后：
作者简介
Alexander Stepanov 于1967~1972年间在国立莫斯科大学学习数学，从1972年开始在苏联，1977年移民后继续在美国从事编程工作。他编写过操作系统、编程工具、编译器和各种程序库。他在程序设计基础方面的工作先后得到GE、Polytechnic、AT&T、惠普、SGI和Adobe的支持。1995年因C++标准模板库的设计获Dr. Dobb,s Journal的程序设计杰出贡献奖。
Paul McJones 于1967~1971年间在加州大学伯克利分校学习工程数学。从1967年开始介入程序设计，涉足的领域包括操作系统、程序设计环境、事务处理系统以及企业和客户应用系统等。他先后在加州大学、IBM、Xerox、Tandem、DEC和Adobe工作。1982年他与合作者一起因论文“The Recovery Manager of the System R Database Manager”获得ACM程序设计系统和语言论文奖。
译者简介
裘宗燕 北京大学数学学院信息科学系教授。长期从事计算机软件理论、形式化方法、程序设计和程序设计语言等方面的教学和研究工作。译著包括《程序设计实践》、《从规范出发的程序设计》、《C++语言的设计和演化》、《C++程序设计语言》、《计算机程序的构造和解释》、《程序设计语言——实践之路》等，著作有《从问题到程序——程序设计与C语言引论》等。
本书将演绎方法应用于程序设计,讨论程序与保证它们能正确工作的抽象数学理论之间的联系.书中把反映这些理论的规程(speci.cation),基于这些理论写出的算法,以及描述算法性质的引理和定理一起呈现给读者.这些算法在一种实际程序设计语言里的实现是本书的中心.虽然规程主要是供人阅读,但它们也应该(或者说必须)严格地与非形式化的、供机器使用的代码相结合,必须在通用的同时又是抽象而且精确的.
与在其他科学和工程领域里的情况一样,适合作为程序设计的基础的同样是演绎方法.演绎方法能帮助我们将复杂系统分解为一些具有特定数学行为的组件,而这种分解又是设计高效、可靠、安全和经济的软件的前提.
本书是想奉献给那些希望更深入地理解程序设计的人们,无论他们是专职软件开发人员,还是把程序设计看作其专业活动中一个重要组成部分的科学家或工程师.
本书编写的基本想法是让读者从头到尾完整阅读.读者只有通过阅读代码、证明引理、完成练习,才能真正理解书中的各方面材料.此外我们还建议了一些项目,其中有些是完全开放的.本书的内容很紧凑,认真的读者最终会看到书中各部分之间的联系,以及我们选择这些材料的理由.发现本书在体系结构方面的原理应该是读者的一个目标.
我们假定读者已经具有完成各种基本代数操作的能力. 1 还假定读者熟悉逻辑和集合论的基本术语,如普通本科生在离散数学课程中学习的内容.附录A总结了书中使用的各种记法.如果在一些特定的算法里需要某些抽象代数的概念,书中会给出相应的定义.我们还假定读者熟悉程序设计,理解计算机体系结构, 2 理解最基本的算法和数据结构. 3
1.有关基本代数知识,推荐Chrystal[1904].
我们选用C++,是因为它组合了强有力的抽象设施和基础机器的正确表示.4 这里只用了该语言的一个小子集,需求被写成程序里的结构化注释.我们希望不熟悉C++的读者也能阅读本书.附录B描述了书中使用的C++子集.5 在书中的任何地方,在需要区分数学记法和C++的地方,根据所用的字体、排版和上下文就能确定用的是哪种意义(是数学的还是C++的).虽然书中的许多概念和程序与STL(C++标准模板库)里的东西对应,但这里的一些设计决策是与STL不同的.书中还忽略了实际程序库(如STL)必须考虑和处理的许多问题,如名字空间、可见性、inline指令等等.
第1章描述值、对象、类型、过程和概念.第2～5章描述各种代数结构(如半群、全序集)上的算法.第6～11章讨论抽象内存上的算法.第12章讨论包含对象成员的对象.跋给出了我们对本书中阐释的工作途径的反思.
致谢
真诚感谢AdobeSystems及其支持程序设计基础课程和本书的管理部门,本书就是在这一课程中成长起来的.特别感谢GregGilley启动了这个课程并建议我们写这本书;DaveStory以及后来BillHensler提供了始终不渝的支持.最后,如果没有SeanParent富于启发的管理以及对代码和正文持续的彻查,本书也不可能完成.本书的思想萌芽于我们与DaveMusser跨越了近三十年的紧密合作.感谢BjarneStroustrup认真地发展C++来支持这些想法.Dave和Bjarne友善地专门到SanJose来并仔细审阅了早期的书稿.SeanParent和BjarneStroustrup为本书写了定义C++子集的附录.JonBrandt审阅了本书的多个稿本.JohnWilkinson仔细阅读了最后的书稿,提出了不计其数有价值的建议.
我们的编辑PeterGordon,项目编辑ElizabethRyan,文本编辑EvelynPyle,审阅编辑MattAustern、AndrewKoenig、DavidMusser、ArchRobison、Jerry Schwarz、JeremySiek和JohnWilkinson都对本书做出了重要的贡献.
2.推荐PattersonandHennessy[2007].
3.推荐Tarjan[1983],这是一本有关算法和数据结构的有选择的但又非常深刻的入门书.
4.标准的参考书是Stroustrup[2000].
5.书中代码都能在MicrosoftVisualC++9和g++4下编译运行.所有代码,以及几个使它们能编译直至做单元测试的简单的宏,都可以在www.elementsofprogramming.com下载.
我们感谢在Adobe以及更早在SGI参与有关课程的学生们的各种建议.我们希望自己成功地把这些课程里的材料编织为一个统一的整体.我们衷心感谢DaveAbrahams、AndreiAlexandrescu、KonstantineArkoudas、JohnBanning、HansBoehm、AngeloBorsotti、JimDehnert、JohnDeTreville、BorisFomitchev、KevlinHenney、JussiKetonen、KarlMalbrain、MatMarcus、LarryMasinter、DaveParent、DmitryPolukhin、JonReid、MarkRuzon、Geo.Scott、DavidSimons、AnnaStepanov、TonyVanEerd、WalterVannini、TimWinkler和OlegZabluda的意见和建议.我们感谢JohnBanning, BobEnglish、StevenGrat-ton、MaxHailperin、EugeneKirpichov、AlexeiNekrassov、MarkRuzon和HaoSong指出了第一次印刷里的一些错误;FosterBrereton、GabrielDosReis、RyanErnst、AbrahamSebastian、MikeSpertus、HenningThielemann和CarlaVilloriaBurgazzi指出了第二次印刷里的错误;ShinjiDosaka、RyanErnst、StevenGrat-ton、VolkerLukas、QiuZongyan、AbrahamSebastian和SeanSilva指出了第三次印刷里的错误.6
最后,还要衷心感谢通过其写作或者个人联系给我们教益,使我们加深了对程序设计的理解的所有人以及相关的机构.
6.最新的勘误信息见www.elementsofprogramming.com.
关于作者
AlexanderStepanov于1967到1972年间在国立莫斯科大学学习数学,从1972年开始在苏联,1977年移民后继续在美国从事程序设计工作.他编写过操作系统、程序设计工具、编译器和各种程序库.他在程序设计基础方面的工作先后得到GE、BrooklynPolytechnic、AT&T、HP、SGI和Adobe的支持.他在1995年因C++标准模板库的设计获Dr.Dobb’sJournal的程序设计杰出贡献奖.
PaulMcJones于1967到1971年间在加州大学伯克利分校学习工程数学,1967年进入程序设计领域.他涉足的领域包括操作系统、程序设计环境、事务处理系统,以及企业和客户应用系统等.他先后在加州大学、IBM、Xerox、Tandem、DEC和Adobe工作.1982年他与合作者一起因论文TheRecoveryManageroftheSystemRDatabaseManager获得ACM程序设计系统和语言论文奖.
计算机\程序设计
（美）Alexander Stepanov， Paul McJones 著：请参考《编程的本质》（英文版）设计。该书书号：978-7-111-30027-4 谢谢！
裘宗燕 译：暂无简介
在Addison-Wesley新书预告上看到本书时,我就感觉到本书的不同凡响,觉得应该让更多国内同行了解书中蕴涵的理念.我立刻把信息告诉了华章的朋友.没多久就得到了华章引进版权的消息.
市面上讨论编程的书籍浩如烟海.说起编程,人们头脑中浮现的多半是语言、代码、hacking、测试、排除程序错误,以及与之相关的许多琐碎事务.而本书作者看到的重点却不同.在讨论编程时,他们关注的是数学、结构、规律、规范性、抽象、推导、前后条件、验证等等.本书作者的技术水平和成就毋庸置疑,但为什么他们能构造出像STL那样的巅峰之作,这件事却值得认真思考.如果国内有人说程序的基础是数学,估计会有不少人对其嗤之以鼻:“你懂得什么是程序?写过多少行代码?”但是,恐怕无人敢小觑本书作者,其见解和论据也无法忽视.基于上述基本考虑,本书中给出了大量精妙而且根基坚实的程序,解决了一个个具体而重要的问题.进一步说,作者还揭示了这些程序的理论基础,并从多个角度建立起它们之间的联系,使之可能成为无数实际程序的基础构件.作者的根本目标,或许就是希望基于这种思维方法和开发技术,为范围广泛的软件系统建立起坚实基础.在这里看不到调侃和讨好读者的流行俗语或插科打诨,只有严肃的叙述、分析和讨论.阅读本书的过程绝不会轻松,但我们可以相信,在这里的付出会使人收获厚丰.
作者取“Elements”作为书名也很值得玩味.我们都知道欧几里得的名著“Στoιχε′ια”(英译“Elements”),中文译为《几何原本》可能偏离了作者的本意.欧氏应该是想为一种世界观和方法论提供一个范本,其内涵和意义绝不限于今天所说的“几何”领域.实际上,《原本》希望展示的是思维和研究背后的一套基础概念和思想.现在我们面对的是程序,这是一个完全人造的世界,这里的一切也有什么“本原”吗?本书作者基于其经验和认识也想来尝试一下,模仿欧几里得探究一下位于所有编程背后的最根本的东西.作者认为,程序背后的本原就是数学的各种概念、技术和方法,需要演绎、推导和证明等,而绝不是模糊的想法和草率的编码和蛮力调试.随着计算机被更广泛地应用于各种重要领域,只靠朴素认识去工作将越来越显得脆弱和不可信.从这个角度看,本书也可以看成是作者的规劝和忠告.
我本无意翻译本书,但经不住华章的朋友一再相邀,只好勉强为之.原书出自作者上课的幻灯片,言简意赅,涉及面广,找到简洁又切中原义的译文常常很难,一句译文经常需要斟酌很久,每一遍检查都会发现许多不如意之处.由于没有足够的时间,经常有其他事务干扰,这个翻译工作一拖再拖.但无论如何,一件事总要有个结束.我决定现在将此工作告一段落,将结果交给出版社和读者检验.我希望这个中译本能对读者有所帮助,也为其中的缺陷和不足负责.
为尽可能保持原貌,我基于原书的LaTeX文件编辑译文(感谢作者提供的原文件),写了许多LaTeX宏定义,最后用MiKTeX生成全书的PDF文件交给出版社.这样做多花了不少时间,但有利于保持全书(及与原书)的统一性,可以减少不应出现的小错误.当然,这种费时费力的做法也使排版错误变成了我的个人责任.本译本已收入原作者迄今的所有勘误,翻译中发现的原书错误也都得到了作者确认.为方便读者阅读,本书实际上提供了两套索引:原书的英文索引都予以保留,与之对应,我又加入了一套中文索引(通过LaTeX生成),供读者交叉参考.原作者自创了不少术语,没有习见译法,我只能设法编造出相应译文,其合理性需要时间检验.此外,正文中出现的术语都给出了英文对照.有关本书的工作,我要感谢刘海洋在使用LaTeX处理中文方面的若干意见,感谢编辑发现了译稿的一些文字错误.
裘宗燕
2011年10月6日,于北京大学理科一号楼
译者序
前言
关于作者
第1 章基础...................................................... 1
1.1理念范畴:实体,类别,类属.......................1
1.2值.....................................2
1.3对象....................................4
1.4过程....................................6
1.5规范类型.................................7
1.6规范过程.................................8
1.7概念....................................10
1.8总结....................................14
第2 章变换及其轨道............................................. 15
2.1变换....................................15
2.2轨道....................................18
2.3碰撞点...................................21
2.4轨道规模的度量.............................27
2.5动作....................................28
2.6总结....................................29
第3 章可结合运算............................................... 31
3.1可结合性.................................31
3.2计算乘幂.................................32
3.3程序变换.................................35
3.4处理特殊情况的过程..........................40
3.5参数化算法................................43
3.6线性递归.................................44
3.7累积过程.................................47
3.8总结....................................48
第4 章线性序.................................................... 49
4.1关系的分类................................49
4.2全序和弱序................................51
4.3按序选取.................................52
4.4自然全序.................................62
4.5派生过程组................................63
4.6按序选取过程的扩展..........................63
4.7总结....................................64
第5 章有序代数结构............................................. 65
5.1基本代数结构..............................65
5.2有序代数结构..............................70
5.3求余....................................72
5.4最大公因子................................76
5.5广义gcd..................................79
5.6Steingcd.................................81
5.7商.....................................82
5.8负量的商和余数.............................84
5.9概念及其模型..............................87
5.10计算机整数类型.............................88
5.11结论....................................89
第6 章迭代器.................................................... 91
6.1可读性...................................91
6.2迭代器...................................92
6.3范围....................................94
6.4可读范围.................................97
6.5递增的范围................................106
6.6前向迭代器................................108
6.7索引迭代器................................113
6.8双向迭代器................................114
6.9随机访问迭代器.............................115
6.10总结....................................117
第7 章坐标结构................................................. 119
7.1二叉坐标.................................119
7.2双向二叉坐标..............................123
7.3坐标结构.................................129
7.4同构,等价和有序............................129
7.5总结....................................137
第8 章后继可变的坐标........................................... 139
8.1链接迭代器................................139
8.2链接重整.................................140
8.3链接重整的应用.............................147
8.4链接的二叉坐标.............................151
8.5结论....................................155
第9 章拷贝...................................................... 157
9.1可写性...................................157
9.2基于位置的拷贝.............................159
9.3基于谓词的拷贝.............................166
9.4范围的交换................................174
9.5总结....................................178
第10 章重整..................................................... 179
10.1置换....................................179
10.2重整....................................182
10.3 反转算法
10.4 轮换算法
10.5 算法选择
10.6 总结.................................184
第11 章划分和归并.............................................. 201
11.1划分....................................201
11.2平衡的归约................................207
11.3归并....................................212
11.4总结....................................218
第12 章复合对象................................................ 219
12.1简单复合对象..............................219
12.2动态序列.................................227
12.3基础类型.................................233
12.4总结....................................236
跋................................................................ 237
附录 A 数学表示................................................ 241
附录B 程序设计语言............................................ 243
参考文献......................................................... 253
索引......................................................... 257
