The Art of Computer Programming

Softpanorama Classic Series

The Art of Computer Programming (TAOCP)
by Donald Knuth

See the introduction to the series for more information

Donald Knuth is probably the greatest of living computer scientists and an important contributor to the open source (he authored Tex). See Portraits of Open Source Pioneers-- the chapter 2 is devoted to Donald Knuth. It also contains additional information about this classic book and a collection of Donald Knuth interviews

All three volumes of The Art of Computer Programming (TAOCP), are classic. Each is IMHO a book that every CS student should try to study re-implementing example by example. Not many will succeed to finish even half of one volume, but if you do please buy all three of them :-).

I think the most important is to study Vol 1. It gives enough exposition to the Donald Knuth style and brilliant thinking. It is the level of thinking of the author that represents the main value of the book: you instantly understand the the book was written by a great scientist and it does not matter much that now the contents of most chapters can be significantly improved using more modern sources. After all Vol 1 is more then a 30 years old book (it is older then Unix) and as such it should be outdated (we all believe in progress, don't we)...

Please note that parts of Vol. 1 on of TAOCP looks completely out of touch with reality especially MIX assembler.

Actually MIX assembler was outdated even when the book was first published and more reflects unique Knuth's background with IBM 650, not so much the state of hardware development in late 60th, the period when IBM/360 was the king of the hill.

Now IBM 650, a 1,966 lb machine that consumed almost 30 Kw of electricity looks more like a primitive calculator than a real computer: typical installation has the memory of just 10,000 decimal digits ( 1,000 words; 10 digit per word).

It's really sad that Knuth did not adopt System 360 architecture and PL/360 assembler (Wirth's structured assembler for S/360) for his books but we can do nothing about it.

But actually the statement above is not true: this is a book about timeless truths, not the book about the resent CS fashion like Java or you name it :-). It actually can serve as a perfect antidote agaisnt any current CS fashion.

And Knuth does provide pseudocode with his natural language algorithm description. The problem with a "language-like" pseudocode is that the set of control structures is fixed and may not reflect the needs of a particular algorithms (branching out of loop is a common problem that is not addressed by structured programming well) and the subsequent languages advances. For example Perl has an interesting set of control structures that is superior to C. But even it can be improved. That's why assembler language is preferable: it never obscures "natural" control structures for each algorithms, that one day can be mapped into some new elegant language construct. Also as one review noted "sometimes high level languages with all their abstractions make things look more complex than they need be.".

Each volume is very difficult to read; you really need to work your way thru each chapter by reimplementing the examples that Knuth gives in your favorite language (assembler might help but it is not essential).

Mathematical considerations as for average and worst running time a particular algorithm can be largely ignored during the first couple of years of study of this book. Actually most mathematics in Vol. 1 can (and probably should) be initially completely ignored. See Softpanorama Classic computer books for more information.

On the negative side this is an overpriced book. To save money you can buy one of the first editions: there is not that much difference in content to justify the differences in price.
Actually the differences are so minor that are almost unnoticeable. Knuth did an excellent work the first time he published each volume and for a significant improvement we probably need another century and another person.

Here is one of the more interesting (and not so sycophantic :-) reviews of the book on Amazon

Note: I suspect that the author of this review never dealt with algorithms in depth in his professional life: I totally disagree with his recommendation of Cormen &Co. (a.k.a. CLR) which IMHO is devoid of any connection with the reality to be useful. Don't know much about Goodrich's book and the Foundations of Computer Science by Aho/Ullmann (The Tortoise book).

And Knuth does provide pseudocode with his natural language algorithm description. The problem with language as a pseudocode is that the set of control structures is fixed and may not reflect the needs of a particular algorithms (branching out of loop is a common problem that is not addresses by structured programming well) and the subsequent languages development (for example Perl has an interesting set of control structures that are somewhat superior to C. But even it can be improved. That's why assembler language is preferable: it never obscures "natural" control structures for each algorithms. Also as one review noted "sometimes high level languages with all their abstractions make things look more complex than they need be."

92 of 113 people found the following review helpful:

THE CS Bible? Let's be realistic and honest, November 15, 2003

Reviewer:

Strict Evaluation (Seattle, WA USA) - See all my reviews

The Art of CP (TAoCP) book set covers the core of computer science curriculum on data structures and algorithms. Not everything there is today (that would be impossible), just the core, but that's more than enough to begin with (and for most people quite sufficient in general.) This is typical Knuth: he knows his stuff, he writes very well, he's an encyclopedic mind; his texts are mathematically rich, yet at the same time not overwhelming; time and again he demonstrates this 19-th century germanic scientific style, which is to say he's incredibly detailed and exact -- one can even accuse him of pedantry, but in a good sense. He writes with a sharp, dry wit (his sense of humour makes him unique among the rest of the writers on the computing theme.) So far so good.

However, all the benefits mentioned above notwithstanding, I have to say that on balance this triptych of his is impractical. It has either become outdated, or was even originally written with an independently-wealthy reader in mind, someone like an 18th century gentleman-farmer who, fully disencumbered of the vulgarity of having to earn a living, is leasurely indulging in the exercise of his mental ability for the pure intellectual challenge of it; someone with no plebeian concerns of practicality ever entering his exalted mind.

The problem is with MIX. I second what the others said about it, and what's more, I refuse to accept the explanation (purportedly Knuth's) posted below by someone: the problem is not only that MIX is an assembly language (which still would be a functional malapropism in a book like that) -- no, a far more grievous problem is that MIX is a phantasm, a whimsically extravagant invention having no real-life equivalent, at least today. The mythical processor underlying this thing (5-byte words, etc) is not something that anyone below 40 years of age has ever seen, even if it does have historical analogues.

The gravity of the offence here is not that it is some real but unfamiliar processor's assembly -- after all, if you know i86 assembly, you can (kinda, sorta) read the motorola equivalent... No, it is that MIX and the fairy-tale processor architecture it is imagined to run on are *purposely made to resemble nothing* that you may have some familiarity with -- thus making the already-difficult material obfuscated beyond anything even marginally manageable for a regular computing Joe, who has a (real) life, and at any rate, can't limit his CS intake to this one work.

