Elements of Programming
Search in google:
“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 CenterElements 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.
Preface ix About the Authors xiiiChapter 1: Foundations 11.1 Categories of Ideas: Entity, Species, Genus 11.2 Values 21.3 Objects 41.4 Procedures 61.5 Regular Types 61.6 Regular Procedures 81.7 Concepts 101.8 Conclusions 14Chapter 2: Transformations and Their Orbits 152.1 Transformations 152.2 Orbits 182.3 Collision Point 212.4 Measuring Orbit Sizes 272.5 Actions 282.6 Conclusions 29Chapter 3: Associative Operations 313.1 Associativity 313.2 Computing Powers 333.3 Program Transformations 353.4 Special-Case Procedures 393.5 Parameterizing Algorithms 423.6 Linear Recurrences 433.7 Accumulation Procedures 463.8 Conclusions 47Chapter 4: Linear Orderings 494.1 Classification of Relations 494.2 Total and Weak Orderings 514.3 Order Selection 524.4 Natural Total Ordering 614.5 Clusters of Derived Procedures 624.6 Extending Order-Selection Procedures 634.7 Conclusions 63Chapter 5: Ordered Algebraic Structures 655.1 Basic Algebraic Structures 655.2 Ordered Algebraic Structures 705.3 Remainder 715.4 Greatest Common Divisor 765.5 Generalizing gcd 795.6 Stein gcd 815.7 Quotient 815.8 Quotient and Remainder for Negative Quantities 835.9 Concepts and Their Models 855.10 Computer Integer Types 875.11 Conclusions 88Chapter 6: Iterators 896.1 Readability 896.2 Iterators 906.3 Ranges 926.4 Readable Ranges 956.5 Increasing Ranges 1036.6 Forward Iterators 1066.7 Indexed Iterators 1106.8 Bidirectional Iterators 1116.9 Random-Access Iterators 1136.10 Conclusions 114Chapter 7: Coordinate Structures 1157.1 Bifurcate Coordinates 1157.2 Bidirectional Bifurcate Coordinates 1197.3 Coordinate Structures 1247.4 Isomorphism, Equivalence, and Ordering 1247.5 Conclusions 131Chapter 8: Coordinates with Mutable Successors 1338.1 Linked Iterators 1338.2 Link Rearrangements 1348.3 Applications of Link Rearrangements 1408.4 Linked Bifurcate Coordinates 1438.5 Conclusions 148Chapter 9: Copying 1499.1 Writability 1499.2 Position-Based Copying 1519.3 Predicate-Based Copying 1579.4 Swapping Ranges 1649.5 Conclusions 168Chapter 10: Rearrangements 16910.1 Permutations 16910.2 Rearrangements 17210.3 Reverse Algorithms 17410.4 Rotate Algorithms 17810.5 Algorithm Selection 18610.6 Conclusions 189Chapter 11: Partition and Merging 19111.1 Partition 19111.2 Balanced Reduction 19811.3 Merging 20211.4 Conclusions 208Chapter 12: Composite Objects 20912.1 Simple Composite Objects 20912.2 Dynamic Sequences 21612.3 Underlying Type 22212.4 Conclusions 225Afterword 227Appendix A: Mathematical Notation 231Appendix B: Programming Language 233B.1 Language Definition 233B.2 Macros and Trait Structures 240Bibliography 243Index 247
