Softpanorama (slightly skeptical) Open Source Software Educational Society

May the source be with you, but remember the KISS principle ;-)

Chapter 1: Donald Knuth: Leonard Euler of Computer Science

version 0.72 beta

"Computer programming is an art form, 
like the creation of poetry or music"

Donald E. Knuth[1974]

Contents

• Introduction

• Biographic notes

• TAoCP and its Influence of Computer Science

• The second love: typography

• TeX and TAOCP Bugs (a.k.a. "Entomology")

• Literate programming

• Thank you Donald Knuth

• Webliography.shtml (interviews, reviews of books, etc)

Let me make it clear from the beginning: I really admire this man. Donald E. Knuth is not only Professor Emeritus of The Art of Computer Programming at Stanford University, the author of the multi-volume work-in-progress The Art of Computer Programming, five volumes of Computers & Typesetting, a member of the American Academy of Arts and Sciences, the National Academy of Sciences, and the National Academy of Engineering and so on and so forth. Unlike many other bearers of a similar number of prestigious titles and published books, he is a unique lonely star among computer science researchers. I would say he is man of a stature similar to the stature of Leonard Euler in mathematics. Such men are not born every century...

Despite opinion of some overzealous (or in a permanent state of religious stupor) free/open software evangelists, free software existed long before Gnu project and the volume of it far exceeded the GNU project. Moreover the current free/open software is largely based on what has come before it. Professor Donald Knuth is one of the largest contributors to this pool of knowledge. Moreover, free and open programs are only as good as algorithms they are using. And dismissing his contributions to free software movement as irrelevant like "professional software freedom fighter" Richard Stallman once did (see Slashdot/2nd Annual Free Software Foundation Awards ) was at least disrespectful (even if we forget the fact that TeX is one of the most important free software programs ever written). 

It's amazing that despite the information explosion in computer science Professor Knuth is still trying to finish his monumental The Art of Computer Programming (TAoCP), a one-author written encyclopedia in algorithms and computer science. That really makes him  "The Last of the Mohicans" -- the last Renaissance man in computer science. He really has managed to make contributions to a very wide area of computer science topics. Among them:

• Suggested the name "Backus-Naur Form";
• Wrote one of first and one of the most compact Algol compilers;
• Designed the SOL simulation language;
• Designed and wrote the TeX and Metafont systems of documentation (written in WEB for Pascal);
• Introduced and refined the LR parsing algorithm (see Knuth, D.E. 1965. "On the Translation of Languages from Left to Right", Information and Control, Vol. 8, pp. 607-639. The first paper on LR parsing.)
• Invented several important algorithms including Knuth-Morris-Pratt string-searching algorithm;
• Made the crucial contribution to the "Structured programming without GOTO" programming debate, which was a decisive blow to the structured programming fundamentalists led by E. Dijkstra;
• Published his groundbreaking paper  "An empirical study of FORTRAN programs." ( Software---Practice and Experience, vol 1, pages 105-133, 1971) which laid the cornerstone of an empirical study of programming languages.
• Made the crucial contribution to dispelling "correctness proof" mythology.  Here is his famous citation about correctness proofs;
   

  On March 22, 1977, as I was drafting Section 7.1 of The Art of Computer Programming, I read four papers by Peter van Emde Boas that turned out to be more appropriate for Chapter 8 than Chapter 7. I wrote a five-page memo entitled ``Notes on the van Emde Boas construction of priority deques: An instructive use of recursion,'' and sent it to Peter on March 29 (with copies also to Bob Tarjan and John Hopcroft). The final sentence was this: "Beware of bugs in the above code; I have only proved it correct, not tried it.''

Still no other book in CS can be compared with his encyclopedic The Art of Computer Programming (TAoCP). It is one of the few books that remain largely relevant 30 years after the initial publication. I am convinced that every person who suspects that he/she has a programming abilities (and BTW an early start is a good indication of abilities in any field, including programming) should buy or borrow the first volume of TAoCP and try to solve exercises after each chapter. The ability to solve difficult exercises form the first volume is a sure sign of people with substantial talent and can be a good self-test if you it make sense to dedicate yourself to carrier in computer science or not. 

