Where is The Purple Dragon Book?

The "second" edition of the Dragon Book (a.k.a. "Compilers: Principles, Techniques and Tools" by Alfred Aho and others) has already been delayed a lot, considering that the previous edition was published twenty years ago in 1986 and the new edition was supposed to be published "soon" years ago. The final publishing date was supposed to be 31^st August 2006 and the corresponding Amazon.com page and the Addison-Wesley page continue to stick to the same date as of this writing and yet proclaim the title to be unavailable. Jeffrey Ullman says that the book is finally done and that they handed it over to the publisher at the end of June 2006, so I wonder what is causing all these delays and whether the wait would be worth it. Note that an online preview of some of the revised as well as newly-added chapters is still available, though the site uses an awful amount of Flash, JavaScript and pop-ups for some weird reason.

I put "second" in quotes since the publisher says that this is the second edition, though coming after the Green Dragon Book and the Red Dragon Book, I think this should be called the third edition of the book. However, I do realise that there was a change in the title of the book and it was thoroughly revised when it was published as the Red Dragon Book, so this is just nitpicking on my part. It has already been nicknamed the Purple Dragon Book based on its cover, continuing the convention for giving nicknames to its predecessors.

I read parts of the Red Dragon Book when I took the Compilers course in my college about twelve years ago. It was a bit boring (as are almost all textbooks I have ever read), but it was the only book I could lay my hands on that covered bits of everything about compiler construction. Even to this day, 20 years after it was published, it still seems to be a recommended book if you want to know about the basics of compiler construction. However, it is acknowledged to be terribly out-of-date with the current techniques, so a major revision was long overdue.

I have been meaning to brush up on the fundamentals of compiler construction techniques for several years now, especially since the time I was introduced to the development of GCC, but my excuse was that I wanted to postpone it till the time the new edition of the Dragon Book becomes available (which was always marked to be released "any time now"). Now that the Purple Dragon Book would become available "soon", my excuse is that I would at least wait for the second printing so that all the readily-apparent errors are corrected and I don't have to read the book with a thick errata in hand. I would also wait for the low-priced Indian edition to become available since the international editions are atrociously priced in my opinion.

Yes, I do make up really silly excuses for what is ultimately procrastination driven by plain old sloth.

Update (2006-06-07): As luck would have it, just a day after I write about the unavailability of this book, both Amazon.com and Addison-Wesley now show it as in-stock and ready for shipping.

"If You Come Today"

"If you come today, it's too early. If you come tomorrow, it's too late. You pick the time."

Sriram pointed out a video of the (English) song "If You Come Today" sung by and featuring Rajkumar. The lyrics of the song are rather confounding, but my favourite parts are the "Tick, Tick, Tick, Tick..." and the "DOHLING!".

A Bold Question

Does anyone know why comics writers put one or two words in every sentence in every dialogue in bold typeface?

For example, "Watchmen" is perfect in every other way except for this flaw. I tend to translate bold typeface as indicating an emphasis on a word or a phrase, so it is rather jarring to read dialogues mouthed by characters in comics.

Why do they do this?

RMS, GPLv3 and Bangalore

Richard Stallman will be talking about "Free Software: Current Status and Challenges" at 11 AM in the Faculty Hall in IISc Bangalore tomorrow (Saturday, 19^th August 2006). I came to know of this event just this afternoon and I understand that this is too short a notice, but I hope to meet some of the fellow Free Software enthusiasts in Bangalore.

On a related note, Bangalore will also be hosting the Fourth International Conference on GPLv3 on the 23^rd and 24^th August 2006, this time in IIM-B. Both Richard Stallman and Eben Moglen will be presenting in this event. Since this falls in the middle of a work week (Wednesday/Thursday), I will have to skip it.

Good Math, Bad Math

I came to know of Mark Chu-Carroll's "Good Math, Bad Math" blog via a post in "Programming Musings", the blog of José Antonio Ortega Ruiz. Mark writes mostly about mathematics, the theoretical foundations of programming, debunking bad use of mathematics in popular and not-so-popular media, etc.

I find many of Mark's articles very interesting to read, though many others go way over the top of my head. Some of his recent articles that I found really interesting include one that shows how absurd arithmetic with Roman numerals can be, one on Poincaré Conjecture, some in the "Friday Pathological Programming Language" series, one on zero, one on i, one on e, one on φ, one on Ω, one on π, one on continued fractions, etc. The old home for the GM/BM blog contains many more interesting and insightful articles on math and programming theory. What an amazing guy!

Highly recommended.

Balancing Acts

You are given 8 billiards balls, numbered 1 to 8, identical in shape and size. All but one weigh exactly the same. The odd ball is either heavier or lighter than the others. Using just three weighings on an ordinary two-pan balance, find the odd ball out as well as whether it is heavier or lighter than the others.

If you solve the previous puzzle, solve the same problem for 12 billiards balls (instead of 8) while keeping the maximum weighings to just three. Yes, there is a solution for this puzzle - if you give up, you can find the solution here.

For the first puzzle (with just 8 billiards balls), here is my solution (obfuscated using rot-13):

