Donald Ervin Knuth is trying to explain what has delayed work on Volume 4 of his magnum opus. "I've never been a good estimator of how long things are going to take," he says.
Coming from someone who's been writing one book on and off for the past quarter-century, this seems a bit of an understatement. But when you consider that most of Knuth's work has been devoted to just that -- figuring out how much time things like computer programs take -- and the statement takes on new (and slightly disingenuous) meanings.
"I'm getting toward being able to take up Volume 4 full time," Knuth says. "I'm writing little snippets. I wrote a sentence just the other day."
"Volume 4," of course, refers to the long-awaited next installment of Knuth's masterwork, "The Art of Computer Programming." Less a set of instruction manuals than a kind of analytic philosophy of programming, the books -- which first appeared in the 1960s -- lay out principles both broad and specific to guide computer programmers toward greater efficiency. So comprehensive are the texts that the Jargon File of hacker slang offers a definition of the word "Knuth": "Mythically, the reference that answers all questions about data structures or algorithms," and goes on to recommend a safe response to any question for which you don't have a ready answer: "I think you can find that in Knuth."
Time was when such a comment would have the curious programmer dusting off "Fundamental Algorithms" and "Sorting and Searching" (Volumes 1 and 3 of "Knuth"), which were required reading in computer science courses for decades. But modern keyboard jocks no longer worry about things like saving 11 microseconds in each iteration of a binary tree search (if they even know what a binary tree is). Instead, they spend their time assembling prefab software components and designing graphical user interfaces to wow clients. Some "write" whole systems having never even seen a line of code. To them, Knuth, now professor emeritus of the art of computer programming at Stanford University, is irrelevant, abstruse and bothersome because he illustrates concepts in machine code, the lowest-level programming language and the hardest to read.
If his attention to the minutiae of programming has earned the annoyance of a younger generation of programmers, though, Knuth remains the iminence grise of algorithm analysis, and one of the leading thinkers on programming in general.
"I think of him as sort of a godfather," says software engineer Ellen Ullman, author of "Close to the Machine: Technophilia and its Discontents." "It would be very difficult these days to take a job and approach programming in that sort of algorithm and design sense, [but] it's a solace to think that there are places where people think deeply about algorithms in a general and abstract way and have notions of elegance and beauty."
Of course, other computer scientists have made contributions to the field that are every bit as substantial (most notably Edsger Dijkstra, Tony Hoare and Niklaus Wirth). But Knuth's work brings to life the complex mathematical underpinnings of the discipline, and deals with the logistics of programming on all levels, from the conceptual design of solutions to the most intimate details of the machine. The fundamental elements of any computer program are, perhaps not surprisingly, time and space. (In programming terms, time describes the speed with which a program accomplishes its task, while space refers to the amount of memory a program requires both to store itself -- i.e. the length of the code -- and to compute and store its results.) But Knuth is concerned not only with bytes and microseconds, but with a concept that has come to be known in coding circles as "elegance," and that applies to programming at any level.
Elegance takes in such factors as readability, modular coding techniques and the ease with which a program can be adapted to other functions or expanded to perform additional tasks. (Knuth's broader ideas about documentation and structured programming are laid out in his 1992 book, "Literate Programming.") Though rarely mentioned, "sloppy coding" often costs companies a great deal in terms of time and money; programmers brought in to update the code of consultants gone by must spend hours or days deciphering a poorly documented program, or hunting down bugs that might have been caught easily had the initial programmer simply been a bit more conscientious in the practice of his craft.
Ullman points out that "the practice of programming has moved very far away from the notion that the professional programmer considers algorithms in a deep way. Of course," she adds, "it would be impossible if every bit of code had to go through that kind of deeply professional process. On the other hand, the code that we have would be better. There's no doubt in my mind that it would be better and more long-lasting code."
Ullman, however, admits she hasn't revisited Knuth's work in many years. Many people are put off on even a first reading by the "mythical" computer with which Knuth illustrates his concepts. MIX, "the world's first polyunsaturated computer," was designed by Knuth as a kind of ideal machine along the lines popular in the 1960s. (Knuth is now updating MIX to MMIX, a reduced instruction-set computing machine that more closely mimics computers in use today.) "The Art of Computer Programming" is filled with examples in MIX, Knuth's fictional machine code and assembly language. In today's world of natural-language compilers, pseudo-code and "click-and-drag" programming tools, though, learning a new assembly language is as attractive to most students of computer science as a visit to the dentist.
But programmers ignore "the very pulse of the machine" (a Wordsworth quotation found in Volume 1) at their peril. As Lyle Ramshaw, a former graduate student of Knuth's, points out, "Don claims that one of the skills that you need to be a computer scientist is the ability to work with multiple levels of abstraction simultaneously. When you're working at one level, you try and ignore the details of what's happening at the lower levels. But when you're debugging a computer program and you get some mysterious error message, it could be a failure in any of the levels below you, so you can't afford to be too compartmentalized."
"MIX was incredibly popular in the early '70s," Knuth says. "Right now there are a lot of comments on Amazon.com saying how it was my terrible mistake, and how am I ever going to recover from it? Well, some of those comments are right, but some of them are dead wrong. The people who say I shouldn't have machine language and just go into high-level languages, they're the ones I think are wrong."
In fact, without machine code, it would be impossible for Knuth to even attempt the low-level analyses (like the time spent executing each instruction in a computer program) that are the backbone of his work. The same BASIC program, for instance, may run at different speeds and use different amounts of memory on different types of machine. In addition, such languages tend to go in and out of vogue faster than a Madonna single. If Knuth based his books on Java, C++, VisualBASIC or SNOBOL (remember SNOBOL?), they'd be obsolete in a matter of months.
And as Knuth points out, "People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird."
If Volume 4 has been a long time coming, Knuth has not been idle. Since finishing Volume 3 in 1973, he has written several academic works on computer science and mathematics, composed a novel (it took him one week), developed revolutionary and widely used desktop typography and font design systems (in which all of his books are now handsomely typeset) and engaged in a study of Chapter 3, Verse 16, of every single book of the Bible, which he published in 1991. ("It's different from any other book, and that means it was either very necessary or never should have been written," Knuth says.) He has also revised his earlier books, incorporating thousands of improvements, "including all the letters from people saying they had found errors." Knuth offers a reward of "at least" $2.56 (a "hexadecimal dollar") to anyone who points out a previously unsighted mistake in one of his books. To date, he has written more than $10,000 worth of such checks. "But I'm not sure how much of it has actually been cashed," he notes.
Unlike most books, Volume 4 will not appear all at once. Instead, 128-page fascicles will be released more or less as Knuth finishes writing them. Though not scheduled for publication until 2000 or later, the fascicles are sure to begin circulating informally before then. (A fascicle describing the MMIX machine is already available on the Internet.) Knuth, now 61, hopes to finish the book around 2003 -- though "that's probably slipped by a year or two," he admits. It could be a decade or two into the next millennium before he completes the set.
Peter Gordon, Knuth's editor at Addison-Wesley, sounds wistful when asked about a due date for Volume 4 (which will actually be published as three "sub-volumes"). "From my 20 years' experience in computer-science publishing, the most frequently asked question by far is, 'Where is Volume 4?'" he says. "Nobody has to say more than that, who the author is, what book they're talking about. Just 'Volume 4.'"
Speaking with Knuth, one gets the impression of a man hard pressed to keep up with his mind's high-speed output of ideas. His writing career dates back to 1957, when, as a 19-year-old freshman at the Case Institute of Technology, he earned $25 for the publication of his "Potrzebie System of Weights and Measures" in Mad magazine. His style has remained delightfully literate, featuring sly plays on the jargon of computing, as well as some that are not so sly: Chapter 2 of "Fundamental Algorithms" opens with "Hamlet's" first-act resolution "Yea, from the table of my memory I'll wipe away all trivial fond records."
Besides demonstrating the techniques of clear, efficient coding, Knuth has sought to bring a deeper sense of aesthetics to the discipline. "You try to consider that the program is an essay, a work of literature," he says. "I'm hoping someday that the Pulitzer Prize committee will agree." Prizes would be handed out for "best-written program," he says, only half-joking. Knuth himself has already collected numerous awards, including the National Medal of Science from then-President Jimmy Carter and Japan's prestigious Kyoto Prize.
And though it may take him another quarter century to complete his magnum opus, Knuth is already dreaming up projects to come -- including the computer-aided composition of an orchestral piece based on the Book of Revelations.
At Stanford, Knuth no longer teaches, though he occasionally lectures on whatever happens to interest him at the moment. (This fall will find him at the Massachusetts Institute of Technology, talking about "Things a Computer Scientist Rarely Talks About.") When he has the time, Knuth reads four-hand piano music with friends on his Bosendorfer grand, or plays the 16-rank organ that stands across from it in the music room of the Palo Alto, Calif., home he shares with his wife, Jill. Otherwise, his days are spent sifting through scientific journals, research papers and pages on pages of notes for his next books. "I'm obsessively detail-oriented," Knuth says. An example: During the 10 years or more in which Knuth was occupied designing the TeX typesetting system and revising Volumes 1 through 3, he accumulated a 270-inch stack of such correspondence. Twenty-two and a half feet of heady research may be daunting, but more revealing is the fact that Knuth actually measured it.
Though the world of programming may have little time these days for Knuth's rigorous analytical style and painstaking attention to low-level detail, his work remains an indispensable contribution to the body of knowledge that is computer science. He will perhaps one day be remembered as programming's Dr. Johnson, but the label would do him a disservice, for Knuth's ideas of elegance can be applied to more disciplines than simply the digital realm. Knuth hesitates at this suggestion, then demurs: "Everyday life is like programming, I guess," he says. "If you love something you can put beauty into it."