Slashdot Mirror
Programming Pearls (Second Edition)
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.
For a second there, i thought it was:
'Programming PERL'.
I guess i should read a tad slower, huh?
--
rJames.org - illustration
The subject says it all...:)
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*
Bad things often happen to good people,
It is up to them to see that they remain good.
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....
- "How do we do it? Volume!" - The Bursar of Unseen University.
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....
- "How do we do it? Volume!" - The Bursar of Unseen University.
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.
... it'll be worth your time ...
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
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.
We are agents of the free
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":
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.
Check out the books website for lots of little snippets from the book
Programming Pearls
What is wrong with you?
I like monkey penis.
Who doesn't?!!?
More than once I have seen this book shelved with the perl books at the bookstore...
"Luck is the residue of design" -- Branch Rickey
... it's just a shame that so many of the populace require it in the first place....
- "How do we do it? Volume!" - The Bursar of Unseen University.
Well, give the damn thing a bagel so it'll do taxes.
Weblogging Considered Harmful:
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.
Babar
That was pretty cool though I only got 4 correct. I was close on others and embarassingly off on some like the max takeoff weight of a 747 and Napoleon's birthday (ok so I'm historically bankrupt).
I don't mean to disrespect the author, but I really think that those who write programming books should pay more attention to writing code in a secure manner. From "sign.c":
...
int main()
{ char word[WORDMAX], sig[WORDMAX];
while (scanf("%s", word) != EOF) {
...
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.
Read a good book lately?
Read a good book lately?
Hey, I scored a perfect 10, then again, I knew the answers.
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:
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.
dragonhawk@iname.microsoft.com
I do not like Microsoft. Remove them from my email address.
Pick it up in $CDN here.
Click Me!
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.
This message composed using 100% recycled electrons.
John Markovich is a photographer based in Minneapolis, MN...
If you're not part of the solution, you're part of the precipitate.
Good movie. Recommended.
--
--
Marc A. Lepage
Software Developer
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
My usual seat in the cluetrain is at A HREF="http://pub4.ezboard.com/biwethey.ht
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
My usual seat in the cluetrain is at A HREF="http://pub4.ezboard.com/biwethey.ht
Hm, Amazon.co.uk's page for this book says the book has 1 ;^)
main(O){10<putchar(4^--O?77-(15&5128 >>4*O):10)&&main(2+O);}
You may want to correct your page, as it lists him as Alan J Perils! Just thought i'd better warn you....
- "How do we do it? Volume!" - The Bursar of Unseen University.