) are due to arrive in November.
It is Knuth's philosophical approach that preserves his work so well. He
does not prescribe to the latest trend in programming languages. Instead, he expounds the fundamental flow of programming algorithms, the essential architecture of data structures, and the basic mechanisms of stacks and queues, using, as he puts it, "English as my high-level language." This approach cannot fairly be dubbed "generic." Given the clarity and specificity of Knuth's models, these constructs can be directly applied to a broad range of languages, OSes, and hardware architectures.
Typically, Knuth first describes an algorithm or structure in general terms. He sets up the discussion with tables, flow diagrams, and other graphical aids. For instance, when opening the section on information structures, Knuth covers important terms and notations by describing a simple algorithm involving playing cards. The sample data structure includes fields for TAG, SUIT, RANK, NEXT, and TITLE -- the fields required for the data record. He then displays the actual cards next to a computer representation of the
data records. Next, a figure shows record structures along with arrows that depict how the records are linked. An algorithm for turning over a new card is presented step-by-step, accompanied in parentheses by relevant comments, as shown below.
A1. Set NEXT(NEWCARD) to TOP. (This puts the appropriate link
into the new card node.)
A2. Set TOP to NEWCARD. (This keeps TOP pointing to the top
of the pile.)
A3. Set TAG(TOP) to 0. (This marks the card as "face up.")
Finally, Knuth uses low-level assembly language for the routine, listing each command with comments. This meticulous, thorough methodology proceeds from a general description to a specific implementation, so you understand the flow logic, the data architecture, and the practical implications of the algorithm. The bulk of the first volume covers information structures, including stacks, queues, binary trees, and dynamic storage.
In his update, Knuth incorporates his o
wn handwritten notes and adds hundreds of new exercises and solutions, focusing on subjects that have "converged" over the years. In some cases, Knuth concedes that a subject is evolving too rapidly to pin down. And in one notable passage, Knuth admits that his MIX system, a mythical computer that he uses to elucidate his models, is "now quite obsolete" -- for example, MIX has no OS; it bootstraps from tape. He plans to replace MIX with a 64-bit RISC computer, the MMIX 2009, but he has delayed converting the programs in Volumes 1 through 3 until after next year (and the completion of Volumes 4 and 5).
This is no casual read. But it is
the
essential reference for the serious computer scientist and anyone who wants to understand computer structures and programmatic flows. If you want a deep understanding of buffer-allocation or garbage-collection routines, along with alternative approaches and efficiency analysis, consult your Knuths.
Stan Diehl is a frequent contributor to BYTE a
nd former director of BYTE reviews. You can reach him at
sdiehl@nebs.com
.
Book Review: The Bible, Updated
