編程的本質(zhì)

前言

This book applies the deductive method to programming by affiliating programs with the abstract mathematical theories that enable them to work. Specification of these theories, algorithms written in terms of these theories, and theorems and lemmas describing their properties are presented together. The implementation of the algorithms in a real programming language is central to the book. While the specifications, which are addressed to human beings, should, and even must, combine rigor with appropriate informality, the code, which is addressed to the computer, must be absolutely precise even while being general. As with other areas of science and engineering, the appropriate foundation of programming is the deductive method. It facilitates the decomposition of complex systems into components with mathematically specified behavior. That, in turn, is a necessary precondition for designing efficient, reliable, secure, and economical software. The book is addressed to those who want a deeper understanding of program- ming, whether they are full-time software developers, or scientists and engineers for whom programming is an important part of their professional activity. The book is intended to be read from beginning to end. Only by reading the code, proving the lemmas, and doing the exercises can readers gain understanding of the material. In addition, we suggest several projects, some open-ended. While the book is terse, a careful reader will eventually see the connections between its parts and the reasons for our choice of material. Discovering the architectural principles of the book should be the reader's goal. We assume an ability to do elementary algebraic manipulations, l We also assume familiarity with the basic vocabulary of logic and set theory at the level of undergrad- uate courses on discrete mathematics; Appendix A summarizes the notation that we use. We provide definitions of a few concepts of abstract algebra when they are needed to specify algorithms. We assume programming maturity and understanding of computer architecture2 and fundamental algorithms and data structures) We chose C++ because it combines powerful abstraction facilities with faithful representation of the underlying machine) We use a small subset of the language and write requirements as structured comments. We hope that readers not already familiar with C++ are able to follow the book. Appendix B specifies the subset of the language used in the book? Wherever there is a difference between mathematical notation and C++, the typesetting and the context determine whether the mathe- matical or C++ meaning applies. While many concepts and programs in the book have parallels in STL (the C++ Standard Template Library), the book departs from some of the STL design decisions. The book also ignores issues that a real library, such as STL, has to address: namespaces, visibility, inline directives, and so on. Chapter 1 describes values, objects, types, procedures, and concepts. Chapters 2-5 describe algorithms on algebraic structures, such as semigroups and totally ordered sets. Chapters 6-11 describe algorithms on abstractions of memory. Chapter 12 describes objects containing other objects. The Afterword presents our reflections on the approach presented by the book.

內(nèi)容概要

　　本書提供了有關(guān)編程的一種與眾不同的理解。其主旨是，實(shí)際的編程也應(yīng)像其他科學(xué)和工程領(lǐng)域一樣基于堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)。本書展示了在實(shí)際編程語(yǔ)言(如C++)中實(shí)現(xiàn)的算法如何在最一般的數(shù)學(xué)背景中操作。例如，如何定義快速求冪算法，使之能使用任何可交換運(yùn)算。使用抽象算法將能得到更高效、可靠、安全和經(jīng)濟(jì)的軟件?！　∵@不是一本很容易讀的書，它也不是能提升你的編程技能的秘訣和技巧匯編。本書的價(jià)值是更根本性的，其終極目標(biāo)是提升你對(duì)編程的洞察力。要想從中大獲裨益，你需要從頭到尾認(rèn)真學(xué)習(xí)：閱讀代碼，證明引理，完成練習(xí)。到結(jié)束之時(shí)，你將看到如何把這里討論的演繹式方法應(yīng)用到你的程序中，保證你做出的軟件部件能一起工作，并表現(xiàn)出它們所應(yīng)該表現(xiàn)的行為?！　薪o出的算法和需求針對(duì)某些被操作的類型。有關(guān)這些描述的代碼(也可以通過(guò)Web得到)采用C++的一個(gè)小子集書寫，這樣做是為了讓所有有經(jīng)驗(yàn)的程序員都能理解。這個(gè)小子集可以看做一種特殊語(yǔ)言，是由Sean Parent和Bjarne Stroustrup一起設(shè)計(jì)的?！　o(wú)論你是一位軟件開(kāi)發(fā)者，還是其他以編程作為一項(xiàng)重要活動(dòng)的專業(yè)人員，或者是一名在校的學(xué)生，你都會(huì)逐漸理解本書的經(jīng)驗(yàn)豐富的作者多年來(lái)一直在教授和闡釋的道理：數(shù)學(xué)對(duì)于編程是絕好的東西，理論對(duì)于實(shí)際是絕好的東西。

