Day 4: CM, Page iv

Richard M. Stallman, Linus Torvalds, and Donald E. Knuth engage in a discussion on whose impact on the computerized world was the greatest.
Stallman: "God told me I have programmed the best editor in the world!"
Torvalds: "Well, God told *me* that I have programmed the best operating system in the world!"
Knuth: "Wait, wait - I never said that."

From rec.humor.funny.
submitted by ermel@gmx.de (Erik Meltzer)

Day 4. Another easy page. The bibliographic information. Copyright '94, and '89. Nothing else too interesting, so let's take some time and get to know Knuth a little better. Here's a good link with information about Knuth. I will pull out some of the highlights, but go read the link for more. http://www.softpanorama.org/People/Knuth/index.shtml

Here is one of the earlier anecdotes about Knuth. Even when he was young, he was a problem solver:

One episode, repeated in most biographies of Knuth but still worth repeating in this one, concerns "Ziegler's Giant Bar." He entered a competition by the confectionary manufacturer Ziegler to make as many words with the letters from the phrase "Ziegler's Giant Bar" as possible. Donald spent two weeks during which he pretended to be ill and came up with 4500 words. The judges for the competition had only found 2500.

Not surprisingly, Knuth was a strong student, but had doubts about his mathematical abilities:

According to www.digitalcentury.com encyclopedia article about him: Although Knuth accomplished the highest grade point average in the history of his high school, he and his advisors had doubts as to his ability to succeed at college math. Knuth reports having something of an inferiority complex during his high school and early college years, a problem to which he attributes his over-achiever status. As a college freshman he would spend hours working extra problems in math out of fear that he would fail, only to find after a few months that his abilities far exceeded any of his colleagues.

He proved to be a strong mathematician:

Here is a relevant quote from www.digitalcentury.com encyclopedia: Knuth’s plan to become a music major changed when he was offered a physics scholarship at Case Institute of Technology (now Case Western Reserve). His turn toward math came during his sophomore year when a particularly difficult professor assigned a special problem, offering an immediate "A" in the class to any student who could solve it. Although like most of the other students, Knuth considered the problem unsolvable, he made an attempt at it one day when he found himself with some free time, having missed the bus that was taking the marching band to a performance. By what he states was "a stroke of luck," he solved the problem in short order, earned his "A," and skipped class for the rest of the semester. Although Knuth reports that he felt guilty about skipping class, he was obviously able to overcome the lost instruction because the following year he earned an "A" in abstract mathematics and was given the job of grading papers for the very course he had failed to attend.

And eventually got his PhD - he solved his thesis problem in an hour:

I got a listing from a guy at Princeton who had just computed 32 solutions to a problem that I had been looking at for a homework problem in my combinatorics class. I was riding up on the elevator with Olga Todd, one of our professors, and I said, "Mrs. Todd, I think I'm going to have a theorem in an hour. I am going to psyche out the rule that explains why there happen to be 32 of each kind." Sure enough, an hour later I had seen how to get from each solution on the first page to the solution on the second page. I showed this to Marshall Hall. He said, "Don, that's your thesis. Don't worry about this block design with =2 business. Write this up instead and get out of here." So that became my thesis. And it is a good thing, because since then only one more design with =2 has been discovered in the history of the world. I might still be working on my thesis if I had stuck to that problem. But I felt a little guilty that I had solved my Ph.D. problem in one hour, so I dressed it up with a few other chapters of stuff.

With Knuth's ability, he had a lot of options. He eventually decided he wasn't going to "optimize [his] income":

I had learned about the Burroughs 205 machine language, and it was kind of appealing to me. So I made my own proposal to Burroughs. I said, "I'll write you an ALGOL compiler for $5,000. But I can't implement all of ALGOL for this; I am just one guy. Let's leave out procedures." Well, this is a big hole in the language! Burroughs said, "No, you've got to put in procedures." I said, "Okay, I will put in procedures, but you've got to pay me $5,500." That's what happened. They paid me $5,500, which was a fairly good salary in those days. So between graduating from Case and going to Caltech, I worked on this compiler. Heading out to California, I drove 100 miles each day and then sat in a motel and wrote code. Then a startup company came to me and said, "Don, write compilers for us and we will take care of finding computers to debug them. Name your price." I said, "Oh, okay, $100,000," assuming that this was [outrageous]. The guy didn't blink. He agreed. I didn't blink either. I said, "I'm not going to do it. I just thought that was an impossible number." At that point I made the decision in my life that I wasn't going to optimize my income.

