Softpanorama Bulletin
Vol 14, No. 04 (October, 2002)

Chapter 1: Donald Knuth: Leonard Euler of Computer Science

version 0.80

"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

• Literate programming

• Thank you Donald Knuth

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

Let me make it clear from the very 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 of algorithms and computer science. That really makes him  "The Last of the Mohicans" -- the last Renaissance man in computer science. He one of few who has managed to make contributions to a very diverse spectrum of  computer science topics. Among them:

• Wrote one of the first and one of the most compact Algol compilers at the age of 22 (1960)
• Obtained 1,271 digits of Euler's constant, using the Euler-Maclaurin summation (1962).
• Designed the SOL simulation language;
• Suggested the name "Backus-Naur Form" (1964).
• 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.)
• Published the first volume of The Art of Computer Programming at the age of 20 (1968). His three volumes of  The Art of Computer Programming (1968, 1969, and 1973) played an important role in establishing and defining Computer Science as a rigorous, intellectual discipline.
• 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 the "Structured programming without GOTO" programming debate, which was a decisive blow to the structured programming fundamentalists led by Edsger Dijkstra by publishing an article Structured Programming with go to Statements. ACM Comput. Surv. 6(4): 261-301 (1974)
• Designed and wrote the TeX and Metafont systems of documentation (written in WEB for Pascal). 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 his book The TeXbook (Addison-Wesley, 1984, ISBN 0-201-13447-0, paperback ISBN 0-201-13448-9).
• Invented several important algorithms including LR parsing algorithm and Knuth-Morris-Pratt string-searching algorithm (1977);
• 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 computer science can be compared with his encyclopedic The Art of Computer Programming (TAoCP). It is one of the few books which remain 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 interest/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 from the first volume is a sure sign of people with substantial talent and can be a good self-test. It can help to decide whether it makes sense to dedicate yourself to career in computer science or not. Of course, computer science changed a lot since 1960th when TAOC was published; stagnation of CS departments is a fact that cannot be hidden. But despite that there are still a few areas in it where creativity matters and where talented people can make a significant contribution. As a side note, it is clear that becoming a quant in company like Goldman Sachs is not such a bright future as many assume.  Modern financial system in parasitic in a sense that it imposes huge cost on the society; one part of that cost is that large pool of top talent in the western world gravitates to financial firms. At the level of the society and aggregate economy, this is a waste  of resources: their activity adds little or no economic value.

Science including computer science is another story. It does has value to the society at large and Donald Knuth life is a good example what a single talented individual can accomplish besides buying a yacht with his name on it and a half-dozen of villas in different parts of the globe.

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 [email protected] (Erik Meltzer)

While the above joke is somewhat silly, it has a grain of truth in it: even among numerous computer pioneers in Stanford, Donald Knuth is a legendary figure. The figure with its own set of urban legends. For example, the 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."

Donald Knuth probably received more prestigious computer science related 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 Leonard 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. An interesting, but little known fact is that in 1962 Knuth obtained 1,271 digits of Euler's constant, using the Euler-Maclaurin summation.

Actually the analogy between Donald Knuth and Leonard Euler is deeper than Lutheran religion, tremendous productivity and groundbreaking contributions. Both has interest in things quite remote from the their 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 while he developed 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.

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

Note:

This article is a part of the first chapter of the book Nikolai Bezroukov. Portraits of Open Source Pioneers: Essays on early history of open source). Newer version of this article might be avalable at  Donald Knuth: Leonard Euler of Computer Science

Etc

Society

Groupthink : Two Party System as Polyarchy : Corruption of Regulators : Bureaucracies : Understanding Micromanagers and Control Freaks : Toxic Managers :   Harvard Mafia : Diplomatic Communication : Surviving a Bad Performance Review : Insufficient Retirement Funds as Immanent Problem of Neoliberal Regime : PseudoScience : Who Rules America : Neoliberalism  : The Iron Law of Oligarchy : Libertarian Philosophy

Quotes

War and Peace : Skeptical Finance : John Kenneth Galbraith :Talleyrand : Oscar Wilde : Otto Von Bismarck : Keynes : George Carlin : Skeptics : Propaganda  : SE quotes : Language Design and Programming Quotes : Random IT-related quotes :  Somerset Maugham : Marcus Aurelius : Kurt Vonnegut : Eric Hoffer : Winston Churchill : Napoleon Bonaparte : Ambrose Bierce :  Bernard Shaw : Mark Twain Quotes