作者簡(jiǎn)介

Alexander Stepanov于1967～1972年間在莫斯科國(guó)立大學(xué)學(xué)習(xí)數(shù)學(xué)，從1972年開(kāi)始在蘇聯(lián)，1977年移民美國(guó)后在美國(guó)從事編程工作。他編寫過(guò)操作系統(tǒng)、編程工具、編譯器和各種庫(kù)。他在程序設(shè)計(jì)基礎(chǔ)方面的工作先后得到GE、Polytechnic、AT&T、惠普、Silicon Graphics的支持，2002年后是Adobe的支持。1995年因C++標(biāo)準(zhǔn)模板庫(kù)的設(shè)計(jì)獲Dr.Dobb的程序設(shè)計(jì)杰出貢獻(xiàn)獎(jiǎng)。Paul McJones于1967～1971年間在加州大學(xué)伯克利分校學(xué)習(xí)工程數(shù)學(xué)。從1967年開(kāi)始介入程序設(shè)計(jì)，涉足的領(lǐng)域包括操作系統(tǒng)、程序設(shè)計(jì)環(huán)境、事務(wù)處理系統(tǒng)以及企業(yè)和客戶應(yīng)用系統(tǒng)等。他先后在加州大學(xué)、IBM、Xerox、Tandem、DEC工作，2003年至今在Adobe公司。1982年他與合作者一起因其論文“The Recovery Manager of the System R Database Manager”獲得ACM程序設(shè)計(jì)系統(tǒng)和語(yǔ)言論文獎(jiǎng)。

書籍目錄

Preface ix AbouttheAuthors xiii 1 Foundations  　1.1 CategoriesofIdeas:Entity,Species,Genus  　1.2 Values  　1.3 Objects  　1.4 rocedures6 　1.5 RegularTypes  　1.6 RegularProcedures  　1.7 Concepts  　1.8 Conclusions14 2 TransformationsandTheirOrbits1  　2.1 Transformations  　2.2 Orbits  　2.3 CollisionPoint  　2.4 MeasuringOrbitSizes  　2.5 Actions  　2.6 Conclusions  3 AssociativeOperations  　3.1 Associativity  　3.2 ComputingPowers  　3.3 ProgramTransformations  　3.4 Special-CaseProcedures  　3.5 ParameterizingAlgorithms  　3.6 LinearRecurrences  　3.7 AccumulationProcedures  　3.8 Conclusions  4 LinearOrderings  　4.1 Classi?cationofRelations  　4.2 TotalandWeakOrderings  　4.3 OrderSelection  　4.4 NaturalTotalOrdering  　4.5 ClustersofDerivedProcedures  　4.6 ExtendingOrder-SelectionProcedures  　4.7 Conclusions  5 OrderedAlgebraicStructures  　5.1 BasicAlgebraicStructures  　5.2 OrderedAlgebraicStructures  　5.3 Remainder  　5.4 GreatestCommonDivisor  　5.5 Generalizinggcd  　5.6 Steingcd  　5.7 Quotient  　5.8 QuotientandRemainderforNegativeQuantities  　5.9 ConceptsandTheirModels  　5.10 ComputerIntegerTypes  　5.11 Conclusions 6 Iterators  　6.1 Readability  　6.2 Iterators  　6.3 Ranges  　6.4 ReadableRanges  　6.5IncreasingRanges  　6.6 ForwardIterators  　6.7 IndexedIterators  　6.8 BidirectionalIterators 　6.9 Random-AccessIterators  　6.1 Conclusions  7 CoordinateStructures  　7.1 ifurcateCoordinates  　7.2 BidirectionalBifurcateCoordinates  　7.3 CoordinateStructures  　7.4 Isomorphism,Equivalence,andOrdering  　7.5 Conclusions  8 CoordinateswithMutableSuccessors  　8.1 LinkedIterators  　8.2 LinkRearrangements  　8.3 ApplicationsofLinkRearrangements  　8.4 LinkedBifurcateCoordinates  　8.5 Conclusions9 Copying  　9.1 Writability  　9.2 Position-BasedCopying  　9.3 Predicate-BasedCopying  　9.4 SwappingRanges  　9.5 Conclusions  10 Rearrangements  　10.1 Permutations  　10.2 Rearrangements  　10.3 ReverseAlgorithms  　10.4 RotateAlgorithms  　10.5 AlgorithmSelection  　10.6 Conclusions  11 PartitionandMerging  　11.1 Partition  　11.2 BalancedReduction 　11.3 Merging  　11.4 Conclusions 12 CompositeObjects  　12.1 SimpleCompositeObjects  　12.2 DynamicSequences  　12.3 UnderlyingType  　12.4 Conclusions  Afterword  AppendixA MathematicalNotation  AppendixB ProgrammingLanguage  B.1 LanguageDe?nition  B.2 MacrosandTraitStructures  Bibliography  Index