His work on compilers eventually morphed into TAOCP:

In 1962 Addison-Wesley proposed that he write a book on compiler construction. That was a much larger and much more important field that it is now. Indeed, all computer science research in those days was pretty much carved up into three parts: numerical analysis, artificial intelligence, programming languages and their compilers. The offer was accepted and lead to now famous "The Art of Computer Programming" which is definitely much more then the book on computer construction and related algorithms. He began that project in the summer of 1962 one year before graduation and being married to his wife just four months.

Here's what Knuth had to say about it:

A man from Addison-Wesley came to visit me and said "Don, we would like you to write a book about how to write compilers." I thought about it and decided "Yes, I've got this book inside of me." That day I sketched out—I still have that sheet of tablet paper—12 chapters that I thought should be in such a book. I told my new wife, Jill, "I think I'm going to write a book." Well, we had just four months of bliss, because the rest of our marriage has all been devoted to this book. We still have had happiness, but really, I wake up every morning and I still haven't finished the book. So I try to organize the rest of my life around this, as one main unifying theme.

He wrote the first volume of TAOCP by the age of 28:

[Knuth] wrote one of the most compact Algol compilers at the age of 22 and published the first volume of The Art of Computer Programming at the age of 28. His three volumes of The Art of Computer Programming played an important role in establishing and defining Computer Science as a rigorous, intellectual discipline.

After getting his PhD and finishing the first volume, he became a professor at Stanford. He already had a reputation:

Even among computer pioneers in Stanford, Donald Knuth was considered to be almost legendary figure. The following old anecdote from Alan Kay, one of the principal designers of the Smalltalk language, illustrates the point: When I was at Stanford with the AI project [in the late 1960s] one of the things we used to do every Thanksgiving is have a computer programming contest with people on research projects in the Bay area. The prize I think was a turkey. [John] McCarthy used to make up the problems. The one year that Knuth entered this, he won both the fastest time getting the program running and he also won the fastest execution of the algorithm. He did it on the worst system with remote batch called the Wilbur system. And he basically beat the shit out of everyone. And they asked him, "How could you possibly do this?" And he answered, "When I learned to program, you were lucky if you got five minutes with the machine a day. If you wanted to get the program going, it just had to be written right. So people just learned to program like it was carving stone. You sort of have to sidle up to it. That's how I learned to program."

Knuth finished the second and third volume of TAOCP as well as creating the TeX typesetting language. And of course he has done many other things:

He really has managed to make contributions to a very wide area of computer science topics. Among them:
- Suggested the name "Backus-Naur Form"
- Wrote one of first and one of the most compact Algol compilers;
- Designed the SOL simulation language;
- Designed and wrote the TeX and Metafont systems of documentation (written in WEB for Pascal);
- Introduced and refined the LR parsing algorithm (see Knuth, D.E. 1965. "On the Translation of Languages from Left to Right", Information and Control, Vol. 8, pp. 607-639. The first paper on LR parsing.)
- Invented several important algorithms including Knuth-Morris-Pratt string-searching algorithm;
- Made the crucial contribution to the "Structured programming without GOTO" programming debate, which was a decisive blow to the structured programming fundamentalists led by E. Dijkstra;
- Published his groundbreaking paper "An empirical study of FORTRAN programs." ( Software---Practice and Experience, vol 1, pages 105-133, 1971) which laid the cornerstone of an empirical study of programming languages.
- Made the crucial contribution to dispelling "correctness proof" mythology.

But the TAOCP is his masterpiece:

Still no other book in CS can be compared with his encyclopedic The Art of Computer Programming (TAoCP). It is one of the few books that remain largely relevant 30 years after the initial publication. I am convinced that every person who suspects that he/she has a programming abilities (and BTW an early start is a good indication of abilities in any field, including programming) should buy or borrow the first volume of TAoCP and try to solve exercises after each chapter. The ability to solve difficult exercises form the first volume is a sure sign of people with substantial talent and can be a good self-test if you it make sense to dedicate yourself to carrier in computer science or not.

He is continuing to work on the forth volume. Hopefully, he will finish it soon (there are rumors of 2008). But he admits he may not be able to finish his original ambitious plan:

His primary agenda item is, after all, Volume 4, although every few months he’ll browse journals for items to squirrel away for Volumes 5 through 7. People inquire delicately about how he expects to complete a seven-volume project at his current pace, and Knuth concedes he’ll be content to finish the first five.

How do your gain expertise in something?

By studying the masters and not their pupils. Abel, Niels H. (1802 - 1829)

So let's get started studying the master!