 |
|
This is the fifth in a series of eight volumes that contain archival forms of my published papers, together with new material. (The first book in the series was Literate Programming; the second was Selected Papers on Computer Science; the third was Digital Typography; the fourth was Selected Papers on Analysis of Algorithms.) The Computer Languages volume is characterized by the following remarks quoted from its preface.
This book is devoted to the topic that got me hooked on computers in the first place: the languages by which people are able to communicate with machines.
Rules of grammar have always fascinated me. In retrospect I think that the most exciting days of my elementary school education came during the seventh grade, when I was taught how to make diagrams of English-language sentences in order to see how the various parts of speech fit together. My friends and I would stay after class, trying to put more and more sentences into diagrammatic form---and getting totally confused by poetry, which seemed to break most of the rules.
During the summer of 1957, after I had just written my first computer programs for numerical problems like factoring numbers and for fun problems like playing tic-tac-toe, an amazing program called IT---the ``Internal Translator''---arrived at the Case Tech Computing Center, where I had been working as a college freshman. IT would look at a card that contained an algebraic equation, then the machine would flash its lights for a few seconds and go punch-punch-punch; out would come a deck of cards containing a machine-language program to compute the value of the equation. Mystified by the fact that a mere computer could understand algebra well enough to create its own programs, I got hold of the source code for IT and spent two weeks poring over the listing. Lo, the secrets were revealed, and several friends helped me in 1958 to extend IT even further.
Of course in those days we had only a vague notion of what we were doing; our work was almost totally disorganized, with very few principles to guide us. But researchers in linguistics were beginning to formulate rules of grammar that were considerably more mathematical than before. And people began to realize that such methods are highly relevant to the artificial languages that were becoming popular for computer programming, even though natural languages like English remained intractable.
I found the mathematical approach to grammar immediately appealing---so much so, in fact, that I must admit to taking a copy of Noam Chomsky's Syntactic Structures along with me on my honeymoon in 1961. During odd moments, while crossing the Atlantic in an ocean liner and while camping in Europe, I read that book rather thoroughly and tried to answer some basic theoretical questions. Here was a marvelous thing: a mathematical theory of language in which I could use a computer programmer's intuition! The mathematical, linguistic, and algorithmic parts of my life had previously been totally separate. During the ensuing years those three aspects became steadily more intertwined; and by the end of the 1960s I found myself a Professor of Computer Science at Stanford University, primarily because of work that I had done with respect to languages for computer programming.
... And then the preface continues by describing the various chapters, which can be summarized more succinctly by quoting from the hype on the back cover:
Two dozen of Knuth's classic papers on the subject are collected in this volume, brought up to date with supplementary material, and augmented by a previously unpublished essay on language design. Of particular interest are his fascinating and definitive survey of the twenty languages for programming that preceded FORTRAN I, along with three of his fundamental papers that each launched significant subfields of computer science: (1) The theories of LL(k) and LR(k) parsing; (2) attribute grammars to define the meaning of languages; (3) empirical studies of user programs and profile-based optimization. Every chapter is self-contained and accessible to computer programmers with varied backgrounds. Readers will be able to participate vicariously in the creation of the concepts that have now become thoroughly integrated into modern software systems.
Here's the table of contents:
(Numbers like P83 and Q11 in this list refer to the corresponding papers in my list of publications.)
This is a useful historical document, as much for the selection being made by Knuth, as for many of the papers being hard to find or just unobtainable. ... From an intellectual point of view, it is a pleasure to have ready access to the founding paper for the subject of LR(k) parsing and a paper that has a similar position with respect to attribute grammars. From an historical perspective, it is also a pleasure to explore the activity around the creation of Algol, its precursors and successors. ... Two chapters are of particular note among the rest. One is Chapter 24, presenting probably one of the earliest detailed performance studies. ... The other, Chapter 25, is relatively recent, was written for Ole-Johan Dahl's 70th birthday and is a delightful reminder of the elegance and effectiveness of the coroutine as a control abstraction. All in all, a nice addition to the library shelf and a useful source for those who wish to avoid re-inventing wheels. -- Julian Padget, Math Reviews (2004)
The reader will be able to see the early history and development of fundamental concepts that have now become thoroughly integrated into modern software systems. -- G. Grigas, Zentralblatt MATH 1046 (2004)
This book can be ordered from the publisher (CSLI), and also from the distributor (University of Chicago Press).
As usual, I promise to deposit 0x$1.00 ($2.56) to the account of the first person who finds and reports anything that remains technically, historically, typographically, or politically incorrect.
Here is a list of all nits that have been picked so far in the first printing (2003); an asterisk (*) marks technical errors that are not merely typographical:
- page xv, line 7 (25 Apr 2004)
- change "7," to "7"
- page xv, line 14 from the bottom (25 Apr 2004)
- change "general purpose" to "general-purpose"
- page xv, line 9 from the bottom (25 Apr 2004)
- change "EC--13" to "EC-13"
- page xvi, line 16 from the bottom (25 Apr 2004)
- change "flow charts" to "flowcharts"
- page xvi, line 2 from the bottom (03 June 2004)
- change "(2003). Copyright (c)2003" to "(2004), pp. 183--208. Copyright (c)2004"
- page 11, line 23 from the bottom (10 Apr 2011)
- change "$R_0$ is of type" to "the components of $R_0$ have type"
- page 22, line 10 from the bottom (27 Dec 2009)
- change "1,35" to "1, 35"
- page 24, line 2 from the bottom (27 Dec 2009)
- change "Zurich" to "Zürich"
- page 26, line 2 (04 Jan 2010)
- change "Sgn(x)" to "Sgn(x)"
- page 27, line 12 from the bottom (27 Dec 2009)
- change "i," to "i"
- page 27, line 11 from the bottom (27 Dec 2009)
- change the second "Op," to "Op"
- page 28, line 9 (29 May 2004)
- change "h," to "h"
- page 76, new entry for Table 1 following Brooker's AUTOCODE (06 February 2009)
- Transcode / Hume & Worsley / 1954 / F / A / D / D / C / C / C / Separate subroutine modules
- page 91, beginning of the Addendum (06 February 2009)
- Change "Another language ... this history." to: "Two other languages, Transcode and PACT I, deserve to be part of the story as well, so they appear in Table 1 above although they were unfortunately missed by the authors when we first compiled this history."
[Now include a 1.5-page detailed discussion of Transcode; this inserted material causes the index to change rather drastically, with many changes not documented below.]- original page 92, line 9 from the bottom (27 Dec 2009)
- change "Jr., and Bruce" to "Jr. and Bruce"
- page 115, lines 14 and 19 (29 May 2004)
- change "ALGOL" to "ALGOL"
- page 123, line 4 (16 Feb 2007)
- change "1964) 7" to "1964), 7"
- page 130, line 6 after Figure 1
- change "spaces; that" to "spaces; thus"
- page 200, line 1 (12 June 2004)
- change "Statement" to "Statements"
- page 212, line 16 (12 June 2004)
- change "4H" to "4H ." (the printer thought this period was a speck of dust and cleaned it off)
- page 218, line 12 (31 May 2005)
- change "according the" to "according to the"
- *page 250, line 2 (05 July 2004)
- change "$q_\infty$" to "$q_f, q_\infty$"
- page 266, line 17 from the bottom (05 July 2004)
- change "e)" to "e"
- *page 315, line 10 from the bottom (09 February 2008)
- change "{\sl if the following}" to "{\sl if $S\rightarrow^+S$ is false and if the following}"
- page 326, line 5 (05 July 2004)
- change "60," to "60,''"
- *page 329, line 10 (09 February 2008)
- add a new sentence: "We shall assume that `$S$' itself is not a sentential form."
- page 336, line 2 (09 February 2008)
- change "above" to "above, together with $S{\dashv}^k$"
- *page 337, line 2 from the bottom (09 February 2008)
- change "now equals" to "now contains"
- page 359, in reference [5] (02 August 2009)
- change "62--66" to "62--67"
- page 429, lines 12 and 13 from the bottom (05 May 2011)
- change "... my" to "About two weeks ago my", and change "five weeks" to "five days"
- page 505, bottom line (02 March 2010)
- change "89.]" to "89."
- page 536, line 4 (05 July 2004)
- change "4.8 2.7" to "4.6 2.6"
- page 536, line 8 (05 July 2004)
- change "9.0" to "8.6"
- page 536, line 9 (05 July 2004)
- change "2.0 2.1 5.4" to "2.1 2.1 5.3"
- page 536, line 15 (05 July 2004)
- change "1.1 1.1" to "1.2 1.1"
- page 536, line 17 (05 July 2004)
- change "1.6" to "1.7"
- page 536, line 18 (05 July 2004)
- change "1.1" to "1.2"
- page 537, line 11 from the bottom (31 May 2005)
- change "elevenfold" to "eleven-fold"
- page 545, line 16 (03 June 2004)
- change "2003)." to "2004), 183--208."
- page 579, left column (28 August 2003)
- change "Čulik" to "Čulík" (twice)
- page 579, right column, Dijkstra entry (28 Mar 2005)
- change "Wijbe" to "Wybe"
- page 580, left column, new entry (08 July 2005)
- Empty string, 300, 357, 367, 374.
- page 580, left column (11 November 2003)
- change "Elsworth, A. Kenton" to "Elsworth, Adolph Kenton"
- page 582, left column, Greibach entry (14 October 2009)
- change "Shiela" to "Sheila"
- page 582, right column, Haynam entry (16 October 2009)
- change "E." to "Elmer"
- page 582, right column, new entry (06 February 2009)
- Hume, James Nairn Patterson, 76, 91--92.
- page 584, the entry for Knuth, Donald (02 August 2009)
- change "xvi" to "xiv"
- page 585, right column (08 August 2012)
- change "Luke, Richard C." to "Luke, Richard Carlen"
- page 586, left column (08 February 2008)
- change "Metropolis, Nicolas" to "Metropolis, Nicholas"
- page 588, right column (15 August 2003)
- change "Price, Alan G." to "Price, Alan George"
- page 589, left column (19 March 2011)
- change "pushdown automation" to "pushdown automaton"
- page 591, left column (06 August 2007)
- change "Speroni, Joseph P." to "Speroni, Joseph Paul"
- page 593, right column (15 August 2006)
- change "Warren, Don W." to "Warren, Don Wyman"
- page 594, left column, new entry (06 February 2009)
- Worsley, Beatrice Helen, 76, 91--92.
I hope the book is otherwise error-free; but (sigh) it probably isn't, because each page presented me with hundreds of opportunities to make mistakes. Please send suggested corrections to knuth-bug@cs.stanford.edu, or send snail mail to Prof. D. Knuth, Computer Science Department, Gates Building 4B, Stanford University, Stanford, CA 94305-9045 USA. I may not be able to read your message until many months have gone by, because I'm working intensively on The Art of Computer Programming. However, I promise to reply in due time.
DO NOT SEND EMAIL TO KNUTH-BUG EXCEPT TO REPORT ERRORS IN BOOKS! And if you do report an error via email, please do not include attachments of any kind; your message should be readable on brand-X operating systems for all values of X.
Don Knuth's home page
Don Knuth's other books
