Beginning

In the beginning I ahve created the type face and the Page.
And the paper was without format and woid. And blank-
ness was upon the face of the page. And the spirit of Mono-
type moved upon the face of the metals. And Isaac (Burch)
said, Let there be type: and there was type. And I ahve saw
the type, that it was good: And I ahve divided the type from
the margins. And I ahve called the type okay, and the marg-
gins I ahve called right. And the evenings and the mornings
were the first year.1
— BRUCE ROGERS, Pi (1953)

n THE BEGINNING, Donald Ervin Knuth outlined; he 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.2 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:

  1. Finiteness. An algorithm must always terminate after a very finite number of steps. A procedure which has all of the characteristics of an algorithm except that it possibly does not terminate is called a “computational method.”
  2. Definiteness. Each step of an algorithm must be precisely defined. 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.
  3. Input. An algorithm has zero or more inputs.
  4. Output. An algorithm has one or more outputs.
  5. 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 person3 using pencil and paper.
Knuth, not being one to build on shaky foundations, closed the section with a brief indication of a method—virtually the same method as that given by A. A. Markov in 1951, in his book The Theory of Algorithms—by which the concept “algorithm” can be firmly grounded in terms of mathematical set theory. Finally, Knuth provided the example of using Turing machines as yet another way to formulate the concept of an effective computational method. Evening came and morning came: section 1.1.

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,
with his books he taught them,
male and female he taught them.
He blessed them, saying to them, ‘Be fruitful: randomly mutate, add, subtract, multiply, and divide; confront the combinatorics; program the machine and subdue it; then return and reinvent 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.

Knuth saw all that he had made and has yet to make, and indeed it is very good. Evening came and morning came, The Art of Computer Programming, which i

  1. From the first draft of an accounting of the making of the new Oxford Bible, reproduced in “A NEW BRIBLE STORY (unAuthorized perVersion) The Last Book of Bruce’s, called JE NE SUIS” in Pi: A Hodege-Podge of Letters, Papers, Addresses, written during a period of 60 years.
  2. 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.
  3. Or man or woman or man or woman. Gender neutral nouns are usually not intended to distract the reader.