IMG_4822.jpg IMG_4862.jpg IMG_4886.jpg IMG_4841.jpg olje%204%20copy.jpg

To Knuth or not to Knuth

08.07.2012 av: Einar Høst
hentet fra: Einar Høsteksterne blogg

I received an email with an interesting question a while back. The question was this:

Dear doctor, should I read Knuth?

As you can see, the email was deviously crafted to appeal to my vanity – which of course was a clever thing to do, since it spurred one of those lengthy, slightly self-absorbed responses I’m wont to. However, it also triggered an unexpected chain of events which is now resulting in this blog post. You see, the flattery inflated my ego to the degree that I figured I should follow Scott Hanselman’s advice, and maximize the effectiveness and reach of my keystrokes. I am therefore publishing my response here to the vast readership of my blog. That means you, dear reader! Nothing like a bit of old-fashioned hubris!

So, should you read Knuth? I dunno.

It’s an interesting question, though, with some pretty deep repercussions. In fact, it is interesting enough that Peter Seibel included it as one of the questions he asked each of the prominent programmers he interviewed for the book “Coders at Work“. You should totally read that book, by the way.

Anyways. In case you’re unfamiliar with Knuth, we’re talking about this guy:

Knuth

Professor Donald Knuth

Knuth received the ACM Turing award in 1974 (a year before I was born) for his work on the analysis of algorithms and data structures. That work is captured in the first three volumes of a series of books known as The Art of Computer Programming or TAOCP for short. “Reading Knuth” refers to reading those books.

Of course, that’s a pretty significant argument for reading Knuth right there. The content of the books is worth a Turing award! I bet you don’t have many books in your bookshelf for which that is true. I don’t, and I have awesome books! TAOCP is the quintessential, be-all end-all resource for the study of algorithms. If you are familiar with the so-called big-oh notation for estimating run-time costs of algorithms, that’s due to Knuth’s influence.

One of the quirks of Knuth is that apparently all the examples in the TAOCP use a language called “MIX assembly language”. It runs on a hypothetical computer called “MIX”, dreamed up by Knuth. Clearly, then, the examples are not directly transferable to your day-to-day work as a programmer. And undoubtedly, it can be somewhat off-putting for modern readers to have to learn everything by means of this ancient assembly language for an obsolete machine that never existed. To be fair, Knuth has since come up with MMIX, a “64-bit RISC architecture for the third millenium” (no less), intended to replace the original MIX in TAOCP. I’m not quite sure how far the work of upgrading MIX to MMIX has progressed, though. Also I’m not quite sure that it really rectifies the situation. But YMMV.

A further obstacle is that TAOCP requires significant mathematical sophistication on behalf of its readers. It speaks volumes to me when Guy L. Steele Jr claims he lacks the mathematical background to read parts of it. What about us mere mortals, then?

These challenges conspire to raise some serious doubt: is reading Knuth worth the effort? Clearly it requires a lot of intellectual struggle and perseverance. Isn’t it simply too much trouble to go through? At the same time, the challenges contribute to a further selling point for Knuth: TAOCP as the ultimate rite-of-passage for programmers. Arguably you’ve beaten the game of programming and computers in general when you’ve read Knuth.

So then: do I think you should read Knuth? I dunno.

I feel like it’s an important question to try to answer, though. It’s kind of amusing, really – it reminds me of the opening of “The Myth of Sisyphus” by Albert Camus, 20th century French writer and philosopher. It was one of my favorite books way back when I was young and oh-so much older that I am now. I would be sitting in a cafe, reading French literature and aiming for an air of profoundness and mystery by occasionally raising my head and gazing at the world through faraway eyes. It attracted less girls than you’d think.

Anyways, the opening goes like this:

There is but one truly serious philosophical problem, and that is suicide. Judging whether life is or is not worth living amounts to answering the fundamental question of philosophy. All the rest – whether or not the world has three dimensions, whether the mind has nine or twelve categories – comes afterwards. These are games; one must first answer. And if it is true, as Nietzsche claims, that a philosopher, to deserve our respect, must preach by example, you can appreciate the importance of that reply, for it will precede the definitive act. These are facts the heart can feel; yet they call for careful study before they become clear to the intellect.

Isn’t it just grand? Who cares about girls when you can read stuff like that.

Translated to the Knuth dilemma: if I reach the conclusion that you should read Knuth, I immediately have a problem: it follows suite that I should proceed to read Knuth as well! (Indeed, how can I claim to give a meaningful and convincing recommendation for or against it without actually having read the books first?)

So then: should I read Knuth? I dunno.

So far in my career, I’ve sort of dogded the issue of Knuth and TAOCP. I’ve avoided ordering the books despite their obvious merits because I’ve been quite convinced that they would just be sitting on a bookshelf collecting dust and radiating failure. As long as I don’t actually have the books in my possession, I don’t feel that bad about not having read them. But if I were to own the books, and I still didn’t read them, I would actively have not-read Knuth. Which is clearly a lot worse. Hence I’ve backed out of the challenge thus far by cunningly avoiding purchase. But of course that has more to do with my knowing a thing or two about my innate laziness and resistance to discomfort than anything else. It’s not a good reason to avoid Knuth, but at least a truthful one.

But that’s me, not necessarily you. What about you? Should you read Knuth? I dunno.

In my mind, reading Knuth is similar to choosing to walk three years by foot to some remote location in the mountains, in order to study with some famous zen monk (a thought that is somehow made more amusing by the fact that Knuth bears a certain resemblance to Yoda). Once you’ve made up your mind to study with this monk, you don’t really question why he does things this way or that way – you just do as you’re told. Wax on, wax off, if you like.

Paro-taktsang-tigers-nest-monastery-bhutan-500x375

Taktshang – the Tiger’s Nest monastery

Of course, there is a underlying assumption that you will, at some point, become enlightened. The invisible veil that hindered your sight before (although you were not aware of it) will fall from your eyes, and everything will become clear. But you don’t ask yourself when or how this will happen. I believe this is the attitude with which you need to approach Knuth in general, and the MIX architecture in particular.

However. While I am quite convinced that you will be enlightened should you seek Master Knuth in his monastery, I am equally convinced that there are other paths that lead to enlightenment as well.

In the end, I suppose it comes down to with which monk you want to study. What are you looking for? What is the nature of the enlightenment you seek? If the answer is that you want the most profound understanding possible of how algorithms and data structures correlate with the detailed workings of the the physical machine, you should read Knuth. If the answer is something else, well, perhaps you should read something else.

For my part, I’m not sure I won’t at some point in the future, in fact, walk the long, winding, barefoot road to Knuth. First, though, I want to be a wizard’s apprentice in the school of Abelson and Sussman. There I can study the problems of calculation and abstraction free from the tethering of the underlying hardware. It seems like so much more fun, to be honest. That may be an immature grounds for making such an important decision, but there you go. I’m so much younger now that I’m older, I can afford those kinds of transgressions.