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

2 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 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

3 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, 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.

4 Our publisher decided against further print-ings and has reverted the rights to us. 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.

5 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. Only by readingthe code, proving the lemmas, and doing the exercises can readers gainunderstanding of the material.

6 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].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.

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

8 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].5. The code in the book compiles and runs under Microsoft Visual C++ 9 and g++ code, together with a few trivial macros that enable it to compile, as well as unittests, can be downloaded from ideas. Both Dave and Bjarne were kind enough to come to San Joseand carefully review the preliminary draft.

9 Sean Parent and Bjarne Strous-trup wrote the appendix defining the C++ subset used in the book. JonBrandt reviewed multiple drafts of the book. John Wilkinson carefully readthe final manuscript, providing innumerable valuable book has benefited significantly from the contributions of our editor,Peter Gordon, our project editor, Elizabeth Ryan, our copy editor, EvelynPyle, and the editorial reviewers: Matt Austern, Andrew Koenig, DavidMusser, Arch Robison, Jerry Schwarz, Jeremy Siek, and John thank all the students who took the course at Adobe and an earliercourse at SGI for their suggestions. We hope we succeeded in weaving thematerial from these courses into a coherent whole. We are grateful for com-ments from Dave Abrahams, Andrei Alexandrescu, Konstantine Arkoudas,John Banning, Hans Boehm, Angelo Borsotti, Jim Dehnert, John DeTre-ville, Boris Fomitchev, Kevlin Henney, Jussi Ketonen, Karl Malbrain, MatMarcus, Larry Masinter, Dave Parent, Dmitry Polukhin, Jon Reid, MarkRuzon, Geoff Scott, David Simons, Anna Stepanov, Tony Van Eerd, WalterVannini, Tim Winkler, and Oleg thank John Banning, Bob English, Steven Gratton, Max Hailperin,Eugene Kirpichov, Alexei Nekrassov, Mark Ruzon, and Hao Song for findingerrors in the first printing.

10 We thank Foster Brereton, Gabriel Dos Reis,Ryan Ernst, Abraham Sebastian, Mike Spertus, Henning Thielemann, andCarla Villoria Burgazzi for finding errors in the second printing. We thankShinji Dosaka, Ryan Ernst, Steven Gratton, and Abraham Sebastian forfinding errors in the third printing. We thank Matt Austern, Robert JanHarteveld, Daniel Kr ugler, Volker Lukas, Veljko Miljanic, Doug Morgan,Jeremy Murphy, Qiu Zongyan, Mark Ruzon, Yoshiki Shibata, Sean Silva,Andrej Sprogar, Mitsutaka Takeda, Stefan Vargyas, and Guilliam Xavier forfinding errors in the (third and) fourth printing. We thank Jeremy Murphy,Robert Southee, and Yutaka Tsutano for finding errors in the sixth printing,and Fernando Pelliccioni for proofreading the Authors , we are grateful to all the people who taught us through theirwritings or in person and to the institutions that allowed us to deepen ourunderstanding of See for the up-to-date 1 FoundationsStarting with a brief taxonomy of ideas, we introduce notions ofvalue,object,type,procedure, andconceptthat represent different categories ofideas in the computer.