Preface to The MMIX Supplement: Supplement to The Art of Computer Programming Volumes 1, 2, 3 by Donald E. Knuth
This chapter is from the book
This chapter is from the book
This chapter is from the book
Translations are made to bring important works of literature closer to those reading — and thinking — in a different language. The challenge of translating is finding new words, phrases, or modes of expression without changing what was said before. An easy task, you may think, when the translation asks only for replacing one programming language with another. Wouldn’t a simple compiler suffice to do the job? The answer is Yes, as long as the translated programs are intended to be executed by a machine; the answer is No, if the translated programs are intended to explain concepts, ideas, limitations, tricks, and techniques to a human reader. The Art of Computer Programming by Donald E. Knuth starts out by describing the “process of preparing programs for a digital computer” as “an aesthetic experience much like composing poetry or music.” That raises the level of expectation to a point where a translation becomes a formidable challenge.
In 1990, the mythical MIX computer used for the exposition of implementation details in The Art of Computer Programming was so outdated that Knuth decided to replace it. The design of the new MMIX computer was finally published as a fascicle, comprising a replacement for the description of MIX in Chapter 1 of that series of books. It made the translation of all the MIX programs to MMIX programs in Volumes 1, 2, and 3 inevitable; but Knuth decided that it would be more important to complete Volumes 4 and 5 first before starting to rewrite Volumes 1–3. Volume 4 meanwhile has grown and by now is to be delivered in (at least) three installments, Volumes 4A, 4B, and 4C, of which the first has already appeared in print. Still it means we have to exercise patience until the new edition of Volume 1 will be published.
With the introduction of the new MMIX, Knuth asked programmers who would like to help with the conversion process to join the MMIXmasters, a loose group of volunteers organized and coordinated by Vladimir Ivanović. However, progress was slow, so in the fall of 2011, when I took over the maintenance of the MMIX home page, I decided to take on the task of translating all the remaining programs and update them to a readable form. The result of that effort is the present book, which is intended to be a bridge into the future although not the future itself. It is supplementing Volumes 1, 2, and 3 for those who do not want to wait several more years until that future arrives.
This book is not written for independent reading; it is a supplement, supplementing the reading of another book. You should read it side by side with The Art of Computer Programming (let’s call that “the original” for short). Therefore it is sprinkled with page references such as “[123]” pointing the reader to the exact page (in the third edition of Volumes 1 and 2, and in the second edition of Volume 3) where the MIX version can be found in the original. References are also included in the headings to simplify searching for a translation given the page number in the original. Further, I tried to pick up a sentence or two unchanged from the original before switching to MMIX mode. I also tried to preserve, even in MMIX mode, the wording of the original as closely as possible, changing as little as possible and as much as needed. Of course, all section names and their numbering, as well as the numbers of tables, figures, or equations are taken unchanged from the original. It should help you find the point where the translation should be spliced in with the original.
When I assume that you are reading this book in parallel with the original, strictly speaking, I assume that you are reading the original as augmented by the above-mentioned Fascicle 1. A basic knowledge of the MMIX computer and its assembly language as explained there is indispensable for an understanding of the material presented here. If you want to know every detail, you should consult MMIXware [Lecture Notes in Computer Science 1750, Springer Verlag, as updated in 2014].
Also online you can find plenty of documentation; the MMIX home page at http://mmix.cs.hm.edu provides full documentation and current sources of the MMIXware package. Further, the tools mentioned below, other useful MMIX-related software, and all the programs presented in this book, including test cases, are available for download. The best companion of MMIX theory is MMIX practice — so download the software, run the programs, and see for yourself.
This book is written using the TEX typesetting system. To display MMIX code in print, it is therefore needed in TEX format; however, to assemble and test MMIX code, it is needed in MMIX assembly language. An automatic converter, mmstotex, was used to produce (almost all) TEX code in the book from the same file that was submitted to the MMIX assembler. Another tool, testgen, was written just for the production of this book: It combines a set of source files, containing program fragments and test case descriptions, with library code to produce a sequence of complete, ready-to-run test programs.
Great care was taken to complement the programs shown in this book with appropriate test cases. Every line of code you see on the following pages was checked by the MMIX assembler for syntactic correctness and executed at least once in a test case. While I am sure that no errors could creep in by manual preparation of TEX sources, that by no means implies that the MMIX code shown is error free. Of course, it is not only possible but most likely that several bugs are still hidden in the about 15,000 lines of code written for this book. So please help in finding them!
Thanks to Donald Knuth, I have several boxes of nice MMIX T-shirts (sizes L and XL) sitting on the shelf in my office, and I will gladly send one to each first finder of a bug — technical, typographical, orthographical, grammatical, or otherwise — as long as supplies last (T-shirts, not bugs). Known bugs will be listed on the MMIX home page, so check there first before sending me an email.
Aside from tracking down bugs, the test cases helped me a lot while conducting experiments with the code because I could see immediately how changes affected correctness and running time. Think of the public test cases as an invitation to do your own experiments. Let me know about your findings, be it an improvement to the code or a new test case to uncover a hidden bug.
Speaking about experiments: Of course it was tempting to experiment with the pipeline meta simulator mmmix. The temptation was irresistible, especially since it is so easy to take the existing programs, run them on the pipeline simulator, and investigate the influence of configuration parameters on the running time. But in the end, I had to stop any work on this wide-open field of research and decided to postpone a discussion of pipelined execution. It would have made this booklet into a book and delayed its publication for years.
I am extremely grateful to Donald Knuth, who supported me in every aspect of preparing this book. The draft version, which I sent to him at Stanford, came back three months later with dozens of handwritten remarks on nearly every page, ranging from typographic details such as: “Here I would put a \hair between SIZE and ;” to questions of exposition: “No, you’ve got to leave this tag bit 0. Other exercises depend on it (and so does illustration (10))”, wrong instruction counts: “Should be A + 1[A]”, suggestions: “Did you consider keeping 2b instead of b in a register? ”, and bug fixes: “SRU or you’ll be propagating a ‘minus’ sign.” Without him, this book would not have been written in the first place, and without him, it would also not have reached its present form. For the remaining shortcomings, errors, and omissions, I take full responsibility. I hope that there are not too many left, and that you will enjoy the book all the same.
- Martin Ruckert
München
December 2014