Elucidating difficult in itself CS material via examples in assembly language of even a real (or made-up but realistic) kind is a very bad choice because the student's attention, already taxed by the subject matter itself, will be further burdened by the non-algorithmic nature of the assembly language. But to exacerbate this potential ordeal by insisting on the use of something so gratuitously eccentric and profitless for the reader as MIX is simply unconscionable.

Ideally, what a good CS text of this sort will use is pseudocode. But if a writer wishes to add to his book a realistic slant, it is acceptable that he use some sort of real language -- so long as it is algorithmic; today, C is a perfect choice. Knuth counters (and he's absolutely right): there was no C when the book was written. He's also right in saying that had he written it with Pascal it would have become outdated by now. So if that was the problem, TAoCP could have been written with some sort of pseudocode; this would last forever.

Of course, even using a real language would not actually be such a great problem -- we all know of similar books where the originally-chosen language was replaced when it fell in disuse: for example the numeric programming book by Teukolsky; it started with fortran and was then redone in C; this demonstrates that the language part can be brought up-to-date if necessary. Both Fortran and C are algorithmic languages that, owing to their readability, can be used instead of pseudocode.

Ideally, books should be written with both pseudocode (a must, in my view), and, in order to give an example of an actual implementation, some real language (see the recent book by Goodrich; it's pseudocode throughout and a smattering of Java here and there -- perfect!)

To sum it all up: measured by today's needs, The Art of CP is overrated (out of snobbery; bragging of having read it is "kewl"; meantime, the truth is, not too many people are capable of such a feat for the reasons stipulated above; when actually used, TAoCP books are read in chunks, a chapter here, a chapter there -- which is a shame, because they are very well written, and to work through them in their entirety would be much more profitable than biting off a little here and there.)

I am going to be slammed by the Knuth cult followers for saying this, but I do not recommend these books. Instead, consider something similar but more practical: two titles immediately come to mind, Cormen &Co. (a.k.a. CLR) and Goodrich (forget the title but search on the name.) Foundations of Computer Science by Aho/Ullmann (The Tortoise book) is a suitable option as well.

TAoCP is potentially very good, but until someone ruthlessly excises all the bloody junk (MIX etc.) and replaces it with pseudocode or C, it will remain useless.

Don't get me wrong here: Knuth is an admirable, justly venerated computer scientist, and a very good writer to boot (for example his Concrete Mathematics book is excellent). But when it comes to TAoCP, even though to mention it is very chic in some circles, we must admit the obvious: he has produced a work that's impenetrable (or, rather, the enormity of time and effort required to penetrate it makes such an attempt an unworthy investment) and therefore useless in practical terms for the majority of the potential readership.

Here is another review that touches very important subject: professionalim in programming is strongly correlated with the level of knowledge of TAOCP:

Without reading Knuth you are at most a talented amateur, August 27, 2002

Reviewer:

J. putnam "jefu" (eastern washington state, usa) - See all my reviews

The three volumes of the original version of "The Art of Computer Programming" are more than thirty years old now. I still have the edition I bought back in 1978 or so and they're never too far from the "easy to reach shelf" in my bookshelves. Sometimes I rearrange things and move them away, always figuring that newer books will work as well, but somehow they always move back - not always quickly, but rarely too slowly.

Sometimes its because I just want to reread something, sometimes its because I want to challenge myself with one of the problems, but often enough it is because I find myself needing to supplement information from somewhere else or because I just can not find quite what I need anywhere else. And I will turn to the web to search for things - but first I usually check out TAOCP.

It can be tough going in some places, the math sometimes reaching the "AAArrrggghhhh, run away, run away" kind of appearance, but a bit of work almost invariably pays off.

This is not a book from which you will learn to program. You should have some facility with more than college freshman level mathematics. And you'll need to read things more than once in many cases.

If you're an IT person, a software installer type, a low level coder or the like and are content with this, you can probably afford to avoid ever reading TAOCP, but if you want to solve the hard problems, if you want to learn just WHY things work, and learn the mathematics and the kinds of analysis techniques that make the difference between the grunt programmer and the really good ones, you'll need the math, you'll need the kind of information, knowledge and computerology-goodness-and-niceness that TAOCP (and few books other than TAOCP) can give you.

Seeing a well used copy of TAOCP on a computer professionals bookshelf is always a sign to me that they're serious about their profession and about their own learning. Not seeing one is often a flag that they're someone I'd rather not have on a project I'm involved with. Worse yet not seeing TAOCP on a CS professors bookshelf leads me to the impression that professor is at best semi-educated, and at worst one of those frightening types who managed to slip through the cracks somehow.

Now I'm waiting for Volume 4 (and all the rest). (Interestingly, I got one of those mail back cards from the publisher about 4 years ago asking me if I wanted to reserve a copy of the "soon to be published" V4 - I could not resist calling and asking lots of details about it.)

I was also lucky enough to find copies of the original editions of V1 and V3 two years back in a booksale for a grand total of about a dollar. Now now I have 1.101010... (in binary) sets. If V1-4 get published in a boxed set I'll undoubtedly spring for the set at whatever price.

The Art of Computer Programming : Fundamental Algorithms (Vol 1, 3rd Ed) Vol 1

Donald E. Knuth / Paperback / Published 1997
This is actually a book first published in 1968 and written in 1962-1967. Only small corrections were make in the second and third edition. This edition of the book was produced using TeX.

This book is real classic and it combines unique author style with the the introduction to many important algorithms and concepts of system programming (coroutnes).

The Art of Computer Programming : Seminumerical Algorithms (Vol 2, 3rd Ed) Vol 2

Donald E. Knuth / Paperback / Published 1997
The first edition was published in 1969, one year after the first volume. This edition of the book was produced using TeX. This volume is more difficult to read, more specialized and generally less impressive that the first volume. Some parts of the text now shows its age as the thirty of random generation is now more advanced than in late 60th, when the book was written. You might avoid buying it "just for collection" unless you really use random number generators and other things covered in this volume.

The Art of Computer Programming : Sorting and Searching (Vol 3, 2nd Ed) Vol 3

Donald E. Knuth / Paperback / Published 1998

The first edition was published in 1973. This edition of the book was produced using TeX. This volume now shows its age but still is a very valuable, unique book. I would still recommend buying it.


Preface
Cookery is become an art, a noble science; cooks are gentlemen.: TITUS LIVIUS, Ab Urbe Condita XXXIX.vi
(Robert Burton, Anatomy of Melancholy 1.2.2.2)

This book forms a natural sequel to the material on information structures in Chapter 2 of Volume 1, because it adds the concept of linearly ordered data to the other basic structural ideas.

The title "Sorting and Searching" may sound as if this book is only for those systems programmers who are concerned with the preparation of general-purpose sorting routines or applications to information retrieval. But in fact the area of sorting and searching provides an ideal framework for discussing a wide variety of important general issues:

How are good algorithms discovered?
How can given algorithms and programs be improved?
How can the efficiency of algorithms be analyzed mathematically?
How can a person choose rationally between different algorithms for the same task?
In what senses can algorithms be proved ''best possible''?
How does the theory of computing interact with practical considerations?
How can external memories like tapes, drums, or disks be used efficiently with large databases?

Indeed, I believe that virtually every important aspect of programming arises somewhere in the context of sorting or searching!

This volume comprises Chapters 5 and 6 of the complete series. Chapter 5 is concerned with sorting into order; this is a large subject that has been divided chiefly into two parts, internal sorting and external sorting. There also are supplementary sections, which develop auxiliary theories about permutations (Section 5.1) and about optimum techniques for sorting (Section 5.3). Chapter 6 deals with the problem of searching for specified items in tables or files; this is subdivided into methods that search sequentially, or by comparison of keys, or by digital properties, or by hashing, and then the more difficult problem of secondary key retrieval is considered. There searching related to sorting is a surprising amount of interplay between both chapters, with strong analogies tying the topics together. Two important varieties of information structures are also discussed, in addition to those considered in Chapter 2, namely priority queues (Section 5.2.3) and linear lists represented as balanced trees (Section 6.2.3).

Like Volumes 1 and 2, this book includes a lot of material that does not appear in other publications. Many people have kindly written to me about their ideas, or spoken to me about them, and I hope that I have not distorted the material too badly when I have presented it in my own words.

I have not had time to search the patent literature systematically; indeed, I decry the current tendency to seek patents on algorithms (see Section 5.4.5). If somebody sends me a copy of a relevant patent not presently cited in this book, I will dutifully refer to it in future editions. However, I want to encourage people to continue the centuries-old mathematical tradition of putting newly discovered algorithms into the public domain. There are better ways to earn a living than to prevent other people from making use of one's contributions to computer science.

Before I retired from teaching, I used this book as a text for a student's second course in data structures, at the junior-to-graduate level, omitting most of the mathematical material. I also used the mathematical portions of this book as the basis for graduate-level courses in the analysis of algorithms, emphasizing especially Sections 5.1, 5.2.2, 6.3, and 6.4. A graduate-level course on concrete computational complexity could also be based on Sections 5.3, and 5.4.4, together with Sections 4.3.3, 4.6.3, and 4.6.4 of Volume 2.

For the most part this book is self-contained, except for occasional discussions relating to the MIX computer explained in Volume 1. Appendix B MIX computer contains a summary of the mathematical notations used, some of which are a little different from those found in traditional mathematics books.

Amazon Readers Reviews to all three volumes

Excellent, for certain people!, April 4, 2000
Reviewer: A reader from Uppsala, Sweden

These books are indisputably classics of the field, and like all classics they have religious adherents and equally firm detractors. The key difference between the two groups is that the adherents are interested in computer SCIENCE, whereas the rest are more taken with computer programming. The books are well written, quite mathematical, and abstract. The books deal with the core subjects of computer science and shy away from the trendy, and so some people tend to see them as anachronistic. Nevertheless, they are deservedly core references in computer science, and a joy for any patient, theoretically minded reader. There are three points I believe should be made.

A lot of the detractors of the books are saying correct things: the books don't deal with hot topics, they do present things in greater detail than is necessary in day to day programming, they are books they require a lot of the reader. What they don't recognize is that this is the intention, and that there is nothing wrong with that. The book is targeted at those with a geniune interest in theoretical computer science.
Many reviewers complain about Knuth's typesetting system, TeX. What they fail to recognize is that TeX is incredibly useful, and about as user friendly as could be expected, for the task for which it was designed: typesetting professional quality mathematics. Anyone who challenges this statement would have to contend with virtually the entire community of people who write papers using higher mathematics, including virtually all professional physicists, mathematicians, and computer scientists.
Some people accuse Knuth's books of being poorly written. These people are ignorant: either they have not read the works, or they would not recognize skillful writing if they saw it. These books are splendid examples of scientific writing, and are justifiably acclaimed as such. In short, Knuth's books have ensured that the word "science" deserves its place in the phrase "computer science"

Definitive, June 15, 1999
Reviewer: A reader from Illinois

As Knuth himself says, it is impossible for any one person to keep up with all the research in computer science, but these 3 volumes do a remarkably good job of distilling the most important results and explaining them with mathematical rigor.

Each volume contains 2 chapters.

Ch. 1, Basic Concepts: mathematical foundations and a description of MIX, a hypothetical machine (now available in software emulations).
Ch. 2, Information Structures: lists, trees, memory allocation, garbage collection.
Ch. 3, Random Numbers: how to produce series of "random" numbers and test their statistical properties. Ch. 4, Arithmetic: algorithms for integer and floating-point arithmetic.
Ch. 5, Sorting: both in memory and on disks or tapes.
Ch. 6, Searching: sequential, binary, hashing.

Despite the detailed coverage of the topics, which often involves esoteric mathematical notation, the author's lively style makes the algorithms and the main theoretical results relatively easy to grasp. If all you care about is getting a program to run, buy another book; but if you really want to understand how and why software works, there's nothing quite like this.

Full of little gems, March 8, 2001
Reviewer: fife (see more about me)
Knuth is obviously in the education business. This is a book written for learning from. It's very easy to ignore the parts that are too detailed for your needs and not feel like you've missed something. My favorite parts are his historical notes. These are the reward for ploughing through a section, some of them quite fascinating.

I'm a compiler designer. Compilers like most other big applications are built on stacks, queues, lists, trees, etc. These books will teach you how to implement these structures solidly and efficiently. Alot of my time at work involves reading research papers on optimizations. I need to understand how algorithms are analyzed and how to compare two algorithms. These books give the mathematical tools needed to perform that job. Some criticize his using a machine language for examples. I personally think that this is a good thing. Seeing something done in assembly shows you how easy it really is. Sometimes high level languages with all their abstractions make things look more complex than they need be.

Brilliant & Amazing. Unequaled achievement in this field., August 23, 1998
Reviewer: A reader from Menlo Park
I used to be a high-school student when I accidently found a copy of the first volume. It moved my all life. I decided to become a computer scientist at the end of the first chapter. And today, having accomplished this, I still didn't finish the second volume and it has been a long time already. Nevertheless, I couldn't resist buying the third volume. I just hope to live long enough to get to the end of the fifth and last volume of this collection. Thank you Donald Knuth for this brilliant and inspiring work. --This text refers to an out of print or unavailable edition of this title.

Art of Computer Programming Vol 4 Donald E. Knuth / Hardcover / (Not Yet Published) -- When published this volume will definitely be recorded in the Guinness Book of Records as for the longest interval between the first editions of the previous and next volumes (more than 20 years ;-)

TeX is Donald Knuth most famous open source program. It is extremely rare for a mathematician at Knuth's level to write both a large application program and the documentation -- and even rarer still to succeed. Donald Knuth has written this program to help him to publish his Art of Computer Programming without typos. He created it in 1986 just before PC revolution and it was the first open source typesetting program of such outstanding quality. Donald Knuth spent considerable time learning the book compositor's art, and that shows in the details of TeX -- as with the oft-mentioned paragraph optimization routines. But more than this, TeX is malleable. It is a tool that lets skilled compositors automate more of the niceties of fine composition, rather than having to add them by hand.

Just by chance SGML was chosen as a basis of HTML instead of TeX and TeX instantly became a second class citizen of computer publishing. But the jury is still out and only future can tell the final verdict.

Digital Typography (Csli Lecture Notes, 78) ~ Usually ships in 24 hours

Donald Ervin Knuth / Paperback / Published 1999

The Texbook : A Complete Guide to Computer Typesetting With Tex ~ Usually ships in 24 hours

Donald Ervin Knuth / Paperback / Published 1988

Amazon price: $41.95

Tex : The Program (Computers and Typesetting, Vol B) ~ Usually ships in 24 hours

Donald Ervin Knuth / Hardcover / Published 1986

Amazon price: $51.95

The Metafontbook (Computers and Typesetting, Vol C)

Donald Ervin Knuth / Hardcover / Published 1986

Metafont : The Program (Computers and Typesetting, Vol D)

Donald Ervin Knuth / Hardcover / Published 1986

Computer Modern Typefaces (Computers and Typesetting, Vol E)

Donald Ervin Knuth / Hardcover / Published 1986

Knuth is also an avid proponent of so called literate programming. For me it looks like using HTML for writing both text and documentation and convert the text of the program from HTML to ASCII on the fly before compilation. Also dictionary of all word should be constructed and maintained on the fly by the literate programming tool. It makes perfect sense for large programs. Probably Ms Word, FrontPage or any other powerful HTML editor can be used as a literate programming tool.

Literate Programming CSLI Lecture Notes Number 27. Center for the Study of Language and Information (Palo Alto: 1992). ISBN 0-937073-80-6:

This book that contains description of hypertext based approach to writing code (see Literate Programming -- Propaganda and Tools for intro information) as well as some of the most well know papers. including influential "Structured Programming with GOTO Statements" and Turing Lecture Computer Programming as an Art. A detailed history of all errors in TeX can be found in chapters 10 and 11.

   Contents
     Acknowledgments
     Preface
     1. [A.M. Turing Award Lecture, 1974]
     2. Structured Programming with goto Statements [1974]
     3. A Structured Program to Generate All Topological Sorting Arrangements [with Jayme L. Szwarcfiter, 1974]
     4. Literate Programming [1984]
     5. Programming Pearls, by Jon Bentley: Sampling [1986]
     6. Programming Pearls, Continued: Common Words [1986]
     7. How to Read a WEB [1986]
     8. Excerpts from the Programs for T_EX and METAFONT [1986]
     9. Mathematical Writing [1987]
     10. The Errors of T_EX [1989]
     11. The Error Log of T_EX [1991]
     12. An Example of CWEB [1990]
     Further Reading
     Index

Arguing for an aesthetic appreciation of programming, March 30, 2000
Reviewer: Charles Ashbacher (see more about me) from Hiawatha, IA (ashbacher@ashbacher.com)
Writing computer programs is easy, writing programs that are useful is hard and writing programs that are very useful as well as correct sometimes seems impossible. Knuth takes this truism even further and offers up the radical notion that the very best programs are so profound that people will one day read them as one would a piece of classic literature. If the idea of curling up by the fire with a copy of The World's Greatest Programs and spending the night in a state of rapture seems absurd, you think as I did. However, after reading this book, my mind now concedes the possibility does exist. After all, most of the great works of literature describe actions, conditions and solutions (algorithms) to problems of human-human and sometimes human-god interactions. Science fiction writers and readers have known for a long time that computers are very interesting objects. Buildings, paintings or other works of art are often admired not only for their subjective beauty, but also for the talent that it took to create them. Programming ability can be admired just as easily.
However, an extremely large technical barrier exists, in that programming languages are literal, terse and lack flair. Knuth works to eliminate this problem by combining the programming and documentation languages into a structure called a WEB. He also adopts the reverse paradigm that a program should be an explanation to humans of what the computer is doing. The result does wonders for readability and introduces a bit of flair. Certainly, this is a good first step towards Knuth's ideal.
The development of TEX is chronicled in great detail. It is personally comforting to read about some of the errors made in its development. Learning that the great ones make errors provides emotional security to all who hack for fun and/or profit. Some classic programming problems are used to demonstrate exactly what literate programming is meant to be. Jon Bentley, author of the 'Programming Pearls' section of "Communications of the ACM", contributes two chapters that were co-authored with Donald Knuth. These pearls demonstrate the applications of literate programming to common coding problems. All are presented in a clear, easy-to-understand style.
A bit of clever humor is also used. A WEB program is constructed from two distinct components. The Weave part explains what the program is doing, and the Tangle component produces the program. Of course, this suggests the line from Sir Walter Scott's poem Marmion, "O what a tangled web we weave, when first we practice to deceive."
I do not know whether to consider this book the product of a dreamer or a visionary. The truth, like most of the work of pioneers, is no doubt somewhere in between. My opinion is that it is more vision than dream. And is that not a common theme among the greatest works of art and literature?

Published in Mathematics and Computer Education, reprinted with permission.

There is a free literate programming system -- CWeb -- that is used by Donald Knuth himself. For details see:

The Cweb System of Structured Documentation/Version 3.0

Donald E. Knuth, et al / Paperback / Published 1994

ACM has copyright on a lot of Donald Knuth articles but they were never published them on the WEB for free access, although ACM electronic archive is now available for ACM members for approx. $70 a year.

Selected Papers on Computer Science (Csli Lecture Notes, No. 59)

Donald Ervin Knuth/ Paperback / Published 1996

Everyone should read Don Knuth's homage to the 650. He describes his rapture upon first reading Stan Poley's code for SOAP(Symbolic Optimal Assembly Language, written by Stan Poley of IBM, that was the assembler of choice for almost every 650 user) and the sheer beauty of his work.

Content
     Preface
     Acknowledgments
     0. Algorithms, Programs, and Computer Science [1966; 1992]
     1. Computer Science and its Relation to Mathematics [1973; 1974]
     2. Mathematics and Computer Science: Coping with Finiteness [1976]
     3. Algorithms [1977]
     4. Algorithms in Modern Mathematics and Computer Science [1981]
     5. Algorithmic Themes [1988]
     6. Theory and Practice, I [1977]
     7. Theory and Practice, II [1985]
     8. Theory and Practice, III [1986]
     9. Theory and Practice, IV [1989]
     10. Are Toy Problems Useful [1977]
     11. Ancient Babylonian Algorithms [1972; 1976]
     12. Von Neumann's First Computer Program [1970]
     13. The IBM 650: An Appreciation from the Field [1986]
     14. George Forsythe and the Development of Computer Science [1972]
     15. Artistic Programming [1993]
     Index

[Knuth2000]

Knuth, Donald E. Selected Papers on Analysis of Algorithms. CLSI Lecture Notes Number 102. Center for the Study of Language and Information (Palo Alto: 2000). ISBN 1-57586-212-3 pbk.

Old News

[Apr 25, 2008] Interview with Donald Knuth

By Donald E. Knuth,Andrew Binstock

Date: Apr 25, 2008

Andrew Binstock and Donald Knuth converse on the success of open source, the problem with multicore architecture, the disappointing lack of interest in literate programming, the menace of reusable code, and that urban legend about winning a programming contest with a single compilation.

Andrew Binstock: You are one of the fathers of the open-source revolution, even if you aren’t widely heralded as such. You previously have stated that you released TeX as open source because of the problem of proprietary implementations at the time, and to invite corrections to the code—both of which are key drivers for open-source projects today. Have you been surprised by the success of open source since that time?

Donald Knuth: The success of open source code is perhaps the only thing in the computer field that hasn’t surprised me during the past several decades. But it still hasn’t reached its full potential; I believe that open-source programs will begin to be completely dominant as the economy moves more and more from products towards services, and as more and more volunteers arise to improve the code.

For example, open-source code can produce thousands of binaries, tuned perfectly to the configurations of individual users, whereas commercial software usually will exist in only a few versions. A generic binary executable file must include things like inefficient "sync" instructions that are totally inappropriate for many installations; such wastage goes away when the source code is highly configurable. This should be a huge win for open source.

Yet I think that a few programs, such as Adobe Photoshop, will always be superior to competitors like the Gimp—for some reason, I really don’t know why! I’m quite willing to pay good money for really good software, if I believe that it has been produced by the best programmers.

Remember, though, that my opinion on economic questions is highly suspect, since I’m just an educator and scientist. I understand almost nothing about the marketplace.

Andrew: A story states that you once entered a programming contest at Stanford (I believe) and you submitted the winning entry, which worked correctly after a single compilation. Is this story true? In that vein, today’s developers frequently build programs writing small code increments followed by immediate compilation and the creation and running of unit tests. What are your thoughts on this approach to software development?

Donald: The story you heard is typical of legends that are based on only a small kernel of truth. Here’s what actually happened: John McCarthy decided in 1971 to have a Memorial Day Programming Race. All of the contestants except me worked at his AI Lab up in the hills above Stanford, using the WAITS time-sharing system; I was down on the main campus, where the only computer available to me was a mainframe for which I had to punch cards and submit them for processing in batch mode. I used Wirth’s ALGOL W system (the predecessor of Pascal). My program didn’t work the first time, but fortunately I could use Ed Satterthwaite’s excellent offline debugging system for ALGOL W, so I needed only two runs. Meanwhile, the folks using WAITS couldn’t get enough machine cycles because their machine was so overloaded. (I think that the second-place finisher, using that "modern" approach, came in about an hour after I had submitted the winning entry with old-fangled methods.) It wasn’t a fair contest.

As to your real question, the idea of immediate compilation and "unit tests" appeals to me only rarely, when I’m feeling my way in a totally unknown environment and need feedback about what works and what doesn’t. Otherwise, lots of time is wasted on activities that I simply never need to perform or even think about. Nothing needs to be "mocked up."

Andrew: One of the emerging problems for developers, especially client-side developers, is changing their thinking to write programs in terms of threads. This concern, driven by the advent of inexpensive multicore PCs, surely will require that many algorithms be recast for multithreading, or at least to be thread-safe. So far, much of the work you’ve published for Volume 4 of The Art of Computer Programming (TAOCP) doesn’t seem to touch on this dimension. Do you expect to enter into problems of concurrency and parallel programming in upcoming work, especially since it would seem to be a natural fit with the combinatorial topics you’re currently working on?

Donald: The field of combinatorial algorithms is so vast that I’ll be lucky to pack its sequential aspects into three or four physical volumes, and I don’t think the sequential methods are ever going to be unimportant. Conversely, the half-life of parallel techniques is very short, because hardware changes rapidly and each new machine needs a somewhat different approach. So I decided long ago to stick to what I know best. Other people understand parallel machines much better than I do; programmers should listen to them, not me, for guidance on how to deal with simultaneity.

Andrew: Vendors of multicore processors have expressed frustration at the difficulty of moving developers to this model. As a former professor, what thoughts do you have on this transition and how to make it happen? Is it a question of proper tools, such as better native support for concurrency in languages, or of execution frameworks? Or are there other solutions?

Donald: I don’t want to duck your question entirely. I might as well flame a bit about my personal unhappiness with the current trend toward multicore architecture. To me, it looks more or less like the hardware designers have run out of ideas, and that they’re trying to pass the blame for the future demise of Moore’s Law to the software writers by giving us machines that work faster only on a few key benchmarks! I won’t be surprised at all if the whole multithreading idea turns out to be a flop, worse than the "Titanium" approach that was supposed to be so terrific—until it turned out that the wished-for compilers were basically impossible to write.

Let me put it this way: During the past 50 years, I’ve written well over a thousand programs, many of which have substantial size. I can’t think of even five of those programs that would have been enhanced noticeably by parallelism or multithreading. Surely, for example, multiple processors are no help to TeX.^[1]

How many programmers do you know who are enthusiastic about these promised machines of the future? I hear almost nothing but grief from software people, although the hardware folks in our department assure me that I’m wrong.

I know that important applications for parallelism exist—rendering graphics, breaking codes, scanning images, simulating physical and biological processes, etc. But all these applications require dedicated code and special-purpose techniques, which will need to be changed substantially every few years.

Even if I knew enough about such methods to write about them in TAOCP, my time would be largely wasted, because soon there would be little reason for anybody to read those parts. (Similarly, when I prepare the third edition of Volume 3 I plan to rip out much of the material about how to sort on magnetic tapes. That stuff was once one of the hottest topics in the whole software field, but now it largely wastes paper when the book is printed.)

The machine I use today has dual processors. I get to use them both only when I’m running two independent jobs at the same time; that’s nice, but it happens only a few minutes every week. If I had four processors, or eight, or more, I still wouldn’t be any better off, considering the kind of work I do—even though I’m using my computer almost every day during most of the day. So why should I be so happy about the future that hardware vendors promise? They think a magic bullet will come along to make multicores speed up my kind of work; I think it’s a pipe dream. (No—that’s the wrong metaphor! "Pipelines" actually work for me, but threads don’t. Maybe the word I want is "bubble.")

From the opposite point of view, I do grant that web browsing probably will get better with multicores. I’ve been talking about my technical work, however, not recreation. I also admit that I haven’t got many bright ideas about what I wish hardware designers would provide instead of multicores, now that they’ve begun to hit a wall with respect to sequential computation. (But my MMIX design contains several ideas that would substantially improve the current performance of the kinds of programs that concern me most—at the cost of incompatibility with legacy x86 programs.)

Andrew: One of the few projects of yours that hasn’t been embraced by a widespread community is literate programming. What are your thoughts about why literate programming didn’t catch on? And is there anything you’d have done differently in retrospect regarding literate programming?

Donald: Literate programming is a very personal thing. I think it’s terrific, but that might well be because I’m a very strange person. It has tens of thousands of fans, but not millions.

In my experience, software created with literate programming has turned out to be significantly better than software developed in more traditional ways. Yet ordinary software is usually okay—I’d give it a grade of C (or maybe C++), but not F; hence, the traditional methods stay with us. Since they’re understood by a vast community of programmers, most people have no big incentive to change, just as I’m not motivated to learn Esperanto even though it might be preferable to English and German and French and Russian (if everybody switched).

Jon Bentley probably hit the nail on the head when he once was asked why literate programming hasn’t taken the whole world by storm. He observed that a small percentage of the world’s population is good at programming, and a small percentage is good at writing; apparently I am asking everybody to be in both subsets.

Yet to me, literate programming is certainly the most important thing that came out of the TeX project. Not only has it enabled me to write and maintain programs faster and more reliably than ever before, and been one of my greatest sources of joy since the 1980s—it has actually been indispensable at times. Some of my major programs, such as the MMIX meta-simulator, could not have been written with any other methodology that I’ve ever heard of. The complexity was simply too daunting for my limited brain to handle; without literate programming, the whole enterprise would have flopped miserably.

If people do discover nice ways to use the newfangled multithreaded machines, I would expect the discovery to come from people who routinely use literate programming. Literate programming is what you need to rise above the ordinary level of achievement. But I don’t believe in forcing ideas on anybody. If literate programming isn’t your style, please forget it and do what you like. If nobody likes it but me, let it die.

On a positive note, I’ve been pleased to discover that the conventions of CWEB are already standard equipment within preinstalled software such as Makefiles, when I get off-the-shelf Linux these days.

Andrew: In Fascicle 1 of Volume 1, you reintroduced the MMIX computer, which is the 64-bit upgrade to the venerable MIX machine comp-sci students have come to know over many years. You previously described MMIX in great detail in MMIXware. I’ve read portions of both books, but can’t tell whether the Fascicle updates or changes anything that appeared in MMIXware, or whether it’s a pure synopsis. Could you clarify?

Donald: Volume 1 Fascicle 1 is a programmer’s introduction, which includes instructive exercises and such things. The MMIXware book is a detailed reference manual, somewhat terse and dry, plus a bunch of literate programs that describe prototype software for people to build upon. Both books define the same computer (once the errata to MMIXware are incorporated from my website). For most readers of TAOCP, the first fascicle contains everything about MMIX that they’ll ever need or want to know.

I should point out, however, that MMIX isn’t a single machine; it’s an architecture with almost unlimited varieties of implementations, depending on different choices of functional units, different pipeline configurations, different approaches to multiple-instruction-issue, different ways to do branch prediction, different cache sizes, different strategies for cache replacement, different bus speeds, etc. Some instructions and/or registers can be emulated with software on "cheaper" versions of the hardware. And so on. It’s a test bed, all simulatable with my meta-simulator, even though advanced versions would be impossible to build effectively until another five years go by (and then we could ask for even further advances just by advancing the meta-simulator specs another notch).

Suppose you want to know if five separate multiplier units and/or three-way instruction issuing would speed up a given MMIX program. Or maybe the instruction and/or data cache could be made larger or smaller or more associative. Just fire up the meta-simulator and see what happens.

Andrew: As I suspect you don’t use unit testing with MMIXAL, could you step me through how you go about making sure that your code works correctly under a wide variety of conditions and inputs? If you have a specific work routine around verification, could you describe it?

Donald: Most examples of machine language code in TAOCP appear in Volumes 1-3; by the time we get to Volume 4, such low-level detail is largely unnecessary and we can work safely at a higher level of abstraction. Thus, I’ve needed to write only a dozen or so MMIX programs while preparing the opening parts of Volume 4, and they’re all pretty much toy programs—nothing substantial. For little things like that, I just use informal verification methods, based on the theory that I’ve written up for the book, together with the MMIXAL assembler and MMIX simulator that are readily available on the Net (and described in full detail in the MMIXware book).

That simulator includes debugging features like the ones I found so useful in Ed Satterthwaite’s system for ALGOL W, mentioned earlier. I always feel quite confident after checking a program with those tools.

Andrew: Despite its formulation many years ago, TeX is still thriving, primarily as the foundation for LaTeX. While TeX has been effectively frozen at your request, are there features that you would want to change or add to it, if you had the time and bandwidth? If so, what are the major items you add/change?

Donald: I believe changes to TeX would cause much more harm than good. Other people who want other features are creating their own systems, and I’ve always encouraged further development—except that nobody should give their program the same name as mine. I want to take permanent responsibility for TeX and Metafont, and for all the nitty-gritty things that affect existing documents that rely on my work, such as the precise dimensions of characters in the Computer Modern fonts.

Andrew: One of the little-discussed aspects of software development is how to do design work on software in a completely new domain. You were faced with this issue when you undertook TeX: No prior art was available to you as source code, and it was a domain in which you weren’t an expert. How did you approach the design, and how long did it take before you were comfortable entering into the coding portion?

Donald: That’s another good question! I’ve discussed the answer in great detail in Chapter 10 of my book Literate Programming, together with Chapters 1 and 2 of my book Digital Typography. I think that anybody who is really interested in this topic will enjoy reading those chapters. (See also Digital Typography Chapters 24 and 25 for the complete first and second drafts of my initial design of TeX in 1977.)

Andrew: The books on TeX and the program itself show a clear concern for limiting memory usage—an important problem for systems of that era. Today, the concern for memory usage in programs has more to do with cache sizes. As someone who has designed a processor in software, the issues of cache-aware and cache-oblivious algorithms surely must have crossed your radar screen. Is the role of processor caches on algorithm design something that you expect to cover, even if indirectly, in your upcoming work?

Donald: I mentioned earlier that MMIX provides a test bed for many varieties of cache. And it’s a software-implemented machine, so we can perform experiments that will be repeatable even a hundred years from now. Certainly the next editions of Volumes 1-3 will discuss the behavior of various basic algorithms with respect to different cache parameters.

In Volume 4 so far, I count about a dozen references to cache memory and cache-friendly approaches (not to mention a "memo cache," which is a different but related idea in software).

Andrew: What set of tools do you use today for writing TAOCP? Do you use TeX? LaTeX? CWEB? Word processor? And what do you use for the coding?

Donald: My general working style is to write everything first with pencil and paper, sitting beside a big wastebasket. Then I use Emacs to enter the text into my machine, using the conventions of TeX. I use tex, dvips, and gv to see the results, which appear on my screen almost instantaneously these days. I check my math with Mathematica.

I program every algorithm that’s discussed (so that I can thoroughly understand it) using CWEB, which works splendidly with the GDB debugger. I make the illustrations with MetaPost (or, in rare cases, on a Mac with Adobe Photoshop or Illustrator). I have some homemade tools, like my own spell-checker for TeX and CWEB within Emacs. I designed my own bitmap font for use with Emacs, because I hate the way the ASCII apostrophe and the left open quote have morphed into independent symbols that no longer match each other visually. I have special Emacs modes to help me classify all the tens of thousands of papers and notes in my files, and special Emacs keyboard shortcuts that make bookwriting a little bit like playing an organ. I prefer rxvt to xterm for terminal input. Since last December, I’ve been using a file backup system called backupfs, which meets my need beautifully to archive the daily state of every file.

According to the current directories on my machine, I’ve written 68 different CWEB programs so far this year. There were about 100 in 2007, 90 in 2006, 100 in 2005, 90 in 2004, etc. Furthermore, CWEB has an extremely convenient "change file" mechanism, with which I can rapidly create multiple versions and variations on a theme; so far in 2008 I’ve made 73 variations on those 68 themes. (Some of the variations are quite short, only a few bytes; others are 5KB or more. Some of the CWEB programs are quite substantial, like the 55-page BDD package that I completed in January.) Thus, you can see how important literate programming is in my life.

I currently use Ubuntu Linux, on a standalone laptop—it has no Internet connection. I occasionally carry flash memory drives between this machine and the Macs that I use for network surfing and graphics; but I trust my family jewels only to Linux. Incidentally, with Linux I much prefer the keyboard focus that I can get with classic FVWM to the GNOME and KDE environments that other people seem to like better. To each his own.

Andrew: You state in the preface of Fascicle 0 of Volume 4 of TAOCP that Volume 4 surely will comprise three volumes and possibly more. It’s clear from the text that you’re really enjoying writing on this topic. Given that, what is your confidence in the note posted on the TAOCP website that Volume 5 will see light of day by 2015?

Donald: If you check the Wayback Machine for previous incarnations of that web page, you will see that the number 2015 has not been constant.

You’re certainly correct that I’m having a ball writing up this material, because I keep running into fascinating facts that simply can’t be left out—even though more than half of my notes don’t make the final cut.

Precise time estimates are impossible, because I can’t tell until getting deep into each section how much of the stuff in my files is going to be really fundamental and how much of it is going to be irrelevant to my book or too advanced. A lot of the recent literature is academic one-upmanship of limited interest to me; authors these days often introduce arcane methods that outperform the simpler techniques only when the problem size exceeds the number of protons in the universe. Such algorithms could never be important in a real computer application. I read hundreds of such papers to see if they might contain nuggets for programmers, but most of them wind up getting short shrift.

From a scheduling standpoint, all I know at present is that I must someday digest a huge amount of material that I’ve been collecting and filing for 45 years. I gain important time by working in batch mode: I don’t read a paper in depth until I can deal with dozens of others on the same topic during the same week. When I finally am ready to read what has been collected about a topic, I might find out that I can zoom ahead because most of it is eminently forgettable for my purposes. On the other hand, I might discover that it’s fundamental and deserves weeks of study; then I’d have to edit my website and push that number 2015 closer to infinity.

Andrew: In late 2006, you were diagnosed with prostate cancer. How is your health today?

Donald: Naturally, the cancer will be a serious concern. I have superb doctors. At the moment I feel as healthy as ever, modulo being 70 years old. Words flow freely as I write TAOCP and as I write the literate programs that precede drafts of TAOCP. I wake up in the morning with ideas that please me, and some of those ideas actually please me also later in the day when I’ve entered them into my computer.

On the other hand, I willingly put myself in God’s hands with respect to how much more I’ll be able to do before cancer or heart disease or senility or whatever strikes. If I should unexpectedly die tomorrow, I’ll have no reason to complain, because my life has been incredibly blessed. Conversely, as long as I’m able to write about computer science, I intend to do my best to organize and expound upon the tens of thousands of technical papers that I’ve collected and made notes on since 1962.

Andrew: On your website, you mention that the Peoples Archive recently made a series of videos in which you reflect on your past life. In segment 93, "Advice to Young People," you advise that people shouldn’t do something simply because it’s trendy. As we know all too well, software development is as subject to fads as any other discipline. Can you give some examples that are currently in vogue, which developers shouldn’t adopt simply because they’re currently popular or because that’s the way they’re currently done? Would you care to identify important examples of this outside of software development?

Donald: Hmm. That question is almost contradictory, because I’m basically advising young people to listen to themselves rather than to others, and I’m one of the others. Almost every biography of every person whom you would like to emulate will say that he or she did many things against the "conventional wisdom" of the day.

Still, I hate to duck your questions even though I also hate to offend other people’s sensibilities—given that software methodology has always been akin to religion. With the caveat that there’s no reason anybody should care about the opinions of a computer scientist/mathematician like me regarding software development, let me just say that almost everything I’ve ever heard associated with the term "extreme programming" sounds like exactly the wrong way to go...with one exception. The exception is the idea of working in teams and reading each other’s code. That idea is crucial, and it might even mask out all the terrible aspects of extreme programming that alarm me.

I also must confess to a strong bias against the fashion for reusable code. To me, "re-editable code" is much, much better than an untouchable black box or toolkit. I could go on and on about this. If you’re totally convinced that reusable code is wonderful, I probably won’t be able to sway you anyway, but you’ll never convince me that reusable code isn’t mostly a menace.

Here’s a question that you may well have meant to ask: Why is the new book called Volume 4 Fascicle 0, instead of Volume 4 Fascicle 1? The answer is that computer programmers will understand that I wasn’t ready to begin writing Volume 4 of TAOCP at its true beginning point, because we know that the initialization of a program can’t be written until the program itself takes shape. So I started in 2005 with Volume 4 Fascicle 2, after which came Fascicles 3 and 4. (Think of Star Wars, which began with Episode 4.)

Copyright © 1996-2008 by Dr. Nikolai Bezroukov. www.softpanorama.org was created as a service to the UN Sustainable Development Networking Programme (SDNP) in the author free time. Submit comments This document is an industrial compilation designed and created exclusively for educational use and is placed under the copyright of the Open Content License(OPL). Original materials copyright belong to respective owners. Quotes are made for educational purposes only in compliance with the fair use doctrine.

Standard disclaimer: The statements, views and opinions presented on this web page are those of the author and are not endorsed by, nor do they necessarily reflect, the opinions of the author present and former employers, SDNP or any other organization the author may be associated with. We do not warrant the correctness of the information provided or its fitness for any purpose.

Last modified: April 28, 2008

Softpanorama Classic Series