Bulletin:

Vol 25, No.12 (December, 2013) Rational Fools vs. Efficient Crooks The efficient markets hypothesis : Political Skeptic Bulletin, 2013 : Unemployment Bulletin, 2010 :  Vol 23, No.10 (October, 2011) An observation about corporate security departments : Slightly Skeptical Euromaydan Chronicles, June 2014 : Greenspan legacy bulletin, 2008 : Vol 25, No.10 (October, 2013) Cryptolocker Trojan (Win32/Crilock.A) : Vol 25, No.08 (August, 2013) Cloud providers as intelligence collection hubs : Financial Humor Bulletin, 2010 : Inequality Bulletin, 2009 : Financial Humor Bulletin, 2008 : Copyleft Problems Bulletin, 2004 : Financial Humor Bulletin, 2011 : Energy Bulletin, 2010 : Malware Protection Bulletin, 2010 : Vol 26, No.1 (January, 2013) Object-Oriented Cult : Political Skeptic Bulletin, 2011 : Vol 23, No.11 (November, 2011) Softpanorama classification of sysadmin horror stories : Vol 25, No.05 (May, 2013) Corporate bullshit as a communication method  : Vol 25, No.06 (June, 2013) A Note on the Relationship of Brooks Law and Conway Law

History:

Fifty glorious years (1950-2000): the triumph of the US computer engineering : Donald Knuth : TAoCP and its Influence of Computer Science : Richard Stallman : Linus Torvalds  : Larry Wall  : John K. Ousterhout : CTSS : Multix OS Unix History : Unix shell history : VI editor : History of pipes concept : Solaris : MS DOS :  Programming Languages History : PL/1 : Simula 67 : C : History of GCC development :  Scripting Languages : Perl history   : OS History : Mail : DNS : SSH : CPU Instruction Sets : SPARC systems 1987-2006 : Norton Commander : Norton Utilities : Norton Ghost : Frontpage history : Malware Defense History : GNU Screen : OSS early history

Classic books:

The Peter Principle : Parkinson Law : 1984 : The Mythical Man-Month :  How to Solve It by George Polya : The Art of Computer Programming : The Elements of Programming Style : The Unix Hater’s Handbook : The Jargon file : The True Believer : Programming Pearls : The Good Soldier Svejk : The Power Elite

Most popular humor pages:

Manifest of the Softpanorama IT Slacker Society : Ten Commandments of the IT Slackers Society : Computer Humor Collection : BSD Logo Story : The Cuckoo's Egg : IT Slang : C++ Humor : ARE YOU A BBS ADDICT? : The Perl Purity Test : Object oriented programmers of all nations : Financial Humor : Financial Humor Bulletin, 2008 : Financial Humor Bulletin, 2010 : The Most Comprehensive Collection of Editor-related Humor : Programming Language Humor : Goldman Sachs related humor : Greenspan humor : C Humor : Scripting Humor : Real Programmers Humor : Web Humor : GPL-related Humor : OFM Humor : Politically Incorrect Humor : IDS Humor : "Linux Sucks" Humor : Russian Musical Humor : Best Russian Programmer Humor : Microsoft plans to buy Catholic Church : Richard Stallman Related Humor : Admin Humor : Perl-related Humor : Linus Torvalds Related humor : PseudoScience Related Humor : Networking Humor : Shell Humor : Financial Humor Bulletin, 2011 : Financial Humor Bulletin, 2012 : Financial Humor Bulletin, 2013 : Java Humor : Software Engineering Humor : Sun Solaris Related Humor : Education Humor : IBM Humor : Assembler-related Humor : VIM Humor : Computer Viruses Humor : Bright tomorrow is rescheduled to a day after tomorrow : Classic Computer Humor

The Last but not Least Technology is dominated by two types of people: those who understand what they do not manage and those who manage what they do not understand ~Archibald Putt. Ph.D

The statements, views and opinions presented on this web page are those of the author (or referenced source) and are not endorsed by, nor do they necessarily reflect, the opinions of the Softpanorama society. We do not warrant the correctness of the information provided or its fitness for any purpose. The site uses AdSense so you need to be aware of Google privacy policy. You you do not want to be tracked by Google please disable Javascript for this site. This site is perfectly usable without Javascript.

Last modified: March 12, 2019