Elements of Programming

“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.

“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.

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 Preface About the Authors Foundations Categories of Ideas: Entity, Species, Genus Values Objects Procedures Regular Types Regular Procedures Concepts Conclusions Transformations and Their Orbits Transformations Orbits Collision Point Measuring Orbit Sizes Actions Conclusions Associative Operations Associativity Computing Powers Program Transformations Special-Case Procedures Parameterizing Algorithms Linear Recurrences Accumulation Procedures Conclusions Linear Orderings Classification of Relations Total and Weak Orderings Order Selection Natural Total Ordering Clusters of Derived Procedures Extending Order-Selection Procedures Conclusions Ordered Algebraic Structures Basic Algebraic Structures Ordered Algebraic Structures Remainder Greatest Common Divisor Generalizing gcd Stein gcd Quotient Quotient and Remainder for Negative Quantities Concepts and Their Models Computer Integer Types Conclusions Iterators Readability Iterators Ranges Readable Ranges Increasing Ranges Forward Iterators Indexed Iterators Bidirectional Iterators Random-Access Iterators Conclusions Coordinate Structures Bifurcate Coordinates Bidirectional Bifurcate Coordinates Coordinate Structures Isomorphism, Equivalence, and Ordering Conclusions Coordinates with Mutable Successors Linked Iterators Link Rearrangements Applications of Link Rearrangements Linked Bifurcate Coordinates Conclusions Copying Writability Position-Based Copying Predicate-Based Copying Swapping Ranges Conclusions Rearrangements Permutations Rearrangements Reverse Algorithms Rotate Algorithms Algorithm Selection Conclusions Partition and Merging Partition Balanced Reduction Merging Conclusions Composite Objects Simple Composite Objects Dynamic Sequences Underlying Type Conclusions Afterward Mathematical Notation Programming Language Language Definition Maros and Trait Structures Bibliography Index A truly foundational book on the discipline of generic programming reveals how to write better software by mastering the development of abstract components. The authors show programmers how to use mathematics to compose reliable algorithms from components, and to design effective interfaces between algorithms and data structures A mathematically oriented approach to practical programming with an emphasis on abstraction via mathematical generalizations.