Thursday, June 5, 2014: People of ACM: Donald Knuth
Thursday, June 5, 2014
Donald Ervin Knuth is Professor Emeritus at Stanford University. He received the 1974 ACM A.M. Turing Award for his major contributions to the analysis of algorithms and the design of programming languages, and in particular for his contributions to the "art of computer programming" through his series of well-known books. The collections of technique, algorithms, and relevant theory in these books have served as a focal point for developing curricula and as an organizing influence on computer science. A perfectionist, Knuth is also known for his contributions to typesetting, developing the TeX typesetting engine in the 1970s with Stanford students and colleagues in response to what he saw as inferior computerized typesetting of his published books at the time. He holds BS (and honorary MS) degrees in Mathematics from Case Institute of Technology, and a PhD in Mathematics from the California Institute of Technology. He has been professor of Computer Science at Stanford since 1968. Throughout his career, Knuth has published extensively in a variety of technical areas, including computer languages, analysis of algorithms, and literate programming.
As one who has said that he always wanted to be a teacher, what shortcomings in traditional higher education models for computer science would you alter or abandon?
I suppose any complicated enterprise has its shortcomings. But I was always happy with the experiences I had with students at Stanford, both inside and outside the classroom. Maybe it's because I'd heard the idea of "flipped classrooms" already from George Polya in the 60s, and so I used his methods whenever I could, in my classes ever since.
I'm a great fan of having interactive discussions during class, and trusting the students to read their textbooks on their own time.
At other schools, I think the most common fault in general is to teach students how to pass exams instead of teaching them the science.
Similarly, the most common fault in computer classes is to emphasize the rules of specific programming languages, instead of to emphasize the algorithms that are being expressed in those languages. It's bad to dwell on form over substance.
Did you choose the 3:16 John text as part of your systematic sampling Bible study project because 3.16 is the square root of 10, or because this passage was particularly thought-provoking to you?
This question surprises me, because it mainly concerns aspects of my life that are "orthogonal" to ACM's missions. My computer work on book publishing put me in touch with a wonderful community of graphic artists, who helped me to illustrate my book "3:16 Bible Texts Illuminated." And my work on typography allowed me to design special fonts for that book, and to control the production so that every page contains exactly 36 lines of text! Otherwise, the book was independent of computers; I wrote it during my spare time, on weekends, in the parts of libraries that are the most remote from technology. (Well, I guess there was an ACM connection after all, but only tenuous: I think the first time I told anybody that I was planning to write such a strange book was at a gathering of ACM SIGCSE people in Boston, 1986.)
Anyway I don't want to duck your question. I wanted to choose "random" verses of the Bible, in order to investigate what people of many different persuasions had written about them during the years; and I wanted a rule that was easy to remember and impossible to "fudge". So I chose the verse in the Bible whose chapter number and verse number was by far the best known. Maybe I was hoping that I'd get free advertising when a person held up a sign saying "John 3:16" during a football game. In my own personal study, I looked actually at John chapter 16 verse 3, which was unfamiliar; but I knew that other people would like to see at least one famous verse. So my sample was only 98% random.
I did know that 3.16 is essentially the square root of 10, and that the numbers 3 and 16 have lots of other properties. Pages 30-49 of my book Things a Computer Scientist Rarely Talks About will tell you more than you want to know about this! But my main goal was emphatically NOT to select verses that were special, it was to get a cross section.
My experience with algorithms has taught me that random samples are very effective ways to get insights about complex subjects.
Would you agree with a New York Times' reference in 2001 that your three-volume "The Art of Computer Programming" is the profession's defining treatise?
Naturally I'm glad that many people have evidently appreciated my attempts to organize large parts of our field and to try to give those topics a secure foundation. I've also tried to present an adequate history of the important ideas, and to emphasize things that I think are likely to remain important 50 years from today.
But hey, I decided on the table of contents in January of 1962, and I'm still not half done covering the topics that were contemplated then.
So I can certainly not claim to be "definitive" except with respect to the most classical parts of our subject. For those parts, on the other hand, I've spent most of my life trying to tell the story as well as I could.
As a founding artist of computer science and a proponent of elegance in programming, what advice would you give to young people considering careers in computing?
Computing today involves many different kinds of paradigms and many different kinds of talents. I can speak only to people who happen to have grown up with the strange kind of "brain-organization" that I seem to have somehow acquired; for lack of a better word, let me simply say that I'm a "geek." I haven't got a good definition or a good litmus test for geekhood, but I definitely know it when I see it; and I see it in about 2% of the world's population. The main characteristic is an ability to understand many levels of abstraction simultaneously, and to shift effortlessly between in-the-large and in-the-small. A geek knows that, to achieve a certain high-level goal, you need to add one to a certain counter at a certain time.
Dear young person, if you are a geek, the world needs you, and you will never run out of opportunities to apply your talents. I urge you to take a close look at "literate programming"; it's a way to write programs that makes me incredibly happy, several times each week. My book The Stanford GraphBase contains several dozen short examples of programs written in that style, intended to be read by humans first and machines next.
Dear young person, if you are not a geek, please ask somebody else for advice.