Elements of Programming

1 Elements of ProgrammingElements of ProgrammingAlexander StepanovPaul McJones(ab)c=a(bc)Semigroup PressPalo Alto Mountain ViewMany of the designations used by manufacturers and sellers to distinguish theirproducts are claimed as trademarks. Where those designations appear in this book, andthe publisher was aware of a trademark claim, the designations have been printed withinitial capital letters or in all authors and publisher have taken care in the preparation of this book, but make noexpressed or implied warranty of any kind and assume no responsibility for errors oromissions. No liability is assumed for incidental or consequential damages in connectionwith or arising out of the use of the information or programs contained 2009 Pearson Education, Copyrightc 2019 Alexander Stepanov and Paul McJonesAll rights reserved.

2 Printed in the United States of America. This publication isprotected by copyright, and permission must be obtained from the publisher prior toany prohibited reproduction, storage in a retrieval system, or transmission in any formor by any means, electronic, mechanical, photocopying, recording, or likewise. Forinformation regarding permissions, request forms and the appropriate contacts withinthe Pearson Education Global Rights & Permissions Department, please : 978-0-578-22214-1 First printing, June 2019 ContentsPreface to Authors EditionixPrefacexi1 Categories of Ideas: Entity, Species, Genus Values Objects Procedures Regular Types Regular Procedures Concepts Conclusions 142 Transformations and Their Transformations Orbits Collision Point Measuring Orbit Sizes Actions Conclusions 283 Associative Associativity Computing Powers Program Transformations Special-Case Procedures Parameterizing Algorithms Linear Recurrences Accumulation Procedures Conclusions 454 Linear Classification of Relations Total and Weak Orderings Order Selection Natural Total

3 Ordering Clusters of Derived Procedures Extending Order-Selection Procedures Conclusions 615 Ordered Algebraic 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 856 Readability Iterators Ranges Readable Ranges Increasing Ranges Forward Iterators Indexed Iterators Bidirectional Iterators Random-Access Iterators Conclusions 111 Contentsvii7 Coordinate Bifurcate Coordinates Bidirectional Bifurcate Coordinates Coordinate Structures Isomorphism, Equivalence.

4 And Ordering Conclusions 1298 Coordinates with Mutable Linked Iterators Link Rearrangement Applications of Link Rearrangements Linked Bifurcate Coordinates Conclusions 1469 Writability Position-Based Copying Predicate-Based Copying Swapping Ranges Conclusions 16610 Permutations Rearrangements Reverse Algorithms Rotate Algorithms Algorithm Selection Conclusions 18711 Partition and Partition Balanced Reduction Merging Conclusions 20512 Composite Simple Composite Objects Dynamic Sequences Underlying Type Conclusions 223viiiContentsAfterword225A Mathematical Notation229B Programming Language Definition Macros and Trait Structures 238 Bibliography241 Index247 Preface toAuthors EditionAfter ten years in print, our publisher decided against further print-ings and has reverted the rights to us.

5 We have decided to publishEl-ements of Programmingin two forms: a free PDF and a paperback; book is now typeset by us using LATEX, and the text includes cor-rections for all errata reported to us from previous printings (see the Ac-knowledgments). We will attempt to apply corrections have made no changes other than these corrections, and do not expectto do so in the future. Readers may be interested in this additional bookon the same subject:From Mathematics to Generic Programmingby Alexander A. Stepanov and Daniel E. RoseAddison-Wesley Professional, 2014ixPrefaceThis book applies the deductive method to Programming by affiliatingprograms with the abstract mathematical theories that enable them to of these theories, algorithms written in terms of these theories,and theorems and lemmas describing their properties are presented implementation of the algorithms in a real Programming language iscentral to the book.

6 While the specifications, which are addressed to humanbeings, should, and even must, combine rigor with appropriate informality,the code, which is addressed to the computer, must be absolutely preciseeven while being with other areas of science and engineering, the appropriate founda-tion of Programming is the deductive method. It facilitates the decompo-sition of complex systems into components with mathematically specifiedbehavior. That, in turn, is a necessary precondition for designing efficient,reliable, secure, and economical book is addressed to those who want a deeper understanding of pro-gramming, whether they are full-time software developers, or scientists andengineers for whom Programming is an important part of their book is intended to be read from beginning to end.

7 Only by readingthe code, proving the lemmas, and doing the exercises can readers gainunderstanding of the material. In addition, we suggest several projects,some open-ended. While the book is terse, a careful reader will eventuallysee the connections between its parts and the reasons for our choice ofmaterial. Discovering the architectural principles of the book should be thereader s assume an ability to do elementary algebraic assume familiarity with the basic vocabulary of logic and set theory1. For a refresher on elementary algebra, we recommend Chrystal [1904].

8 XixiiPrefaceat the level of undergraduate courses on discrete mathematics; Appendix Asummarizes the notation that we use. We provide definitions of a few con-cepts of abstract algebra when they are needed to specify algorithms. Weassume Programming maturity and understanding of computer architecture2and fundamental algorithms and data chose C++ because it combines powerful abstraction facilities withfaithful representation of the underlying use a small subsetof the language and write requirements as structured comments. We hopethat readers not already familiar with C++ are able to follow the book. Ap-pendix B specifies the subset of the language used in the is a difference between mathematical notation and C++, the typeset-ting and the context determine whether the mathematical or C++ meaningapplies.

9 While many concepts and programs in the book have parallels inSTL (the C++ Standard Template Library), the book departs from some ofthe STL design decisions. The book also ignores issues that a real library,such as STL, has to address: namespaces, visibility, inline directives, and 1 describes values, objects, types, procedures, and 2 5 describe algorithms on algebraic structures, such as semi-groups and totally ordered sets. Chapters 6 11 describe algorithms on ab-stractions of memory. Chapter 12 describes objects containing other ob-jects. The afterword presents our reflections on the approach presented bythe are grateful to Adobe Systems and its management for supporting theFoundations of Programming course and this book, which grew out of it.

10 Inparticular, Greg Gilley initiated the course and suggested writing the book;Dave Story and then Bill Hensler provided unwavering support. Finally,the book would not have been possible without Sean Parent s enlightenedmanagement and continuous scrutiny of the code and the text. The ideas inthe book stem from our close collaboration, spanning almost three decades,with Dave Musser. Bjarne Stroustrup deliberately evolved C++ to support2. We recommend Patterson and Hennessy [2007].3. For a selective but incisive introduction to algorithms and data structures, we recom-mend Tarjan [1983].4. The standard reference is Stroustrup [2000].