Elements of Programming

by Stepanov, Alexander A.; McJones, Paul

• ISBN13: 9780321635372
• ISBN10: 032163537X
• Edition: 1st
• Format: Hardcover
• Copyright: 2009-06-09
• Publisher: Addison-Wesley Professional

Summary

New techniques for building more secure, reliable, high-performance software, from the renowned creator of the C++ STL- A truly foundational book on the discipline of generic programming: how to write better software by mastering the development of abstract components.- Based on Alexander Stepanov's breakthrough lectures to programmers at Adobe and throughout Silicon Valley.- For serious software developers, architects, and engineers, the perfect complement to Knuth's theory and Stoustrup's practice. Elements of Programming is the next breakthrough book for serious practitioners seeking ways to write better software. In this book, Alexander Stepanov - the legendary architect and creator of the C++ Standard Template Libraries - focuses on the discipline that offers the greatest potential for improving contemporary software: the proper development of abstract components. Drawing on his enormously popular lectures to programmers at Adobe and throughout Silicon Valley, Stepanov illuminates crucial techniques of generic programming, specifically focusing on abstraction as the key to secure, reliable, and high-performance software. Together with co-author and ACM Fellow Paul McJones, Stepanov shows programmers how to use mathematics to compose reliable algorithms from components, and to design effective interfaces between algorithms and data structures. Topics covered in Elements of Programming include: transformations, associative operations, linear orderings, ordered algebraic structures, iterators, coordinates and coordinate structures, copying algorithms, rearrangement, sorting, and much more. This book requires an understanding of mathematics, but is consistently focused on identifying superior solutions to practical programming problems. Stepanov and McJones illuminate their concepts and techniques with C++ code, but the techniques are equally applicable to a wide range of contemporary object-oriented languages.

Author Biography

Alexander Stepanov studied mathematics at Moscow State University from 1967 to 1972. He has been programming since 1972: first in the Soviet Union and, after emigrating in 1977, in the United States. He has programmed operating systems, programming tools, compilers, and libraries. His work on foundations of programming has been supported by GE, Brooklyn Polytechnic, AT&T,HP, SGI, and, since 2002, Adobe. In 1995 he received the Dr. Dobb’s Journal Excellence in Programming Award for the design of the C++ Standard Template Library.

Paul McJones studied engineering mathematics at the University of California, Berkeley, from 1967 to 1971. He has been programming since 1967 in the areas of operating systems, programming environments, transaction processing systems, and enterprise and consumer applications. He has been employed by the University of California, IBM, Xerox, Tandem, DEC, and, since 2003, Adobe. In 1982 he and his coauthors received the ACM Programming Systems and Languages Paper Award for their paper “The Recovery Manager of the System R Database Manager.”

Table of Contents

Preface	p. ix
About the Authors	p. xiii
Foundations	p. 1
Categories of Ideas: Entity, Species, Genus	p. 1
Values	p. 2
Objects	p. 4
Procedures	p. 6
Regular Types	p. 6
Regular Procedures	p. 8
Concepts	p. 10
Conclusions	p. 14
Transformations and Their Orbits	p. 15
Transformations	p. 15
Orbits	p. 18
Collision Point	p. 21
Measuring Orbit Sizes	p. 27
Actions	p. 28
Conclusions	p. 29
Associative Operations	p. 31
Associativity	p. 31
Computing Powers	p. 33
Program Transformations	p. 35
Special-Case Procedures	p. 39
Parameterizing Algorithms	p. 42
Linear Recurrences	p. 43
Accumulation Procedures	p. 46
Conclusions	p. 47
Linear Orderings	p. 49
Classification of Relations	p. 49
Total and Weak Orderings	p. 51
Order Selection	p. 52
Natural Total Ordering	p. 61
Clusters of Derived Procedures	p. 62
Extending Order-Selection Procedures	p. 63
Conclusions	p. 63
Ordered Algebraic Structures	p. 65
Basic Algebraic Structures	p. 65
Ordered Algebraic Structures	p. 70
Remainder	p. 71
Greatest Common Divisor	p. 76
Generalizing gcd	p. 79
Stein gcd	p. 81
Quotient	p. 81
Quotient and Remainder for Negative Quantities	p. 83
Concepts and Their Models	p. 85
Computer Integer Types	p. 87
Conclusions	p. 88
Iterators	p. 89
Readability	p. 89
Iterators	p. 90
Ranges	p. 92
Readable Ranges	p. 95
Increasing Ranges	p. 103
Forward Iterators	p. 106
Indexed Iterators	p. 110
Bidirectional Iterators	p. 111
Random-Access Iterators	p. 113
Conclusions	p. 114
Coordinate Structures	p. 115
Bifurcate Coordinates	p. 115
Bidirectional Bifurcate Coordinates	p. 119
Coordinate Structures	p. 124
Isomorphism, Equivalence, and Ordering	p. 124
Conclusions	p. 131
Coordinates with Mutable Successors	p. 133
Linked Iterators	p. 133
Link Rearrangements	p. 134
Applications of Link Rearrangements	p. 140
Linked Bifurcate Coordinates	p. 143
Conclusions	p. 148
Copying	p. 149
Writability	p. 149
Position-Based Copying	p. 151
Predicate-Based Copying	p. 157
Swapping Ranges	p. 164
Conclusions	p. 168
Rearrangements	p. 169
Permutations	p. 169
Rearrangements	p. 172
Reverse Algorithms	p. 174
Rotate Algorithms	p. 178
Algorithm Selection	p. 186
Conclusions	p. 189
Partition and Merging	p. 191
Partition	p. 191
Balanced Reduction	p. 198
Merging	p. 202
Conclusions	p. 208
Composite Objects	p. 209
Simple Composite Objects	p. 209
Dynamic Sequences	p. 216
Underlying Type	p. 222
Conclusions	p. 225
Afterword	p. 227
Mathematical Notation	p. 231
Programming Language	p. 233
Language Definition	p. 233
Macros and Trait Structures	p. 240
Bibliography	p. 243
Index	p. 247
Table of Contents provided by Ingram. All Rights Reserved.