Forgot your password?
typodupeerror
News Books Media Book Reviews

Programming Pearls (Second Edition) 47

Posted by Hemos
from the return-of-a-classical dept.
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.

This discussion has been archived. No new comments can be posted.

Programming Pearls (Second Edition)

Comments Filter:
  • For a second there, i thought it was:

    'Programming PERL'.

    I guess i should read a tad slower, huh?

    --
  • 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!


    I agree wholeheartedly. Reading Carroll changed my life, and I make a point to re-read Alice and Through the Looking-Glass at least once a year. But more than a Mathematician, Carroll was a surrealist. I've found that the abstract thinking involved in understanding surrealisim is really helpful in learning to work with computers (beit admin or programming). Good to see I'm not the only one who sees the Alice/computing connection ;-)


    Incidentally, they're making a pc game based on Alice, but it's a first person shooter about a goth chick. Sigh. *whacks head on desk*

  • Better still: get The Annotated Alice - Alice's Adventures in Wonderland and Through the Looking Glas, with annotations by Martin Gardner.

    Jeroen Nijhof

  • The Markoff Text Generator should make interesting reading. This was the basis of a program that won first prize in the annual Turing Test competition a couple of years ago.

    I'd post the URL but I think its gone to the great bookmark file in the sky

  • Unfortunately, Disneyfication of world culture leads most people to think that the name of the Disney feature 'Alice In Wonderland' is also the name of the book.....

    Btw, A version in the UK has some wonderful surrealist illustrations by Antony Browne (leading children's illustrator/author with a surreal twist)

    Briefly on topic - any book written well, with enthusiasm for the subject matter tends to instil enthusiasm in those who read it. I just wish more coding authors realised this....
  • Actually, IIRC, there was a very surreal adventure game, (Wonderland?) based loosely on the novels, I think it was released by Mindscape... I also remember it being an Amiga/PC/ST release, so maybe there's a couple of ADF's floating around out there....

  • by RNG (35225) on Tuesday November 30, 1999 @05:58AM (#1494599) Homepage
    Programming Pearls is very cool. The nice thing about it is that really explains in detail some of the thought processes which lead to a programming being written the way it is; it very nicely shows the tradeoffs involved in choosing one approach over another.

    The other cool thing is, that this really is a book for programmers. I appreciate Donald Knuth as much as the next guy, but his books are so mathematical, that I found myself skipping over more of the material, than I thought was good. Programming Pearls is the opposite: it clearly lays out the algorithms involved and often has nice drawings of the actual datastructures used. For a book of it's deapth it's pleasanly short, sparse in math and to the point. Read it, think about it for a while, program for a while and then read it again ... it'll be worth your time ...
  • I bought the 1st edition of this book not too terribly long ago, and before I had read a third of the way through it, I was using its insights in my code.

    I was working on a series of General Ledger reports, and the first one? Well let's just say that I won't win any design awards. Somewhere in there I started reading this book and my code cleaned up dramatically. I can't say that the next report in the series will win any awards either, but I found myself sitting and waiting a bit before coding, and it has paid off. By the end of the project, my programs were almost elegant. I enjoy looking at them--and they aren't a nightmare for mods.

    Just an example: The report before reading the book and the one right after are both variations of Income Statements. I needed to make a change that would affect both. Some of the code was in a joint library file, but some was in each report. The first report required at least a dozen places of change, the second required THREE LINES!

    Granted, better design ideas from other sources were at work, and these were some of my first commercial programs, but this book definitely had an impact.

    Buy this book, and take the time to ingest it. Work the programs--even if you think you understand them. It will pay off nicely.

    At least it did for me.
  • While John Tenniel's drawings provided the original interpretation of Carrol's book, I have to argue that they are not untouchable.

    I have a reproduction of a 1907 limited printing of Alice's Adventures in Wonderland that was illustrated by Arthur Rackham.

    Rackham's illustrations are quite lovely and contain a certain something that Tenniel lacked.

    Here is an except from the "About This Edition":

    This is a facsimile of the deluxe limited edition of 1907 that was illustrated by Arthur Rackham. Rackham [1867-1939] was the first and the greatest of the illustrators to succeed John Tenniel, whose drawings had provided the original interpretation of Lewis Carroll's masterpiece in 1885. Tenniel, however, had not illustrated the book in color; and thus Rackham was the pioneer in that respect.


    While I will not assert that color makes one picture superior over another, I do suggest that any fan of the story who hasn't seen Rackham's illustrations take a look. Even the pieces that are not in color have a charm and flair that escape arbitrary placement in the shadow of Tenniel's exemplary work.
  • by Anonymous Coward
    You can call it Disneyification, but it's not a phenomenon that began with Disney nor is it primarily a result of Disney's actions.
    • Grimm's fairy tales have been watered down for generations because the original ones are actually rather gruesome.
    • Anything animated is now considered targeted at children. Any of the nine old men will tell you that Bambi wasn't a children's movie. Cartoons shown in theaters ('50s and earlier) contained what the (adult) animators thought was entertaining.
    I'm not defending Disney. I'm just saying Disney didn't start it, people who want things simplified so they don't have to think too hard started it.
  • Check out the books website for lots of little snippets from the book

    Programming Pearls [programmingpearls.com]
  • by Ed Avis (5917) <ed@membled.com> on Tuesday November 30, 1999 @06:37AM (#1494604) Homepage
    As Alan J. Perlis said [cam.ac.uk]:
    The best book on programming for the layman is "Alice in Wonderland", but that's because it's the best book on anything for the layman.
  • by dze (89612)

    More than once I have seen this book shelved with the perl books at the bookstore...

  • ... it's just a shame that so many of the populace require it in the first place....

  • Well, give the damn thing a bagel so it'll do taxes.
  • by King Babar (19862) on Tuesday November 30, 1999 @07:12AM (#1494611) Homepage
    While I was checking out the website for Programming Pearls, second edition [bell-labs.com], I stumbled across what turns out to be the complete text of Appendix 2, which is a quiz that tests your estimation ability.

    Whether or not you buy the book, and whether or not you think of yourself as a programmer, if you consider yourself a thinking person, you should take this quiz. [bell-labs.com] If you can't do back-of-the-envelope calculations, you should find this out as soon as possible, and fix the problem while you still can.

  • Do I have to make the link more clear between 'Alice in Wonderland' and 'Being John Markovich'. Enjoy
  • For the Alice's Adventures in Wonderland fans, have you read Jeff Noon's Automated Alice? Alice travels through a clock to a future where termite mounds make comutations (computermites) and wild and silly things abound (civil serpents?). It's a cyberpunk Alice for the 90's. Read about it at Amazon [amazon.com].


    Read a good book lately?
  • Whether or not you buy the book, and whether or not you think of yourself as a programmer, if you consider yourself a thinking person, you should take this quiz. If you can't do back-of-the-envelope calculations, you should find this out as soon as possible, and fix the problem while you still can.

    The problem I had with this quiz was that a lot of the questions assume American units and places. For example, I don't have a really good mental model of what weight a pound is, I don't know where Mississippi or Missouri are, and I've only heard of the Golden Gate bridge - I've never seen it.

    How about some alternative questions:

    • January 1, 2000, population of the United Kingdom in millions
    • Length of the Thames in miles
    • Weight of a Mini Metro in tonnes
    • Length in metres of the span of the Humber bridge
    • Weight in kilograms of a barrel of beer
    • Length of Hadrian's Wall in miles
  • This is a simple trivia quiz, not an estimation quiz.

    Estimation is the process of making reasonable assumptions based on incomplete or limited data. You need to have some data to base your estimates on, however.

    I could perhaps estimate the length of the Golden Gate Bridge or the weight of a Boeing 747, but only if I had a frame of reference. As I have only seen the GGB in artistic visuals not intended to give a sense of scale, and I have only seen a 747 in Hollyweird movies, I couldn't provide a worthwhile estimate for those.

    I happened to know that the Shuttle orbits in about 90 minutes, and that roughly 50 people signed the Declaration of Independence, so I did well on those. But the significant factor here my knowledge of trivia, not estimation skills.

    A true test of estimation would be to give you various pictures of things, with a known quantity for scale, and ask you to figure out dimensions, weight, volume, etc.
  • Pick it up in $CDN here.

    Click Me! [chapters.ca]

    BTW - This book cost enough that Chapters'll ship it free. Even better!

  • Jon Bentley is undoubtedly the best speaker I've ever heard on programming topics. I believe that's a tall compliment since I also had the pleasure of attending a couple Grace Hopper lectures.
  • Would you be thinking of the movie Being John Malkovich [being-john-malkovich.com] maybehaps?

    John Markovich [iaxs.net] is a photographer based in Minneapolis, MN...

  • Recall that part of the problem was not to identify the *exact* answers, but to get 90% ranges for them.

    --
  • Good movie. Recommended.

    --
  • The problem I had with this quiz was that a lot of the questions assume American units and places. For example, I don't have a really good mental model of what weight a pound is, I don't know where Mississippi or Missouri are, and I've only heard of the Golden Gate bridge - I've never seen it.
    I don't think the American units and places are really a problem; the point isn't to be close, it's to be able to predict how close you can be. That's why you're asked for a 90% confidence range; if your range for the length of the Mississippi-Missouri river is 50 to 1 000 000 miles, then fair enough. Then at the end, if either all ten were well within your ranges or half of them were way outside, you know you're not very good at knowing how good your estimates are. Maybe it's misleading that the previous poster referred to "back-of-the-envelope calculations", because that's not really what it's about; if you don't have a clue, you're allowed to make a sensible guess. FWIW, I'm English and your set of questions wouldn't be any easier for me; of Bentley's, seven were within my ranges, which is OK, I guess, although there was one that I got wrong by a couple of orders of magnitude.
  • Charles Lutwidge Dodgson (better known as Lewis Carroll) did not make up Alice. Alice was a real girl, full name of Alice Pleasance Liddell, and Dr Dodgeson is widely believed to be a paedophile.

    There is no evidence that he ever consummated his relationship with young Alice, he was quite proper about it and all, but you can judge his interest from the fact that he took pictures of female children (including Alice) as scantily clad as he could arrange and eventually proposed marriage to Alice.

    For some reason this gets glossed over in a lot of places...

    Regards,
    Ben
  • To his credit, Bentley explains his coding style in the book (and probably on the web site). It's not meant to be robust in IO or error checking, but to convey the ideas.

    --
  • Of course it's written for Alice Pleasance Liddell. Look carefully at the first letters of each line in the final poem of Through the Looking Glass...

    --
  • by Anonymous Coward
    Shamefully and willfully offtopic...

    Lewis Carroll is alluded to being a pedophile usually based upon his hobby of photographing young nude girls. That does sound a bit pervy but that doesnt mean it was sexual. Is a painter who draws male nudes a homosexual? The Victorian times were very different, often alien, times. Some of the girls he photogrphed in the nude were watched over by nannies who didnt see anything unusual about it. In the end since there is no direct proof or real implication that he was a perv it doesnt necessarially need mentioned.

    William Ewart Gladstone a Victorian British Prime Minister made it a habit of his to go to the seedier parts of town and bring home a prostitute. Sounds a little funny doesnt it. Course, he and his wife (kinky!) then served her tea and try to convince her to repent and take up a more honest trade

    John Ruskin, Victorian art critic(most notable after Whistler sued him), married a girl named Effie and on their wedding night he realized that girls arent built quite the way he expected (i suppose he expected her to be made out of marble). He was digusted by her anatomical correctness and never did sleep with her. Eventually she left him, filed for an annulment and then married the painter Millais(who she fell in love with while he was painting her portrait. He was painting Ruskin while the annullment suit was in progress, but Ruskin even though his wife was leaving him for Millais continued to sit for the painting. (see- "stiff upper lip, British") Needless to say the friendship between ruskin and Millais ended.

    Ruskin eventually fell in love with a ten year old girl and when she turned 17 asked her to marry him. Apparently her parents objected to his previous marriage and annullment. But doesnt the fact that he waited until she was 17 imply that he was less of a perv and more socially disfunctional

    remember not everything needs overanalysis and a different time comes with a different culture.

  • Although it does make reading the book a very different experience.

    The book is based on short stories that he told Alice + other female friends to keep them interested in him. Alice (at the age of 7) is the person the story is being told to. The Red Queen appears to be based on the chaperone. So on and so forth.

    So while you can read the book without knowing the background, the background definitely affects how you interpret the book!

    Regards,
    Ben
  • You're right. Typo
  • Hm, Amazon.co.uk's page for this book [amazon.co.uk] says the book has 1 ;^)
  • You may want to correct your page, as it lists him as Alan J Perils! Just thought i'd better warn you....
  • I can see both sides of this:
    • On the one hand examples want to be simple to read.
    • On the other hand students who see hundreds of examples with no bounds checking etc, are being trained to ignore errors themselves


    Still I think its something that more programming books should mention in bold in the
    introduction - not tucked away in an appendix..

    Steve
    ---
    http://GNUSoftware.com/ [gnusoftware.com]

  • The coding style is discussed in the preface, which is available online here [programmingpearls.com]. I think it is reasonable to expect readers to read the preface. In part it reads:

    "The programs use a terse coding style: short variable names, few blank lines, and little or no error checking. This is inappropriate in large software projects, but it is useful to convey the key ideas of algorithms."

    Much of the "code" is in fact pseudocode. One thing it does include which is a good habit, is scaffolding for testing, debugging, and timing the functions. That's something you don't see everyday.

    --
  • This is a simple trivia quiz, not an estimation quiz.

    I have to disagree. There are specific facts that can be helpful to you to get exact answers, but half of the battle is in knowing what to do with information that is more shaky. And we certainly agree that people are not likely to know the exact answers here (that would be trivia).

    Estimation is the process of making reasonable assumptions based on incomplete or limited data. You need to have some data to base your estimates on, however.

    Yup. But it's surprising how close you can come with very little data. And if you know you're not going to be close at all, you should learn how to widen your confidence intervals.

    I could perhaps estimate the length of the Golden Gate Bridge or the weight of a Boeing 747, but only if I had a frame of reference. As I have only seen the GGB in artistic visuals not intended to give a sense of scale, and I have only seen a 747 in Hollyweird movies, I couldn't provide a worthwhile estimate for those.

    The estimate doesn't have to be especially worthwhile. It just has to have confidence bounds that include the true value. Yes, smaller intervals mean something, too, but that wasn't the explicit point of the exercise. Interestingly, I fell into that trap a bit myself, which is why I suggested that people try this out.

    So, let's do the Golden Gate Bridge. I've only seen it once or twice myself; how in the heck should I know how long the main span is? On the other hand, I do know that the big deal about that bridge is that it does have a very impressive main span. So how long does a bridge have to be to be impressive for this? A mile, within a factor of 2? That's a confidence interval of like 2500 to 10000 feet. Yes, it's pretty broad, but it's also correct. Or maybe you know that 10000 feet is right out, because that would mean the main towers would have to be too tall to have the nice shape they have. Fine; then reduce that end of the estimate, to, oh, 6000 feet? That's still a covering interval, and a shorter one. Maybe that's the best that you can do, but give yourself credit for getting that far from almost nothing.

    Again, let's do the weight of a 747. Like I have any idea what that is. Fine; the guess will be pretty wild, then. I think a 747 holds a lot of people. At least 300, probably less than 600? Fine. I can work with that. How much does a plane weigh? Well, how much does a car weigh? A big SUV might weigh 6000 pounds and carries 6 people, so that's 1000 pounds per person. Oh yeah: the person weighs 200 pounds, and they have 50 pounds of baggage. So what does that give us? 375,000 to 750,000 pounds. Anything I'm leaving out? Ah: fuel. The SUV gets 15 miles per gallon to haul those 6 people, or like .01 gallons per person mile. I suppose a jet aircraft could be worse, but I'm not sure how much worse. Now, a 747 can go at least across the Pacific without refueling; I bet that's oh, 6000 miles. 6000 miles * .01 gallons/person/mile*600 people = 36000 gallons of fuel. I know water weighs 8 pounds a gallon, and gasoline (or jet fuel) is rather lighter; maybe 5 pounds per gallon? So that's 90,000 to 180,000 pounds of fuel, for a total wild ass guess of 465,000 to 930,000 pounds. I'm pretty sure that the low end is below, but the high end might not be high enough; I'd be willing to go to 1.3 million or so to be comfortable.

    And, as it turns out, the actual weight is in both ranges. In both cases, you could have treated the questions as trivia questions, but then you would have missed the point of the quiz.

    I happened to know that the Shuttle orbits in about 90 minutes, and that roughly 50 people signed the Declaration of Independence, so I did well on those. But the significant factor here my knowledge of trivia, not estimation skills.

    But one person's trivia is another person's estimation problem.

    Take the Declaration of Independence signing. You know that representatives of 13 colonies signed the things, and that each state had one or more delegates. So the minimum number has to be greater than 13. For the maximum number, I suppose you might choose low. I figured 5 would be generous, so my estimate was [20,65], which includes the real value.

    Now take the space shuttle. That's trivia for you, but I had to figure it out. First, I took out my trusty notepad, pretended it was a decent pendulum, and estimated its period. About 1 second; how convenient. The pad is 11/12 of a foot, and there are 5280 feet in a mile. I guessed that the shuttle orbits like 200 miles above the surface, or about 4200 miles above the center of the earth. Now, I know that the period of a pendulum depends only on the acceleration due to gravity, and the length of the bob; in fact it's proportional to (a/l)^.5. Gravity is (4000/4200)^2 weaker in orbit than on earth, so putting all this together, I get an estimate of 86 minutes, which I'll gather is good to within plus or minus 20%. So my interval is [70,102] minutes. Got it again... And this is the whole point: the exact answer is a trivia question, but the ability to get the answer to within an order of magnitude or a factor of 2, and to know how loose your confidence interval is, depends on your estimation ability.

  • Not my page... interesting mistake, though.

A failure will not appear until a unit has passed final inspection.

Working...