Elements of programming

Alexander Stepanov, Paul McJones

"Ask a mechanical, structural, or electrical engineer how far they would get without a heavy reliance on a firm mathematical foundation, and they will tell you, 'not far.' Yet so-called software engineers often practice their art with little or no idea of the mathematical underpinnings of what they are doing. And then we wonder why software is notorious for being delivered late and full of bugs, while other engineers routinely deliver finished bridges, automobiles, electrical appliances, etc., on time and with only minor defects. This book sets out to redress this imbalance. Members of my advanced development team at Adobe who took the course based on the same material all benefited greatly from the time invested. It may appear as a highly technical text intended only for computer scientists, but it should be required reading for all practicing software engineers." -Martin Newell, Adobe Fellow "The book contains some of the most beautiful code I have ever seen." -Bjarne Stroustrup, Designer of C++ "I am happy to see the content of Alex's course, the development and teaching of which I strongly supported as the CTO of Silicon Graphics, now available to all programmers in this elegant little book." -Forest Baskett, General Partner, New Enterprise Associates "Paul's patience and architectural experience helped to organize Alex's mathematical approach into a tightly-structured edifice-an impressive feat!" -Robert W. Taylor, Founder of Xerox PARC CSL and DEC Systems Research Center Elements of Programming provides a different understanding of programming than is presented elsewhere. Its major premise is that practical programming, like other areas of science and engineering,must be based on a solid mathematical foundation. The book shows that algorithms implemented in a real programming language, such as C++, can operate in the most general mathematical setting. For example, the fast exponentiation algorithm is defined to work with any associative operation. Using abstract algorithms leads to efficient, reliable, secure, and economical software. This is not an easy book. Nor is it a compilation of tips and tricks for incremental improvements in your programming skills. The book's value is more fundamental and, ultimately, more critical for insight into programming. To benefit fully, you will need to work through it from beginning to end, reading the code, proving the lemmas, and doing the exercises. When finished, you will see how the application of the deductive method to your programs assures that your system's software components will work together and behave as they must. The book presents a number of algorithms and requirements for types on which they are defined. The code for these descriptions-also available on the Web-is written in a small subset of C++ meant to be accessible to any experienced programmer. This subset is defined in a special language appendix coauthored by Sean Parent and Bjarne Stroustrup. Whether you are a software developer, or any other professional for whom programming is an important activity, or a committed student, you will come to understand what the book's experienced authors have been teaching and demonstrating for years-that mathematics is good for programming, and that theory is good for practice.

「Nielsen BookData」より

[目次]

  • Preface ix About the Authors xiii Chapter 1: Foundations 1 1.1 Categories of Ideas: Entity, Species, Genus 1 1.2 Values 2 1.3 Objects 4 1.4 Procedures 6 1.5 Regular Types 6 1.6 Regular Procedures 8 1.7 Concepts 10 1.8 Conclusions 14 Chapter 2: Transformations and Their Orbits 15 2.1 Transformations 15 2.2 Orbits 18 2.3 Collision Point 21 2.4 Measuring Orbit Sizes 27 2.5 Actions 28 2.6 Conclusions 29 Chapter 3: Associative Operations 31 3.1 Associativity 31 3.2 Computing Powers 33 3.3 Program Transformations 35 3.4 Special-Case Procedures 39 3.5 Parameterizing Algorithms 42 3.6 Linear Recurrences 43 3.7 Accumulation Procedures 46 3.8 Conclusions 47 Chapter 4: Linear Orderings 49 4.1 Classification of Relations 49 4.2 Total and Weak Orderings 51 4.3 Order Selection 52 4.4 Natural Total Ordering 61 4.5 Clusters of Derived Procedures 62 4.6 Extending Order-Selection Procedures 63 4.7 Conclusions 63 Chapter 5: Ordered Algebraic Structures 65 5.1 Basic Algebraic Structures 65 5.2 Ordered Algebraic Structures 70 5.3 Remainder 71 5.4 Greatest Common Divisor 76 5.5 Generalizing gcd 79 5.6 Stein gcd 81 5.7 Quotient 81 5.8 Quotient and Remainder for Negative Quantities 83 5.9 Concepts and Their Models 85 5.10 Computer Integer Types 87 5.11 Conclusions 88 Chapter 6: Iterators 89 6.1 Readability 89 6.2 Iterators 90 6.3 Ranges 92 6.4 Readable Ranges 95 6.5 Increasing Ranges 103 6.6 Forward Iterators 106 6.7 Indexed Iterators 110 6.8 Bidirectional Iterators 111 6.9 Random-Access Iterators 113 6.10 Conclusions 114 Chapter 7: Coordinate Structures 115 7.1 Bifurcate Coordinates 115 7.2 Bidirectional Bifurcate Coordinates 119 7.3 Coordinate Structures 124 7.4 Isomorphism, Equivalence, and Ordering 124 7.5 Conclusions 131 Chapter 8: Coordinates with Mutable Successors 133 8.1 Linked Iterators 133 8.2 Link Rearrangements 134 8.3 Applications of Link Rearrangements 140 8.4 Linked Bifurcate Coordinates 143 8.5 Conclusions 148 Chapter 9: Copying 149 9.1 Writability 149 9.2 Position-Based Copying 151 9.3 Predicate-Based Copying 157 9.4 Swapping Ranges 164 9.5 Conclusions 168 Chapter 10: Rearrangements 169 10.1 Permutations 169 10.2 Rearrangements 172 10.3 Reverse Algorithms 174 10.4 Rotate Algorithms 178 10.5 Algorithm Selection 186 10.6 Conclusions 189 Chapter 11: Partition and Merging 191 11.1 Partition 191 11.2 Balanced Reduction 198 11.3 Merging 202 11.4 Conclusions 208 Chapter 12: Composite Objects 209 12.1 Simple Composite Objects 209 12.2 Dynamic Sequences 216 12.3 Underlying Type 222 12.4 Conclusions 225 Afterword 227 Appendix A: Mathematical Notation 231 Appendix B: Programming Language 233 B.1 Language Definition 233 B.2 Macros and Trait Structures 240 Bibliography 243 Index 247

「Nielsen BookData」より

この本の情報

書名 Elements of programming
著作者等 Stepanov, Alexander A
Stepanov Alexander
McJones Paul
出版元 Addison-Wesley;Pearson Education
刊行年月 c2009
ページ数 xiii, 262 p.
大きさ 24 cm
ISBN 9780321635372
NCID BB04762148
※クリックでCiNii Booksを表示
言語 英語
出版国 アメリカ合衆国
この本を: 
このエントリーをはてなブックマークに追加

このページを印刷

外部サイトで検索

この本と繋がる本を検索

ウィキペディアから連想