Computer Science
Reflections on the Field, Reflections from the Field
THE NATIONAL ACADEMIES PRESS
Washington, D.C. www.nap.edu
THE NATIONAL ACADEMIES PRESS
500 Fifth Street, N.W. Washington, DC 20001
NOTICE: The project that is the subject of this report was approved by the Governing Board of the National Research Council, whose members are drawn from the councils of the National Academy of Sciences, the National Academy of Engineering, and the Institute of Medicine. The members of the committee responsible for the report were chosen for their special competences and with regard for appropriate balance.
Support for this project was provided by the National Science Foundation under grant No. CCR-9981754. Any opinions, findings, conclusions, or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the sponsor.
International Standard Book Number 0-309-09301-5 (Book)
International Standard Book Number 0-309-54529-3 (PDF)
Copies of this report are available from the
National Academies Press,
500 Fifth Street, N.W., Lockbox 285, Washington, DC 20055; (800) 624-6242 or (202) 334-3313 in the Washington metropolitan area; Internet, http://www.nap.edu.
Copyright 2004 by the National Academy of Sciences. All rights reserved.
Printed in the United States of America
THE NATIONAL ACADEMIES
Advisers to the Nation on Science, Engineering, and Medicine
The National Academy of Sciences is a private, nonprofit, self-perpetuating society of distinguished scholars engaged in scientific and engineering research, dedicated to the furtherance of science and technology and to their use for the general welfare. Upon the authority of the charter granted to it by the Congress in 1863, the Academy has a mandate that requires it to advise the federal government on scientific and technical matters. Dr. Bruce M. Alberts is president of the National Academy of Sciences.
The National Academy of Engineering was established in 1964, under the charter of the National Academy of Sciences, as a parallel organization of outstanding engineers. It is autonomous in its administration and in the selection of its members, sharing with the National Academy of Sciences the responsibility for advising the federal government. The National Academy of Engineering also sponsors engineering programs aimed at meeting national needs, encourages education and research, and recognizes the superior achievements of engineers. Dr. Wm. A. Wulf is president of the National Academy of Engineering.
The Institute of Medicine was established in 1970 by the National Academy of Sciences to secure the services of eminent members of appropriate professions in the examination of policy matters pertaining to the health of the public. The Institute acts under the responsibility given to the National Academy of Sciences by its congressional charter to be an adviser to the federal government and, upon its own initiative, to identify issues of medical care, research, and education. Dr. Harvey V. Fineberg is president of the Institute of Medicine.
The National Research Council was organized by the National Academy of Sciences in 1916 to associate the broad community of science and technology with the Academy’s purposes of furthering knowledge and advising the federal government. Functioning in accordance with general policies determined by the Academy, the Council has become the principal operating agency of both the National Academy of Sciences and the National Academy of Engineering in providing services to the government, the public, and the scientific and engineering communities. The Council is administered jointly by both Academies and the Institute of Medicine. Dr. Bruce M. Alberts and Dr. Wm. A. Wulf are chair and vice chair, respectively, of the National Research Council.
COMMITTEE ON THE FUNDAMENTALS OF COMPUTER SCIENCE: CHALLENGES AND OPPORTUNITIES
MARY SHAW,
Carnegie Mellon University,
Chair
ALFRED V. AHO,
Columbia University
CHARLES H. BENNETT,
IBM Research
ALAN BIERMANN,
Duke University
EDWARD W. FELTEN,
Princeton University
JAMES D. FOLEY,
Georgia Institute of Technology
MARK D. HILL,
University of Wisconsin at Madison
JON M. KLEINBERG,
Cornell University
DAPHNE KOLLER,
Stanford University
JAMES R. LARUS,
Microsoft Research
TOM M. MITCHELL,
Carnegie Mellon University
CHRISTOS H. PAPADIMITRIOU,
University of California, Berkeley
LARRY L. PETERSON,
Princeton University
MADHU SUDAN,
Massachusetts Institute of Technology
KEVIN J. SULLIVAN,
University of Virginia
JEFFREY D. ULLMAN,
Stanford University and Gradience Corporation
Staff
JON EISENBERG, Senior Program Officer and Study Director
LYNETTE I. MILLETT, Program Officer
D.C. DRAKE, Senior Project Assistant (through November 2003)
COMPUTER SCIENCE AND TELECOMMUNICATIONS BOARD
DAVID LIDDLE,
U.S. Venture Partners,
Co-Chair
JEANNETTE M. WING,
Carnegie Mellon University,
Co-Chair
ERIC BENHAMOU,
3Com Corporation
DAVID D. CLARK,
Massachusetts Institute of Technology, CSTB Member Emeritus
WILLIAM DALLY,
Stanford University
MARK E. DEAN,
IBM Systems Group
DEBORAH L. ESTRIN,
University of California, Los Angeles
JOAN FEIGENBAUM,
Yale University
HECTOR GARCIA-MOLINA,
Stanford University
KEVIN KAHN,
Intel Corporation
JAMES KAJIYA,
Microsoft Corporation
MICHAEL KATZ,
University of California, Berkeley
RANDY H. KATZ,
University of California, Berkeley
WENDY A. KELLOGG,
IBM T.J. Watson Research Center
SARA KIESLER,
Carnegie Mellon University
BUTLER W. LAMPSON,
Microsoft Corporation, CSTB Member Emeritus
TERESA H. MENG,
Stanford University
TOM M. MITCHELL,
Carnegie Mellon University
DANIEL PIKE,
GCI Cable and Entertainment
ERIC SCHMIDT,
Google Inc.
FRED B. SCHNEIDER,
Cornell University
WILLIAM STEAD,
Vanderbilt University
ANDREW J. VITERBI,
Viterbi Group, LLC
CHARLES BROWNSTEIN, Director
KRISTEN BATCH, Research Associate
JENNIFER M. BISHOP, Program Associate
JANET BRISCOE, Administrative Officer
JON EISENBERG, Senior Program Officer
RENEE HAWKINS, Financial Associate
MARGARET MARSH HUYNH, Senior Project Assistant
HERBERT S. LIN, Senior Scientist
LYNETTE I. MILLETT, Program Officer
JANICE SABUDA, Senior Project Assistant
BRANDYE WILLIAMS, Staff Assistant
For more information on CSTB, see its Web site at <http://www.cstb.org>, write to CSTB, National Research Council, 500 Fifth Street, N.W., Washington, DC 20001, call at (202) 334-2605, or e-mail the CSTB at cstb@nas.edu.
Preface
The blossoming of computer science (CS) research is evident in the information technology that has migrated from a specialized tool confined to the laboratory or corporate back office to a ubiquitous presence in machines and devices that now figure in the lives of virtually every individual. This widespread diffusion of information technology can obscure the nature of computer science research underlying the IT—from the perspective of many outside the field, computer science is seen not as a basic area of systematic inquiry but as a tool to support other endeavors.
Mindful of these issues, the National Science Foundation’s Computer and Information Science and Engineering Directorate asked the Computer Science and Telecommunications Board of the National Academies to conduct a study that would improve understanding of CS research among the scientific community at large, policymakers, and the general public. By describing in accessible form the field’s intellectual character and by conveying a sense of its vibrancy through a set of examples, the committee also aims to prepare readers for what the future might hold and inspire CS researchers to help create it.
This volume, the product of that study, is divided into two parts that contain nine chapters.
The volume’s prelude, “Emily Shops at VirtualEmporia.com,” takes a now-familiar use of computing—shopping online—and illustrates how CS research has made this seemingly simple activity possible.
Part One—Chapter 1, “The Essential Character of Computer Science”—offers the committee’s concise characterization of CS research. Like CS researchers more generally, the committee members evince a wide range of perspectives that mirror the broad reach of computation into the very fabric of our intellectual and physical lives. Recognizing the richness and diversity of the field, the committee expressly decided not to provide either a comprehensive list of research topics or a taxonomy of research areas, nor to develop criteria for what research is inside and outside of CS. Instead, the committee’s approach is to describe some key ideas that lie at the core of CS but not to define boundaries.
Part Two—Chapters 2 through 9—comprises two dozen essays written by committee members, participants in a June 6-7, 2001, symposium organized by the committee, and other invited authors. The essays describe several aspects of CS research and some of the results from the perspectives of their authors. By providing this diverse set of views on CS research, the committee aims to express some of the spark that motivates and excites CS researchers. The essays have a deliberately historical focus, for three reasons: (1) as described above, the committee decided not to present a research agenda, either explicit or implicit; (2) other publications look at current, hot topics in CS and these tend, in any case, to become dated quickly; and (3) results that have proven durable best illustrate the strengths of CS.
The prelude and Part One are intended to be accessible to all readers (as are many of the essays). But because this report is also intended to reach scientists and engineers from a variety of disciplines, a few of the essays do presume some familiarity with some technical concepts.
The committee would like to thank all of the participants in the June 2001 symposium; presentations and informal discussions at that event provided important input to the committee. Julie Sussman, PPA, provided a number of helpful suggestions concerning the manuscript. The reviewers listed below provided many valuable suggestions for improvement.
Mary Shaw, Chair
Committee on the Fundamentals of Computer Science: Challenges and Opportunities
Acknowledgment of Reviewers
This report has been reviewed in draft form by individuals chosen for their diverse perspectives and technical expertise, in accordance with procedures approved by the National Research Council’s Report Review Committee. The purpose of this independent review is to provide candid and critical comments that will assist the institution in making its published report as sound as possible and to ensure that the report meets institutional standards for objectivity, evidence, and responsiveness to the study charge. The review comments and draft manuscript remain confidential to protect the integrity of the deliberative process. We wish to thank the following individuals for their review of this report:
David D. Clark, Massachusetts Institute of Technology
Robert L. Constable, Cornell University
Ronald Fedkiw, Stanford University
Joan Feigenbaum, Yale University
Juris Hartmanis, Cornell University
James Jay Horning, Intertrust
Anna R. Karlin, University of Washington
Richard Karp, University of California, Berkeley
Wendy A. Kellogg, IBM Research
Monica S. Lam, Stanford University
Butler W. Lampson, Microsoft Research
Fred B. Schneider, Cornell University
Lynn Andrea Stein, Olin College
Gerald Jay Sussman, Massachusetts Institute of Technology
Thomas N. Theis, IBM T.J. Watson Research Center
Jeanette M. Wing, Carnegie Mellon University
Margaret H. Wright, New York University
Although the reviewers listed above provided many constructive comments and suggestions, they were not asked to endorse the conclusions or recommendations nor did they see the final draft of the report before its release. The review of this report was overseen by Lawrence Snyder, University of Washington. Appointed by the National Research Council, he was responsible for making certain that an independent examination of this report was carried out in accordance with institutional procedures and that all review comments were carefully considered. Responsibility for the final content of this report rests entirely with the authoring committee and the institution.
Contents
Computer Game Playing: Beating Humanity at Its Own Game, |
||||
The Internet: An Experiment That Escaped from the Lab, |
||||
Many-to-Many Communication: A New Medium, |
||||
Cryptography, |
||||
Strategies for Software Engineering Research, |
||||
How You Got Microsoft Word, |
||||
VisiCalc, Spreadsheets, and Programming for the Masses, Or “How a Killer App Was Born,” |
||||
Internet Searching, |
||||
PERSONAL STATEMENTS OF PASSION ABOUT COMPUTER SCIENCE RESEARCH |
||||
The Legacy of Computer Science, |
||||
Fairy Tales, |
||||
Revisiting “What Is Computer Science,” |
||||