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

作者簡介

Alexander Stepanov于1967～1972年間在莫斯科國立大學(xué)學(xué)習(xí)數(shù)學(xué)，從1972年開始在蘇聯(lián)，1977年移民美國后在美國從事編程工作。他編寫過操作系統(tǒng)、編程工具、編譯器和各種庫。他在程序設(shè)計基礎(chǔ)方面的工作先后得到GE、Polytechnic、AT&T、惠普、Silicon Graphics的支持，2002年后是Adobe的支持。1995年因C++標(biāo)準(zhǔn)模板庫的設(shè)計獲Dr.Dobb的程序設(shè)計杰出貢獻(xiàn)獎。Paul McJones于1967～1971年間在加州大學(xué)伯克利分校學(xué)習(xí)工程數(shù)學(xué)。從1967年開始介入程序設(shè)計，涉足的領(lǐng)域包括操作系統(tǒng)、程序設(shè)計環(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è)計系統(tǒ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)注與評論

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

編輯推薦

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

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

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

---