In the beginning Donald Ervin Knuth imagined a mythical computer and a symbolic language. Now the computer was a formless void; there was darkness over the deep, with a divine wind sweeping over the machine.
Knuth said, ‘Let Algorithm E be Euclid's algorithm,’ and it was “Euclid's algorithm,” a process for finding the greatest common divisor of two numbers. Knuth saw that there are algorithms and there are good algorithms.1 And Knuth separated an algorithm from the act of performing one. Knuth called the meaning of algorithm quite similar to that of recipe, process, method, technique, procedure, routine, except that ‘algorithm’ connotes something just a little different. Knuth said that an algorithm has five important features:
- Finiteness. An algorithm must always terminate after a finite number of steps. A procedures which has all of the characteristics of an algorithm except that it possibly does not terminate is called a “computational method.”
- Definiteness. Formally defined programming languages or computer languages are designed for specifying algorithms precisely. An expression of a computational method in a computer language is called a program.
- Input. An algorithm has zero or more inputs.
- Output. An algorithm has one or more outputs.
- Effectiveness. All of the operations to be performed in the algorithm must be sufficiently basic that they can in principle be done exactly and in a finite length of time by a person using pencil and paper.
Knuth said, ‘Let there be an investigation of the mathematical notations which are used throughout the rest of the chapters.’ And so there was. Knuth presented the investigation, and the investigation divided the section on algorithms from the section on the machine. Knuth called out two main purposes for the use of mathematical notation in The Art of Computer Programming: (1) to describe portions of an algorithm; and (2) to analyze the performance characteristics of an algorithm. Evening came and morning came: section 1.2.
Knuth said, ‘Let the algorithms under heaven come together, and let my mythical machine appear.’ And so it did. Knuth called the world's first polyunsaturated computer ‘MIX’ and gave it an identifying number—the 1009. And Knuth began to amass MIXAL (“MIX Assembly Language”) programs. Knuth saw that MIX was very much like nearly every other computer then in existence, except that it was, perhaps, nicer. Knuth designed the language of MIX to be powerful enough to allow brief programs to be written for most algorithms, yet simple enough so that its operations are easily learned.
Knuth said, ‘Let MIX interpret words as instructions: register-altering, output-producing operations that may form programs bearing other programs, each corresponding to its own species.’ And so it was. Machines produced output, including various kinds of instruction-bearing output, each corresponding to its own species. Knuth saw that it was good. Evening came and morning came: section 1.3 in a nutshell.
Knuth said, ‘Let there be subroutines, and coroutines, and interpretive routines, and put the coding (called a “subroutine”) of a certain task to be performed at different places in a program into one place instead of repeating the coding in each place.’ Knuth presented two great nouns: “input” and “output”. Knuth explained that inputting is often called reading and outputting is, similarly, called writing. One governs data going into a program and the other governs data coming out. Knuth provided a History and Bibliography and called it good: section 1.4.
Knuth said, “The present chapter summarizes the most important facts about information structures: the static and dynamic properties of different kinds of structure; means for storage allocation and representation of structured data; and efficient algorithms for creating, altering, accessing, and destroying structural information.” And so it does. Knuth described linear lists: stacks, queues, and deques; sequential allocation; linked allocation; circular lists, doubly linked lists; arrays and orthogonal lists. Knuth gave us trees, multilinked structures, dynamic storage allocation, another History and Bibliography. Knuth saw to it that it was good. Knuth blessed the reader with answers to exercises, saying, “Please use them wisely; do not turn to the answer until you have made a genuine effort to solve the problem by yourself, or unless you do not have time to work this particular problem. After getting your own solution or giving the problem a decent try, you may find the answer instructive and helpful.” Appendices and an index and glossary came and the next volume came: chapter 2, volume 1.
Knuth said, “The point of view I have adopted while writing these twelve chapters differs from that taken in many contemporary books about computer programming in that I am not trying to teach the reader how to use somebody else's subroutines; I am concerned rather with teaching the reader how to write better subroutines himself!”
Knuth taught programmers himself,He blessed them, saying to them, ‘Be fruitful; add, subtract, multiply, divide; program the machine and subdue it. Be masters of the algorithms in the sea, the mathematics in the heavens, and all the data that moves around.’ He also said, ‘Look, to you I give all the program bearing algorithms everywhere on the surface of digital computers, and all the programs; this is for your pleasure and your gain. And all the information structures, and all the mathematics in the heavens, and all the operations on the machine shall be ruled by logic.’ And so it was and is and shall be.
with his books he taught them,
male and female he taught them.
Knuth saw all that he had made, and indeed it was very good. Evening came and morning came: The Art of Computer Programming.
Alas, in spite of having actual computers to help him edit his material, Knuth is still working toward the ultimate editions of The Art of Computer Programming, the whole twelve-chapter array.
Meanwhile, in a parallel universe, Selected Papers on Fun & Games, the eighth and final volume of Knuth's collected papers was published c. 21114 C.D. by Standford's Center for the Study of Language and Information. Knuth had been saving it up for “dessert.” When he finished it, he said:
Now that this book is complete, I can't help but be overwhelmed by an enormous feeling of gratitude. I'm truly at a loss for words to describe the transcendental glow that fills me at this moment. What a miracle it has been, to have been able to live my life at a time and place in which it was possible to write a book such as this!
Congratulations. Now that you've made it to the end of this fly-by-night synopsis of the saga of The Art of Computer Programming, try to get your parents to purchase a copy of volume one and start reading it!
Banks, Oregon
c. 2355228762 kovacs C.D.
- All good algorithms are alike; each bad algorithm is bad in its own way. This leads to the extremely interesting and all-important field of algorithmic analysis.