Which computer does Donald Knuth use?

The perfectionist

At the age of 24, Donald E. Knuth began to write a book on the basics of computer science. It quickly became clear that the topic The Art of Computer Programming ’(TAOCP) encompasses material for five volumes. Three have now appeared and are considered the standard work in computer science, the fourth will probably become three volumes, which Knuth currently estimates will have completed in 2007. Not only to shorten the waiting time, but also to have the opportunity to incorporate feedback from the readers into the final version, he wants to publish volume 4 step by step in small portions of around 128 pages each as so-called fascicles. He is already making beta versions of the first fascicles available for download on his homepage [[#literature 1]].

The MMIX processor architecture invented by Knuth is presented on page 184. On the occasion of the ‘MMIXfest’ in October 2001, we met Knuth at the Munich University of Applied Sciences.

c't: Mr. Knuth, you once estimated that the first fascicle of Volume 4 would appear around 1995, 1996. Why the delay?

Knuth: There are many reasons for that. I have never been able to estimate very well how long something will take, I have to get better at that. But I knew I had to retire to do things on my own schedule. Then I had to finish other books first, the Selected Papers ’... And I did a third edition of The Art of Computer Programming, which took up most of ’96 and ’97. I hadn't actually planned to do this, I was only thinking of volume 4. But after talking about the macros for my errata list at the 16th TeX user meeting, Silvio Levy came up to me and said: 'Don, you should really be reprinting these books and using TeX. I'll do all the typing and the pictures, so it won't cost you that much time. ’Of course, I had my quality expectations and new ideas, so it took a couple of years. So before Volume 4 I had to do a number of other things, MMIX was the last.

c't: How is your daily routine today?

Knuth: My days, and that will probably be a steady state for the next 20 years or so if I stay healthy, are typically devoted to TAOCP. That means a combination of reading and writing. I work in batch mode because I don't like to swap different things out of my head and in. I usually do a section of TAOCP and it should be ready in six to eight weeks. I want to do one page a day. Eight weeks, 56 days ... that makes about 60 pages including solutions for the exercises. I hope to keep up this pace, but if I can do 250 pages a year, I'll be satisfied too. When working on ‘Concrete Mathematics’, I even wrote two pages a day, but that was too much in the long run. I could only hold out for a while and risk my marriage and my health in the process.

I have thousands of records, all indexed on the computer. There are 20,000 or 30,000 lines of notes. Each line is either a reference to an article I want to read or an idea that I wrote down. All of this is filed according to the table of contents of the book, so that I know when to read what in detail. Of the six weeks I work on a section, I typically spend the first two reading extensively on the subject, starting with the things I've been saving since 1962. For the next two weeks I will write a concept in pencil and the last two weeks will be fine-tuning.

c't: You write by hand?

Knuth: Oh yeah. The reason is that I can type faster than I think. My handwriting, on the other hand, is perfectly matched to my speed of thinking. So when I type, I lose sync, and this sync problem slows me down, making it actually faster to write by hand. Then I type this concept and edit it.

c't: What kind of computer do you work with?

Knuth: I have two computers at home. I surf the Internet with a Macintosh and do all graphic work with Photoshop, Illustrator, Distiller and so on. But I write my books on a PC with a 600 MHz Athlon that I put together last year with the help of a friend.

c't: Under Linux?

Knuth: Yes.

c't: No Windows at all?

Knuth: For God's sake, no! Until it always booted ... But today I was quite surprised to what extent you can actually use Windows for useful things. The people at my lecture at the Technical University of Munich had additional programs installed so that Windows worked almost as well as Linux. However, we had nothing sensible to display PostScript files and then we took a Linux computer. I don't want to offend anyone here, but I'm a big fan of the open source movement. I am impressed that there are thousands of people doing really good work here. Ten little things happen every day, and after a year they make massive progress.

c't: Perhaps you even triggered that by publishing your programs in the source code.

Knuth: Well, I helped, but I'm not the father of the open source movement. I provided one of several early examples that cooperation can work well instead of competition. However, if I hadn't had my reputation and secure income back then, then I might have been much less generous with TeX.

c't: What do you think of software patents?

Knuth: Oh yes, I noticed that this is currently being discussed in Germany. My personal opinion on this is that algorithms are like mathematics, so inherently not patentable. It worries me that most patents are about ideas so simple that I would expect my students to develop them as homework. Sometimes there are exceptions, for example something very nifty like an interior point method for linear programming, where one can really speak of a significant discovery. But for me that's still math. I come from a math culture where we don't collect money from people who use our sentences. There is the thought that mathematics is discovered, not invented. If something was already there, how can you patent it?

If something was already there, how can you patent it?

I wrote an open letter to the US Patent Office and published it at the end of the second edition of the CWEB manual. Unfortunately they left out the page in the newest edition, but the letter can still be found on the web. Basically, I'm saying what Stallman has been saying for years, namely that patents on algorithms are something like patents on English words. I used our legal system as an analogy: what if every lawyer who cites a case had to pay for it? It would limit us from dealing with new cases, or in the case of a software developer, programming new software.

If there had been software patents back then, I would never have been able to write TeX. And pretty much every program I use in my daily work today would not have been written. Every piece of software that is really important to me probably wouldn't have been developed if there had been software patents back then.

I think software developers make an income, not for grabbing an algorithm and then claiming it for themselves, but for services like customizing programs, writing good manuals, and helping users.

In the first edition of Volume 3 I had the remark that there is a strong analogy between creating a program and making a machine out of wood or other materials. That probably makes it inevitable that one day there will be patents on algorithms. I rephrased this a little in the third edition.

In any case, I don't have the time to check all the algorithms to see whether they affect any patents. I will of course try and refer to a number of patents. But if I don't mention a patent, it doesn't mean it doesn't exist.

c't: Do you hold any patents yourself?

Knuth: I have five patents. Indeed, one of them could be seen as a software patent. It has probably expired by now. It had to do with the rasterization of images. When I was working on the 3:16 project at Adobe* I've been talking to the people there about how to rasterize images. Some of what I suggested seemed patentable to someone, so they wrote it down. The other patents have to do with things that went into Burroughs hardware in the 1960s.

c't: Was TeX your work alone?

Knuth: Some people have advised me in weekly meetings, but I wrote every line of TeX myself. Others wrote drivers, ported them to different machines. They created the interfaces to the outside world to control laser printers and so on. But I programmed the actual core myself. This was the only way I could find out what the problems were.

You don't really understand something if you don't try to implement it. At the very beginning I wrote a little memo for myself about how TeX should work. I gave that to two students as a project and went to China for four weeks, where they couldn't reach me. I thought the spec was 100 percent clear. But when I got back I was surprised that they only had a small prototype up and running.

Then came my research vacation, and it opened my eyes when I tried to implement TeX myself. Every five minutes I came across a question that the spec didn't answer. If I had worked as a student for whoever wrote this specification, I would have needed his help all the time.

You don't really understand something if you don't try to implement it.

If you come to the conclusion that all projects have to be done by one person, then that doesn't mean anything good for software engineering. There must be better solutions for this. But when it comes to the first version of a new system, I really don't know any other way than to divide it into almost completely independent parts and leave each of these parts to just one person. Individuals have to talk to each other about the interfaces, but not about their own work. When you implement the second generation of a system, you have a common vocabulary and people know about the same things, then it's different. But at the very beginning ... For me, the reason why some other projects struggle so hard is very simple: You try it with more than one person.

c't: What do you think of object-oriented programming?

Knuth: I liked the idea the first time I saw it in Simula. But of course, with inheritance and the like, it becomes more difficult to prove that a program is correct. I like the idea of ​​modules and classes, but somehow I don't like them so much that I would find them necessary in my own programs.

c't: Wouldn't that be ideal for an MMIX simulator? Objects for the whole functional units, the memory, the caches ...

Knuth: I would love to see another solution. Especially for the cache simulator, which seems to be quite simple intuitively. I tried that for two months and rejected one solution after the other. Finally, I blasted the problem with tons of code by programming case by case. It was the most complicated program I've ever written. I wouldn't have made it without CWEB.

c't: Wouldn't it have been easier with an object-oriented language?

Knuth: I have never intuitively understood the syntax of a C ++ object at a glance. That is a different world of thought. It's also a matter of practice, of course. I think I need a language beyond C ++ to work better with coroutines and threads. In any case, I couldn't write the MMIX pipeline simulator in any other language I knew.

c't: So you say: object-oriented programming is a good idea, but not useful in practice?

Knuth: No. I want to sum it up like this: If it's a good idea, I'd love to see someone make it happen. You should take the cache simulator as a student project and program it the way it should have been. I would love to see it in a different style, the way it should be. Because I was trying to find a better style. My solution from 1999 is fine; After all, after two years I can still understand it and people can customize it in a variety of ways. But it's absolutely conceivable that there is a much better way of writing this program that I just didn't know about.

c't: Was performance important to you when you wrote the MMIX simulator?

Knuth: I didn't have the ambition to get it as fast as a real machine. But it should be reasonably fast so that you can run longer programs on it.

c't: You went into the hardware implementation in great detail in the specification and also in the emulator. Have you consulted hardware designers?

Knuth: Oh yes, I had amazing help. John Hennessy wrote a long review of my original design. Then I worked with Dick Sites, the designer of the Alpha chip. He had a lot of suggestions and I went over a lot of the details with him. The operating system group at Sun and a few other people also contributed to the MMIX design, a tremendous help overall. All mistakes are mine, of course. Although it would surprise me if there were still big ones, because someone would probably have noticed them by now.

c't: Has anyone tried a hardware implementation of the MMIX processor?

Knuth: Some people have told me they are going to. I talked to Dave Ditzel from Transmeta about it and Arvind from MIT said he might surprise me one day. But I am not sure that this surprise will ever come. I'm not really unhappy that MMIX hasn't been built yet. I would of course be happy to have an MMIX computer on my desk one day, because I think MMIX does a lot of things right that other machines do wrong. But the dream is probably too good to be true. (bo)


[1] Homepage of Donald E. Knuth

* In the book ‘3:16 Bible Texts Illuminated’, Knuth deals with Bible verses, with chapter 3, verse 16 from each book.