Elements of Programming
- By Alexander Stepanov, Paul McJones
- Published Jun 9, 2009 by Addison-Wesley Professional.
- Copyright 2009
- Dimensions: 6-3/8x9-1/8
- Pages: 288
- Edition: 1st
- ISBN-10: 0-321-63537-X
- ISBN-13: 978-0-321-63537-2
- eBook (Adobe DRM)
- ISBN-10: 0-321-64389-5
- ISBN-13: 978-0-321-64389-6
Register your product to gain access to bonus material or receive a coupon.
Product Author Bios
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.”
“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.
Please visit the author's site at elementsofprogramming.com.
68 of 69 people found the following review helpful
An Abstract Algebra of Programs,
This review is from: Elements of Programming (Hardcover)"I believe that iterator theories are as central to Computer Science as theories of rings or Banach spaces are central to Mathematics. Every time I would look at an algorithm I would try to find a structure on which it is defined. So what I wanted to do was to describe algorithms generically. That's what I like to do. I can spend a month working on a well known algorithm trying to find its generic representation. So far, I have been singularly unsuccessful in explaining to people that this is an important activity. But, somehow, the result of the activity - STL - became quite successful." -Stepanov
I had been waiting for this book for a while, as I greatly enjoy Stepanov's unorthodox views on programming. His flat rejection of the object-oriented paradigm was what caught my attention, but he differed from the unwashed newsgroup naysayers in an important respspect -- he offered an alternative. The fact that his alternative seemed to involve applying concepts from the... Read more
113 of 121 people found the following review helpful
A great book,
This review is from: Elements of Programming (Hardcover)I have been wondering what to say about this book and now Peter G. Neumann said it better (see previous review). However, I can still say this: There are many good books, but few great ones. "Elements" is a great book in that it can change the way you think about programming in fundamental ways: If you "get it" programming will never be the same again for you.
Reading "Elements" requires maturity both with mathematics and with software development. Even then it is so different from most books on programming that it can be hard going. The frequent comparisons of "Elements" to Knuth's "The Art of Programming" is well earned.
36 of 40 people found the following review helpful
Does not cover new ground,
This review is from: Elements of Programming (Hardcover)I was really looking forward to reading this book. Now that I'm done proving nearly all the lemmas the reader is asked work out, I have to admit to reading it with gritted teeth and what is best described as nearly constant annoyance. I will say that the subjects covered here are important and carefully chosen. The authors are undeniably passionate about the content, and they definitely know more about writing good programs than I will ever learn (particularly when said programs are written in C++). So what was it that rubbed me the wrong way?
Basically, I could not help but feel like I was re-reading old and very good ideas from the 1970's about writing provably correct and reusable programs. The book often combines these with algebraic structures to produce efficient and reusable C++ code that is as general as possible. It does all this quite well, though it's a bit like being hit on your head with a sledgehammer at times. The code here is hardly beautiful, but on the... Read more
› See all 18 customer reviews...
Online Sample Chapter
Table of Contents
About the Authors xiii
Chapter 1: Foundations 1
1.1 Categories of Ideas: Entity, Species, Genus 1
1.2 Values 2
1.3 Objects 4
1.4 Procedures 6
1.5 Regular Types 6
1.6 Regular Procedures 8
1.7 Concepts 10
1.8 Conclusions 14
Chapter 2: Transformations and Their Orbits 15
2.1 Transformations 15
2.2 Orbits 18
2.3 Collision Point 21
2.4 Measuring Orbit Sizes 27
2.5 Actions 28
2.6 Conclusions 29
Chapter 3: Associative Operations 31
3.1 Associativity 31
3.2 Computing Powers 33
3.3 Program Transformations 35
3.4 Special-Case Procedures 39
3.5 Parameterizing Algorithms 42
3.6 Linear Recurrences 43
3.7 Accumulation Procedures 46
3.8 Conclusions 47
Chapter 4: Linear Orderings 49
4.1 Classification of Relations 49
4.2 Total and Weak Orderings 51
4.3 Order Selection 52
4.4 Natural Total Ordering 61
4.5 Clusters of Derived Procedures 62
4.6 Extending Order-Selection Procedures 63
4.7 Conclusions 63
Chapter 5: Ordered Algebraic Structures 65
5.1 Basic Algebraic Structures 65
5.2 Ordered Algebraic Structures 70
5.3 Remainder 71
5.4 Greatest Common Divisor 76
5.5 Generalizing gcd 79
5.6 Stein gcd 81
5.7 Quotient 81
5.8 Quotient and Remainder for Negative Quantities 83
5.9 Concepts and Their Models 85
5.10 Computer Integer Types 87
5.11 Conclusions 88
Chapter 6: Iterators 89
6.1 Readability 89
6.2 Iterators 90
6.3 Ranges 92
6.4 Readable Ranges 95
6.5 Increasing Ranges 103
6.6 Forward Iterators 106
6.7 Indexed Iterators 110
6.8 Bidirectional Iterators 111
6.9 Random-Access Iterators 113
6.10 Conclusions 114
Chapter 7: Coordinate Structures 115
7.1 Bifurcate Coordinates 115
7.2 Bidirectional Bifurcate Coordinates 119
7.3 Coordinate Structures 124
7.4 Isomorphism, Equivalence, and Ordering 124
7.5 Conclusions 131
Chapter 8: Coordinates with Mutable Successors 133
8.1 Linked Iterators 133
8.2 Link Rearrangements 134
8.3 Applications of Link Rearrangements 140
8.4 Linked Bifurcate Coordinates 143
8.5 Conclusions 148
Chapter 9: Copying 149
9.1 Writability 149
9.2 Position-Based Copying 151
9.3 Predicate-Based Copying 157
9.4 Swapping Ranges 164
9.5 Conclusions 168
Chapter 10: Rearrangements 169
10.1 Permutations 169
10.2 Rearrangements 172
10.3 Reverse Algorithms 174
10.4 Rotate Algorithms 178
10.5 Algorithm Selection 186
10.6 Conclusions 189
Chapter 11: Partition and Merging 191
11.1 Partition 191
11.2 Balanced Reduction 198
11.3 Merging 202
11.4 Conclusions 208
Chapter 12: Composite Objects 209
12.1 Simple Composite Objects 209
12.2 Dynamic Sequences 216
12.3 Underlying Type 222
12.4 Conclusions 225
Appendix A: Mathematical Notation 231
Appendix B: Programming Language 233
B.1 Language Definition 233
B.2 Macros and Trait Structures 240
Download the sample pages (includes Chapter 2 and Index)
Please download the errata at http://www.elementsofprogramming.com/eop-errata.pdf.
This book includes free shipping!
This book includes free shipping!
eBook (Adobe DRM)
This eBook requires the free Adobe® Digital Editions software.
Before downloading this DRM-encrypted PDF, be sure to:
- Install the free Adobe Digital Editions software on your machine. Adobe Digital Editions only works on Macintosh and Windows, and requires the Adobe Flash Player. Please see the official system requirements.
- Authorize your copy of Adobe Digital Editions using your Adobe ID. If you don't already have an Adobe ID, you can create one here.
Get access to thousands of books and training videos about technology, professional development and digital media from more than 40 leading publishers, including Addison-Wesley, Prentice Hall, Cisco Press, IBM Press, O'Reilly Media, Wrox, Apress, and many more. If you continue your subscription after your 30-day trial, you can receive 30% off a monthly subscription to the Safari Library for up to 12 months. That's a total savings of $199.