Preface

This volume tells the story of computer science in the words that created the field. The collection came into being for two reasons. First, to relieve 21st-century readers of the misimpression that the established conventions of the field were handed down to contemporary culture in finished form. Computer science has a rich family history that should be known to students and practitioners of the field. And second, to help readers see how important new ideas come to be, how tentative, clumsy baby steps become graceful, progressive strides—or sometimes go nowhere for years and then are taken up again after a long delay. The field is still young and dynamic; anyone looking around it today might see some novelty that will be tomorrow’s canon, hardly recognizable in its infancy.

To tell this story I have selected, with considerable anxiety, 46 papers from the earliest times to 1980, and have introduced each with a brief context-setting essay. Each of these papers made a memorable contribution to the field. Many others might have been selected in addition to or instead of these, and the 1980 cut-off date is arbitrary—though it does represent a moment when the field became so diversified as to defy summation in a small collection like this one.

This book is an educational volume documenting the origins of the field, and neither a critical edition of the papers nor a history of the field. The Introduction sets the papers in their historical context, but for those seeking a more thorough and nuanced account of historical developments, Priestley (2011) successfully avoids both over-reliance on self-interested recollections of the principals and post hoc ergo propter hoc fallacies. For the early history of computing machines, the reader is referred to Pratt (1987) and Jones (2016).

This volume is suitable for a one-semester course aimed at graduate students or advanced undergraduates, and has been used for that purpose at both Harvard and MIT. It can also serve as a guided tour for a curious professional. Among the factors considered when selecting and editing papers were these:

1. Many papers are heavily excerpted, both to focus on the key contributions and to omit technical details no longer of great interest. For example, I have omitted the ugly details of Turing’s code for his universal machine. Omitted text is indicated throughout by use of an ellipsis (…). Needless to say, readers hungry for more detail should track down the full papers. Each chapter begins with the bibliographic reference for the paper, though the year in the bibliographic citation may not match the year included with the title, since some papers were presented orally first or revised after their first publication. Moreover, the invention or discovery documented in the paper may have occurred earlier than the publication date.

2. I preferred short and readable papers to long or difficult papers, no matter how important.

3. I included only papers, not book extracts (with the exception of Boole’s The Laws of Thought and the title essay from Brooks’s collection The Mythical Man-Month).

4. I did not attempt to condense the defining reports for major programming languages such as FORTRAN, COBOL, or ALGOL, important though they were to the development of the field.

5. Important early efforts to systematize the field are also omitted, for example Curriculum 68 (Atchison et al., 1968) and the history of programming languages by Jean Sammet (1972).

6. The page count of authors included cannot be taken as a measure of their importance as computer scientists of the period. Donald Knuth would be under-represented by that standard and Edsger Dijkstra perhaps over-represented; great names such as Backus, Chomsky, Church, Floyd, Gray, Kleene, Newell, Lamport, Lampson, Rabin, Scott, and Tarjan are missing entirely. Apologies to anyone whose favorite paper or scientist did not make it in!

And a few purely editorial details.

• All references have been moved to a common bibliography at the end of the book, and Chicago style citations are used throughout. Any document cited in the original paper but not cited within the excerpted part of the text of a paper has not been included in the bibliography.
• Typographical errors in the original papers have been corrected, and punctuation has generally been standardized.
• Section and figure numbering has been made uniform. §33.7 is section 7 (or perhaps the seventh unnumbered section) of the original paper that appears here as chapter 33.
• The original numbering of theorems and lemmas has generally been retained.
• Footnotes have been omitted or incorporated as parentheses in the running text.
• In a few places, I have included editorial comments using the form “[EDITOR: The comment].”

For their careful proofreading I am grateful to the students of Harvard CS191 in 2019 and MIT 6.S897 in 2020. Brian Sapozhnikov and Adham Meguid were especially eagle-eyed. Thanks also to Peter Denning, Bill Gasarch, Warren Goldfarb, Matthew Lena, Maryanthe Malliaris, Tasha Schoenstein, Lloyd Strickland, Sherry Turkle, and Joel Wachman for their helpful comments and corrections. Of course, any remaining errors are solely my responsibility.

Harry Lewis

July 2020