Programming Books, part 5: Programming Pearls

To my astonishment, I see that it’s been a whole year since the last  installment in the Programming Books series (1, Coders at Work; 2, The Elements of Programming Style; 3, Programming the Commodore 64; 4, The C Programming Language).  I got distracted.  But today I want to write about what I would judge the second best book on programming I’ve ever read: Jon Bentley’s Programming Pearls [amazon.com, amazon.co.uk]

I tried to write about this book once before, but I was distracted by what it has to say about binary search, and that ended up being a whole series of its own (part 3, part 4a, part 4b, part 4c).And that in itself is a testament to the quality of Jon Bentley’s 1986 classic, compiled from expanded and revised versions of his columns in Communications of the ACM.  It’s the kind of book where a smallish passage in a single chapter can send you spinning off into writing six-part series on techniques.  As I wrote about it the first time around:

There are some programming books that I’ve read from cover to cover repeatedly; there are others that I have dipped into many times, reading a chapter or so at a time.  Programming Pearls is a rare case where both of these are true.

So what makes it so good?  And how can a 1986 book be still relevant a full quarter-century later?  The answer to both questions is the same: it’s a book about thinking about programming.  In a world where we’re drowning in a flood of books that emphasise techniques (both good and bad), and specific programming technologies (both good and bad!), there are surprisingly few books about the kind of thought that needs to go into good work.  (My reaction to this trend is part of what inspired me to write, in Part 3 of the binary search series, that “You need to think.  There’s no way out of it.  Sometimes, no amount of agile, pattern-oriented, test-driven, refactoring-focussed pair-programming methodology will get you out of the responsibility to invest some actual thought into your program.  It’s not all just Move Method and Pull Up Instance Variable, you know.”)

So while it is a genuinely useful thing that Fowler has taught us how to automatically apply a broad selection of refactorings to our programs, the purpose of all that shuffling is really only to get the deck clear so we can concentrate properly on the hard bits without getting distracted by crud.  And when it gets to those hard bits, it’s books like Bentley’s that are going to help you.

So what’s in Programming Pearls?  A brief preface, then the meat of the book is thirteen chapters, allocated into three sections: Preliminaries (Cracking the Oyster, Aha! Algorithms, Data Structures Programs and Writing Correct Programs); Performance (Perspective on Performance, The Back of the Envelope, Algorithm Design Techniques, Code Tuning and Squeezing Space); and The Product (Sorting, Searching, Heaps and A Spelling Checker).  Each chapter comes with a set of Problems, a Further Reading list, and in many cases one or more sidebars containing summaries of relevant case studies.  At the end of the book comes an epilogue, an appendix that contains a Catalog of Algorithms, then both oblique hints and more detailed solutions to most of the problems.  Oh, and there is a comprehensive index — often a sign of a good quality book.

It’s unavoidable that in some respects a 25-year-old book is going to have dated.  Chapter 9, on Squeezing Space, certainly feels quaint now that we measure main-memory sizes in gigabytes and disks in terabytes.  But actually, aside from that one topic, It’s rather shocking to see how relevant all the same issues still are today as they were then.  The opening chapter’s emphasis is on how to cheat — spotting ways to solve a problem that’s easier than the general case, for example using the O(n) radix sort rather than an O(n log n) general-purpose sort, when constraints make it possible.  That kind of thinking around a problem — that constructive laziness — is as important now as it ever was.  Chapter 3’s theme, that getting a program’s data structures right leads to good code more often than the other way around, is if anything truer today than ever, with the near-ubiquity of object-oriented techniques.  Chapter 6 is another that encourages us to step back from problems before ploughing in, by doing simple order-of-magnitude calculations up front to determine whether a planned solution is reasonable or even possible.

And of course the backbone of the book, the main thread running through the great majority of the columns, is algorithm design: figuring out exactly what you want your program to do, how to make it do it, thinking through whether it’s going to work correctly and under what circumstances it might fail, considering its time and space requirements and how they can be improved, judging what data structures best support a given algorithm, and so on.  All absolutely timeless stuff.

All of this may sound rather Worthy But Dull — the kind of material that you study because you have to (either to pass an exam or because you need it for a real program), but in fact it’s anything but dull.  Bentley is a natural communicator, and his writing draws me into his ideas so skillfully that I hardly realise it’s happening.  I might dip into Programming Pearls intending to read a paragraph or two while I wait for the kettle to boil, only to realise an hour later that I’ve re-read the greater part of a chapter.  He has a rare knack of being able to write informally about formal subjects — getting his point across in an appealing way, but without losing any rigour.  Part of this is because pretty much every argument the book makes is based on, and emerges from, real-world examples.  It’s obvious that, while Bentley’s insight and style are the result of a serious academic understanding, he writes from a position on the factory floor — not as one researcher to another, but as a master craftsman to his peers.

Much of what’s covered in this book may be familiar to Computer Science graduates, but much will be new, and even the material that covers old ground looks at it from new and interesting perspectives.  And for young programmers, and those who have picked up a lot of real-world experience but never really studied theory, Programming Pearls will be an eye-opener and a delight.

So this is a whole-hearted Recommend.

Special Bonus Irrelevances

In case anyone in the UK has failed to register this fact, Doctor Who Series 6 starts this Saturday (April 23rd).  I recently watched my way through all of Series 5 again, and I was just as impressed as last time, so I am really excited about the new series.

And the Friday following (April 29), the day of the Royal Wedding, is also going to be an exciting one for me.  You may remember in the article Let’s Do Everything, I said that one of the things I’d like to do, but so far have not done, is to perform a set in a folk club.  I’ve made only small steps towards that, but instead I have a gig as a jazz singer on Royal Wedding day (one half of a duo, with my wife as the pianist), singing songs by Gershwin, Cole Porter and the like, at The Mill Race.  It’s only as background music, but it’s a start!

Advertisement