These days, Donald Ervin Knuth spends most of his time in his study, poring over books, papers, and essays in an attempt to finish his life's work, The Art of Computer Programming. Forty years of advances in computer science are congealing, one idea at a time, into a thorough account of a field that this retired Stanford professor helped birth.
"I wrote a sentence this morning," Knuth says just after 10 a.m. on the phone from his California home. It's probably one sentence in section Zero of Volume 4A, which at the moment takes precedence over sections One, Two, Three, and Four of part A, along with parts B, C, and possibly D.
Ever since he started working on the first three volumes of The Art of Computer Programming in the 1960s, Knuth has been meticulous about representing the field as one where work can be done methodically, using mathematical proofs and verification.
"I was the first to show that it could be a science," Knuth says about the first three volumes, which were published in 1968, 1969, and 1973. At that time, the book helped shape a field in its infancy and is still considered the most authoritative work on its subject. While it's Knuth's largest claim to fame, his accomplishments in both computer programming and mathematics have defined the life of this versatile scientist.
Knuth entered Case Institute of Technology (now Case Western Reserve) as a physics major in 1956, but graduated in 1960 with both a BS and an MS in mathematics. He was passionate about so many subjects that it was hard to settle on just one. During a fateful encounter with the IBM 650 in 1957, though, Knuth knew computer programming would be more than just a hobby.
Yet he never imagined computing would involve so much of his first love - math. "I was an engineer when I was working with the computer, and a mathematician when I did math," he says. "I never thought those worlds would mix."
They began to, and long before Knuth started writing the book, he was helping the field of computer science evolve. While still in school, his numerical analysis class used one of the textbooks he wrote. "I aced that class," he jokes.
A Work in Progress
After graduation, he went to work on his PhD in mathematics at the California Institute of Technology. At that time, universities didn't have established programs in computer science. The field rose out of different departments - math, engineering, physics - at different schools, Knuth says.
By 1962, word of his pioneering efforts in computer programming had spread, and publisher Addison-Wesley asked him to write a text on compiler design. That's when his life's work began.
Knuth took about seven years to hammer out the first version of The Art of Computer Programming, which started out as 3000 handwritten pages and tackled more than just compilers. Since it was so long, Addison-Wesley published it in three volumes - the first when Knuth had become a professor at Stanford. His aim was to summarize all that was known about computer methods and frame it in a mathematical and historical context.
"I wanted to make it more rigorous, so you could be more sure of \\[a program you've written\\]," he says. Rather than just writing programs and fixing bugs later, Knuth hoped his methodical approach would help programmers analyze which algorithms would work best in certain situations.
Knuth now focuses on trying to keep up with all the innovations in the field, which has made organizing the work a bit challenging. "Every three pages is somebody's career," he says. Just for part A of Volume 4, Knuth started writing sections Two, Three, and Four before realizing he needed to include sections One and Zero for context. "In the beginning of computer science, the present was all the knowledge we had at the time. Now, there's so much history and framework to add."
Cultivating His Eccentricities
Some might say his meticulousness is another one of his eccentricities, like how he writes checks for $2.56 - one "hexadecimal" dollar, representing the system of shorthand for binary code - to anyone who catches mistakes in his books.
"You have to cultivate a few eccentricities," he says, though some might say the incentive is just plain generosity. It's certainly characteristic of Knuth, evident in his decision to propagate two of his typesetting programs as open-source.
For 10 years, Knuth took a break from writing to create TeX and METAFONT, two programs that aid the process of typsetting scientific research papers. He developed the software at Stanford, inspired by difficulties in formatting some of his work on mathematical theorems.
One problem dubbed the "big bang," describing what happens as connections are continuously added between points in a line, often kept Knuth awake. Just after 4 a.m. one morning in 1992, he "saw" the problem at the moment the points coalesced, determining what happens immediately before and after the collision.
The next day, Bill Gates came to Stanford with the intention of donating money for the construction of the school's new computer science building. Knuth says he raced to present his research to a class where Gates was sitting in.
"Bill was happy to see it," he says. "The next day, he signed a contract."
By 1993, Knuth retired from Stanford as a Professor Emeritus of the Art of Computer Programming. One of his most memorable moments, he says, was receiving the National Medal of Science from President Carter in 1979. And winning the Kyoto Prize in 1996 was like winning the Japanese equivalent of the Nobel Prize.
"It's like that famous statement," he says. "The hardest thing to do when writing a book is to figure out where to start. It's the same thing with a computer program. You have to try to get everything up to speed, but you just don't know what it will ultimately be like."