Elements of Programmnig

Book Review: Elements of Programming

The C++ STL may be the most impressive achievement in language standard libraries. Where most programmers are stuck complaining that their language’s default strings aren’t performant enough, about every standard C++ function for strings actually runs on arbitrary character sequences. Design your own container? std::find_if works just as well as for the built-ins. And it does this while often being more performant than the code you’d write yourself.

Alex Stepanov is the man who made this happen, and Elements of Programming (EOP) is his 200-page paean to his method for writing generic code. He’s a believer that programming can be turned from an art to a rigorous discipline based on mathematics, and I’ve long admired him for his deep knowledge and impact. Indeed, he’s spent years at #1 on my list of people I’d like to have lunch with. (Hey readers — can anyone help?)

And now, I’m about to ruin all that by writing a negative review.

EOP has a strong beginning and a strong finish. The first chapter explains core programming language concepts such as types and state — using non-standard terminology, but probably intentionally, judging by the explanation’s lucidity. This culminates in his big idea of being able to write programs on any type that offers a bundle of operations and properties called a concept, explained in this book over a decade before they entered the C++ standard. The afterword is a few pages of reflection on the power of this approach.

Between them is 11 chapters where he plays the same game: define a new abstraction and then show a bunch of functions that can be written using it. And unfortunately, these functions and abstractions are largely not very interesting.

There’s a famous site called Project Euler, where users write code to solve mathy problems such as “In a modified version of the board game Monopoly, on what three squares is a player most likely to land?” My former programming-contest coach advocated against using it to practice, because “It’s not really programming, and it’s not really math.”

I think this is an apt description of EOP, particularly the first half. This starts from Chapter 2, which is about cool algorithms that involve applying some function to itself repeatedly (iteration). One of my favorite lectures in undergrad was on this topic, and yet I still couldn’t enjoy this chapter, as I know no application of these algorithms outside of niche mathematical topics. This gets taken up another notch in Chapter 5, where, in about 5 pages, he goes from explaining commutativity to defining the algebraic structures of monoids, groups, and rings, all the way up to algebraic modules (no relation to software modules). I cannot fathom these explanations being useful to someone who does not already know these concepts, and certainly not to someone who already does. And while I do know many uses of groups in software engineering — as an abstraction of the idea of an invertible operation — he actually spends the remainder of this chapter considering generalizations of the greatest common divisor function.

I slogged through these chapters, excited for the second half of the book, which focused largely on iterators and containers, things more relevant to typical software engineering. Yet after encountering endless listings of variations of list-copy functions, I found myself no more fulfilled, and soon regressed to skimming through the pages.

Aside from my long-term goal to find all the good writing on software design, I had a short-term goal when reading this book: a student wanted me to teach a lesson based on it. But, halfway through the book, my deadline was fast approaching, and I hadn’t found any material useful enough for a software design lesson for experienced engineers.

I then noticed all the chapters were generated by the deeper principle of coming up with a good abstraction to write generic functions against. I got the idea that maybe I could use EOP as a problem book, telling them to look at the descriptions of generic functions, and then come up with both the code and the abstractions they can be written against. Alas, the topic selection is not suitable for this purpose. One section of the book, for example, deals with computing integer sequences by matrix exponentiation. Asking students to come up with this themselves would be too familiar for many who have taken a linear algebra course, and impossible for those who haven’t. I did design a lesson where students come up with their own abstractions for generic programming problems, but I used examples completely unrelated to the book.

I asked the friend who recommended EOP what he got out of the book, and his first answer was a technique for elegantly expressing state machines using goto’s. I similarly loved that part, but, alas, that was the only concrete thing I got out of this book. I’ll explain it at the end of this review and spare you the other 200 pages.

I have an undergraduate degree in mathematics and have authored several papers on generic programming, so I knew I was reading it for others’ benefit. Still, I don’t think my opinion would be changed were this not the case, and I’d really like help understanding the viewpoint of the many readers who did thoroughly enjoy it. Instead, I find myself agreeing with this Amazon reviewer, although I have too much admiration for Stepanov to contemplate a 1-star rating:

If you've ever written a generic function, you already know that the type parameters must obey a set of preconditions. This book lays out a big pile of definitions for types, numbers, algebraic structures, iterators, and such, so as to bamboozle people easily impressed by mathematical notation. It does so sloppily and writes some trivial generic algorithms in C++. To whatever extent one might accomplish something interesting with this topic, this book doesn't. Avoid.

