编程原本

    书籍
    计算机书籍
《编程原本(STL之父Alexander Stepanov力作,裘宗燕老师倾情献译,追溯数学原理,探求编程的本质)》将严格的数学定义、公理化和演绎方法应用于程序设计，讨论程序与保证它们能正确工作的抽象数学理论之间的联系。书中把理论的规程、基于这些写出的算法，以及描述算法性质的引理和定理一起呈现给读者，以帮助我们将复杂系统分解为一些具有特定行为的组件。

《编程原本(STL之父Alexander Stepanov力作,裘宗燕老师倾情献译,追溯数学原理,探求编程的本质)》适合软件开发人员和需要进行程序设计的科学家及工程师阅读，也可供高等院校计算机及相关专业的师生参考。

《编程原本》提供了有关编程的一种与众不同的理解。其主旨是，实际的编程也应像其他科学和工程领域一样基于坚实的数学基础。《编程原本》展示了在实际编程语言（如c++）中实现的算法如何在最一般的数学背景中操作。例如，如何定义快速求幂算法，使之能使用任何可交换运算。使用抽象算法将能得到更高效、可靠、安全和经济的软件。

这不是一本很容易读的书，它也不是能提升你的编程技能的秘诀和技巧汇编。《编程原本》的价值是更根本性的，其终极目标是提升你对编程的洞察力。要想从中大获裨益，你需要从头到尾认真学习：阅读代码，证明引理，完成练习。到结束之时，你将看到如何把这里讨论的演绎方法应用到你的程序中，保证你做出的软件部件能一起工作，并表现出它们所应该表现的行为。

《编程原本(STL之父Alexander Stepanov力作,裘宗燕老师倾情献译,追溯数学原理,探求编程的本质)》中给出的算法和需求针对某些被操作的类型。有关这些描述的代码（也可以通过web得到）采用c++的一个小子集书写，这样做是为了让所有有经验的程序员都能理解。这个小子集可以看做一种特殊语言，是由sean parent和bjarne stroustrup一起设计的。

无论你是一位软件开发者，还是其他以编程作为一项重要活动的专业人员，或者是一名在校的学生，你都会逐渐理解《编程原本》的经验丰富的作者多年来一直在教授和阐释的道理：数学对于编程是绝好的东西，理论对于实际是绝好的东西。

Alexander Stepanov 于1967~1972年间在国立莫斯科大学学习数学，从1972年开始在苏联，1977年移民后继续在美国从事编程工作。他编写过操作系统、编程工具、编译器和各种程序库。他在程序设计基础方面的工作先后得到GE、Polytechnic、AT&T、惠普、SGI和Adobe的支持。1995年因C++标准模板库的设计获Dr. Dobb, 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语言引论》等。

《编程原本》
译者序
前言
关于作者
第1章 基础
1.1理念范畴:实体,类别,类属
1.2值
1.3对象
1.4过程
1.5规范类型
1.6规范过程
1.7概念
1.8总结
第2章 变换及其轨道
2.1变换
2.2轨道
2.3碰撞点
2.4轨道规模的度量
2.5动作
2.6总结

　　在Addison-Wesley新书预告上看到《编程原本》时，我就感觉到《编程原本》的不同凡响，觉得应该让更多国内同行了解书中蕴涵的理念。我立刻把信息告诉了华章的朋友。没多久就得到了华章引进版权的消息。
　　市面上讨论编程的书籍浩如烟海。说起编程，人们头脑中浮现的多半是语言、代码、hacking、测试、排除程序错误，以及与之相关的许多琐碎事务。而《编程原本》作者看到的重点却不同。在讨论编程时，他们关注的是数学、结构、规律、规范性、抽象、推导、前后条件、验证等等。《编程原本》作者的技术水平和成就毋庸置疑，但为什么他们能构造出像STL那样的巅峰之作，这件事却值得认真思考。如果国内有人说程序的基础是数学，估计会有不少人对其嗤之以鼻：“你懂得什么是程序?写过多少行代码?”但是，恐怕无人敢小觑《编程原本》作者，其见解和论据也无法忽视。基于上述基本考虑，《编程原本》中给出了大量精妙而且根基坚实的程序，解决了一个个具体而重要的问题。进一步说，作者还揭示了这些程序的理论基础，并从多个角度建立起它们之间的联系，使之可能成为无数实际程序的基础构件。作者的根本目标，或许就是希望基于这种思维方法和开发技术，为范围广泛的软件系统建立起坚实基础。在这里看不到调侃和讨好读者的流行俗语或插科打诨，只有严肃的叙述、分析和讨论。阅读《编程原本》的过程绝不会轻松，但我们可以相信，在这里的付出会使人收获厚丰。
　　作者取“Elements”作为书名也很值得玩味。我们都知道欧几里得的名著“Στoιχε′ια”(英译“Elements”)，中文译为《几何原本》可能偏离了作者的本意。欧氏应该是想为一种世界观和方法论提供一个范本，其内涵和意义绝不限于今天所说的“几何”领域。实际上，《原本》希望展示的是思维和研究背后的一套基础概念和思想。现在我们面对的是程序，这是一个完全人造的世界，这里的一切也有什么“本原”吗?《编程原本》作者基于其经验和认识也想来尝试一下，模仿欧几里得探究一下位于所有编程背后的最根本的东西。作者认为，程序背后的本原就是数学的各种概念、技术和方法，需要演绎、推导和证明等，而绝不是模糊的想法和草率的编码和蛮力调试。随着计算机被更广泛地应用于各种重要领域，只靠朴素认识去工作将越来越显得脆弱和不可信。从这个角度看，《编程原本》也可以看成是作者的规劝和忠告。
　　我本无意翻译《编程原本》，但经不住华章的朋友一再相邀，只好勉强为之。原书出自作者上课的幻灯片，言简意赅，涉及面广，找到简洁又切中原义的译文常常很难，一句译文经常需要斟酌很久，每一遍检查都会发现许多不如意之处。由于没有足够的时间，经常有其他事务干扰，这个翻译工作一拖再拖。但无论如何，一件事总要有个结束。我决定现在将此工作告一段落，将结果交给出版社和读者检验。我希望这个中译本能对读者有所帮助，也为其中的缺陷和不足负责。
　　为尽可能保持原貌，我基于原书的LaTeX文件编辑译文(感谢作者提供的原文件)，写了许多LaTeX宏定义，最后用MiKTeX生成全书的PDF文件交给出版社。这样做多花了不少时间，但有利于保持全书(及与原书)的统一性，可以减少不应出现的小错误。当然，这种费时费力的做法也使排版错误变成了我的个人责任。本译本已收入原作者迄今的所有勘误，翻译中发现的原书错误也都得到了作者确认。为方便读者阅读，《编程原本》实际上提供了两套索引：原书的英文索引都予以保留，与之对应，我又加入了一套中文索引(通过LaTeX生成)，供读者交叉参考。原作者自创了不少术语，没有习见译法，我只能设法编造出相应译文，其合理性需要时间检验。此外，正文中出现的术语都给出了英文对照。有关《编程原本》的工作，我要感谢刘海洋在使用LaTeX处理中文方面的若干意见，感谢编辑发现了译稿的一些文字错误。
　　裘宗燕2011年10月6日，于北京大学理科一号楼
　　

