Programming Pearls (Second Edition)

SEGV has continued his tradition of excellent reviews with an examination of Jon L. Bentley's Programming Pearls (Second Edition), recently released by Addison-Welsey. One of the classics of programming, the new version continues the first edition's heritage of excellence. Click below to read more.

Programming Pearls (Second Edition)
author	Jon L. Bentley
pages	239
publisher	Addison-Wesley, 10/1999
rating	10/10
reviewer	SEGV
ISBN	0-201-65788-0
summary	A classic revised.

Choice and Precious

One definition of pearl is something "very choice or precious." Like the programming pearls it describes, Bentley's collection of essays has itself transcended the ordinary to achieve pearl status.

Originally published in Bentley's "Programming Pearls" column in Communications of the ACM, these fascinating essays were collected and revised in book form in 1986. Now revised 14 years later, this material has definitely stood the test of time. The first edition remains #2 on McConnell's Code Complete Reading List, and is listed favourably in an article on Great Books in Computer Science.

A Sense of Wonder

It was directly because of McConnell's Code Complete reading list that I, a few years ago, purchased and read Programming Pearls and its sequel, More Programming Pearls. Despite McConnell's effusive praise and corroboration from a colleague, I was not fully prepared for the experience.

I say experience, because that's what it was. It reminded me of reading Alice's Adventures in Wonderland [1] or Godel, Escher, Bach [2] (perhaps not coincidentally, also on the above list of great books in computer science). It filled me with a sense of wonder that is difficult to describe. It confirmed my love for computer science.

I believe that I am not alone in this regard.

What's New?

Twelve of the thirteen columns in the first edition have been edited substantially for this edition, and three new columns have been added. The new columns are on the topics of testing & debugging & timing, set representations, and string problems. This new edition is about 25 percent longer.

Although the first edition had been getting a little long in the tooth, the revisions once again place the essays in the modern world. Discussions of performance take into account modern hardware, caches, and instruction-level parallelism. Modern languages (C++, Java) are compared and contrasted where appropriate. Modern books (such as McConnell's Code Complete and Musser & Saini's STL Tutorial and Reference Guide [3]) are referenced and recommended.

Like Meeting an Old Friend

Re-reading this book was like meeting an old friend. Notwithstanding the major revisions, it has changed in subtle ways. Some anecdotes have been updated, some material reorganized. But it's still the same book. All of the energy and fun remains, youthful as ever.

I'm pleased to see that Bentley is still happy working at Bell Labs / AT&T / Lucent. Perhaps that's why this book is so great. There's a lot of intelligent people working there, and they put out some fine books. Bentley produces a Markov text generator in column 15, and compares it favourably to his colleagues' (Kernighan and Pike) version in the recent book The Practice of Programming [4].

Supporting Material

I must say that the supporting web site for this book (URL below) is excellent. It has all the information on why this book was updated, along with exactly what was revised. There the curious reader will find excerpts from columns, some problems and their solutions, and many other parts of the book available online.

All of the source code is available and free for use. Relevant web sites are linked and annotated. I love the Java applet that demonstrates sorting algorithms (source available!). Bentley even provides some overhead transparencies for use in teaching.

Recommendation

This is a no-brainer. I've always recommended reading this classic, and even re-reading it. The second edition is merely an excuse to purchase and (re-)read a revised copy. The time spent is well worth it. (Remember, only one column per sitting!)

I also recommend scrounging a copy of the sequel, which is out of print [5].

Purchase this book at fatbrain.

Links

Programming Pearls (Second Edition) Official Site

Programming Pearls (Second Edition) at Addison-Wesley

Programming Pearls (First Edition) at Addison-Wesley

More Programming Pearls: Confessions of a Coder at Addison-Wesley

Table of Contents

Part I: Preliminaries
1. Cracking the Oyster
2. Aha! Algorithms
3. Data Structures Programs
4. Writing Correct Programs
5. A Small Matter of Programming
Part II: Performance
6. Perspective on Performance
7. The Back of the Envelope
8. Algorithm Design Techniques
9. Code Tuning
10. Squeezing Space
Part III: The Product
11. Sorting
12. A Sample Problem
13. Searching
14. Heaps
15. Strings of Pearls
Epilog to the First Edition
Epilog to the Second Edition
Appendix 1: A Catalog of Algorithms
Appendix 2: An Estimation Quiz
Appendix 3: Cost Models for Time and Space
Appendix 4: Rules for Code Tuning
Appendix 5: C++ Classes for Searching
Hints for Selected Problems
Solutions for Selected Problems
Index

Notes

[1] Why do people (book sellers, web sites, bibliographies, etc.) insist on incorrectly calling this book Alice in Wonderland? It's not just for kids; Lewis Carroll was a mathematician, and it abounds in metaphor, puzzles, hidden treats. Read it. Accept only the John Tenniel illustrations!

[2] Godel, Escher, Bach: An Eternal Golden Braid is subtitled A Metaphorical Fugue on Minds and Machines in the Spirit of Lewis Carroll. It was reviewed on Slashdot: Godel, Escher, Bach (Review).

[3] However, use this book instead: Austern's Generic Programming and the STL.

[4] I reviewed this book for Slashdot: The Practice of Programming (Review).

[5] Why? I don't understand why some classics go out of print. I'm still trying to find copies of Artificial Life II, On Numbers and Games, Computation: Finite and Infinite Machines, and a host of others.