1. Xrrc onyyf ahzorerq 1, 2 naq 3 ba bar cna naq 4, 5 naq 6 ba gur bgure.
2. Vs gurl onynapr, gurl ner nyy abezny naq bar bs 7 naq 8 vf gur bqq onyy. Jrvtu 7 ntnvafg 1.
3. Vs gurl onynapr, 8 vf gur bqq onyy naq lbh pna svaq vgf bqqvgl ol jrvtuvat vg ntnvafg 1.
4. Vs gurl qba'g onynapr, 7 vf gur bqq onyy naq lbh jvyy vzzrqvngryl xabj vs vg vf urnivre be yvtugre guna gur bguref.
5. Vs gur onyyf qba'g onynapr va fgrc #1, bar cna jvyy tb qbja. Jvgubhg ybff bs trarenyvgl, nffhzr guvf vf gur bar pbagnvavat 1, 2 naq 3. Rvgure bar bs 1, 2 naq 3 vf urnivre guna gur bguref be bar bs 4, 5 naq 6 vf yvtugre guna gur bguref.
6. Xrrc 1 naq 5 ba bar cna naq 4 naq 2 ba gur bgure. Xrrc 3 naq 6 nfvqr.
7. Vs gurl onynapr, bar bs 3 naq 6 vf gur bqq onyy. Sebz fgrc #5, jr pna pbapyhqr gung rvgure 3 vf urnivre guna gur bguref be 6 vf yvtugre guna gur bguref. Jrvtu 3 ntnvafg 1.
8. Vs gurl onynapr, 6 vf gur bqq onyy naq vf yvtugre guna gur bguref.
9. Vs gurl qba'g onynapr, 3 vf gur bqq onyy naq vf urnivre guna gur bguref.
10. Vs gur onyyf qba'g onynapr va fgrc #6, rvgure gur cna jvgu 1 naq 5 jvyy tb qbja be gur cna jvgu 4 naq 2 jvyy tb qbja.
11. Vs gur cna jvgu 1 naq 5 tbrf qbja, sebz fgrc #5 jr pna pbapyhqr guna rvgure 1 vf gur bqq bar bhg naq vf urnivre guna gur bguref be 4 vf gur bqq bar bhg naq vf yvtugre guna gur bguref.
12. Jrvtu 1 ntnvafg 8. Vs gurl onynapr, 4 vf gur bqq bar bhg naq vf yvtugre guna gur bguref. Vs gurl qba'g, 1 vf gur bqq bar bhg naq vf urnivre guna gur bguref.
13. Vs gur cna jvgu 4 naq 2 tbrf qbja va fgrc #10, sebz fgrc #5 jr pna pbapyhqr gung rvgure 2 vf gur bqq bar bhg naq vf urnivre guna gur bguref be 5 vf gur bqq bar bhg naq vf yvtugre guna gur bguref.
14. Jrvtu 2 ntnvafg 8. Vs gurl onynapr, 5 vf gur bqq bar bhg naq vf yvtugre guna gur bguref. Vs gurl qba'g, 2 vf gur bqq bar bhg naq vf urnivre guna gur bguref.
15. Va fgrc #5, vs 4, 5 naq 6 tb qbja, pneel bhg gur erznvavat fgrcf ol fjnccvat 1, 2 naq 3 jvgu 4, 5 naq 6 erfcrpgviryl.

I confess that I had to finally give up while trying to solve the 12-ball variation in the second puzzle.

Lost Books on Computer Programming

I am not into old books on computers the way Graydon seems to be, but I still feel sad that the current generation of programmers will most likely never get exposed to some of the great books on computer programming that I was able to read when I was young.

At least here in Bangalore, it is almost impossible to buy these books from a bookshop unless they have either retained very old stock or are selling second-hand books. For example, here are a few books that seem to be very difficult to buy these days in Bangalore:

1. "The Elements of Programming Style", Brian Kernighan and P. J. Plauger.
2. "Algorithms + Data Structures = Programs", Niklaus Wirth.
3. "A Discipline of Programming", Edsger Dijkstra.
4. "The Science of Programming", David Gries.
5. "Communicating Sequential Processes", C. A. R. Hoare.
   
6. "How to Solve it by Computer", R. G. Dromey.
7. "Microprocessors: A Programmer's View", Robert B. K. Dewar and Matthew Smosna.

(I am sure I have not listed a lot of other interesting and important books here, but these are the names that readily spring to my mind.)

Of these, I have only been able to buy Dromey's book so far. In my opinion, it is one of the most under-appreciated books in computer science and deserves to be read by every novice programmer. It is a perfect complement to the usual textbooks for a Data Structures and Algorithms course.

A kind soul has scanned in the pages from "A Discipline of Programming" and made them freely available to everyone. The electronic version of "Communicating Sequential Processes" is now freely available for download. But I still wish I had these books "for real".

By the way, Robert Dewar hopes to produce an updated version of "Microprocessors: A Programmer's View" sometime soon.

Alarmingly, some relatively recent books are also becoming difficult to find these days. For example:

1. "Programming Pearls", Jon Bentley.
2. "The Practice of Programming", Brian Kernighan and Rob Pike.

