Nikolai Bezroukov. Portraits of Open Source Pioneers

For readers with high sensitivity to grammar errors access to this page is not recommended :-)

Biographic Notes

"I decry the current tendency to seek patents on algorithms.
There are better ways to earn a living than to prevent other people
 from making use of one's contributions to computer science."
Donald E. Knuth, TAoCP vol 3

Donald Knuth was born on January 10, 1938, in Milwaukee, Wisconsin. Donald's father Ervin was a  teacher in a Lutheran school; he also played the church organ at the Sunday church services. Ervin Knuth was the first college-educated person in his family. Donald Knuth grandfather was a blacksmith.

During his first years at secondary school there were clear signs of where Knuth's interests would eventually lead. One episode, repeated in most biographies of Knuth, is related to "Ziegler's Giant Bar" competition.  He entered a competition by the confectionary manufacturer Ziegler to make as many  words with the letters from the phrase "Ziegler's Giant Bar" as possible. Donald spent two weeks during which he pretended to be ill and came up with 4500 words. The judges for the competition had only found 2500.

In 1956 he graduated from Milwaukee Lutheran High School and enrolled at the Case Institute of Technology in Cleveland, Ohio, as a physics major. According to www.digitalcentury.com encyclopedia article about him:

Although Knuth accomplished the highest grade point average in the history of his high school, he and his advisors had doubts as to his ability to succeed at college math. Knuth reports having something of an inferiority complex during his high school and early college years, a problem to which he attributes his over-achiever status. As a college freshman he would spend hours working extra problems in math out of fear that he would fail, only to find after a few months that his abilities far exceeded any of his colleagues.

At some point he even considered a musical carrier(digitalcentury.com):

Knuth’s plan to become a music major changed when he was offered a physics scholarship at Case Institute of Technology (now Case Western Reserve). His turn toward math came during his sophomore year when a particularly difficult professor assigned a special problem, offering an immediate "A" in the class to any student who could solve it. Although like most of the other students, Knuth considered the problem unsolvable, he made an attempt at it one day when he found himself with some free time, having missed the bus that was taking the marching band to a performance. By what he states was "a stroke of luck," he solved the problem in short order, earned his "A," and skipped class for the rest of the semester. Although Knuth reports that he felt guilty about skipping class, he was obviously able to overcome the lost instruction because the following year he earned an "A" in abstract mathematics and was given the job of grading papers for the very course he had failed to attend.

Here is how this early period of Donald Knuth's life is described in OUT OF THEIR MINDS: The Lives and Discoveries of 15 Great Computer Scientists:

His father, the first college graduate in the Knuth family, started as a grade school teacher, and later taught bookkeeping in a Lutheran high school. He also played the church organ on Sundays. Donald inherited his father's appreciation of music and education, particularly patterns in language.

I was mostly interested in what the teachers were best at. We had very good training in the diagramming of sentences. A bunch of us would have fun after class figuring out the parts of speech in sentences of poetry.

As editor of the school newspaper, Knuth invented crossword puzzles. He remembers enjoying the search for patterns in words.

He began winning awards early on. When Knuth was in eighth grade, a candy manufacturer sponsored a contest to see who could compose the most words out of the letters in the phrase, ``Ziegler's Giant Bar.'' Knuth decided to give it a try and came in first.

I found approximately 4,500 words without using the apostrophe. With the apostrophe, I could have found many more. The judges had only about 2,500 on their master list.

He won a television set (a pricey item in those days) and enough Ziegler candy bars for the entire school. In high school, Knuth won honorable mention in the Westinghouse Science Talent Search with an unusual proposal: The potrzebie system of weights and measures. With the care that would mark his later career, Knuth defined his basic units precisely: the potrzebie to be the thickness of MAD Magazine 26; a MAD to be 48 things; and a whatmeworry, the basic unit of power. In June of 1957, Mad Magazine itself bought the piece for $25, the first publication of Donald's prolific career. But music, not writing or science, took most of his time during high school.

I thought when I went to college I would be a music major. I played saxophone, but then the tuba player got into an accident and I became a tuba player. I arranged a piece for band that combined all kinds of themes off TV shows --- Dragnet, Howdy Doody Time, and Bryl Cream. I knew nothing about copyright law.

His plans to become a musician changed when Case Institute (later Case Western Reserve) offered him a physics scholarship.

The system channeled anybody with an aptitude for science into physics. It was post World War II and there was a lot of excitement in the field.

In high school, Knuth had found mathematics uninspiring. But at Case, Paul Guenther, who taught freshman calculus, persuaded him to switch from physics to math. Guenther became Knuth's mentor in the process.

I had never met a mathematician before. He had a good sense of humor, but no matter what you said to him, he was unimpressed.

In 1956, Knuth had his first encounter with a computer, an IBM 650 --- a pre-FORTRAN machine. He stayed up all night reading the manual and taught himself basic programming.

The manuals we got from IBM would show examples of programs and I knew I could do a heck of a lot better than that. So I thought I might have some talent.

Case Institute

Knuth got a physics scholarship from Case, but soon he realized that mathematics interests him more. Moreover not all mathematics but specifically discrete mathematics.  As he recollected later in CACM interview (April, 2008):

In my sophomore year in physics I had to take a required class of welding. Welding was so scary and I was a miserable failure at it, so I decided maybe I can't be a physicist. On the other hand—mathematics! In the sophomore year for mathematicians, they give you courses on what we now call discrete mathematics, where you study logic and things that are integers instead of continuous quantities. I was drawn to that. That was something, somehow, that had great appeal to me.

I think that there is something strange inside my head. It's clear that I have much better intuition about discrete things than continuous things. In physics, for example, I could pass the exams and I could do the problems in quantum mechanics, but I couldn't intuit what I was doing. But on the other hand, in my discrete math class, these were things that really seemed a part of me. There's definitely something in how I had developed by the time I was a teenager that made me understand discrete objects, like zeros and ones of course, or things that are made out of alphabetical letters, much better than things like Fourier transforms or waves.

I'm visualizing the symbols. To me, the symbols are reality, in a way. I take a mathematical problem, I translate it into formulas, and then the formulas are the reality.

IBM 650 changes course of Donald Knuth career

It's probably a lucky coincidence that Knuth entered college the same year (1956) the IBM 650 became available on campus and he managed to start working at the Case University Computing Center. IBM 650 was one of the first commercial vacuum-tubes based programmable computers (it was predated by 701, which was launched in 1952).

He wrote his first program for IBM 650 during the spring of his freshman year. As he recollected later it was the program to find the prime factors of a number and final version was approximately 120 machine instructions.

