An interrupted project

In the early 1990s Donald Knuth was of the opinion that it might take another twenty years (i.e. until now) before the remaining four volumes would be complete and that after the series was complete he planned to write music - a subject that he regards as equally important as computing. If fact progress has been slower and the size of the project has increased.

Tex

One reason for the long gap before Volume 4 began to appear was that Knuth became dissatisfied with the typesetting of his books and decided to do something about it. The few months that he intended to spend on the project turned into nine years during which time he invented TeX, a language for typography and Metafont, a font design system.

All of the work he did has been placed in the public domain and Knuth's five-volume Computers & Typesetting, published in 1986, is the explanation of the theory, a user manual and a source of examples.

TeX is the basis of LaTex which is widely used in academia. It used by many academic journals and authors are encouraged to submit electronic manuscripts in this format which handles equations far more successfully than other formats. For this thanks are due to Donald Knuth. 

Volume 4 Facsicles

Another reason was that the topic of the original Chapter 7,  "combinatorial searching" had expanded so much in the intervening period. This and Chapter 8 on recursion had been intended to be combined into a single volume but the plan had to be changed. Knuth decided to split Volume 4 into four - 4A, 4B, 4C and 4D.

He also proposed to publish short chunks (around 128 pages) of the material for each of these as "fascicles" at a rate of two per year. This led to the appearance in 2005 to 2009 of five slim books, the final one of which (in terms of its date) Volume 4, Fascicle 1 was the subject of an early review on this site. These were then combined into Volume 4A on the topic of combinatorial algorithms in 2011.

Nothing more has appeared in print but work towards TAOCP  is continuing. According to information on Knuth's Recent News webpage:

Volume 4B ... will begin with a special section called ‘Mathematical Preliminaries Redux’, which extends the ‘Mathematical Preliminaries’ of Section 1.2 in Volume 1 to things that I didn't know about in the 1960s. Most of this new material deals with probabilities and expectations of random events; there's also an introduction to the theory of martingales.

So far Knuth has produced drafts which he terms "pre-fascilces" that can be downloaded so that readers can spot errors and provide feedback. There are currently two  chunks of of this material: 48 pages of  pre-fascicle 5a, which will become an early part of Volume 4B and a longer chunk, pre-fascicle 6a, which Addison Wesley plans to publish  in paperback before the end of 2015 and then constitute the middle third of Volume 4B.

According to Knuth on Recent News: 

[this] will be a major introduction to the topic of Boolean Satisfiability, emphasizing its many applications, together with a variety of algorithms to solve SAT problems with greater and greater speed. I began studying this topic in autumn 2011, and found it to be amazingly interesting. Thus I've had great fun telling this story, and connecting SAT with many other aspects of computer science and math.

It's not a short story; indeed, this section has turned out to be the largest by far of any in The Art of Computer Programming. But the material is rich, beautiful, instructive, and important, so I'm pleased to have had the opportunity to pull it together from many sources.  

TAOCP also has a dedicated webpage on the Stanford site and the info on this reveals that Volume 5 Syntactical algorithms is also in preparation. Covering lexical scanning (includes also string search and data compression) and parsing techniques it is estimated to be ready in 2020 (postponed from an earlier estimate of 2015). After that Knuth intends to revise Volumes 1-3 and bring them up to date.

The then plans to publish Volume 6 (the theory of context-free languages) but Volume 7 (Compiler techniques) will proceed:

"only if the things I want to say about those topics are still relevant and still haven't been said".

He also states:

Volumes 1--5 represent the central core of computer programming for sequential machines; the subjects of Volumes 6 and 7 are important but more specialized.

Personally, I feel that the difficulty in creating a complete work for each of the remaining topics is more difficult than for Volumes 1-3, but who am I to make this judgement. Perhaps I would have felt the same about the existing volumes had I not actually seen them!

Looking back

When I first read Volume 1 back in 1975 I found it astounding. But you have to remember that the machines I was using were a 360 mainframe and a PDP mini and the book seemed just right for the time. Now when I look at it again I have to say that it seems dated in concept, approach, language and just about everything else you could list.

Knuth invented a computer and its language MIX to use in examples. I doubt if anyone today would set out to write a book on algorithms using assembly language - even a machine independent one.

Also, the topics that are covered are not really the concern of most practising programmers today. You will find good discussions of sorting and searching, of fundamental data structures such as trees, lists etc. and of random numbers, but don't expect to find anything about fractals, sprites or web services. To a certain extent I agree that they would be out of place but on the other hand I'm not at all sure that they couldn't be turned into the same sort of intellectual stuff that is crammed into TAOCP - maybe there is a need for a second generation Knuth even before the master has completed the original work!

Still, this doesn't alter the fact that Knuth describes, explains and analyses many of the fundamental methods that all programmers should know. If you can't take the detailed maths then I would still suggest that a skim read is a good idea. Don't worry too much about understanding the MIX code in detail but concentrate on understanding the algorithms and the discussions of the results.

Knuth's works are classics and I still think that every programmer should at least be exposed to the contents - it's our cultural heritage. 

I'm not alone in thinking this. Bill Gates is quoted on the publisher's (Pearson) website as saying:

If you think you’re a really good programmer… read [Knuth’s] Art of Computer Programming… You should definitely send me a résumé if you can read the whole thing.

TAOCP has been a remarkable success commercially as well as academically. In the mid 80s 2000 copies per month of each title were selling and it has been translated into Chinese, Spanish, Russian and every other language that computers are used in!

MIXX

In his original work, Knuth relied on a 1960's computer called he called MIX. It is supposed to be the 1009 because this is the average of the model numbers of mainframes in use at the time 360, 709 etc. However, once you realise what MIX is in Latin numerals you realize this is evidence of his quirky sense of humor - more of which later.

For Volume 4A he switched to a RISC compter, termed MMIX explaining:

It replaces MIX, the 1960s-style machine that formerly played such a role... I strove to design MMIX so that its machine language would be simple, elegant, and easy to learn. At the same time I was careful to include all of the complexities needed to achieve high performance in practice, so that MMIX could in principle be built and even perhaps be competitive with some of the fastest general-purpose computers in the marketplace. 

Rather than try to incorporate MIX into the existing work in 2005 a standalone volume was published about it with the rather confusing title, The Art of Computer Programming, Volume 1, Fascicle 1: MMIX -- A RISC Computer for the New Millennium.

Uncharacteristically, Knuth then permitted another author, Dr. Martin Ruckert who is professor of mathematics and computer science at Munich University of Applied Sciences and also maintains the MMIX home page to work over and update the programs and exercises in Volumes 1 - 3 for MMIX, resulting in the publication in February 2015 of MMIX Supplement, The: Supplement to The Art of Computer Programming Volumes 1, 2, 3 by Donald E. Knuth. 

In the Foreword to this book Knuth writes:

“I am thrilled to see the present book by Martin Ruckert: It is jam-packed with goodies from which an extraordinary amount can be learned. Martin has not merely transcribed my early programs for MIX and recast them in a modern idiom. He has penetrated to their essence and rendered them anew with elegance and good taste. His carefully checked code represents a significant contribution to the art of pedagogy as well as to the art of programming.” 

 and recommends it with:

“I encourage serious programmers everywhere to sharpen their skills by devouring this book.”

<ASIN:0812219236>

<ASIN:1846280346>

<ASIN:0201038048>

<ASIN:0321580508>

<ASIN:0201485419>

<ASIN:0321637135>

<ASIN:0321534964>

<ASIN:0201853922>

<ASIN:0133992314>