on July 15, 2009
"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.
on July 23, 2009
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.
on July 23, 2009
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
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.
on October 17, 2010
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 whole it was a reminder of why the C++ Standard Template Library was such a brilliant effort. However, at the end of every chapter I felt like the focus on C++ implementations limited the discussion about what the universal "elements of programming" are supposed to be. In particular, I would fault the book on not including any material on mathematically rigorous type inference systems that have been developed since the early 1980's, particularly because types are so central to what the book discusses, and since the book's errata online suggests the authors are dabbling with re-implementing all the code in Haskell.
The bibliographic references also suggested a certain arrogance (I cannot imagine it is ignorance): there are no references to the extensive literature on the formal verification of software. It is this tone that finally got to me, the insinuation that putting so-called software engineers on a formal mathematical foundation was something never attempted before this book was written! People have been doing it for over 40 years, but you wouldn't know it by looking at the bibliography.
In the end, whatever your programming background, if you really work through the text and solve the exercises you will definitely be better off than when you started. I know I'm glad I read it. But I'd be surprised if you really enjoyed it, or if you understood what "elements of programming" you should be looking for in your next software project (particularly if it is not written in C++).
After reading this book I had to ask myself if I would recommend earlier books that covered similar ground (which are missing from the bibliography in this book), like A Discipline of Programming or The Science of Programming (Monographs in Computer Science) (Volume 0), to a practicing programmer. In fact this book made me pull out my copy of Dijkstra's monograph and re-read it after nearly two decades. I have to say that A Discipline of Programming still impresses where this book comes across as, well, somewhat flat.
on January 13, 2010
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 a closed set of possibilities *regardless of the algorithm being investigated*, along with terminology and descriptors for each of the different cases. I find it hard to see how generalization can go much further than this, and the presentation of the material is a pleasure. (Maybe best to use chapter 2 as a litmus test, in fact, to see whether you want to work the book to completion.)
Last, the whole book can be read as a challenge. To what extent can the fundamentals of algorithm design be treated rigorously? It's probably reaching to draw a comparison to the situation before different parts of the math system were defined in terms of set theory, but, in some respects, that does seem to be where we are: many different, notional approaches to what it means to program, with decades' worth of best practices built up, but absent a series of definitions on which to anchor different types of programming work. Stepanov and McJones help take us at least a little bit closer to such a long-term goal.
on September 29, 2014
I used to think that there were two related fields: programming and
mathematics. I thought that while in the process of programming, I
might find myself doing some math like adding some numbers or
averaging something or even multiplying matrices. Likewise, I used to
think that while being mathematical, I might decide to write a program
that performed some mathematical calculations.
Then I encountered Dr. Alexander Stepanov's writings and lectures and the two fields will forever
be inextricably linked together. Moreover, I could not be more happy
with such a union.
Dr. Stepanov is the author of the Standard Template Library (STL) for
C++. Early in my career, I used to glance at the source code for the STL and it was so
beyond my understanding, that I just thought of it as a useful library
created by some guy at Silicon Graphics that frequently made our C++
compiler encounter internal errors (back in the early/mid 90s when
template support was being added to our Visual Cafe compiler). After
hearing Dr. Stepanov talk, reading his book "Elements of Programming",
and seeing how much thought he put into every single detail in the
STL, I'm convinced that there were only a few people on the planet who
could have done what he did with the care he did. And if there were
indeed a few, only one of them took on the immense effort of building
it. Now when I look at the STL, I see logic, efficiency, order, symmetry and most
of all beauty.
The two main resources I have found that have so impacted me are
Alexander's recorded classes he gave at Amazon
and the book "Elements of Programming" that Alexander co-authored with
Paul McJones. Both are amazing resources even if they take lots of
concentration and re-reading and/or re-viewing. The work has paid off
in gained understanding and enjoyment. I've never found myself smiling so
frequently when reading a technical book as I have while reading
"Elements of Programming".
Dr. Stepanov discusses three basic categories that types can belong to: Semi-Regular, Regular, and Totally Ordered. Depending on what categories your type belongs to, you can do different things with it. It's this foundation upon which Stepanov builds a beautiful
mathematical view of programming. He talks about set relations,
unary and binary operations, predicates, operation orbits, associative
operations, weak vs. total ordering, commutative operations, turning
linear operations into logarithmic operations, iterating over
collections, bifurcate coordinates (e.g. binary trees), permutations,
partitionings, balanced reduction, and many more topics.
Mathematics has such a rich collection of concepts and to be able to
apply them to programming gives you more tools with which to reason
about a program.
For those of you who considering watching his video lectures, Dr. Stepanov has developed his teaching style to a level where it is
entertaining, informative, challenging (he skillfully employs the
Socratic method), and well-structured. As brilliant as he is, he is
refreshingly humble when he talks about things he would have done
differently in the STL (e.g. making iterators totally ordered).
My only regret is that I found his book and videos this late in my
career. I'll make up for that by studying his books and videos twice
on December 21, 2010
Having gone through Alex's notes on his Adobe course on generic programming I was expecting a refinement of his introspective and historically well researched writing style when I picked up this book.
Unfortunately, Mr. McJones seems to have exerted some pressure on Alex to abandon his, in my opinion already "right" approach and replace it with the traditional mathematical exposition in terms of interchange of theorems and proofs. In my opinion this has robbed the book of most of its entertainment factor and to some extent of its didactic value as well.
As I've not read Euclid's Elements I really can't say if this book lives up to its name or not, but for what it's worth it does a very good job in laying out many of the mathematical principles that underly programming.
If you enjoy being challenged as a reader, then I believe you will like this book as it does an excellent job in that department and offers plenty of rewards for the persevering.
This little book is quite unusual among current publications on programming. It
supplies a mathematical definition of the various components of a programming language, working up from the simplest constructs. The book then works up to algorithms based on the mathematical rules that have been constructed, and asks the programmer to step back and think about why tasks are performed in a certain way. The preface makes the point of mentioning that no mechanical or electrical engineer would go about solving problems in the same haphazard way that many computer programmers solve problems, and this book's purpose is to apply mathematical reasoning to program construction.
The book does not stay in the realm of the theoretical, however. Algorithms are implemented in a real programming language - C++ - a language with which most all programmers are familiar. There are numerous open-ended projects for the reader to test his/her knowledge of the principles applied.
I see that the table of contents is already supplied in the product description so I'll just briefly summarize the chapter contents as mentioned in the preface: Chapter 1 describes values, objects, types, procedures, and concepts. Chapters 2-5 describe algorithms on algebraic structures, such as semigroups and totally ordered sets. Chapters 6-11 describe algorithms on abstractions of memory. Chapter 12 describes objects containing other objects. The afterword presents the authors' reflections on the approach presented by the book.
The authors also specifically outlines the prerequisite knowledge for the reader of this book. They assume a basic knowledge of algebra and a knowledge equivalent with an undergraduate course on discrete mathematics. They also programming maturity and hopefully familiarity with C++ as well as an understanding of computer architecture and fundamental algorithms and data structures.
If you are just looking for a book from which to extract some useful algorithms you should look elsewhere. If you are looking for a book that teaches you how to quantify, define, and evaluate a useful algorithm, this would be one of the newest books on that subject.
on September 9, 2011
This is literally the best book I have ever read on programming, even above and beyond Knuth or K&R. It will change how you think about programming.
It is tough to read: it assumes that you are already a good programmer, and you should also be familiar with C++'s template facility. But if you can make it through this book (at least sketching proofs for the lemmas and giving some thought to the exercises), it will solidify the instincts and idioms you have about programming into a solid conceptual whole that will turn you from a good programmer to a great programmer. You will have terminology to describe (and think about!) many concepts that appear over and over and over and over when programming but which many top-notch programmers only understand at a subconscious, "fuzzy" level, guided by their intuition rather than intelligent discernment.
This book is not about algorithms (although it contains many beautiful and efficient ones), it deals with how *the actual act of software construction* can be brought to a high level of sophistication. Huge parts of this book are *real* C++ code that works today on your C++ compiler (and is also available for download on the webpage for the book). This book is about how to build solid, working, efficient, robust, reusable, understandable code. If you have ever taken higher-level math courses, you will understand that in order to approach mathematics usefully and become a mathematician, you have to really get back down to the things that you took for granted and analyze them more rigorously. This is much the same, but for programming; you will learn how to iterate over elements in a sequence, how to traverse a tree, how to partition a range of elements (but now you will actually know how to characterize the ranges you operate on), how to ... etc. Many of these things will seem "trivial" at first glance to any programmer good enough to be reading this book, but looking back you will realize that when you coded these operations previously, you really had very little understanding about what you were actually doing and that now you have a conceptual framework where all of these actions fit into a broader whole that you are aware of.
If you are a good C or C++ programmer, do yourself the favor of reading this book, especially if you are a C++ programmer that has a knowledge of STL (note that the primary author of this book is Stepanov, the author of STL). Even though it deals entirely in C++, almost all of the concepts translate directly to C unchanged. Basically the only C++ functionality that is used in the book is templates, which merely make the code generic: you will find that concrete instantiations of all of the concepts in this book appear all over the place in C code. Like I said, this book deals with the fundamentals of the act of programming: things that at some level need to be understood by all competent programmers (in particular C and C++ programmers). Do yourself the favor of making your knowledge of these things conscious!
Note: If you are a fundamentalist of functional programming or object-oriented programming, you will probably get very little from this book.
on August 15, 2009
Stepanov and McJones have created an excellent description of the mappings from mathematics to computer science, and I recommend this book should be in the library of every programmer, software architect and software engineer. I especially appreciated the building of concepts from first principles, which helps in the logical understanding of the concepts in programming. In today's software, there is more than the traditional serial, digraph mappings, and I wish this had been given more explicit treatment - especially in the non-deterministic aspects of parallel computation. With that one small caveat, this is an excellent reference and wonderful treatment of the mathematics underlying computer software.