Donald Knuth

During his freshman year, Knuth worked in the statistics lab drawing graphs, key punching tabulating cards, and using a card sorter. In December of 1956, he spotted the newly installed IBM 650 computer across the hall. The 650 intrigued him, and he spent much of the summer of 1957 getting to know how it worked. He wrote a variety of interesting programs during his undergraduate years, including one to rate the performance of members of the basketball team he managed.

Knuth was so good at mathematical studies at Case that the faculty awarded him an M.S. in mathematics when he finished his B.S. work.

While working on his PhD in mathematics at the California Institute of Technology, Knuth also did private consulting, and wrote compilers for various computers.

The word got around that he knew a lot about compilers, and in January 1962, in his second year at Cal Tech, Addison-Wesley asked him to write a book on compilers. He sketched 12 chapters and signed a contract. After receiving his PhD in 1963, Knuth began working on a chapter on sorting, a topic related to some compilers. He read many technical articles, and noticed the spotty and sometimes unreliable nature of the literature in the, then new, field of computer science. He saw the need for someone to write a book which organized and reliably presented what was then known about the field. Knuth was a good writer and had an instinct for trying to organize things, so he decided to tackle it.  He used a quantitative rather than qualitative approach, and emphasized aesthetics—the creation of programs that are beautiful. The book grew longer as he wrote it, reaching 3,000 hand-written pages (the equivalent of 2,000 printed pages) by the time he finished the first draft of the 12 chapters in June 1965.

Addison-Wesley decided that the 12 chapters should be reorganized into 7 volumes, with a chapter or two per volume. The first four volumes  were to be on basic concepts and information structures (volume 1, chapters 1 and 2), random numbers and arithmetic (volume 2, chapters 3 and 4), sorting and searching (volume 3, chapters 5 and 6), and combinatorial algorithms (volume 4, now scheduled to be divided into at least two volumes). Volumes 5-7 were to be the more compiler specific chapters (lexical scanning and parsing, context free languages, and compiler techniques).

Knuth is well-known for his perfectionism, and offers to pay $2.56 for each error found in TAOCP books. Finding one confers prestige on the discoverer, many of whom frame and display the hand-signed check rather than cashing it.

As the topics covered by volumes 1-3 developed, Knuth revised them. He was deeply disappointed when, in 1973, he saw the typesetting from Addison-Wesley for the second edition of volume 2. By then the publishing industry had replaced traditional mechanical typesetting technology with computerized typesetting that did not reproduce the high quality of the original printings of volumes 1-3.

Consequently, in 1977 Knuth began developing a new typesetting system to enable high quality computerized typesetting, in particular for TAOCP. This system was announced in his 1978 American Mathematical Society Gibbs Lecture entitled "Mathematical Typography" and published in the Bulletin (New Series) of the American Mathematical Society, volume 1, 1979, pp. 337-372. Knuth had two goals for his system:

(1) achieving the finest quality printed documents

(2) creating a system that would be archival in the sense that it was independent of changes in printing technology to the maximum extent possible.

Knuth's system, developed with help from Stanford students and colleagues, had three primary components: the TeX typesetting engine, the METAFONT font design system, and the Computer Modern set of type fonts .  Combined, these revolutionized digital typesetting. Knuth made his code publicly available, and it has been widely adapted by commercial typesetting systems.

In the early 1970s Knuth learned the "structured programming" methodology promoted by Dijkstra, Hoare,  Dahl, and others. TeX and METAFONT were the first large programs Knuth had written since 1970, and he wrote them using structured programming.

The first version of TeX was written in the SAIL (Stanford Artificial Intelligence Language) programming language. People other than Knuth began to use TeX in the summer of 1978. While working to make a more portable Pascal-language version of TeX, Knuth experimented with typesetting the software itself. This led to a system he called DOC to support structured programming and documentation of the program. DOC was used in the spring of 1980 to create a highly portable version of TeX.

The 1974 A.M. Turing Award was presented to Professor Donald E. Knuth of Stanford University for a number of major contributions to analysis of algorithms and the design of programming languages, and in particular for his most significant 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.

The Turing citation also refers to "design of programming languages", the topic that first hooked Knuth on computers, and an area in which he was active from 1957-1971.

Papers

Videos

All lectures by Donald Knuth (Watch on YouTube)