　　《编程原本》将演绎方法应用于程序设计，讨论程序与保证它们能正确工作的抽象数学理论之间的联系.书中把反映这些理论的规程（speci.cation），基于这些理论写出的算法，以及描述算法性质的引理和定理一起呈现给读者.这些算法在一种实际程序设计语言里的实现是《编程原本》的中心。虽然规程主要是供人阅读，但它们也应该（或者说必须）严格地与非形式化的、供机器使用的代码相结合，必须在通用的同时又是抽象而且精确的。
　　与在其他科学和工程领域里的情况一样，适合作为程序设计的基础的同样是演绎方法。演绎方法能帮助我们将复杂系统分解为一些具有特定数学行为的组件，而这种分解又是设计高效、可靠、安全和经济的软件的前提。
　　《编程原本》是想奉献给那些希望更深入地理解程序设计的人们，无论他们是专职软件开发人员，还是把程序设计看作其专业活动中一个重要组成部分的科学家或工程师。
　　《编程原本》编写的基本想法是让读者从头到尾完整阅读。读者只有通过阅读代码、证明引理、完成练习，才能真正理解书中的各方面材料。此外我们还建议了一些项目，其中有些是完全开放的。《编程原本》的内容很紧凑，认真的读者最终会看到书中各部分之间的联系，以及我们选择这些材料的理由。发现《编程原本》在体系结构方面的原理应该是读者的一个目标。
　　我们假定读者已经具有完成各种基本代数操作的能力。还假定读者熟悉逻辑和集合论的基本术语，如普通本科生在离散数学课程中学习的内容。附录A总结了书中使用的各种记法。如果在一些特定的算法里需要某些抽象代数的概念，书中会给出相应的定义。我们还假定读者熟悉程序设计，理解计算机体系结构，理解最基本的算法和数据结构。
　　我们选用C++，是因为它组合了强有力的抽象设施和基础机器的正确表示。这里只用了该语言的一个小子集，需求被写成程序里的结构化注释。我们希望不熟悉C++的读者也能阅读《编程原本》。附录B描述了书中使用的C++子集。在书中的任何地方，在需要区分数学记法和C++的地方，根据所用的字体、排版和上下文就能确定用的是哪种意义（是数学的还是C++的）。虽然书中的许多概念和程序与STL（C++标准模板库）里的东西对应，但这里的一些设计决策是与STL不同的。书中还忽略了实际程序库（如STL）必须考虑和处理的许多问题，如名字空间、可见性、inline指令等等。
　　第1章描述值、对象、类型、过程和概念。第2～5章描述各种代数结构（如半群、全序集）上的算法。第6～11章讨论抽象内存上的算法。第12章讨论包含对象成员的对象。跋给出了我们对《编程原本》中阐释的工作途径的反思。
　　

　　“要是问一位机械、建筑或电子工程师，如果不依靠坚实的数学基础，他们能走多远。他们会告诉你‘走不了多远’。而所谓的软件工程师在实践其技能时，却常常对他们所做工作的数学基础知之甚少，甚至一无所知。同时我们也很奇怪为什么软件由于不能按时发布并充斥错误而声名狼藉，而其他工程师却能按时完成其桥梁、汽车、各种电子装置等，而且缺陷很少。《编程原本》就是想纠正这种不平衡现象。我在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系统研究中心创始人