I also note rather sadly that the "XYZ Unleashed" and "Learn ABC in 3 Days" type books are still going strong even after almost a decade.

Thankfully, the "The Art of Computer Programming" (TAOCP) series by Donald Knuth is still easily available. "Structure and Interpretation of Computer Programs" (SICP) by Harold Abelson, Gerald Jay Sussman and Julie Sussman is also visible in bookshops from time to time.

I think the strong sales of TAOCP are more due to the "classic book" effect than anything else. To quote Mark Twain, "A classic is a book that everyone wants to have read but no one wants to read". If there are people who have actually read TAOCP, they seem to have been rather successful at avoiding to meet me. To quote Bill Gates, "If you have read The Art of Computer Programming from cover to cover, send me your resume!".

The Suez Crisis and The IBM PC

"Those who cannot remember the past are condemned to repeat it."

- George Santayana

A recent issue of The Economist featured the article "An Affair to Remember" about the Suez crisis (also known as the Sinai War) of 50 years ago. I found it to be a very interesting read. It provides some great insights into the events precipitating the formation of the European Union, the establishment of the US and the Soviet Union as the only superpowers, the reasons for the different way that the British and the French view the US, etc. I also found it a bit surprising how the then British prime minister Anthony Eden and his foreign secretary blatantly lied to the House of Commons about the sinister collusion between Britain, France and Israel that led to the war.

In the light of the recent events, it is amusing to find out that at that time the US actually went via the UN to put a stop to this uncalled-for agression by the Israelis, the British and the French against the Egyptians. It was apparently also the last time that the US actually acted against Israel while intervening in a war.

How times change.

The same issue of The Economist also featured the article "Getting Personal" about the 25th anniversary of the introduction of the IBM PC. The first IBM PC was apparently priced at USD 1,565, had 16K of RAM, used audio cassettes for storage (a floppy drive was optional) and featured “green phosphor characters for reading comfort” (i.e. text-only, no graphics). It wasn't until Lotus 1-2-3 was introduced about 1.5 years later that the PC really took off. These days you are overwhelmingly more likely to see a PC than an Apple Macintosh or any other kind of personal computer.

I first got to work on an (8086-based) IBM PC in 1990. It struck me as rather ugly and severely lacking. I was used to the excellent BBC Micro and the primitive CGA display of the IBM PC and the PC speaker were nothing compared to what was available on the Beeb. As a novice programmer, it was also very irritating to find how different BASICA was from BBC BASIC. All the "VDU" (graphics) and "ENVELOPE" (sound) tricks I had learnt on the Beeb were also useless on the PC.

It was not until I got to work on the 80386-based IBM PCs and play Prince of Persia and Wolfenstein 3D that I really began to enjoy working on the PC. Borland's Turbo Pascal and Turbo C/C++ were excellent tools that made programming on the PC much easier. After the advent of Linux, there was no question about what my first personal computer was going to be.

Another River Crossing Puzzle

Most of us would have seen the standard river crossing puzzle. However, Prasadini recently sent me another river crossing puzzle (Flash animation) that I think is far more challenging.

A father and his two sons, a mother and her two daughters, a thief and a policeman are on one side of a river. There is a boat by the river bank, but it can only take two people at a time. Only the father, the mother and the policeman know how to operate the boat. The father can not be with any of the girls without their mother around. The mother can not be with any of the boys without their father around. The thief can not be with anyone else without the policeman around. How can you get everyone across to the other side of the river?

Start the game by clicking on the big round blue button. Click on a person to get him or her on or off the boat. Click on the levers to get the boat to move.

It took me a fair bit of time to crack it and here is my solution (obfuscated using rot-13):

1. Gur Guvrs naq gur Cbyvprzna pebff bire.
2. Gur Cbyvprzna pbzrf onpx (Gur Guvrs qbrf abg eha njnl jura yrsg nybar!).
3. Gur Cbyvprzna naq n obl pebff bire.
4. Gur Cbyvprzna naq gur Guvrs pbzr onpx.
5. Gur Sngure naq gur bgure obl pebff bire.
6. Gur Sngure pbzrf onpx.
7. Gur Sngure naq gur Zbgure pebff bire.
8. Gur Zbgure pbzrf onpx.
9. Gur Guvrs naq gur Cbyvprzna pebff bire.
10. Gur Sngure pbzrf onpx.
11. Gur Sngure naq gur Zbgure pebff bire.
12. Gur Zbgure pbzrf onpx.
13. Gur Zbgure naq n qnhtugre pebff bire.
14. Gur Guvrs naq gur Cbyvprzna pbzr onpx.
15. Gur Cbyvprzna naq gur bgure qnhtugre pebff bire.
16. Gur Cbyvprzna pbzrf onpx.
17. Gur Cbyvprzna naq gur Guvrs pebff bire.

See if you can come up with a better solution.

Optimising Linker Load Times

Last week's LWN.net Weekly Edition had a nice article on optimising linker load times by John Richard Moser. It was based on some recent features added to the linker in GNU binutils. It explains the kind of things that most of us never bother to learn about, but which can affect the loading times of our applications and shared libraries. As someone noted in the comments, an informative read even by LWN.net's usually high standards.