As I read other material by Stepanov, I mourn for the book that could have been. Stepanov clearly cares about these abstractions and algorithms, to the point where he wrote a second book on largely the same material, with a chattier exposition and chapters more explicitly focusing on pure math. How different would it be had he managed to transmit this appreciation to me? The day after finishing, I watched this talk by a close colleague of Stepanov. “In this menu, you can select a bunch of rows and drag them somewhere else,” he explained over animated slides. “How many of you could implement this in one line?” It made me want to open section 10.4 on “rotation algorithms” again.

I’ve started watching a seminar he gave at Amazon. I’m only a few lectures in, but I’m already enthralled by his high teaching ability. I feel like I’m there with him working through problems. I feel like I’ve learned a great secret as he tells the story of how he invented “regular types,” something used throughout EOP but never motivated. To be honest, I still don’t know what this lecture series is about, but nonetheless expect to recommend it when I’m done.

In short, Stepanov has given many gifts to the world of programming, and EOP is not one of them.

Overall rating: Not recommended

With a smattering of exceptions, EOP neither teaches abstractions useful in everyday programming, nor teaches you the skills to invent your own.

Addendum: State machines by goto’s

“The fastest way to go from one place in code to another is goto.”

—

Alexander Stepanov

Many iterative algorithms can be described as state machines: first it looks for an X, then it does Y with it, then it looks for another X, and so on. Rather than trying to massage the cycles in the state machine into structured loops, Stepanov advocates a style using goto’s, with one goto-label per machine state.

In searching for an example to best illustrate this, I wanted something where the code was under 40 lines (which ruled out Stepanov’s examples), understandable with little context or knowledge of C++, and which was not equivalent to a regular expression. And so:

In my defunctionalization talk, I showed that many state machines are derived from recursive functions, being turned into iterative traversals by creating a state for each point in the program between recursive calls. For that talk, I demonstrated this in full for the example of printing a binary tree. It turns out that adding parentheses makes this derivation substantially harder, as an arbitrary number of close-parentheses may need to be printed after processing a node. And that difficulty comes from trying to massage a state machine into a loop.

In this case, seeing as I came up with this example by starring with a recursive function, the recursive version is quite simple:

void print_tree_rec(tree *t) {
  if (t != NULL) {
    printf("(");
    print_tree_rec(t->left);
    printf(" %d ", t->element);
    print_tree_rec(t->right);
    printf(")");
  }
}

But, for other state machines, the recursive version is not so easy. For example, Dijkstra created the “shunting yard” algorithm for parsing an arithmetic expression all the way back in 1961, yet I’m not aware of the recursive equivalent being discovered until 2007, using the technique of refunctionalization.

Here’s the state machine:

A confession: the first time I thought about how to make this recursive function function iterative, I didn’t get it, and had to look it up. The solution is to merge the “Next from stack” state in the diagram with its successors, resulting in a solution with two nested while-loops, at the cost of some duplicated code.

However, the version based on goto’s reads off this diagram rather nicely. One C++-ism in this code to note: while the stack s is initialized to NULL, the push() and pop() calls can actually change it.

void print_tree(tree *t) {
  tree *cur = t;
  stack *s = NULL;
  
begin_print_node:
  if (cur == NULL) {
    goto dispatch_stack_frame;
  } else {
    printf("(");
    push(LEFT_CHILD, cur, s);
    cur = cur->left;
    goto begin_print_node;
  }
  
print_element:
  printf(" %d ", cur->element);
  push(RIGHT_CHILD, cur, s);
  cur = cur->right;
  goto begin_print_node;
    
finish_print_node:
  printf(")");
  goto dispatch_stack_frame;

dispatch_stack_frame:
  std::pair<DIR, tree*> top_frame;
  if (s == NULL) goto end;
    
  top_frame = pop(s);
  cur = top_frame.second;
  if (top_frame.first == LEFT_CHILD)
    goto print_element;
  else
    goto finish_print_node;
  
  
end:
  return;
}

For the full code, including data declarations, go here

Neither I nor the friend who recommended this book have had a chance to use this technique since reading it. But for the times when you are implementing a state machine, it can be a nice trick — and a delightful surprise for those who grew up learning "Goto Considered Harmful."

Further reading: http://www.cs.rpi.edu/~musser/gsd/notes-on-programming-2006-10-13.pdf, page 191

Update: Reader Greg Jorgensen writes in to share an article he saved on this topic from the Computer Language magazine in 1991. "I’ve written a few FSMs in this style with successful results. One of them is still in use in the guts of a graphics terminal emulation program. That emulator is still used at big companies like British Telecom." Article

from Hacker News https://ift.tt/2HHTwp8