Many people do not understand that one of the first major open source project was neither GNU not Linux. And that several free OSes and compliers existed before GNU project started. For example, one of the first free compilers that I know was XPL written by William M. McKeeman  (see his famous book A Compiler Generator published by Prentice Hall in June 1970). The other is Knuth typesetting program TeX along with invented by Knuth mark-up language by the same name. Knuth developed the first version of TeX in in 1971-1978 in order to avoid problem with typesetting of the second edition of his TAoCP volumes. The program proved popular and he produced a second version (in 1982) which was the basis of what we use today.  The whole text of the program was published in this book The TeXbook (Addison-Wesley, 1984, ISBN 0-201-13447-0, paperback ISBN 0-201-13448-9).

Introduction

Richard M. Stallman, Linus Torvalds, and Donald E. Knuth
engage in a discussion on whose impact 
on the computerized world was the greatest.
Stallman: "God told me I have programmed
 the best editor in the world!"
Torvalds: "Well, God told *me* that I have programmed
 the best operating system in the world!"
Knuth: "Wait, wait - I never said that."

From rec.humor.funny. 
submitted by ermel@gmx.de (Erik Meltzer)

Even among computer pioneers in Stanford, Donald Knuth was considered to be almost legendary figure. The following  old anecdote from Alan Kay, one of the principal designers of the Smalltalk language, illustrates the point:

When I was at Stanford with the AI project [in the late 1960s] one of the things we used to do every Thanksgiving is have a computer programming contest with people on research projects in the Bay area. The prize I think was a turkey. [John] McCarthy used to make up the problems. The one year that Knuth entered this, he won both the fastest time getting the program running and he also won the fastest execution of the algorithm. He did it on the worst system with remote batch called the Wilbur system. And he basically beat the shit out of everyone. And they asked him, "How could you possibly do this?" And he answered, "When I learned to program, you were lucky if you got five minutes with the machine a day. If you wanted to get the program going, it just had to be written right. So people just learned to program like it was carving stone. You sort of have to sidle up to it. That's how I learned to program."

In his 2008 interview to InformIT  Donald Knuth recollected events in the following way:

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."

Although many people knows about tremendous contribution of Donald Knuth to the systematization of computer science, to the theory of compiling, to algorithms theory, but few know that among other things Knuth suggested the name "Backus-Naur Form", wrote one of the most compact Algol compilers at the age of 22 and published the first volume of The Art of Computer Programming at the age of 28. His three volumes of  The Art of Computer Programming played an important role in establishing and defining Computer Science as a rigorous, intellectual discipline. He also made fundamental contributions to the analysis of algorithms, compilers, string matching, term rewriting systems, and typography. His TeX and MF systems are widely used for electronic typesetting.

Donald Knuth probably received more awards then any other professor of computer sciences ;-), including the 1974 Turing Award, and the 1979 National Medal of Technology. He holds honorary doctorates from more than 15 universities worldwide including prestigious Russian St. Petersburg University, the university were Leonard Euler, the most prolific mathematician in the 18th century and maybe even of all time, spend his most productive years (he succeeded  Bernoulli as Professor of Mathematics of St. Petersburg University in 1733).

That's probably an example for Knuth to strive for as Euler published 866 books and articles that represented about one third of the entire body of research on mathematics, theoretical physics, and engineering mechanics published between 1726 and 1800. Among other things he modernized mathematical notation including the introduction of now standard symbols    and e.

Actually the analogy between Donald Knuth and Leonard Euler is deeper than Lutheran religion, tremendous productivity and interest in things quite remote from the main field: Leonard Euler was interested in cartography (historians believe that this contributed to his early blindness) and spent a lot of time and effort on non-mathematical studies; Donald Knuth also spend huge amount of time and effort outside his major field and authored of the TeX and Metafont (written in WEB for Pascal) -- the major open source typesetting system that become a standard de-facto in mathematics and computer science. He also published 3:16 Bible Texts Illuminated. An interesting, but little known fact is that in 1962 Knuth obtained 1,271 digits of Euler's constant, using the Euler-Maclaurin summation.

Like Euler believed in the esthetic value of mathematic theories, Knuth believes that preparing programs for a computer can be an aesthetic experience, much like composing poetry or music. As for music he probably knows what he is talking about: he plays a custom-made pipe-organ (this sixteen-rank organ was designed and built for his home by Abbott and Sieker of Los Angeles, California, as their ``Opus 67.'' It has 812 pipes, separated into three divisions).

Last modified: April 28, 2008