That "career move" actually determined his future. The IBM 650 was not just one of the most important early computers, it was the ancestor of personal computers. Prior to the IBM 650 (and in many case after it ;-), computers were so expensive that most programmers never had physical access to the computer room. It was a faceless and frustrating "batch environment": you handed in a punched card deck with your program and data, and got it back next day (or the same day if you are lucky) with the printout of the run. I doubt that programming would attract Donald Knuth in such an environment, and he probably would navigate his way in some other direction.

But on IBM650, users were given a block of time and could run their programs, see what went wrong, fix it and try again. Despite the fact that slots allocated were tini (often just 15 min), this was really fascinating environment... Because of its cost, the machine was kept busy 24 hours a day and for student allocated time was usually at night, as late as 11:00 pm or even 1:00 am.  Often a user needed to share his block of time with another programmer to increase the efficiency of the computer usage: when one user program stopped, or went into a loop (that can be guessed by the way the lights flickered) the user needed to record the console lights, get off, think about the bug and let his partner use the machine. Kind of pair programming  on pre-historical computers ;-)  

For many universities it was their first computer. IBM played cards very skillfully and its attractiveness was considerably enhanced by the availability of a 60% educational discount conditional on the institution teaching certain computer-related courses.

Here are some interesting facts about this ancient computer:

• The first IBM 650 was available in December of 1954. By 1956 when I first saw one there were over 500 [of them] making it at the time the most available computer from IBM.
• In 1956 the rental price for the CPU and power supply was $3,200/month. {This was about the complete price of a fully loaded Cadillac.}
• The CPU was 5ft by 3ft by 6ft and weighed 1966 lbs
• The power unit was 5ft by 3ft by 6ft and weighed 2972 lbs.
• The system required 22 KVA. {a shirt pocket HP-100 will run on 2 AA cells and is much faster}
• A card reader/punch was the I/O unit weighing 1295 lbs and rented for $550/month.
• The probable operating ratio was 80% -- not guaranteed. 
• The estimated cost of spare parts was $4000/year.
• The 650 could add or subtract in 1.63 mill-seconds, multiply in 12.96 ms, and divide in 16.90 ms. Speed per Gill calculation is 27.6 ms
• The memory on most systems was magnetic drum with 2000 word {10 digits and sign} capacity and random access time of 2.496 ms. {my HP-100 has 2 MBytes and is timed in nanoseconds}
• For an additional $1,500/month you could add magnetic core memory of 60 words with access time of .096ms.
• One neat feature about a IBM 650 program was the use of three addresses. {the 3rd for the address of the next instruction} This means you could drop your deck and as long as you got the first card in front your program would load. While at Univ of Kansas this writer figured out a way to remove one instruction from the load card. -- can't recall what it was now.
• While the IBM 650 was not a super-hot machine, it did have one feature that made it sell -- Namely lots of blinking lights. With that anyone could tell something was going on. Some authors attribute the success of IBM to these blinking lights and the fact the computer used the same cards as the other unit record equipment of IBM. {Actually the output of your 650 program was punched on cards and you would take the deck over to a 402 Accounting Machine to get a print out.}

From this description it is clear that this 1,966 lb machine that consumed almost 30 Kw of electricity would look more like a primitive calculator than a real computer: it has the memory of just 10,000 decimal digits of storage (less than 40K or 1,000 words; 10 digit per word).   A word can be interpreted either as representing a data containing ten decimal digits and sign, or as an instruction. Instructions was structured the following way:

• a 2-digit opcode,
• a 4-digit operand address,
• the 4-digit address of the next instruction to execute.

The 650 had a single 10-digit accumulator (called "Upper") for addition and subtraction, with a 10-digit extension ("Lower") for multiplication, division, and shifting, plus a 10-digit Distributor (essentially, another accumulator).  There is a Java IBM 650 Simulator that you can try.

Here is the high level description of the instruction set of IBM 650:

An IBM 650 machine code instruction was of the form: xx yyyy zzzz  where xx was the op code, yyyy was the operand address and zzzz the address of the next instruction. Thus each instruction contained a jump, to allow for the possibility of "optimization." If you program a drum machine with the instructions stored sequentially, you have to wait at least one drum revolution to read the next instruction. By calculating the expected execution time for each instruction, you can place the next instruction at the correct rotation angle around the drum so that it will come up under a read head when the current instruction is done. Since instructions could execute in as little as little as 0.3 ms (for an add), versus a drum revolution time of about 4.8 ms, careful optimization could increase execution speed by a factor of 5 or more. This is similar to the way in which disk drives use an "interleave factor" which interleaves logically adjacent sectors to improve read/write performance.

Instruction words consisted of a two-digit function code, a four-digit operand address, and the four-digit address of the next instruction. The address of the next instruction was important in a drum memory environment. Since the drum was constantly rotating, it would move some distance while each instruction was being executed. So, to minimize the delay between instructions, it would be best to have the next instruction positioned on the drum at the place where the read-write head was when execution of the current instruction was completed. As a result, instructions which followed each other in program logic would be scattered around the drum, not physically next to each other. The manuals for machines gave instruction timings, so that programmers could try to reduce rotational delays. This approach was called minimum latency programming. It was complicated by the need to fetch operands, so that the programmer had to keep in mind the locations of data and of the next instruction. To aid 650 programmers, IBM published a memory chart. It had 200 rows and 10 columns, with each cell representing a word of memory. As you wrote your program, you would place each instruction and data word in an optimal location and then mark that memory cell off as used on the chart.

Today it's really amazing that you can do something useful with such a primitive and slow by today standards machine: (data below were taken from The Columbia University The IBM 650 page; more detailed info can be found in  DDJ The IBM 650 paper by Herb Kugel): 

The 650 could add or subtract in 1.63 milliseconds, multiply in 12.96 msec, and divide in 16.90 ms. The memory was a rotating magnetic drum with 2000 word (10 digits and sign) capacity and random access time of 2.496 ms. For an additional $1,500/month you could add magnetic core memory of 60 words with access time of .096ms.  ...

Despite its limitations (and partially because of them) this computer has deep influence on Donald Knuth and some of its idiosyncrasies can be traced to MIX. Not accidentally Donald Knuth dedicated his the first volume of his classic book "to the Type 650 computer once installed at Case Institute of Technology, in remembrance of many pleasant evenings".  Due to its role as the ancestor of personal computer IBM 650 was an important part of early computer folklore. For example here is an early warning attached to the computer in IBM Watson lab:

Achtung! Alles Lookenspeepers !

Das computermachine ist nicht fur gefingerpoken und mittengrabben.
Ist easy schnappen der springenwerk, blowenfusen, und poppencorken mit spitzensparken.
Ist nicht fur gewerken bei das dumpkopfen.
Das rubbernecken sichtseeren keepen hans in das pockets muss...:
Relaxen und watch das blinkenlichten.