章節(jié)摘錄

插圖：An object is passed directly flit is passed as an argument or returned as the resultand is passed indirectly if it is passed via a pointer or pointerlike object. An object isan input to a procedure if it is read, but not modified, by the procedure. An object isan output from a procedure if it is written, created, or destroyed by the procedure,but its initial state is not read by the procedure. An object is an input~output of aprocedure if it is modified as well as read by the procedure.A computational basis for a type is a finite set of procedures that enable theconstruction of any other procedure on the type. A basis is efficient if and onlyif any procedure implemented using it is as efficient as an equivalent procedurewritten in terms of an alternative basis. For example, a basis for unsigned k-bitintegers providing only zero, equality, and the successor function is not efficient,since the complexity of addition in terms of successor is exponential in k.A basis is expressive if and only if it allows compact and convenient definitionsof procedures on the type. In particular, all the common mathematical operationsneed to be provided when they are appropriate. For example, subtraction could beimplemented using negation and addition but should be included in an expressivebasis. Similarly, negation could be implemented using subtraction and zero butshould be included in an expressive basis.

媒體關(guān)注與評(píng)論

“要是問(wèn)一位機(jī)械、建筑或電子工程師，如果不依靠堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)，他們能走多遠(yuǎn)。他們會(huì)告訴你‘走不了多遠(yuǎn)’。而所謂的軟件工程師在實(shí)踐其技能時(shí)，卻常常對(duì)他們所做工作的數(shù)學(xué)基礎(chǔ)知之甚少，甚至一無(wú)所知。同時(shí)我們也很奇怪為什么軟件由于不能按時(shí)發(fā)布并充斥錯(cuò)誤而聲名狼藉，而其他工程師卻能按時(shí)完成其橋梁、汽車、各種電子裝置等，而且有很少的缺陷。本書就是想糾正這種不平衡現(xiàn)象。我在Adobe的高級(jí)開(kāi)發(fā)團(tuán)隊(duì)的成員們，但凡參加了基于同樣材料的課程，都覺(jué)得付出的時(shí)間獲益匪淺。初看可能覺(jué)得這種高度技術(shù)性的文字只是為計(jì)算機(jī)科學(xué)家寫的，其實(shí)所有從事實(shí)際工作的軟件工程師都應(yīng)該來(lái)讀?！?　　——Martin Newell，Adobe 院士“本書包含一些我所見(jiàn)過(guò)的最美的代碼?！?　　——Bjarne Stroustrup，C++ 設(shè)計(jì)者“我很高興看到Alex課程的內(nèi)容。作為Silicon Graphics的CTO時(shí)，我曾大力支持這一課程的開(kāi)發(fā)和教授，現(xiàn)在這本書已經(jīng)能被所有程序員閱讀了?！?　　——Forest Baskett，合伙人，New Enterprise Associates“Paul的耐心和在體系結(jié)構(gòu)方面的經(jīng)驗(yàn)幫助把Alex的數(shù)學(xué)方法組織成為一套高度結(jié)構(gòu)化的大廈——功德無(wú)量！” 　　——Robert W. Taylor，Xerox PARC CSL和DEC系統(tǒng)研究中心創(chuàng)始人

編輯推薦

《編程的本質(zhì)(英文版)》：經(jīng)典原版書庫(kù)

圖書封面

圖書標(biāo)簽Tags

無(wú)

評(píng)論、評(píng)分、閱讀與下載

---

    編程的本質(zhì) PDF格式下載

---