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 []

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!


16 responses to “Programming Books, part 5: Programming Pearls

  1. Programming Pearls — Nice summary of a great book!, I can also recommend his ‘More Programming Pearls’ (1988) and ‘Structured Programming’ by Dahl, Dijkstra & Hoare (1972) which are in the same catagory : small books that contain huge insights into the process of thinking about how to program. I’ve had these book in my library since publication and their value has not diminished with time.
    Genuine Classics!

  2. Nothing in there about praying Apple approves your app.

  3. I’ve been meaning to get my younger brother into programming. He’s already some stuff by himself (Kochan’s The Objective C Programming Language) and a whole slew of Apple Docs and bits and parts of Cocoa material. He’s thoroughly lacking in algorithms and general program structure concepts though. Would you recommend Programming Pearls for someone like him? Or perhaps he should stick at first with other more basic books?

  4. Heck, yes — Programming Pearls would be perfect for him. Part of its charm is that, although it wades into a deep waters, it’s not a difficult book. It makes everything as simple as possible, but no simpler.

  5. Great, I think I can get my hands on the first edition. Do you think the second edition (2000) is worth getting?

  6. I’ve never seen the second edition. But I’d be confident, knowing what I do of Bentley’s approach, that it will be at least as good as the first, i.e. he won’t have fallen for the common trap of expanding it until it’s bloated to the point where it doesn’t resemble the original and has lost all its good point. In your situation, I’d just get whichever edition is cheap and easy to get hold of.

  7. Never judge a book by its cover… In this case, the cover is a real atrocity.
    Even the second edition is dead-ugly.

    Sorry for this comment. I want this book.

  8. Pingback: Top Posts —

  9. I haven’t quite gotten to chapter 9 yet so I don’t know what techniques it teaches, but size still matters in the embedded world. Sure we have a lot of memory compared to a C64 but in some applications we really need to optimize the code to fit in the small internal memory of the micro controller.

  10. Get the second edition; it combines Programming Pearls with More Programming Pearls. The section on back-of-the-envelope estimation is probably my favorite, not least because it has global applicability. Trading space for speed was fun too; as cheap as memory gets, there will always be a demand for small memory systems, microcontrollers, etc.

  11. Pingback: How to get things done: don’t open your post | The Reinvigorated Programmer

  12. Just about finished with a class where we used this. Definitely my favorite book on programming thus far.

    A few of you talked about how “memory is cheap”, but one thing I noticed while coding up a lot of these solutions is that we still need memory efficient algorithms, but for different reasons. Although we have gigabytes of RAM, sometimes proper algorithms/data structures will allow you to fit everything into cache which is much, much faster than RAM. I like to think of this as a “soft” requirement, but still something to keep in mind.

  13. Pingback: Are you one of the 10% of programmers who can write a binary search? | The Reinvigorated Programmer

  14. Ankush Jindal

    > …I would judge the second best book on programming I’ve ever read…

    What is the first best, I wonder?

  15. Thank you for this well-merited prod. I really must get around to writing Pogramming Books, part 6. Things are a bit insane at the moment (I have to prepare for a conference talk on Friday week) but I’ll try to get back to this soon thereafter.

  16. It’s a fantastic book!

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.