IBM expected to deploy only about 50 of these systems, but the demand was much larger and approximately 2000 were installed in the nine years (1953-62), surpassing the entire combined sales of all the 700 series. Support for the 650 was withdrawn by IBM in 1969. The IBM 7070 (1959) was architecturally similar transistors-based computer. Along with card reader and punch it featured printer and typewriter console.

In order to understand better the atmosphere of those early years and the level of  hardware and software development at this time I will reproduce here a part of the computer timeline that covers the period from 1955 to 1960, the college years of Donald Knuth:

1954 650 medium-sized computer introduced by IBM
1955 Sperry-Rand formed by merger of Remington Rand and Sperry Corp 1955 IBM branch in Wellington, NZ starts operations
1955 Wang Laboratories incorporated
1955 Shockley Semiconductor founded in Palo Alto, California, USA
1955 One of the first algorithmic languages II II [PP] was created by A. P. Ershov for BESM computer; also L. N. Korolev, L.D. Panova, V.D. Poderiugin & V.M. Kurochkin, USSR
1955 SHARE users group
1955 BACAIS compiler by Mandalay Grems & R.E. Porter, Boeing Airplane Company, Seattle, USA for IBM 701 [Boeing Airplane Company Algebraic Interpretive Computing System]
1955 IT discussed by Alan Perlis, Mark Koschman, Sylvia Orgel, Joseph W. Smith & Joanne Chipps for Datatron computer, Purdue University Computing Laboratory [Internal Translator]
1955 Kompiler 2 by A. Kenton Elsworth, Robert Kuhn, Leona Schloss & Kenneth Tiede, University of California Radiation Laboratory, Livermore
1956 IPL language by A Newell, D Shaw, F Simon (Information Programming Language)
1956 ADES declarative language by E. K. Blum, US Naval Ordnance Laboratory [Automatic Digital Encoding System]
1956 APT language by D.T. Ross (Automatic Programmed Tool) - industrial
1956 B-0 compiler by Grace Hopper's programming staff, UNIVAC [later called Procedure Translator, & FLOW-MATIC]
1956 MAILÜFTERL computer by H. Zemanek & team, University of Technology, Austria [MAILUEFTERL = Viennese spring-time breeze - ie, not a Whirlwind]
1956 Burroughs 205
1956 MADCAP language by Los Alamos Scientific Laboratory (Mark B. Wells?)
1956 IT adapted & run on IBM 650 by Perlis & Smith, with Harold van Zoeren, Carnegie Institute of Technology
1956 Physics Nobel Prize won by Bardeen, Brattain & Shockley for transistor
1956 MATH-MATIC compiler by Charles Katz et al, UNIVAC
1956 Bull S.A. announces very-large, very-fast Gamma 60 for 1960 to compete against IBM
1956 T.J. Watson Jr becomes president of IBM
1956 'Artificial Intelligence' term coined by John McCarthy, MIT
1956 Bizmac shipped by RCA
1956 US Govt antitrust suit settled. IBM has to sell not just leases
1957 Datamatic 1000 Honeywell & Raytheon
1957 Digital Equipment Corp (DEC) founded by Ken Olsen, Maynard Massachusetts
1957 Fairchild Semiconductor founded
1957 Philco 2000 by Philco Corporation - first commercially available transistorised computer.
1957 MAC compiler for Whirlwind by Laning, Philip C. Hankins & Charles P. Werner
1957 Control Data Corporation est. by William Norris & Sperry-Rand engineers
1957 Datamation first published
1958 SAGE direction centre operational, McGuire Air Force Base, New Jersey
1958 Atlas by R.M. Kilburn, University of Manchester - first virtual memory
1958 Integrated Circuit (IC) by Jack Kilby, Texas Instruments
1958 NEC-1101, NEC-1102 NEC Japan's First computer (Nippon Electric Company)
1958 Commodore Business Machines founded by Jack Tramiel
1958 FORTRAN II - 1st language accepted worldwide.
1958 CRT as output device by Frank Rosenblatt on Perceptron Mark I
1958 CDC 1604 by Seymour Cray, Control Data Corp, 1st transistorised supercomputer
1958 Planar process of making transistors by Jean Hoerni
1958 ALGOL Zurich. Originally called IAL
1958 LISP language by John McCarthy et al, MIT (LISt Processing) - for artificial intelligence
1959 Packaged program by Computer Science Corporation
1959 Monolithic idea for ICs by Robert Noyce, Fairchild Semiconductor
1959 ACM-GAMM report by John Backus
1959 Planar IC by Robert Noyce - for mass manufacturing of ICs
1959 1620 & 1790 - IBM's 2nd generation computers
1959 1401 introduced by IBM
1959 COBOL language by committee of mainframe makers (COmmon Business-Oriented Language)
1959 Teleprinter link between Auckland & Sydney

Soon Donald Knuth was experimenting with IT ("Internal Translator") which was one of the first algorithmic language translators. He was so interested in understanding how this complex program work that he got source code and spend the whole summer trying to understand the logic. 

Knuth used his growing expertise as a programmer not only for scientific computations. In 1958 he wrote a program to analyze the performance of the College basketball team. It led to huge publicity and IBM used a picture of Knuth in their advertising.

In 1960 the Case faculty took the unprecedented step of awarding Donald Knuth a Master's degree simultaneously with the B.S. degree. At this time he was 22 years old. Knuth was also awarded two Fellowships, a Woodrow Wilson Fellowship and a National Foundation Fellowship in the year of his graduation. Knuth also published his first two papers in 1960:

• An imaginary number system Describes an imaginary number system using the imaginary number 2i as its base, giving methods for the addition, subtraction and multiplication of the numbers.
• On methods of constructing sets of mutually orthogonal Latin squares using a computer (jointly with R C Bose and I M Chakravarti). Presents two sets of five mutually orthogonal Latin squares of order 12.

Writing Algol Compiler for Burroughs

During the summer of 1960 he worked for Burroughs where he wrote an Algol compiler -- one of the smallest at the time. For that compiler he was paid $5,500 -- not bad money for a student at 1960, but much less that was a common price for such a project.

The flowcharts of the compiler were published in Communications of the ACM (Donald E. Knuth: RUNCIBLE-Algebraic Translation on a Limited Computer. Volume 2, Number 11, November 1959. pp 18-21).  Here is how Donald Knuth recollected this period in his April 2008 CACM interview:

I had learned about the Burroughs 205 machine language, and it was kind of appealing to me. So I made my own proposal to Burroughs. I said, "I'll write you an ALGOL compiler for $5,000. But I can't implement all of ALGOL for this; I am just one guy. Let's leave out procedures." Well, this is a big hole in the language! Burroughs said, "No, you've got to put in procedures." I said, "Okay, I will put in procedures, but you've got to pay me $5,500." That's what happened. They paid me $5,500, which was a fairly good salary in those days. So between graduating from Case and going to Caltech, I worked on this compiler. Heading out to California, I drove 100 miles each day and then sat in a motel and wrote code.

