The Art of Computer Programming, Volume 1, Fascicle 1: MMIX — A RISC Computer for the New Millennium

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.
Rating: 5 / 5

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. 1) 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. 2) 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. 3) 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”
Rating: 5 / 5

It is with good reason that these books are so well-respected in the field. These books have enough depth for several years of careful study and will be quite rewarding for anyone who takes the time. Still, there are a couple of things to keep in mind before jumping in:

(1) These books are not for the mathematically weak-at-heart. The first section, of over 100 pages, is on mathematical preliminaries. While it is true that there are many later sections that can be understood without this background, to truly get the most from these books will take some mathematical maturity,

(2) The algorithms and programs in the book will be difficult to understand to the modern reader, since they are written in an unstructured (i.e. GOTO-centric) style. Program code is given in assembly language for a fictional computer called MIX. Knuth may have his reasons for sticking with this form, but the reader should be aware that some extra work will be required to follow along.

Aside from these caveats, these books come highly recommended.
Rating: 4 / 5

Decades ago, when Knuth wrote the first edition of his classic Art of Computer Programming, he invented an assembly language in which to implement the many algorithms of the books. He called it MIX. It was quite representative of the actual assemblers of the time [late 60s]. But time and Moore’s Law marched on. The 8 bit nature of MIX grew increasingly outdated.

In response, Knuth gives us here a massively upgraded version, called MMIX. It operates on 64 bit wide data. Yay! Still a classic von Neumann architecture, mind you. But very spiffy. MMIX also has 256 general purpose registers and 32 special purpose registers, where these all are 64 bits wide, naturally. Plus, MMIX lives in an address space of 2**64 bytes of memory.

Unlike the Intel or AMD chips, which are CISC, Knuth opted for a RISC MMIX. So learning the opcodes is very rapid, if you have dealt with assemblers before.

This little text gets you up to speed in MMIX. Consider it as prep for the full volume 4, when that comes out. [Prof. Knuth, it's late.]

But this MMIX book is utterly unlike any other assembler book. It comes replete with programming problems (and answers) of considerable intellectual heft. Conventional assembler books simply don’t do this. Their problems tend to be mundane and trivial. This book lets you find surprising conceptual depths hidden under a deceptively simple language. Compare this to chess.
Rating: 4 / 5

Twenty five years ago, after five years of experience programming scientific applications (mostly math stuff, not much real programming beyond algorithms) I began a job programming business applications. At that time, there was very little general communal knowledge about very basic stuff we take for granted today like searching, sorting, memory allocation, data structures…

I began my collection with Knuth and another book (no longer in print) dedicated to data structures. These books defined me as a programmer. I learned MIX only because, as a programmer, I felt that I should be able to understand Knuth’s abstraction. I admit that I was frustrated by having to do this. Ironically, even back then, the “other book” used, what was the de facto standard for generically describing algorithms, an ALGOL like language-very pretty!

Many of us have looked forward to Knuth rewriting his artful collection to satisfy our sense of aesthetics. We don’t consider that he would have to repeat this huge task over and over again. Or (save me from this one) he could produce an obnoxious series of books titled “The Art of Computer Programming in C”, “The Art of Computer Programming in C++”, “The Art of Computer Programming in JAVA”, “The Art of Computer Programming in C#”, and (my favorite) “The Art of Computer Programming for Dummies”. I thank Knuth for not doing this, although the last would certainly have a wide audience. Publishers know what they are about.

Another reason, in my humble opinion, that Knuth probably holds to MIX is that the latest generation of programmers do not have a clue what it is like to program a machine directly, or what is happening underneath the hood. There is a huge leap from MIX to MACRO, but the basic principles are still relevant.

The bottom line: YOU CAN COMPLETELY IGNORE MIX! All the relevant ideas are explained in simple plane English and the algorithms in structured English. Those who would prefer not to understand, but to simply cut and paste code, you are simply out of luck.

Now, if that isn’t insulting enough (you caught me on a good day (after 32 years of programming I have come to hate computers and …)) you would be amazed at how many self proclaimed senior programmers (programmers with more than three years of experience?) can’t write an algorithm to save their lives.

BUY THE BOOKS! THEYRE A BARGAIN!

By the way, you all should read some of Knuth’s other works. How many of us know that Knuth was an important player in getting rid of GOTO statements? I haven’t written a GOTO statement in over twenty years! If my memory serves me (on a good day) Knuth wrote in an April edition of the ACM a paper titled, “Goto Bad, ComeFrom Good”. He would be pleased to know that he anticipated the Publish-Subscribe Architectural Pattern.

Rating: 4 / 5