|
Softpanorama |
May the source be with you, but remember the KISS principle ;-)
|
Nikolai Bezroukov. Portraits of Open Source Pioneers
For readers with high sensitivity to grammar errors access to this page is explicitly prohibited :-)
| Advogato.org/Interview Donald E. Knuth | Rewriting the Bible in 0’s and 1’s | Innovations Interviews Donald Knuth on The Art of Computer Programming (Addison Weslye, Fall/Winter 96) | Amazon.com Interview by Tom Mace | 1993 Donald Knuth Interview to Computer Literacy | Geek Chic short questionary filled by Donald Knuth |
Apr 25, 2008 | informit.com
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.)
Finally I was psyched up to write the early parts, but I soon realized that the introductory sections needed to include much more stuff than would fit into a single fascicle. Therefore, remembering Dijkstra’s dictum that counting should begin at 0, I decided to launch Volume 4 with Fascicle 0. Look for Volume 4 Fascicle 1 later this year.
References
[1] My colleague Kunle Olukotun points out that, if the usage of TeX became a major bottleneck so that people had a dozen processors and really needed to speed up their typesetting terrifically, a super-parallel version of TeX could be developed that uses "speculation" to typeset a dozen chapters at once: Each chapter could be typeset under the assumption that the previous chapters don’t do anything strange to mess up the default logic. If that assumption fails, we can fall back on the normal method of doing a chapter at a time; but in the majority of cases, when only normal typesetting was being invoked, the processing would indeed go 12 times faster. Users who cared about speed could adapt their behavior and use TeX in a disciplined way.
Andrew Binstock is the principal analyst at Pacific Data Works. He is a columnist for SD Times and senior contributing editor for InfoWorld magazine. His blog can be found at: http://binstock.blogspot.com.
Advogato: The first questions that I have are about free software. TeX was one of the first big projects that was released as free software and had a major impact. These days, of course, it's a big deal. But I think when TeX came out it was just something you did, right?
Prof. Knuth: I saw that the whole business of typesetting was being held back by proprietary interests, and I didn't need any claim to fame. I had already been successful with my books and so I didn't have to stake it all on anything. So it didn't matter to me whether or not whether I got anything financial out of it.
But how did you address those problems with the fonts that got contributed to TeX?
Prof. Knuth: In my case, I hired research associates and they put their fonts out into the open. Or else, other people learned it and they did it for the love of it. Some of the excellent fonts came about because they were for Armenian and Ethiopian and so on, where there wasn't that much money. It was either them taking time and making the fonts or else their favorite language would be forever backwards, so I made tools by which they could do this. But in every case, the people who did it weren't relying on this for their income.
If we had somebody who would commission fonts and pay the font designer, the font designer wouldn't be upset at all about having it open, as long as the font designer gets some support.
And you did some of that.
Yeah. In fact, I worked with some of the absolute best type designers, and they were thrilled by the idea that they could tell what they knew to students and have it published and everything. They weren't interested in closed stuff. They're interested in controlling the quality, that somebody isn't going to spoil it, but we could assure them of that.
One of the things that struck me when I was reading "Digital Typography" is the intensive study that you did, especially in the area of math typesetting. When I was writing papers, using math formulas in TeX, I just typed in the commands and out came the math and it looked pretty good to me. It shouldn't have been surprising, but it definitely struck me how much attention you paid to the best mathematics typesetting of past centuries.
I do strongly think that people, when they start throwing computers at something, they think that it's a whole new ballgame, so why should they study the past. I think that is a terrible mistake. But also, I love to read historical source materials, so I couldn't resist. I had a good excuse to study these things, and the more I looked at it, the more interesting it was. But I don't think responsible computer scientists should be unaware of hundreds of years of history that went before us. So that was just a natural thing to approach it that way, for me.
There's a fairly major controversy with TrueType right now, that there a number of patents that are owned now by Apple. It's kind of interesting to me that that is the case even though it's for the most part derivative work of what was in Metafont.
I've been very unhappy with the way patents are handled. But the more I look at it, the more I decide that it's a waste of time. I mean, my life is too short to fight with that, so I've just been staying away. But I know that the ideas for rendering... The main thing is that TrueType uses only quadratic splines, and that Type1 fonts use cubic splines, which allow you to get by with a lot fewer points where you have to specify things.
The quadratic has the great advantage that there's a real cheap way to render them. You can make hardware to draw a quadratic spline lickety-split. It's all Greek mathematics, the conic sections. You can describe a quadratic spline by a quadratic equation (x, y) so that the value of f(x, y) is positive on one side of the curve and negative on the other side. And then you can just follow along pixel by pixel, and when x changes by one and y changes by one, you can see which way to move to draw the curve in the optimal way. And the mathematics is really simple for a quadratic. The corresponding thing for a cubic is six times as complicated, and it has extra very strange effects in it because cubic curves can have cusps in them that are hidden. They can have places where the function will be plus on both sides of the cubic, instead of plus on one side and minus on the other.
As it is, if you look at Principles of Programming Languages, there's all this type theory in there with beautiful Greek letters, inference rules and so on. The visual aesthetic seems to have been inspired by the easy availability that TeX provides.
Certainly, TeX was partly influenced by the needs of computer science, that pushed beyond what mathematicians had needed. Computer scientists needed to see mathematical structure, but they also needed to see the kind of structure you have in programs. So we had to push the envelope in the ACM Journal in the '60s. To publish computer science papers, the typesetters using hand methods in the '60s were being forced to work harder by the computer scientists than by the mathematicians at that time. It's part of the need for a way to see the structure that's in the stuff you're working with. Since I'm writing books about computers, naturally I made TeX so that it could do that.
It's clear that TeX was inspired by the visual aesthetic of mathematics.
Oh yeah.
I'm just saying: to what extent mathematics and computer science today is being influenced by the visual aesthetic of TeX?
Well, I don't know. I think the fact that TeX was open-ended means that people can choose their notation themselves. They don't have to adopt somebody else's macros particularly. That was the bind that we were in before. We would have to first write our paper, then explain it to the printer, and the printer would maybe get it right. But now we're less hesitant to use a notation that's not traditional, but that we think is appropriate, because we know that we don't have to go through a noisy channel in the middle.
One of the other accomplishments of TeX that I continue to be impressed with is the consistent rendering, the idea that you have a source file and that on virtually any implementation of TeX, you'll get the same results.
That's what I insisted on the most. I didn't want to get paid, but I didn't want it to change.
Speaking of literate programming, the question that I have for you is: now that people are moving everything to the Web, including programming, do you think that's another chance for literate programming to become popular?
There's a lot of ferment in this direction. I still don't have the dvipdf program that I got to get installed on my Linux. I guess I gotta try it. But a guy has worked out now that he can convert to Acrobat format, a literate program automatically come out in Acrobat format, so that you can use all the features of the Acrobat reader to click on stuff to move around in the documentation.
Cross-referencing and so on?
Yeah, find a variable where it's declared, and all other uses of the variable. It's certainly a natural thing for hypertext, and this guy in Brazil has worked out a nice system. Still, the thing that's holding it back is probably that some programmers just don't like to document their stuff.
That's certainly a problem we've had in free software, that if there's a documentation file and then a code file, that the two often get out of sync.
These are slowly changing, but most of the horror stories that you hear about that stuff is because of the illiterate nature of the program.
So you think that literate programming is a way to make that better?
It's so much better than the alternative, but I think Jon Bentley explained it to me best, not much percentage of the world's population is really good at programming, and not much percentage of the world's population is really good at documenting, and here you need to be doing both. [laughs]
So, I think that in my experiments with Stanford students I found that more than half of the students that I worked with really hit it off well with literate programming. Maybe Stanford students aren't average. [laugh]
Now intent on completing his scriptures, the 61-year-old Knuth (ka-NOOTH) leads what he calls a hermit-like existence (with his wife) in the hills surrounding the university, having taken early retirement from teaching. He has unplugged his personal e-mail account, posting a Web page (www-cs-faculty.stanford.edu/~knuth/) to keep the software multitudes at bay by answering frequently asked questions such as, “When is Volume 4 coming out?”
About once a month during the academic year, Knuth comes down from the heights to a basement lecture room in the Gates Computer Science Building at Stanford to deliver one of his “Computer Musings” lectures, usually about some aspect of his current work on The Art of Computer Programming. These talks draw computer science students, visiting professors, software engineers from nearby companies and an occasional CEO. On a balmy day earlier this year, the topic and listeners are different. To celebrate the publication of the
third volume of his collected papers, Digital Typography, the associates of the Stanford University Libraries have invited an audience of fans of the printed word to hear Knuth talk about creating the TeX system for scientific and mathematical publication. Wearing a black T-shirt over a long-sleeve black shirt, his bald pate glistening in the overhead lights, he appears suitably monkish before about 70 acolytes and colleagues.
Hesitatingly, his words fighting his innate Lutheran modesty, he begins: “My main life’s work and the reason that I started this whole project is to write a series of books called The Art of Computer Programming—for which I hope to live another 20 years and finish the project I began in 1962. Unfortunately, computer programming has grown over the years and so I’ve had to write a little more than I thought when I sketched it out.” The faithful laugh knowingly.
Knuth relates his detour into digital typography during the 1970s. This was a time of enormous change in the typesetting industry, as computer systems replaced the hot type that had been used since the day of Gutenberg. Computer typography was less expensive, but also less esthetically pleasing—especially for complex mathematical notation. Recalls Knuth: “As printing technology changed, the more important commercial activities were treated first and mathematicians came last. So our books and journals started to look very bad. I couldn’t stand to write books that weren’t going to look good.”
Knuth took it upon himself to write every line of code for software that yielded beautiful typography. He drew the name of his typesetting program from the Greek word for art—the letters are tau epsilon chi (it rhymes with “blecch”). Says Knuth: “Well over 90 percent of all books on mathematics and physics” are typeset with TeX and with its companion software, Metafont, a tool Knuth developed to design pleasing type fonts.
He is quick to acknowledge the contribution of the type designers, punch cutters, typographers, book historians and scholars he gathered at Stanford while developing TeX. Some are in the audience. He tells them: “TeX is what we now call open-system software—anybody around the world can use it free of charge. Because of this, we had thousands of people around the world to help us find all the mistakes. I think it’s probably the most reliable computer program of its size ever.”
Anyone who doubts this claim by the decidedly unboastful Knuth can find confirmation from Guy Steele, one of TeX’s first users and now a distinguished engineer at Sun Microsystems. TeX, says Steele, was one of the first large programs whose source code was published openly. Steele says Knuth’s publication of the TeX code in a book, along with full comments, made it so that “anyone could understand how it works and offer bug fixes.” With academe’s top scientists and mathematicians as beta-testers, an extraordinary quality control team helped perfect TeX. (The TeX development effort was a model for today’s open-source software movement, which has given the world Linux—an operating system that is beginning to compete with Microsoft Windows.)
Perfectability is a major preoccupation of Knuth’s. The only e-mail address Knuth maintains gathers reports of errata from readers of his books, offering $2.56 for each previously unreported error. (The amount is an inside joke: 256 equals 2 to the 8th power—the number of values a byte can represent.) Knuth’s reward checks are among computerdom’s most prized trophies; few are actually cashed.
He takes this error business very seriously. Engraved in the entryway to his home are the words of Danish poet Piet Hein:
The road to wisdom?
Well it’s plain
and simple to express:
Err
and err
and err again
but less
and less
and less.
In a variation on this theme of perfectability, Knuth’s contribution to computer science theory in the pages of The Art of Computer Programming has been his rigorous analysis of algorithms. Using methods in his book, the operations used to translate machine instructions into equations can be tested to determine whether they are optimal. Improving a program then becomes a question of finding algorithms with the most desirable attributes. Not that theoretical proofs can replace actually running software on a computer. In an often-cited remark he mentions on his Web page, he once warned a colleague: “Beware of the above code; I have only proved it correct, not tried it.”
Bad Breaks
In Knuth’s Stanford talk, perfectability was again a theme. He followed the pages in his volume on Digital Typography beyond its introductory chapters to the longest section in the book, which attacks a crucial problem in typography. He calls his listeners’ attention to “one of the main technical tricks in the TeX system: the question of how to break up paragraphs so that the lines are approximately equal and good.”
Poor spacing between words and ugly choices for line breaks had been among the major computer typography gaffes that launched Knuth on his TeX crusade. Odd word chasms, ladders of hyphens, and orphaned bits of text resulted from the rigid algorithms used to program line breaks without regard for visual elegance. Knuth’s solution: have the computer use trial-and-error methods to test how each paragraph of text can best be broken up. Instead of “greedy” algorithms packing in the most words on a line—standard in computer typography before and after TeX—Knuth’s computation-intensive method evaluates beauty.
Knuth seems born to the task of promoting beauty on the printed page—via computational methods. “I had a love of books from the beginning,” he tells his audience. “In my mother’s collection, we found the first alphabet book I had. I had taken the letters and counted all the serifs.” He is proud of his early literacy, telling a writer that he was the youngest member of the Book Worm Club at the Milwaukee Public Library. His interest in typographic reproduction also came early in life. One of his earliest memories of pre-desktop publishing was helping his father, Ervin, with the mimeograph stencils for printing the church newsletter in the basement. Like his father’s newsletter, TeX was meant to be a homebrew project, on a manageable scale. “The original intent was that it would be for me and my secretary,” he tells TR in an interview in his home’s second-floor study. Leaning back in the black lounge chair, Knuth acknowledges that the long journey into TeX was intended to be a quick side trip: “I was going to finish it in a year.”
Events took a different turn. In 1978, Sun’s Steele—then an MIT grad student visiting Stanford—translated TeX for use on MIT’s mainframe computer. Suddenly, Knuth recalls, “I had 10 users, then 100. Each time it went through different levels of error. In between the 1,000th and 10,000th user, I tore up the code and started over.” Knuth says he realized then that TeX wasn’t just a digression, it was itself part of the vision. “I saw that this fulfilled a need in the world and so I better do it right.”
A key turning point in the spread of TeX was a lecture Knuth gave before the American Mathematical Society (AMS). Barbara Beeton, a staff specialist in composition systems for AMS and a longtime official of the Portland, Ore.-based TeX User’s Group, remembers the occasion: “He was invited to deliver the Josiah Willard Gibbs Lecture. Albert Einstein and John von Neumann had been among the previous speakers. Knuth talked about his new typesetting system for the first time in public.” Knuth was preaching to the choir; the assembled mathematicians were familiar with how printing quality had declined. Adds Beeton: “TeX was the first composition system meant to be used by the author of an article or book” as opposed to a publishing house. Soon after, AMS became the original institutional user of TeX, employing Knuth’s system to publish all of its documents and journals.
As word spread and more users took advantage of his free software (written for an academic mainframe computer but soon made available for PCs), Knuth found himself studying the history of printing to find solutions for narrow applications. Often as not, his research proved fruitless and he would have to come up with his own answer. For ceremonial invitations, he created new fonts; for musical typesetting he solved difficult alignment problems. “I had so many users,” he recalls. “From wedding invitations and programs for the local symphonic orchestra to computer programs.”
For nearly nine years, Knuth’s foray into typography occupied him full time—pulling him away from work on the programming book that he considered his true calling. “I had to think of the endgame,” he says. “How could I responsibly finish TeX and say: This is not going to change anymore? I had to work out a four-year strategy to extricate myself” and return to The Art of Computer Programming.
Knuth’s solution: with the release of TeX version 3.0 in 1990, he declared his work complete. Disciples will have to maintain the system. Knuth says he will limit his work to repairing the rare bugs brought to his attention; with each fix he assigns one more digit to the version number so that it tends to pi (the current version is 3.14159).
One result of Knuth’s decision to stop making major changes to TeX is that the TeX file format has remained unchanged. “It’s the only software where you can take the file for your paper from 1985 and not have to convert it to print out the same way today,” notes David Fuchs, a senior researcher with Liberate Technologies (formerly Network Computer Inc.),who was a grad student at Stanford during the development of TeX. Fuchs estimates that there are 1 million TeX users worldwide; many employ special-purpose commercial packages built around the TeX “kernel,” such as LATeX (a command-oriented macro language) and TeXDoc (optimized for software documentation).
“On the downside, TeX is limited in its appeal because it’s not WYSIWYG,” Fuchs admits, employing the acronym for “what you see is what you get”—the standard term describing text processing software that displays formatting on screen as it will appear on the printed page. Rather than offering real-time onscreen interactivity, TeX requires a markup language typed into a document and interpreted by the computer; you see what you get only after it is in print. Despite its unintuitive user interface, TeX has developed a dedicated core of production professionals who will accept no substitute. “Why would anyone want anything else?” asks Paul Anagnostopolis, a Carlisle, Mass.-based publishers’ consultant and author of TeX-based software for book composition. “A lot of people don’t care about WYSIWYG.”
Opus in Progress
Spending nine years instead of one to create tex is the same kind of epic miscalculation that led Knuth to the monumental scale of The Art of Computer Programming. After earning his undergraduate degree at Case Institute (now Case Western Reserve), he was studying for his PhD and teaching at the California Institute of Technology in 1962 when he was contracted by textbook publisher Addison-Wesley to write a volume on computer compilers. (Compilers are special programs that convert the text typed in by programmers into instructions in a computer’s native binary language.)
In his book-lined study, Knuth recounts the history of the project. From 1962 to 1966, he wrote the first draft in pencil. The manuscript was 3,000 pages long. “I was thinking it was one volume of maybe 600 pages. I just figured type in books was smaller than my handwriting. Then I typed up chapter one and by itself it was 450 pages. I sent it to the publisher and they said: Don, do you have any idea how long your book will be?”
Faced with such an unwieldy manuscript, many publishers would have dumped the project. Instead, Addison-Wesley worked out a publication schedule for what could eventually stretch out to seven volumes. Volume 4 is supposed to be ready in 2004 and Volume 5 by 2009. Then Knuth may finish Volumes 6 and 7—if what he has to say on his chosen topics is still instructive. Peter Gordon, publishing partner at Addison-Wesley and Donald Knuth’s editor for the last 20 years, explains that the success of the first three volumes of The Art of Computer Programming has allowed the publisher to build its entire computer science line around Knuth’s work. “Don has his own life plan and his own sense of timing,” he notes. “He’s such a creative and gifted author, the best any editor can do is stay out of his way and let him follow his plan.”
It helps that the book continues to draw praise from other seers in the digital realm. In his syndicated newspaper column, Bill Gates once responded to a reader: “If you think you’re a really good programmer, or if you want to challenge your knowledge, read The Art of Computer Programming, by Donald Knuth.” Gates described his own encounter with the book: “It took incredible discipline, and several months, for me to read it. I studied 20 pages, put it away for a week, and came back for another 20 pages. If somebody is so brash that they think they know everything, Knuth will help them understand that the world is deep and complicated. If you can read the whole thing, send me a resume.”
What sustains Knuth through his epic project is his fundamental love of the subject. “People who work on the analysis of algorithms have double happiness,” he says, sounding Yoda-like. “You are happy when you solve a problem and again when people smile using your solution in their software.”
Before he can rest in the promised land, Knuth faces one last mountain. He must redesign the generalized computer used in his book for programming examples and exercises from a 50-year-old von Neumann-style machine with inefficient commands to a more modern RISC (reduced instruction set computer) system permitting faster operation. (Intel processors in most PCs are of the older variety; PowerPC chips in recent Macintosh models are RISC.) “I’m trying to design it so it’s 10 years ahead of its time,” says Knuth. “I’ve studied all the machines we have now and tried to take their nicest features and put them all together.” This super RISC machine, which he calls MMIX, is essentially a teaching concept. But he says he “would love to see it built. I’m spending a lot of time documenting it so someone could build it. The design will be in the public domain.” In the midst of his “Computer Musings” series of introductory talks on MMIX, Knuth is mere months away from completing this phase of his work.
And then? “I start charging away on Volume 4 at top speed. I can write about one publishable page a day,” he says. On another book he once wrote at a rate of two pages a day “but that was too much. I couldn’t be a good husband and a good father and that was not good. So, I’m just promising 250 pages a year for Volume 4.” For devotees of Knuth’s software Bible, Bill Gates included, those pages can’t come soon enough.
| Donald Knuth is updating all
three volumes of his definitive series,
The Art of
Computer Programming, one of the most well-known works in computer
science. Innovations interviewed him to find out more about how this came
about. Innovations: What do you see as the most important developments in programming since starting The Art of Computer Programming (TAOCP)? Knuth: The most important developments were surely the ideas of structured programming (1970s) and literate programming (1980s). But I'm a fan of all developments, not just the most important ones; and, of course, we now know a huge number of new techniques, especially with respect to Volume 4 [forthcoming]. When I began writing TAOCP in 1962, almost none of the ideas now in Volume 4 had been discovered; almost nobody would even have thought of writing a book about Combinatorial Algorithms. But during the 1970s, more than half of all papers on Computer Science were about that subject. Innovations: Where are those developments reflected in these new editions? Knuth: I've gone over every page and updated material, when I think the subject has "converged" to a form that people will find important not only today but also 50 or 100 years from now. Such changes appear throughout the books, most notably in the chapter on random numbers. On the other hand, many topics in Volumes 1, 2, and 3 are still evolving rapidly. In such cases, I have not made a major update; I've simply added a little icon to the page, meaning "sorry, still under construction"! I will do a final update to those books after I finish Volumes 4 and 5; otherwise I'd have to rewrite them again, and I would never finish. It's more important for me to get Volume 4 done than to keep Volumes 1, 2, and 3 strictly up to the minute. The new editions have hundreds of new exercises and answers to exercises that I know will always be instructive; I've been noting these things in my own copies of the books since the 1970s, and I'm making them public now. Innovations: Why revise Volumes 1, 2, & 3 before publishing
Volume 4?
Innovations: Do you still see this as a seven volume set? Innovations: Can you tell us about the process by which Volume 4
will eventually be published? Innovations: What inspired you to start this project? Innovations: What do you see as the biggest challenge facing
programmers today? Innovations: Who have been the biggest influences on your
computing career? Innovations: What do you think about the whole language war with
C++, Java, etc.? Innovations: Other than working on the new editions of The Art
of Computer Programming, what takes up your time these days? Innovations: What was your first reaction to the news of being
selected a recipient of the Kyoto Prize? |
"Computer programs are fun to write, and well-written computer programs are fun to read. One of life's greatest pleasures can be the composition of a computer program that you know will be a pleasure for other people to read, and for yourself to read.
Computer programs can also do useful work. One of life's greatest sources of satisfaction is the knowledge that something you have created is contributing to the progress of welfare of society.
Some people even get paid for writing computer programs! Programming can therefore be triply rewarding---on aesthetic, humanitarian, and economic grounds.
Of course I don't mean to imply that programming is easy. Easy things are often amusing and relaxing, but their value soon fades. Greater pleasure, deeper satisfaction, and higher wages are associated with genuine accomplishments, with the successful fulfillment of a challenging task.
I have spent a good deal of my life trying to help make computer programming as rewarding as possible, in all three senses. t first, I thought programming was primarily analogous to musical composition---to the creation of intricate patterns, which are meant to be performed. But lately I have come to realize that a far better analogy is available: Programming is best regarded as the process of creating works of literature, which are meant to be read.
Literature of the program genre is performable by machines, but that is not its main purpose. The computer programs that are truly beautiful, useful, and profitable must be readable by people. So we ought to address them to people, not to machines. All of the major problems associated with computer programming---issues of reliability, portability, learnability, maintainability, and efficiency---are ameliorated when programs and their dialogs with users become more literate.
...
Literate programming is still a fairly new concept, still in its infancy, still undergoing much-needed experimentation. Many people have contributed important ideas and independent approaches to the creation of systems that improve on WEB in various ways. In this book I describe the techniques that have worked best for me, but I have never imagined that any of my ideas would be the "last word" in any sense. I am sure that people with differing tastes will prefer a system that differs from my own initial attempts.
The time is on ripe for second-generation systems that integrate literate programming into complete programming environments. "
-- Donald E. Knuth, " Literate Programming", 1992.
Compiled by Nikolai Bezroukov
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: August 27, 2008