But he rejects "compiler writer" as a career, and decides what is important in life. Then a startup company came to me and said, "Don, write compilers for us and we will take care of finding computers to debug them. Name your price." I said, "Oh, okay, $100,000," assuming that this was [outrageous]. The guy didn't blink. He agreed. I didn't blink either. I said, "I'm not going to do it. I just thought that was an impossible number." At that point I made the decision in my life that I wasn't going to optimize my income.

I spent a day that summer looking at the mathematics of how fast linear probing works. I got lucky, and I solved the problem. I figured out some math, and I kept two or three sheets of paper with me and I typed it up. This became the genesis of my main research work, which developed not to be working on compilers, but to be working on the analysis of algorithms. It dawned on me that this was just one of many algorithms that would be important, and each one would lead to a fascinating mathematical problem. This was easily a good lifetime source of rich problems to work on.

Please note that $100,000 a year in 1960 is approximately $700K in 2011 (assuming on average 4% inflation.  It is not that easy to reject such an offer. Here Knuth really demonstrated that real scientists are not extinct and not everybody can be bought wholesale by a hedge fund. Like he said "I wasn't going to optimize my income."

Caltech Period

He began his doctoral studies in the fall of 1960 at the California Institute of Technology. On 24 June 1961 Knuth married Nancy Jill Carter who was one year younger (b. Jul-15, 1939).  Their two children John Martin Knuth and Jennifer Sierra Knuth were born in 1965 and 1966 respectively, two years before he finished his first volute of the Art of the computer Programming. That definitely created tremendous stress.

Due to a lucky incident he got an excellent thesis advisor (Marchall Hall) and managed to do his PhD very quickly, quickly enough not to lose the taste for research:

I got a listing from a guy at Princeton who had just computed 32 solutions to a problem that I had been looking at for a homework problem in my combinatorics class. I was riding up on the elevator with Olga Todd, one of our professors, and I said, "Mrs. Todd, I think I'm going to have a theorem in an hour. I am going to psyche out the rule that explains why there happen to be 32 of each kind." Sure enough, an hour later I had seen how to get from each solution on the first page to the solution on the second page. I showed this to Marshall Hall. He said, "Don, that's your thesis. Don't worry about this block design with =2 business. Write this up instead and get out of here." So that became my thesis. And it is a good thing, because since then only one more design with =2 has been discovered in the history of the world. I might still be working on my thesis if I had stuck to that problem. But I felt a little guilty that I had solved my Ph.D. problem in one hour, so I dressed it up with a few other chapters of stuff.

In 1962 the Addison-Wesley proposed that he write a book on compiler construction.  At this time it was a pioneering field, which was much more important that it is now. Indeed, all computer science research in those days was pretty can be classified as belonging to three major groups:

• Numerical analysis
• Artificial intelligence
• Programming languages and their compilers.

Knuth accepted the offer and it dramatically changed his life. The effort to write a book (which actually was never finished)  led to now famous "The Art of Computer Programming"  series which it definitely much more then a book on computer construction and related algorithms.  He began writing the book in the summer of 1962: one year before graduation and being married to his wife just four months. That writing soon completely consumed him and became the leitmotiv of his life, the unifying theme of the tremendous volume of work that he has done as a computer scientist and the first systematic introduction onto computer algorithms.

Althouth marriage experienced tremendous stress he managed to preserve it, another achievement which is not that common among top scientists. 

At the time there was no more or less general book on compiler construction. The whole field was pretty much "terra incognita" and only several algorithms useful in compiler construction were published. What is interesting that Knuth work managed to redefine the filed by publishing several groundbraking paers on the subject and first of all  the article On the translation of languages from left to right, Information and Control 8, 607-639 (1965) (scanned version is available from On the translation languages from left to right, Knuth, D.E.). Along with later important paper Top-down syntax analysis (1971) it was later republished in book Selected Papers on Computer Languages

I think that the first good "how to" books on compiler constructions appeared only 8 years later, in 1970:

• A Compiler Generator by William M. McKeeman was published by Prentice Hall in June 1970.  It defined the language XPL which was a derivative of Pl/1 modified for compiler writing and system programming (with dynamic allocation and garbage collection for strings) and desribed the compiler from this language for System 360 with full listings (open source). The compiler is writeen in XPL and as such was quite portable. 
• "Compiler Construction for Digital Computers " was written by David Gries in late 60th and published only in 1971 (David Gries is mostly known for his role in creating famous Cornell PL/C compiler from a subset of PL/1; He later fall under influence of Edsger W. Dijkstra  and was lost to compiler construction area ;-)

Around this time Knuth found a friend in other programming maverick Robert Floyd, who made important early contributions to the field of syntactic analyses and syntax parser writing, inventing so called Floyd-Evans production language -- a flexible notation for writing syntax analyzers that can be either directly interpreted or compiled into any high-level language.  Here is a quote about him from Wikipedia:

Born in New York, Floyd finished school at age 14. At the University of Chicago, he received a Bachelor's degree in liberal arts in 1953 (when still only 17) and a second Bachelor's degree in physics in 1958.

Floyd became a staff member of the Armour Research Foundation (now IIT Research Institute) at Illinois Institute of Technology in the 1950s. Becoming a computer operator in the early 1960s, he began publishing many noteworthy papers and was appointed an associate professor at Carnegie Mellon University by the time he was 27 and became a full professor at Stanford University six years later. He obtained this position without a Ph.D.

He received the Turing Award in 1978 "for having a clear influence on methodologies for the creation of efficient and reliable software, and for helping to found the following important subfields of computer science: the theory of parsing, the semantics of programming languages, automatic program verification, automatic program synthesis, and analysis of algorithms".

Floyd worked closely with Donald Knuth, in particular as the major reviewer for Knuth's seminal book The Art of Computer Programming, and is the person most cited in that work. He was the co-author, with Richard Beigel, of the textbook The Language of Machines: an Introduction to Computability and Formal Languages (1994, W.H. Freeman and Company, ISBN 978-0716782667).

As Knuth recollected later he first encounter with Robert Floyd writings as an editor of Communications of the ACM, when he was assigned to review his paper in which famous Floyd-Evans production language (in which syntax analysis part of several early compilers was written) was introduced:

My first encounter with Floyd’s work goes back to 1962, when I was asked by Computing Reviews to assess his article “A descriptive language for symbol manipulation” [Journal of the Association for Computing Machinery 8 (1961), 579-584]. At that time I was studying mathematics as a second-year grad student at Caltech; he was working as a programmer-analyst at Armour Research Foundation in Chicago.

Since I had recently completed a compiler for a subset of ALGOL, and had read the writeups and source listings of several other compilers, I was immediately impressed by what he had written [see Computing Reviews 3 (1962), 148, review #2140]:

 “This paper is a significant step forward in the field of automatic programming. Over the past few years, simple algorithms for analyzing arithmetic expressions have been discovered independently by many people. But conventional methods for explaining such algorithms obscured the essential facts. Floyd has developed a new notation which lets the trees be distinguished from the forest, and which admirably points out what is really going on in a translation process. An algebraic compiler can be described very precisely and compactly in this notation, and one can design such a compiler in Floyd’s form in a few hours.”

In essence, Bob had introduced the notion of productions as an organizing principle for programming, anticipating to a certain extent the future development of so-called expert systems.

... ... ...

Bob became an Associate Professor of Computer Science at the Carnegie Institute of Technology in the fall of 1965, introducing among other things a course on “the great algorithms,” and supervising the Ph.D. theses of Zohar Manna (1968), Jay Earley (1968), and Jim King (1969).

Floyd influenced Knuth approach to programming making is more mathematical then it used to be (sometimes I think whether this was should be classified as an achievement or as a fault ;-). He also contributed to the creation of established framework of writing computers and several early algorithms.

At the end of 1964 I had nearly finished drafting Chapter 10 of TAOCP, the chapter on syntax analysis, and I wrote Bob a long letter attempting to explain a general approach that had emerged from this work (now known as LR(k) parsing). “I must apologize for the complexity of my construction (indeed, it is too complicated to put in my book), but this seems to be inherent in the problem. I know of at least three Ph.D. theses which were entirely concerned with only the most simple cases of parts of this problem! As I go further into chapter 10 I become more convinced that only five really worthwhile papers on scanning techniques have ever been written, and you were the author of all five of them!”

Floyd also influenced the first three volumes of TAoCP as  pre-publication reviewer.

Meanwhile my publishers and I had asked Bob for a detailed critique of TAOCP Volume 1, which was being prepared for the press in 1967. Needless to say, his comments proved to be invaluable to me, although I didn’t agree with every single one of his remarks. Here are some excerpts from what he wrote:

:“Chapter I: Overall opinion. I like the chapter, but I think it could be improved by chopping most of the humor and anecdotes, retaining the historical material. ... The system of rating problems underestimates their difficulty for, say, college seniors, and designates too many with the ‘►’.

The author’s personal notes of advice, etc., are often valuable; at times, though, the non-technical material gets a little thick. The technical content meets very high standards of scholarship, and is a credit to the author.”

Then he gave hundreds of detailed suggestions for improvements to the text.

Floyd was the person cited more than anyone else in the book. He might contributed to  influenced Knuth's perfectionists desire to accommodate vast variety of key algorithms into the book and huge overload connected with this Herculean task.

Floyd was also of the first advocates of refactoring -- the rewriting of working programs by clarifying and simplifying their logic. Refactoring is now standard practice among computer programmers but at the time of writing TAoCP it was not that common. By polishing his small programs to perfection in TAoCP  Knuth can be also claimed to be one of pioneers of refactoring, but he goals were wider and more noble: he aimed to improve not only programs but first of all programmers understanding of underlying algorithms.

Cal Tech awarded Knuth a doctorate in mathematics in June 1963 for his thesis Finite semifields and projective planes. In other words Donald Knuth became Ph.D at the age of 25.

He then joined the faculty as an assistant professor. He also remained a software development consultant to the Burroughs Corporation in Pasadena, California.  He taught at the Cal Tech from 1962 until 1968 and work on the first volute of this famous The Art of Computer Programming was done in Cal Tech.  Throughout this period he continued to be involved with software development, serving as consultant to Burroughs Corporation from 1960-1968 and as editor of Programming Languages for ACM publications from 1964-1967. His publications from this period show remarkable diversity of his interests. For example he computed Euler's constant to 1271 decimal places and published the result in 1962.

But the main work was writing the Art of Computer Programming.  It actually formed Knuth as a scientist and served as a unifying theme of his life. As I already noted, paradoxically this book  started as a book on compiler writing: the goal he never managed to accompish. Here is how it happened in his own words: 

A man from Addison-Wesley came to visit me and said "Don, we would like you to write a book about how to write compilers." I thought about it and decided "Yes, I've got this book inside of me." That day I sketched out — I still have that sheet of tablet paper — 12 chapters that I thought should be in such a book.

I told my new wife, Jill, "I think I'm going to write a book." Well, we had just four months of bliss, because the rest of our marriage has all been devoted to this book. We still have had happiness, but really, I wake up every morning and I still haven't finished the book. So I try to organize the rest of my life around this, as one main unifying theme.

Along with other work and responsibilities of a husband and father of two small children this writing created huge load and in May 1967 Donald Knuth has a massive bleeding ulcer and was hospitalized. I think that at the time ulcer drags were still unknown and surgery was the only option, but I might be mistaken (BTW ulcer drag became the first "blockbuster" drag and lead to deterioration (aka corruption) of the whole US pharmaceutical industry).

A this point he resigned from his consultancy position with the Burroughs Corporation, multiple positions in editorial board of ACM journals. He resigned from most editorial boards to cut his workload and be able to concentrate on the book which he already considered to the primary goal of his professional life.  

The first volume of The Art of Computer Programming was published in 1968 and instantly became classic. Please note that at this point Donald Knuth was just 30 years old.  But at the same time he was an "old hand", a programmer with 12 years of experience; few have this level of experience those days.

Knuth held the position at Caltech until 1968 but was thinking about finding "permanent home" where he can spend the rest of his life productively working.  On 22 February 1967 he wrote to Bob Floyd:

 “Bob, I have the feeling that this is going to be a somewhat extraordinary letter. During the last year or so I have been getting lots of offers of employment from other colleges. I think I told you that I plan (and have planned for a long time) to decide on a permanent home where I will want to live the rest of my life, and to move there after the year I spend in Princeton working for the government. (Namely, to move in September 1969.)

Due to the present supply and demand in computer science, I am fortunate enough to be able to pick just about any place I want to go; but there are several good places and it’s quite a dilemma to decide what I should do. I believe the four places that are now uppermost in my mind are Stanford, Cornell, Harvard, and Caltech (in that order). I expect to take about a year before I make up my mind, with Jill’s help.

It occurs to me that I would very much like to be located at the same place you are, if this is feasible; at any rate your plans have a non-trivial place in the non-linear function I am trying to optimize! ... So I would like to explore some of these possibilities with you. ...”

Bob responded with his own perspective on the current state of affairs at various universities; the bottom line of his reply was, “I’d say if you want to make the move, I don’t have any plans that would conflict, and I will be very tempted to go to Stanford myself; I probably will go, in fact.”

Stanford Period

The next five years (1968-1973) were the most productive in Donald Knuth life. The same year as the first volume of TAoCP was published (1968) Knuth joined the faculty at Stanford University as a tenured Professor.  Actually publishing TAoCP instantly make him a national start and as such very suitable to Ivy League schools position. As he recollected:

In February of 1968 I finally got the offer from Stanford. The committees were saying, "This guy is just 30 years old." But when they looked at the book, they said, "Oh, there's some credibility here." That helped me.

After he joined a position of professor at Stanford University he for some time, I think, was a chair of computer science department there.  He invited  Robert Floyd and lobbied for a professor position for Floyd, who actually did not have Ph.D. (or more correctly never gone through the formalities of obtaining a Ph.D. degree.)

In 1969 the first edition of the second volume of TAoCP was published, just one year after the first volume.

Knuth spent the academic year 1972-73 at the University of Oslo and this visit was influential for the further development of Computer Science in Norway.

In 1973 the third and, so far, the last compete volume of TAoCP was published. This volume was influenced by Floyd course "Sorting and Searching." which he taught at Stanford. In particular the presentation  of “heapsort” algorithm of J. W. J. Williams was influenced by Floyd.

In 1974 ACM presented Donald Knuth with the Turing Award, formally the most prestigious award for computer scientists. Some consider it to be highest honor in Computer Science similar to a Nobel Price for physicists, but I respectfully disagree. Here is ACM A.M. Turing Award citation

For his major contributions to the analysis of algorithms and the design of programming languages, and in particular for his contributions to the "art of computer programming" through his well-known books in a continuous series by this title.

Unfortunately his very interesting Turing lecture (Donald E. Knuth: Computer Programming as an Art. CACM 17(12): 667-673, 1974) is not available online. Those who are interested can get it along with his another ground-breaking paper Structured Programming with goto Statements [1974] in the book  Literate Programming.  BTW the article Structured Programming with goto Statements is available online[PDF]. Here are some quote from Wikiqpote

1974 Turing Award Lecture[1], Communications of the ACM 17 (12), (December 1974), pp. 667–673

• Science is knowledge which we understand so well that we can teach it to a computer; and if we don't fully understand something, it is an art to deal with it.
  • p. 668

• We should continually be striving to transform every art into a science: in the process, we advance the art.
  • p. 669 [italics in source]

• Premature optimization is the root of all evil (or at least most of it) in programming.
  • p. 671
  • Premature optimization is the root of all evil.
    • Variant in Knuth, "Structured Programming with Goto Statements". Computing Surveys 6:4 (December 1974), pp. 261–301, §1.

• Computer programming is an art, because it applies accumulated knowledge to the world, because it requires skill and ingenuity, and especially because it produces objects of beauty. A programmer who subconsciously views himself as an artist will enjoy what he does and will do it better.

He was appointed Fletcher Jones Professor of Computer Science in 1977 and in 1990 he was named Professor of The Art of Computer Programming.

During Stanford  period he made a substantial contributions to the theory of algorithms and his research papers have been instrumental in establishing several important branches of computer science including but not limited to the analysis of algorithms, LR(k) and LL(k) parsing, attribute grammars, empirical study of programming languages, and literate programming. His best-known research in mathematics is represented by the Knuth-Bendix algorithm for word problems (axiomatic reasoning), the Schensted-Knuth correspondence between matrices and tableaux, and an analysis of the big bang that occurs in the evolution of random graphs. In general, his works has been always  directed towards the search for a proper balance between theory and practice.

In 1977 Knuth abruptly shifted his career from writing next volume of the Art of Programming to writing a complex and very successful  typography system TeX and METAFOND. It took him long ten years to finish the TeX system for document preparation and the MF (MetaFont) system for alphabet design. Noteworthy byproducts of those activities were the WEB and CWEB languages for structured documentation, and the accompanying methodology of Literate Programming. One can think about literary programming approach as a hypertext  merge of program code and computer documentation that is produced with an explicit idea of explaining the program to a good competent programmer.

This approach proved to be a very successful in writing TeX, but this new paradigm of software development never found widespread use. As he explained in his interview to Computer Literacy (now Fatbrain.com):

You think of yourself as writing for a human being, explaining to a human being what a computer should do, instead of thinking of yourself as talking to the computer telling it what to do. You get your act together better when you're explaining it to another person. This approach helps even for a program that you're going to throw away after an hour. CWEB is a tool that I recommend using even if you're writing a program only for yourself, for your eyes only.
...

You can create the parts in whatever order is psychologically best for you. Sometimes you can create them from the bottom up. Bottom-up means that you know somehow that you probably need a subroutine that will do something, so you write it now while you're ready, while you're psyched for it. With this bottom- up programming, your pencil gets more powerful every page, because on page nine you've developed more tools that you can use on page ten... your pencil is stronger.

With top-down programming you start at the beginning and say "I'm going to do this first and then this, and then this"... but then you have to spell out what those are--- you can wind up gasping for breath a hundred pages later when you finally figure out how you're actually going to do those things!

Top-down programming tends to look very nice for the first few pages and then it becomes a little hard to keep the threads going. Bottom-up programming also tends to look nice for a while, your pencil is more powerful, but that means you can also do more tricky stuff. If you mix the two in a good psychological way, then it works, even at the end.

I did this with TeX, a very large program: 500+ pages of code in the book . Throughout that entire program, all those lines of code, there was always one thing that had to be the next thing I did. I didn't really have much choice; each step was based on what I'd done so far. No methodology would teach me how to write a piece of software like that, if I followed it rigorously. But if I imagined myself explaining the program to a good competent programmer, all that this long program was, then there was just this one natural way to do it. The order in which the code appears in the book is the order in which I wrote it.

TeX is now used to produce most of the world's scientific literature in physics and mathematics. This one of the first large scale successful open source projects and for this contribution Knuth is considered to be a progeny of free/open source programming movement. As he mentioned in his Advocado interview [Knuth1990]:

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

There were people who saw that there was a need for such software, but each one thought that they were going to lock everyone into their system. And pretty much there would be no progress. They wouldn't explain to people what they were doing. They would have people using their thing; they couldn't switch to another, and they couldn't get another person to do the typesetting for them. The fonts would be only available for one, and so on.

But I was thinking about FORTRAN actually, the situation in programming in the '50s, when IBM didn't make FORTRAN an IBM-only thing. So it became a lingua franca. It was implemented on all different machines. And I figured this was such a new subject that whatever I came up with probably wouldn't be the best possible solution. It would be more like FORTRAN, which was the first fairly good solution [chuckle]. But it would be better if it was available to everybody than if there were all kinds of things that people were keeping only on one machine.

So that was part of the thinking. But partly that if I hadn't already been successful with my books, and this was my big thing, I probably would not have said, "well, let's give it away." But since I was doing it really for the love it and I didn't have a stake in it where I needed it, I was much more concerned with the idea that it should be usable by everybody. It's partly also that I come out of traditional mathematics where we prove things, but we don't charge people for using what we prove.

In 1979, at age forty-one, he was awarded the National Medal of Science by President Jimmy Carter for the first three volumes of the "Art of Computer Programming". He became a Fellow of the British Computer Society in 1980, and an Honorary Member of the IEEE in 1982.

In spring 1986 he published five volume Computers and Typesetting, another monumental piece of work of lasting value.  But that work distracted him from more important work on The Art of Computer Programming and no new volume was published after the third volume was published in 1973.

Self-exile in order to finish the TAOCP

On Jan 1 1990 Donald Knuth discontinued using email because of the level of noise. From this point of view he can be called one of the first registered victims of spam ;-). Later he explained his frustration with junk e-mail in the following way:

I spent fifteen years using electronic mail on the ARPANET and the Internet. Then, in January 1990, I stopped, because it was taking up too much of my time to sift through garbage. I don't have an email address. People trying to write me unsolicited email messages get a polite note saying "Professor Knuth has discontinued reading electronic mail; you can write to him at such and such an address."

Email is wonderful for some people, absolutely necessary for their job, and they can do their work better. I like to say that for people whose role is to be on top of things, electronic mail is great. But my role is to be on the bottom of things. I look at ideas and think about them carefully and try to write them up... I move slowly through things that people have done and try to organize the material. But I don't know what is happening this month.

So now I don't read electronic mail, but I do use it occasionally.

In 1993 he became Professor Emeritus at Stanford University, resigned from the faculty to devote himself to the finishing TAOCP.  This is probably the last attempt of a single person to cover all major areas of computer science. He continue to live on the Stanford University Campus with his wife Jill and their two children John and Jennifer.  Unofficially, he retired in 1990, on the same day he gave up email. He explained his move in the following way:

...I had looked ahead and seen that it would take twenty years of work, full-time. If I continued doing everything else that I was doing, it was going to be forty or fifty years of work. I was just not getting anywhere, I was getting further and further behind. So I said, "Enough." Naturally, I hate to give up many of these other things that I like doing very much. But there are some things I didn't hate giving up, like writing proposals. I'm very happy to give up those!

... as a professor, in order to have decent equipment for my grad students, or to have visitors for active research programs, to publish reports, etc., I needed to find sponsors. It's a lot of work begging for money. The System Development Foundation said they'd give me a million dollars so that I could finish TeX and get back to The Art of Computer Programming.

...still [it] took many, many years to finish TeX. I decided that the only way I would be able to finish The Art of Computer Programming is by going into full-time writing, and being a hermit, and telling people "No." It was hard to adjust the first couple of years. Now I feel real efficient, and the writing is going well. A nice steady state.

In 1994 Robert Floyd retired from Snadford due to rare ailment known as Pick's disease, a neurodegenerative illness that gradually began to affect his mind and his body. As Knuth noted:

Still since his retirement, Knuth gives seven to eight lectures annually under the title of “Computer Musings.” In essence this is half-lectures/half reports about his work on current problems connected with writing The Art of Computer Programming:

I give lectures at Stanford every month or so, when I'm in town, called "Computer Musings" . I plan to keep this up for twenty years, to give a talk on whatever I find interesting that month, on neat ideas I've picked up... I bring up problems that I can't solve, so that somebody will do it for me. Now, if I can't solve a problem in two hours, I've got to give it up and tell somebody else to work on it; otherwise, I'll get behind again. As I write the book, I've got to move from topic to topic, and my attention span is maybe three weeks on any particular topic.

Some of those lectures are available on the Internet.

In 1996 he was awarded Kyoto Prize  for lifetime achievement in the arts and sciences, Japan’s equivalent of the Nobel Prize and the country’s highest private award for lifetime achievement. The Kyoto Prize is awarded each year in three categories: advanced technology, basic sciences and creative arts. Knuth won in advanced technology.  The "Advanced Technology" prize is approximately $460,000, along with a certificate and a gold medal. “This is just a dream and I’ll have to wake up to see who really won the prize,” Knuth said. He and his wife have decided to donate the money to charity.

Personality-wise Knuth is known for being kind and humble person. By virtue of being near him, you feel you are smarter and a better person. The greatness of his achievements is inversely proportional to his willingness to admit them. He’s made it clear that he considers himself less of an innovator than a cataloguer.  At the same time he is one of few computer scientists, who has an award in his name while still alive -- The Knuth Prize:

The Donald E. Knuth prize for outstanding contributions to the foundations of computer science is awarded every 1.5 years by the ACM Special Interest Group on Algorithms and Computing Theory (SIGACT) and the IEEE Technical Committee on the Mathematical Foundations of Computing. The Prize includes a $5000 award and a $1000 travel stipend (for travel to the award ceremony) paid by ACM SIGACT and IEEE TCMFC. The Prize is awarded for major research accomplishments and contributions to the foundations of computer science over an extended period of time. The first Knuth Prize was presented at the 1996 ACM Symposium on Theory of Computing (STOC). Future prizes will be awarded alternately at the ACM STOC and the IEEE Conference on Foundations of Computer Science (FOCS).

The Prize is named in honor and recognition of the extraordinary accomplishments of Prof. Donald Knuth, Emeritus at Stanford University. Prof. Knuth is best known for his ongoing multivolume series, The Art of Computer Programming, which played a critical role in establishing and defining Computer Science as a rigorous, intellectual discipline. Prof. Knuth has also made fundamental contributions to the subfields of analysis of algorithms, compilers, string matching, term rewriting systems, literate programming, and typography. His TeX and MF systems are widely accepted as standards for electronic typesetting. Prof. Knuth's work is distinguished by its integration of theoretical analyses and practical real-world concerns. In his work, theory and practice are not separate components of Computer Science, but rather he shows them to be inexorably linked branches of the same whole.

The Knuth Prize winner is selected by a Prize Committee consisting of 6 individuals selected by the SIGACT and TCMFC Chairs.

In selecting the Knuth Prize winner, the Committee will place particular attention on a sustained record of high-impact, seminal contributions to the foundations of computer science. The selection can also be partly based on educational accomplishments and contributions such as fundamental textbooks and high-quality students. The award is not based on service work for the community, although service might be included in the citation for a winner if it is appropriate.

Nominations for the prize will be considered by the Committee, but are not required in order to receive the Prize. All nominations should be sent to the Chair of the Prize Committee.

Past Winners

• 1999: László Lovász    
• 1997: Leslie M. Valiant
• 1996: Andrew C.-C. Yao

Funny enough he was nominated for the 2nd Annual Free Software Foundation Awards and lost to Miguel de Icaza, the guy who has tremendous difficulties in replicating Norton Commander and was never able fully grasp the concepts beyond this John Socha's masterpiece. 

After reading about this event on Slashdot,  I begin to suspect that Richard Stallman and his pet The Free Software Foundation completely had lost contact with reality and became more like a variation of an second-rate leftist party or, if you wish, an obscure cult :-(.  As one Slashdot reader pointed out:

Why not Knuth?
by the_tsi ([email protected]) on Tuesday December 14, @07:01PM EST (#21)
(User Info)

I recognize that Gnome is an important step for linux (err.. unices in general) to move towards the desktop, but it certainly isn't ``core functionality'' that I need my computers to do. I mean, there are parallel technologies which allow similar things.

TeX on the other hand, has been around for a long time and is used non-stop in the lab where I work. Without it, the reports we dump out would probably take forever to make. I can't imagine using Word (or any word processor for that matter) to create documents that change as much in revision as ours do. TeX is a much more earth-shattering development than a spiffy new interface to X.

I think the FSF awards copped out and picked based on ``current and trendy'' instead of deserving of an award. Of course, if there is a monetary award involved (since there's no article, I can't tell, but I imagine there is), then I can see the politics behind it. Gnome sure needs cash more than any TeX-related project.

Congrats to the nominees and the winner.

-Chris

Currently Donald Knuth is still writing Volume 4 of  The Art of Computer programming. Due to deficiencies of earlier MIX computer he changed the computer (creating MMIX, a new CPU architecture that replaced outdated MIX) and published its description in 2005:

The Art of Computer Programming, Volume 1, Fascicle 1: MMIX -- A RISC Computer for the New Millennium by Donald E. Knuth (Paperback - Feb 24, 2005)

Around this time several preprints of new chapter were also published in 2005 (along with the description of MMIX, a new CPU architecture that replaced outdated MIX).

Final version of several parts of Volume 4 were published in 2010 as The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1.  But the situation changed dramatically. While first volumes were published when computer science and programming in general when quickly developing and new discipline, this volume was published when programming was far past its peak as a specialty and in USA was severely damaged by outsourcing. They never generated the same interest as his first volumes.

It is interesting to note that he writes his programs first in pencil and that he usually works with computer standing [STANFORD Magazine May-June 2006 ]

Most nights you can find him in his upstairs study, a cozy room lined with so many books and papers that he relies on a computerized index to tell him what goes where. Although he stands to work at his computers, Knuth writes longhand, reclining beneath the amber lamplight in a Dux chaise lounge whose upholstery is in its third incarnation and whose powers of comfort he deems “magical.”

Initially Knuth expected that he might manage to finish the volume 4 in 2008, but like with first volumes the scope of the work increased to the extent when it needed to be published in separate parts.

In 2011 Knuth is 73 years old and the task of writing became more and more difficult.. Knuth understand the size of the task and is somewhat skeptical himself:

Volume Four is about combinatorial algorithms. Combinatorial algorithms were such a small topic in 1962, when I made that Chapter Seven of my outline, that Johan Dahl asked me, "How did you ever think of putting in a chapter about combinatorial algorithms in 1962?" I said, "Well, the only reason was that it was the part I thought was most fun." But there was almost nothing known about it at the time.

The way I look at it, this is where you've got to use some art. You've got to be really skillful, because one good idea can save you six orders of magnitude and make your program run a million times faster. People are coming up with these ideas all the time. For me, the combinatorial explosion was the explosion of research in combinatorics. Not the problems exploding, but the ideas were exploding. There's that much more to cover now.

It's true that in the back of my mind I was scared stiff that I can't write Volume Four anymore. So maybe I was waiting for it to simmer down. Somebody did say to me once, after I solved the problem of typesetting, maybe I would start to look at binding or something, because I had to have some other reason [to delay]. I've certainly seen enough graduate student procrastinators in my life. Maybe I was in denial.

He estimate that it might take another twenty years to write the remaining five volumes. Let's hope that he will manage to finish them all. Actually the gap between the third and the forth volume is such that he can get to Guinness Book of Records ;-). Anyway Knuth is still hopeful about finishing five volumes but wonders how long computer science, which is, after all, a man-made field of study, will continue to provide challenging problems that aren’t too esoteric or derivative [STANFORD Magazine May-June 2006]:

“We’re nowhere near the limits of interesting things to do—we’re getting more every year than we had the previous year,” he says, yet muses, “How can we predict that that’s going to continue, that we aren’t going to have some kind of closure?”

But he’s also very hopeful about the field’s future—computers are more powerful than ever, and the kind of cross-disciplinary cooperation he enjoyed with artists during his typography days is increasingly common. Just as he showed mathematicians that computer science would give them new room to explore, he hopes scholars from other fields will infuse computer science with fresh ideas. “The scientific world of the future will be pairs, or connections,” he says. “Everybody is going to be a bridge between specialties.” Fascinated by interdisciplinary overlap, Knuth is researching a book on how people computed before computers, finding the roots of binary thinking in places like the I Ching and ancient Greek poetry.

In retirement, he still writes several programs a week. He no longer advises students, but he hosts free public Computer Musings talks several times a year, drops in on graduate-level courses occasionally, and bikes to campus most days of the week to use the libraries or swim at the aquatic center. He famously regards e-mail as a time sink and no longer reads it—except for correspondence (printed out by a department secretary) relating to errata or his current work. His primary agenda item is, after all, Volume 4, although every few months he’ll browse journals for items to squirrel away for Volumes 5 through 7. People inquire delicately about how he expects to complete a seven-volume project at his current pace, and Knuth concedes he’ll be content to finish the first five.

Those are the core of his series, he says, and the last two are more specialized topics. “If I get to the end of Number 5 and I see nobody’s yet written what I want to say about Number 6, I’ll continue.” Despite the enormous changes in computer technology since he began his series, the English editions of each of the first three books still sell about 3,000 copies annually. The books have been translated into 10 languages, with more on the way.

Those around him also seem unfazed by the enormousness of his task, including his extraordinarily patient editor (“When I actually present him with something, he’s surprised,” says Knuth) and Jill, who recently tried to urge deadline compliance with the help of stickers on a chart. She gave up when her husband overshot every goal. “Because he is a perfectionist, he is often tempted to go off on a sidetrack,” she says. “The whole typeface thing was one of those branches, and that’s been beneficial to a lot of people. Nobody can say he shouldn’t have done it.”

For a guy who’s devoted to exploring, this is fitting. “The journey is more important than the destination—that’s part of life,” he says. “If you only live for getting to the end, you’re almost always disappointed.” Perhaps, he adds, what seems like a liability is really a stroke of luck. “If I had been good at making estimates of how long something was going to take, I never would have started.”

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