Donald ("Don") Ervin Knuth

Donald Ervin “Don” Knuth was born January 10, 1938, in Milwaukee, Wisconsin. His father was a teacher in a Lutheran high school and a church organist. Don Knuth attended Lutheran high school and, in later life, also became a church organist.

Education

In the 7th and 8th grades Knuth was very interested in the structure of English grammar. In high school he was interested in physics and was good at mathematics. Heading for college, he wondered whether to major in physics or music, but chose the former because he got a scholarship to the Case Institute of Technology in Cleveland, Ohio. In his sophomore year of college he switched his major from physics to mathematics, partly because he had trouble with science labs.

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 recalls his first computer programming, for an IBM 650.

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.

The Art of Computer Programming

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

Knuth describes the Algol compiler he wrote for Burroughs and his decision not to develop commercial software for a living.

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 [1] 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 describes how The Art of Computer Programming series became his lifetime project.

Volume 1 of The Art of Computer Programming was published in 1968. That same year Knuth moved from Cal Tech to Stanford University, a move motivated partly by the fact Stanford also agreed to hire his colleague Robert Floyd, the 1978 Turing Award winner.

Knuth on Stanford, computer science, and Robert Floyd.

By 1973 Knuth had published volumes 1-3 of The Art of Computer Programming (“TAOCP”), which did the job Knuth intended of summarizing what was then known about the topics covered in those first six chapters. TAOCP emphasized a mathematical approach for comparing algorithms to find out how good a method is. Knuth says that when he decided this approach, he suggested to his publishers renaming the book The Analysis of Algorithms, but they said "We can’t; it will never sell." Arguably, the books established analysis of algorithms as a computer science topic in its own right. Knuth has stated that developing analysis of algorithms as an academic subject is his proudest achievement.

Turing Award

The first three volumes of TAOCP had great impact on the field and encouraged many people to build on his work. In 1974 Knuth was awarded the ACM's Alan M. Turing Award, with the citation specifically citing his book series. B. A. Galler commented [7]: 

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 [d].

TeX and METAFONT: typesetting and font design

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.

Knuth explains the origins and motivations of the TeX project.

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 recalls the design and implementation of TeX.

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 [4].  Combined, these revolutionized digital typesetting. Knuth made his code publicly available, and it has been widely adapted by commercial typesetting systems.

Knuth explains why he hated the initial output of TeX and how he learned to take fonts seriously.

Knuth put hooks in his TeX engine so that others could make additions, with the condition that any resulting system be give a different name. That produced a vibrant, worldwide community of users and developers for TeX and related systems like LaTeX, ConTeXt, LuaTeX. Knuth's TeX was an early success story for the free and open-source software movement.

Knuth thought his typesetting work would take a year or two, but it was not until 1990 that he announced that he would make no further changes to his systems except to correct serious bugs.

Structured and literate programming

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 TeX Users Group was also established in early 1980.  Once enough user feedback was gathered, Knuth decided that TeX and METAFONT needed to be rewritten. The original program was renamed TeX78, and the new program was called TeX82. In writing TeX82, Knuth decided DOC also needed to be rewritten and he created WEB, so called because it created a web of program and documentation that was both a compilable program and beautiful documentation. METAFONT was also rewritten in WEB. The second and fourth volumes of bibliographic item 4 illustrate TeX and METAFONT documented using WEB—what Knuth called literate programming.  Later versions and additions to WEB were based on the C programming language.

Knuth describes the concept of “literate programming”.

Other activities, TAOCP continued, and Knuth's overall approach

Throughout his career, Knuth has published extensively in a variety of technical areas; bibliographic item [7] lists the volumes of his collected papers in eight different topic areas. At Stanford he supervised more than 30 PhD students. He created important courses such as Analysis of Algorithms [2], Concrete Mathematics [3], and the legendary Programming and Problem Solving Seminar.

In addition to his own teaching and research, Knuth has served the computing community on professional society committees, as an invited lecturer on many occasions, and on the editorial boards of more than 30 technical journals. He is the holder or co-holder of 5 patents.

Knuth considers TAOCP his masterwork, and in 1993 he retired early to spend more time writing additional volumes. He had produced revised editions of volumes 1-3 in 1978-1979. He designed a new hypothetical computer to replace the MIX computer of volumes 1-3 for the analysis of algorithms; this new computer was described in Knuth's 1999 book devoted to the topic [8]. 

Knuth began releasing volume 4A of TAOCP, on combinatorial algorithms, in fascicles ranging from 128 to 250 pages. In early 2011 the 921-page volume 4A was published, but the later parts of chapter 7 were reserved for future volumes.

Donald Knuth is one of the preeminent computer scientists of our time. He has made major contribution to many areas, in effect pursuing multiple simultaneous and serial careers, any one of which would be a proud lifetime achievement for other people. He credits much of the success of his work to combining theory with practice. Knuth is the rare theoretician who writes many lines of code every day. Programming is an art he practices often.

Knuth married Nancy Jill Carter in 1961. They have two children, John Martin (born 1965) and Jennifer Sierra (born 1966).

Knuth has been widely interviewed, both for print and on video. The TeX Users Group maintains a fairly comprehensive list of his interviews.

Essay Sources

a. "Donald Knuth," Interviewed by Donald J. Albers and Lynn A. Steen, Mathematical People: Profiles and Interviews, Donald J. Albers and G. L. Alexanderson, editors, Birkhauser, Boston, 1985, pp. 182-203.
b. Donald Knuth, "Robert W Floyd, In Memoriam," ACM SIGACT News, Volume 34 Issue 4, December 2003, pp. 3-12.
c. "The Art of Computer Programming," June 2011 interview of Knuth by British Computer Society editor Justin Richards, http://www.bcs.org/content/conWebDoc/40462
d. Donald Knuth, Selected Papers on Computer Languages, see the 2003 volume of bibliographic item 7.
e. Donald Knuth, Digital Typography, see the 1999 volume of bibliographic item 7.
f. Donald Knuth, Selected Papers on Computer Science, see the 1996 volume of bibliographic item 7.
g. Donald Knuth, Literate Programming, see the 1992 volume of bibliographic item 7.
h. Knuth's personal website: http://www-cs-faculty.stanford.edu/~uno/
i. Knuth's curriculum vitae (CV) : http://www-cs-faculty.stanford.edu/~uno/vita.pdf

Author: David Walden