Elements of Programming

Because Ralabate's review covers the most important points, this review should be read as supplemental to it. First, the book makes substantial contributions towards regularizing the terminology of algorithm design and analysis. Concepts like regularity, transformation, accumulation and ordering that are treated as notional in most other presentations of the material are here given rigorous formalization. This matters because understanding whether a type or procedure is regular (chapter 1) helps explain the availability of the different types of iterator definable against it (chapter 6). Likewise, understanding which algebraic structures are available against the input to an algorithm (chapter 5) can clarify both the boundary cases to the algorithm and the avenues open for its optimization. Second, because early chapters introduce terminology on which the later chapters build, the book should be read in order. (This point is made in the preface, but bears repeating here.) Chapters, and the examples they contain, are short and relatively easy to accomplish in a sitting or two, which makes sequential reading straightforward. (The exceptions to this are project suggestions, which require a different level of attention but which can be skipped working from chapter to chapter.) Third, the math on which Stepanov and McJones rely will be familiar to second- or third-year CS or engineering undergrads. Examples are taken from set theory, matrices and the foundations of abstract algebra (groups and rings); advanced understanding of continuous mathematics is not assumed. (Willingness to work out examples with pencil and paper still important, however.) Fourth, the subset of C++ in which the examples in the book are presented should embolden, rather than discourage, developers working primarily in other languages. With the exception of the templating instructions that wrap each of the examples, there's nothing particularly C++-ish in the examples. The examples are kept short and they read at least as well as any sort of pseudocode that might have been devised as an alternative. (No problems coming from recent work done primarily in Python, for example.) Fifth, antagonism between the type of algorithm analysis presented here and the fundamentals of object orientation is misguided. Among very many other things, object orientation affords a type of systems design oriented in terms of *things*. How should data and methods be bundled? Which parts of the system need to be exposed and which encapsulated? Is functionality best acquired through inheritance or aggregation? The type of analysis that Stepanov and McJones provide operates at what is arguably more fundamental a level. How are assumptions of regularity related to optimization? When is special-case optimization warranted? To get a feeling for this, read chapter two on what happens in the repeated application of a transformation to its own output. The code and presentation of the material demonstrate

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.

What could be one of the most important books for developers of low-risk systems has come to my attention, and deserves your consideration if you are serious about understanding the mathematical foundations of programming and applying them sensibly to your practice. It is not an easy read, but it is a very compelling approach. To support its mathematically oriented crispness, the book includes the definition of a small but elegant C++ subset that has been crafted by Sean Parent and Bjarne Stroustrup for illustrative use in the book. I believe this material should be taught within all computer science curricula. A long quote and a short one on the back jacket give an idea of what is involved: 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 The bottom of the inside cover suggests that through this book you will come to understand that mathematics is good for programming, and theory is good for practice. I applaud that sentiment.

"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 realm of abstract algebra to computer programming made me realize I would be spending a lot of time and thought catching up. This is a short, but dense book. There is little trace of Knuth's sympathetic humor or Dijkstra's aesthetic passion. The material is presented as a series of definitions and sample programs, written in a programming language based on C++. Importantly, there are also exercises and projects throughout each chapter. At first attempt, these puzzlers seem to contain as much insight as the prose itself. I look at this book as a combination of the two books that Stepanov is known to prescribe to his students, hyper-distilled into a slim few hundred pages: "The books that I recommend to my students are The Art of Computer Programming by Donald Knuth, which is the great encyclopedia of programming techniques. ... It is something that they should keep studying for the rest of their lives. The other book that I urge my students to read is The Textbook of Algebra by George Chrystal. It is a massive two volume work covering most of elementary algebra. Sadly enough, nowadays even people with graduate degrees in Mathematics do not know most of the material in Chrystal." More to the point, I look at this book as an intentional challenge. The preface urges the reader to consider why the material absent is absent and vice versa, a sentiment I had only seen in one other place -- Victor Vyssotsky's review of MacLane and Birkhoff. A challenge like that doesn't make for a pleasant exposition, seemingly trading approachability for a more mature understanding. Stepanov has some great papers in the public domain -- if you are reading this review I highly reccomend seeking them out. Also see the Google Tech Talk "A Possible Future of Software Development" by Sean Parent. If you like those, you will love this.

Did you study differential calculus? While not a prerequisite for this book, if you are the type who desires rigorous maths, you almost certainly have done so. There are two teaching methods for calculus. One uses the differential forms ("delta x", "delta y")) pioneered by Newton. While the other is stricter and uses the epsilon delta method and theorems. The former is favoured by scientists learning calculus, while mathematicians prefer the latter. This book is analogous to the latter, while the former can be represented by Knuth's Art of Computer Programming, The, Volumes 1-3 Boxed Set (2nd Edition) (The Art of Computer Programming Series) (Vol 1-3). Another point of difference is that Stepanov and McJones deal with the foundations of programming, while Knuth delves deeper into the algorithms. The approach in the book is not difficult to follow, unlike sections of Knuth which can get very intricate. More generally, you will rarely come across a book like this, which deals closely with theorems and lemmas and yet is also tied to actual code. One consequence however is that the audience may be somewhat exclusive (ie. limited). I can readily see a mathematician wandering into this book, to learn more about the basis of computer science. But the typical computer scientist, let alone a programmer, favours a more informal approach.