REPORT

COMPUTING AS A DISCIPLINE

The final report of the Task Force on the Core of Computer Science presents
a new intellectual framework for the discipline of computing and a new
basis for computing curricula. This report has been endorsed and approved
for release by the ACM Education Board.

PETER J. DENNING (CHAIRMAN), DOUGLAS E. COMER, DAVID GRIES, MICHAEL C. MULDER,

ALLEN TUCKER, A. JOE TURNER, and PAUL R. YOUNG

It is ACM’s 42nd year and an old debate continues. Is The field has matured enough that it is now possible
computer science a science? An engineering discipline? to describe its intellectual substance in a new and com-
Or merely a technology, an inventor and purveyor of pelling way. This realization arose in discussions
computing commodities? What is the intellectual sub- among the heads of the Ph.D.-granting departments of
stance of the discipline? Is it lasting, or will it fade computer science and engineering in their meeting in
within a generation? Do core curricula in computer Snowbird, Utah, in July 1984. These and other similar
science and engineering accurately reflect the field? discussions prompted ACM and the IEEE Computer
How can theory and lab work be integrated in a com- Society to form task forces to create a new approach.
puting curriculum? Do core curricula foster compe- In the spring of 1985, ACM President Adele Goldberg
tence in computing? and ACM Education Board Chairman Robert Aiken ap-
We project an image of a technology-oriented disci- pointed this task force on the core of computer science
pline whose fundamentals are in mathematics and with the enthusiastic cooperation of the IEEE Computer
engineering-for example, we represent algorithms as Society. At the same time, the Computer Society
the most basic objects of concern and programming and formed a task force on computing laboratories with the
hardware design as the primary activities. The view enthusiastic cooperation of the ACM.
that “computer science equals programming” is espe- We hope that the work of the core task force, embod-
cially strong in most of our current curricula: the intro- ied in this report, will produce benefits beyond the
ductory course is programming, the technology is in original charter. By identifying a common core of sub-
our core courses, and the science is in our electives. ject matter, we hope to streamline the processes of de-
This view blocks progress in reorganizing the curricu- veloping curricula and model programs in the two soci-
lum and turns away the best students, who want a eties. The report can be the basis for future discussions
greater challenge. It denies a coherent approach to of computer science and engineering as a profession,
making experimental and theoretical computer science stimulate improvements in secondary school courses in
integral and harmonious parts of a curriculum. computing, and can lead to a greater widespread appre-
Those in the discipline know that computer science ciation of computing as a discipline.
encompasses far more than programming-for example, Our goal has been to create a new way of thinking
hardware design, system architecture, designing operat- about the field. Hoping to inspire general inquiry into
ing system layers, structuring a database for a specific
application, and validating models are all part of the This article has been condensed from the Report of the ACM
discipline, but are not programming. The emphasis on Task Force on the Core of Computer Science. Copies of the
programming arises from our long-standing belief that report in its entirety may be ordered, prepaid, from
programming languages are excellent vehicles for gain-
ACM Order Department
ing access to the rest of the field, a belief that limits our P.O. Box 64145
ability to speak about the discipline in terms that reveal Baltimore, MD 21264
its full breadth and richness.
Please specify order #201880. Prices are $7.00 for ACM
members, and $12.00 for nonmembers.
0,989 ACM 0001.0782/89/0100-0009 $1.50

Janua y 1989 Volume 32 Number I Communications of the ACM 9

 Report

the nature of our discipline, we sought a framework, (3) determine whether the relationships are true
not a prescription; a guideline, not an instruction. We (proof);
invite you to adopt this framework and adapt it to your (4) interpret results.
own situation.
We are pleased to present a new intellectual frame- A mathematician expects to iterate these steps (e.g.,
work for our discipline and a new basis for our when errors or inconsistencies are discovered.
curricula. The second paradigm, abstraction (modeling), is rooted
in the experimental scientific method and consists of
four stages that are followed in the investigation of a
CHARTER OF THE TASK FORCE phenomenon:
The task force was given three general charges:
(1) form a hypothesis;
1. Present a description of computer science that em- (2) construct a model and make a prediction;
phasizes fundamental questions and significant ac- (3) design an experiment and collect data;
complishments. The definition should recognize that (4) analyze results.
the field is constantly changing and that what is said
is merely a snapshot of an ongoing process of growth. A scientist expects to iterate these steps (e.g., when a
2. Propose a teaching paradigm for computer science model’s predictions disagree with experimental evi-
that conforms to traditional scientific standards, dence). Even though “modeling” and “experimentation”
emphasizes the development of competence in the might be appropriate substitutes, we have chosen the
field, and harmoniously integrates theory, experi- word “abstraction” for this paradigm because this usage
mentation, and design. is common in the discipline.
3. Give a detailed example of an introductory course The third paradigm, design, is rooted in engineering
sequence in computer science based on the curricu- and consists of four steps followed in the construction
lum model and the disciplinary description. of a system (or device) to solve a given problem:
We immediately extended our task to encompass both (1) state requirements;
computer science and computer engineering, because (2) state specifications;
we concluded that no fundamental difference exists be- (3) design and implement the system;
tween the two fields in the core material. The differ- (4) test the system.
ences are manifested in the way the two disciplines
elaborate the core: computer science focuses on analy- An engineer expects to iterate these steps (e.g., when
sis and abstraction; computer engineering on abstrac- tests reveal that the latest version of the system does
tion and design. The phrase discipline of computing is not satisfactorily meet the requirements).
used here to embrace all of computer science and Theory is the bedrock of the mathematical sciences:
engineering. applied mathematicians share the notion that science
Two important issues are outside the charter of this advances only on a foundation of sound mathematics.
task force. First, the curriculum recommendations in Abstraction (modeling) is the bedrock of the natural
this report deal only with the introductory course se- sciences: scientists share the notion that scientific prog-
quence. It does not address the important, larger ques- ress is achieved primarily by formulating hypotheses
tion of the design of the entire core curriculum, and and systematically following the modeling process to
indeed the suggested introductory course would be verify and validate them. Likewise, design is the bed-
meaningless without a new design for the rest of the rock of engineering: engineers share the notion that
core. Second, our specification of an introductory progress is achieved primarily by posing problems and
course is intended to be an example of an approach to systematically following the design process to construct
introduce students to the whole discipline in a rigorous systems that solve them. Many debates about the rela-
and challenging way, an “existence proof” that our def- tive merits of mathematics, science, and engineering
inition of computing can be put to work. We leave it to are implicitly based on an assumption that one of the
individual departments to apply the framework to de- three processes (theory, abstraction, or design) is the
velop their own introductory courses that meet local most fundamental.
needs. Closer examination, however, reveals that in com-
puting the three processes are so intricately intertwined
that it is irrational to say that any one is fundamental.
PARADIGMS FOR THE DISCIPLINE
Instances of theory appear at every stage of abstraction
The three major paradigms, or cultural styles, by which
and design, instances of modeling at every s,tageof the-
we approach our work provide a context for our defini-
ory and design, and instances of design at every stage of
tion of the discipline of computing. The first paradigm,
theory and abstraction.
theory, is rooted in mathematics and consists of four
Despite their inseparability, the three paradigms are
steps followed in the development of a coherent, valid
theory: distinct from one another because they represent sepa-
rate areas of competence. Theory is concerned with the
(1) characterize objects of study (definition); ability to describe and prove relationships among ob-
(2) hypothesize possible relationships among them jects. Abstraction is concerned with the ability to use
(theorem); those relationships to make predictions that can be

10 Communications of the ACM January 1989 Volume 32 Number 1

 Report

compared with the world. Design is concerned with the and dynamic field. We intend this to be a “living defini-
ability to implement specific instances of those relation- tion,” that can be revised from time to time to reflect
ships and use them to perform useful actions. Applied maturity and change in the field. We expect revisions
mathematicians, computational scientists, and design to occur most frequently in the details of the subareas,
engineers generally do not have interchangeable skills. occasionally in the list of subareas, and rarely in the
Moreover, in computing we tend to study computa- short definition.
tional aids that support people engaged in information-
transforming processes. On the design side, for exam- Requirements
ple, sophisticated VLSI design and simulation systems There are many possible ways to formulate a definition.
enable the efficient and correct design of microcir- We set five requirements for ours:
cuitry, and programming environments enable the
1. It should be understandable by people outside the
efficient design of software. On the modeling side, su-
field.
percomputers evaluate mathematical models and make
2. It should be a rallying point for people inside the
predictions about the world, and networks help dissem-
field.
inate findings from scientific experiments. On the the-
3. It should be concrete and specific,
ory side, computers help prove theorems, check the
4. It should elucidate the historical roots of the disci-
consistency of specifications, check for counterexam-
pline in mathematics, logic, and engineering.
ples, and demonstrate test cases.
5. It should set forth the fundamental questions and
Computing sits at the crossroads among the central
significant accomplishments in each area of the
processes of applied mathematics, science, and engi-
discipline.
neering. The three processes are of equal-and funda-
mental-importance in the discipline, which is a In the process of formulating a description, we consid-
unique blend of interaction among theory, abstraction, ered several other previous definitions and concluded
and design. The binding forces are a common interest that a description meeting these requirements must
in experimentation and design as information trans- have several levels of complexity. The other definitions
formers, a common interest in computational support of are briefly summarized here.
the stages of those processes, and a common interest in In 1967, Newell, Perlis, and Simon [5] argued that
efficiency. computer science is the study of computers and the
major phenomena that surround them, and that all the
THE ROLE OF PROGRAMMING common objections to this definition could just as well
Many activities in computing are not programming-for be used to demonstrate that other sciences are not sci-
example, hardware design, system architecture, operat- ence. Despite their eloquence, too many people view
ing system structure, designing a database application, this as a circular definition that seems flippant to out-
and validating models-therefore the notion that “com- siders. It is, however, a good starting point because
puter science equals programming” is misleading. What the definition we present later can be viewed as an
is the role of programming in the discipline? In the enumeration of the major phenomena surrounding
curriculum? computers.
Clearly programming is part of the standard practices A slightly more elaborate version of this idea was
of the discipline and every computing major should recently used by the Computing Sciences Accreditation
achieve competence in it. This does not, however, im- Board (CSAB), which said, “Computer science is the
ply that the curriculum should be based on program- body of knowledge concerned with computers and
ming or that the introductory courses should be pro- computation. It has theoretical, experimental, and de-
gramming courses. sign components and includes (1) theories for under-
It is also clear that access to the distinctions of any standing computing devices, programs, and systems;
domain is given through language, and that most of the (2) experimentation for the development and testing of
distinctions of computing are embodied in program- concepts; (3) design methodology, algorithms, and tools
ming notations. Programming languages are useful tools for practical realization; and (4) methods of analysis for
for gaining access to the distinctions of the discipline. verifying that these realizations meet requirements.”
We recommend, therefore, that programming be a part A third definition is, “Computer science is the study
of the competence sought by the core curriculum, and of knowledge representations and their implementa-
that programming languages be treated as useful vehi- tions.” This definition suffers from excessive abstrac-
cles for gaining access to important distinctions of tion and few people would agree on the meaning of
computing. knowledge representation. A related example that suf-
fers the same fate is, “Computer science is the study of
A DESCRIPTION OF COMPUTING abstraction and the mastering of complexity,” a state-
Our description of computing as a discipline consists ment that also applies to physics, mathematics, or
of four parts: (1) requirements; (2) short definition; philosophy.
(3) division into subareas; and (4) elaboration of suba- A final observation comes from Abelson and Suss-
reas. Our presentation consists of four passes, each man, who say, “The computer revolution is a revolu-
going to a greater level of detail. tion in the way we think and in the way we express
What we say here is merely a snapshot of a changing what we think. The essence of this change is the emer-

[anua y 1989 Volume 32 Number 1 Communications of the ACM 11

Report

gence of what might best be called procedural espiste- 3. Architecture

mology-the study of the structure of knowledge from 4. Numerical and symbolic computation
an imperative point of view, as opposed to the more 5. Operating systems
decla:rative point of view taken by classical mathemati- 6. Software methodology and engineering
cal subjects. Mathematics provides a framework for 7. Database and information retrieval systems
dealing precisely with notions of ‘what is.’ Computation 8. Artificial intelligence and robotics
provides a framework for dealing precisely with notions 9. Human-computer communication
of ‘how to’ [I].”
Elaboration of Subareas
Short Definition To present the content of the subareas, we found it
The [Link] of computing is the systematic study of useful to think of a 9 x 3 matrix, as shown in Figure 1.
algorithmic processes that describe and transform infor- Each row is associated with a subarea, and theory, ab-
mation: their theory, analysis, design, efficiency, imple- straction, and design each define a column.
mentation, and application. The fundamental question Each square of the matrix will be filled in with spe-
underlying all of computing is, “What can be (effi- cific statements about that subarea component; these
ciently) automated?” statements will describe issues of concern and signifi-
cant accomplishments.
Division into Subareas Certain affinity groups in which there is scientific
We grappled at some length with the question of divid- literature are not shown as subareas because they are
ing the discipline into subareas. We began with a pref- basic concerns throughout the discipline. For example,
erence for a small number of subareas, such as model parallelism surfaces in all subareas (there are parallel
versu.s implementation, or algorithm versus machine. algorithms, parallel languages, parallel architectures,
However, the various candidates we devised were too etc.) and in theory, abstraction, and design. !Similar con-
abstract, the boundaries between divisions were too clusions hold for security, reliability, and performance
fuzzy, and most people would not have identified com- evaluation.
fortably with them. Computer scientists will tend to associate with the
Then we realized that the fundamentals of the disci- first two columns of the matrix, and computer engi-
pline are contained in three basic processes-theory, neers with the last two. The full description of comput-
abstraction, and design-that are used by the discipli- ing, as specified here, is given in the appendix.
nary subareas to accomplish their goals. Thus, a de-
scription of the discipline’s subareas and their relation CURRICULUM MODEL
to these three basic processes would be useful. To qual-
ify as a subarea, a segment of the discipline must satisfy Competence in the Discipline
four criteria: The goal of education is to develop compete:nce in a
domain. Competence, the capability for effective action
(I) underlying unity of subject matter;
(2) substantial theoretical component;
(3) significant abstractions; Theory Abstraction Design
(4) important design and implementation issues.
1 Algorithms and data
Moreover, we felt that each subarea should be identi- structures
fied with a research community, or set of related com-
2 Programming languages
munities, that sustains its own literature.
Theory includes the processes for developing
the underlying mathematics of the subarea. These 3 Architecture
processes are supported by theory from other areas. For
4 Numerical and symbolic
example, the subarea of algorithms and data structures computation
contains complexity theory and is supported by graph
theory. Abstraction deals with modeling potential im- 5 Operating systems
plementations. These models suppress detail while re-
taining essential features; they are amenable to analysis 6 Software methodology and
and provide means for calculating predictions of the engineering
modeled system’s behavior. Design deals with the proc- 7 Databases and information
ess of specifying a problem, transforming the problem retrieval
statement into a design specification, and repeatedly 8 Artificial intelligence and
inventing and investigating alternative solutions until a robotics
reliable, maintainable, documented, and tested design
9 Human-computer
that meets cost criteria is achieved. communication
We discerned nine subareas that cover the field:
1. Algorithms and data structures
2. Programming languages FIGURE1. Definition Matrix for the Computing Discipline

12 Communications of the ACM ]anuary 1989 Volume .32 Number 2

 Report

is an assessment of individual performance against the development of a commitment to a lifelong process of

standard practices of the field. The criteria for assess- learning.
ment are grounded in the history of the field. The edu-
cational process that leads to competence has five steps: INTRODUCTORY SEQUENCE
(1) motivate the domain; (2) demonstrate what can be In this curriculum model, the motivation and demon-
accomplished in the domain; (3) expose the distinctions stration of the domain must precede instruction and
of the domain; (4) ground the distinctions in history; practice in the domain. The purpose of the introductory
and (5) practice the distinctions [4]. course sequence is precisely this. The principal areas of
This model has interesting implications for curricu- computing-in which majors must develop compe-
lum design. The first question it leads to is, In what tence-must be presented to students with sufficient
areas of computing must majors be competent? There depth and rigor that they can appreciate the power of
are two broad areas of competence: the areas and the benefits from achieving competence
in them. The remainder of the curriculum must be
1. Discipline-Oriented Thinking: The ability to invent carefully designed to systematically explore those
new distinctions in the field, leading to new modes areas, exposing new concepts and distinctions, and
of action and new tools that make those distinctions giving students practice in them.
available for others to use. We therefore recommend that the introductory
2. Tool Use: The ability to use the tools of the field for course consist of regular lectures and a closely coordi-
effective action in other domains. nated weekly laboratory. The lectures should empha-
size fundamentals; the laboratories technology and
We suggest that discipline-oriented thinking is the pri-
know-how.
mary goal of a curriculum for computing majors, and
This model is traditional in the physical sciences and
that majors must be familiar enough with the tools to
work effectively with people in other disciplines to help engineering: lectures emphasize enduring principles
and concepts while laboratories emphasize the tran-
design modes of effective action in those disciplines.
sient material and skills relating to the current technol-
The inquiry into competence reveals a number of
ogy. For example, lectures would discuss the design
areas where current core curricula in computing is
and analysis of algorithms, or the organization of net-
inadequate. For example, the historical context of the
computing field is often deemphasized, leaving many work protocols in functional layers. In the correspond-
ing laboratory sessions, students would write programs
graduates ignorant of computing history and destined to
for algorithms analyzed in lecture and measure their
repeat its mistakes. Many computing graduates wind up
in business data processing, a domain in which most running times, or instal and test network interfaces and
computing curricula do not seek to develop compe- measure their packet throughputs.
tence; whether computing departments or business de- Within this recommendation, the first courses in
partments should develop that competence is an old computer science would not only introduce program-
controversy. Discipline-oriented thinking must be based ming, algorithms, and data structures, but introduce
on solid mathematical foundations, yet theory is not an material from all the other subdisciplines as well.
integral part of most computing curricula. The standard Mathematics and other theory would be well integrated
into the lectures at appropriate points.
practices of the computing field include setting up and
conducting experiments, contributing to team projects, We recommend that the introductory course contain
a rigorous, challenging survey of the whole discipline.
and interacting with other disciplines to support their
interests in effective use of computing, but most curric- The physics model, exemplified by the Feynman Lec-
tures in Physics, is a paradigm for the introductory
ula neglect laboratory exercises, team projects, or inter-
course we envisage.
disciplinary studies.
The question of what results should be achieved by We emphasize that simply redesigning the introduc-
tory course sequence following this recommendation
computing curricula has not been explored thoroughly
without redesigning the entire undergraduate curricu-
in past discussions, and we will not attempt a thorough
analysis here. We do strongly recommend that this lum would be a serious mistake. The experience of
question be among the first considered in the design of physics departments contains many lessons for comput-
new core curricula for computing. ing departments in this regard.

Prerequisites
Lifelong Learning We assume that computing majors have a modest back-
The curriculum should be designed to develop an ap- ground in programming in some language and some
preciation for learning which graduates will carry with experience with computer-based tools such as word
them throughout their careers. Many courses are de- processors, spreadsheets, and databases. Given the
signed with a paradigm that presents “answers” in a widening use of computers in high schools and at
lecture format, rather than focusing on the process of home, it might seem that universities could assume
questioning that underlies all learning. We recommend that most incoming students have such a background
that the follow-on committee consider other teaching and provide a “remedial” course in programming for
paradigms which involve processes of inquiry, an ori- the others. We have found, however, that the assump-
entation to using the computing literature, and the tion of adequate high school preparation in program-

]anuary 1989 Volume 32 Number 1 Communicationsof the ACM 13

Report

ming is quite controversial and there is evidence that entitled Fundamental Algorithm Concepts. It covers the
adequate preparation is rare. We therefore recommend role of formalism and theory, methods in programming,
that c:omputing departments offer an introduction to programming concepts, efficiency, and specific algo-
programming and computer tools that would be a pre- rithms, draws information from the first, second,
requisite (or corequisite) for the introductory courses. fourth, and sixth rows of the definition matrix and
We further recommend that departments provide an deals only with sequential algorithms. Later modules,
advanced placement procedure so that students with on Distributed Computing and Networks, and on Paral-
adequate high school preparation can bypass this lel Computation, extend the material in the first mod-
course. ule and draw new material from the third and fifth
Formal prerequisites and corequisites in mathematics rows of the definition matrix.
are more difficult to state and will depend on local As a general approach, each module contains lectures
circumstances. However, accrediting boards in comput- that cover the required theory and most abstractions.
ing require considerable mathematics, including dis- Theory is generally not introduced until it is: needed.
crete mathematics, differential and integral calculus, Each module is closely coupled with laboratory ses-
and probability and statistics. These requirements are sions, and the nature of the laboratory assignments is
often exceeded in the better undergraduate programs. included with the module specifications. Our specifica-
In our description of a beginning computing curricu- tion is drawn up for a three-semester course sequence
lum, we have spelled out in some detail what mathe- containing 42 lectures and 35 scheduled laboratory ses-
matics is applicable in each of the nine identified areas sions per semester. Our specification is not included
of computing. Where possible we have displayed the here, but is in the full report.
required mathematical background for each of the We reemphasize that this specification is intended
teaching modules we describe. This will allow individ- only to be an example of a mapping from the discipli-
ual departments to synchronize their own mathemati- nary description to an introductory course sequence,
cal requirements and courses with the material in the not a prescription for all introductory courses. Other
modules. In some cases it may be appropriate to intro- approaches are exemplified by existing introductory
duce appropriate underlying mathematical topics as curricula at selected colleges and universities.
needed for the development of particular topics in com-
puting. In general, we recommend that students see
LABORATORIES
applications of relevant mathematics as early as possi-
We have described a curriculum that separates princi-
ble in their computing studies.
ples from technology while maintaining [Link] be-
tween the two. We have recommended that lectures
Modular Organization
deal with principles and laboratories with technology,
The introductory sequence should bring out the under-
with the two being closely coordinated.
lying unity of the field and should flow from topic to
The laboratories serve three purposes:
topic in a pedagogically natural way. It would therefore
be inadequate to organize the course as a sequence of Laboratories should demonstrate how principles cov-
nine sections, one for each of the subareas; such a map- ered in the lectures apply to the design, implementa-
ping would appear to be a hodge-podge, with difficult tion, and testing of practical software and hardware.
transitions between sections. An ordering of topics that They should provide concrete experiences that help
meet these requirements is: students understand abstract concepts. These experi-
ences are essential to sharpen students’ intuition
Fundamental algorithm concepts
about practical computing, and to [Link] the in-
Computer organization (“von Neumann”)
tellectual effort in building correct, efficient com-
Mathematical programming
puter programs and systems.
Data structures and abstraction
Laboratories should emphasize processes leading to
Limits of computability
good computing know-how. They should emphasize
Operating systems and security
programming, not programs; laboratory techniques;
Distributed computing and networks
understanding of hardware capabilities; correct use
Models in artificial intelligence
of software tools; correct use of documentation; and
File and database systems
proper documentation of experiments and projects.
Parallel computation
Many software tools will be required on host com-
Human interface
puters to assist in constructing, controlling, and
We have grouped the topics into 11 modules. Each monitoring experiments on attached subsystems; the
module includes challenging material representative of laboratory should teach proper use of these tools:
the subject matter without becoming a superficial sur- Laboratories should introduce experimental meth-
vey of every aspect or topic. Each module draws mate- ods, including use and design of experiments, soft-
rial from several squares of the definition matrix as ware and hardware ‘monitors, statistical #analysis of
appropriate. As a result, many modules will not corre- results, and proper presentation of findings. Students
spond one-to-one with rows of the definition matrix. should learn to distinguish careful experiments from
For example, the first module in our example course is casual observations.

14 Communications of the ACM January 1989 Volume 32 Number 1

 Report

To meet these goals, laboratory work should be care- 2. Hardware and software must be fully maintained,
fully planned and supervised. Students should attend Malfunctioning equipment will frustrate students
labs at specified times, nominally three hours per week. and interfere with learning. Appropriate staff must
Lab assignments should be planned, and written de- be available to maintain the hardware and software
scriptions of the purposes and methodology of each used in the lab. The situation is analogous to labora-
experiment should be given to the students. The depth tories in other disciplines.
of description should be commensurate with students’ 3. Full functionality is important. (This includes ade-
prior lab experience: more detail is required in early quate response time on shared systems.) Restricting
laboratories. Lab assignments should be carried out un- students to small subsets of a language or system
der the guidance of a lab instructor who ensures that may be useful in initial contacts, but the restrictions
each student follows correct methodology. should be lifted as the students progress.
The labs associated with the introductory courses 4. Good programming tools are needed. Compilers get a
will require close supervision and should contain well- lot of attention, but other programming tools are
planned activities. This implies that more staff will be used as often. In UNIX systems, for example, stu-
required per student for these laboratories than for dents should use editors like emacs and learn to use
more advanced ones. tools like the shell, grep, awk, and make. Storage
The lab problems should be coordinated with mate- and processing facilities must be sufficient to make
rial in the lecture parts of the course. Individual lab such tools available for use in the lab.
problems in general will deal with combinations of 5. Adequate support for hardware and instrumentation
hardware and software. Some lab assignments empha- must be provided. Some projects may require stu-
size technologies and tools that ease the software devel- dents to connect hardware units together, take
opment process. Others emphasize analyzing and measurements of signals, monitor data paths, and
measuring existing software or comparing known algo- the like. A sufficient supply of small parts, connec-
rithms. Others emphasize program development based tors, cables, monitoring devices, and test instruments
on principles learned in class. must be available.
Laboratory assignments should be self-contained in
The IEEE Computer Society Task Force on Goal Ori-
the sense that an average student should be able to
ented Laboratory Development has studied this subject
complete the work in the time allocated. Laboratory
in depth. Their report includes a discussion of the re-
assignments should encourage students to discover and
sources (i.e., staff and facilities) needed for laboratories
learn things for themselves. Students should be re-
at all levels of the curriculum.
quired to maintain a proper lab book documenting ex-
periments, observations, and data. Students should also
be required to maintain their software and to build ACCREDITATION
libraries that can be used in later lab projects. This work has been conducted with the intent that
We expect that, in labs as in lectures, students will example courses be consistent with current guidelines
be assigned homework that will require using com- of the Computing Sciences Accreditation Board (CSAB).
puters outside the supervised realm of a laboratory. In The details of the mapping of this content to CSAB
other words, organized laboratory sessions will supple- guidelines does not fall within the scope of this com-
ment, not replace, the usual programming and other mittee.
written assignments.
In a substantial number of labs dealing with program
CONCLUSION
development, the assignment should be to modify or
This report has been designed to provoke new thinking
complete an existing program supplied by the instruc-
about computing as a discipline by exhibiting the disci-
tor. This forces the student to read well-written pro-
pline’s content in a way that emphasizes the funda-
grams, provides experience with integration of soft-
mental concepts, principles, and distinctions. It has also
ware, and results in a larger and more satisfying
suggested a redesign of the core curriculum according
program for the student.
to an education model used in other disciplines: dem-
Computing technology constantly changes. It is diffi-
onstrating the existence of useful distinctions followed
cult, therefore, to give a detailed specification of the
by practice that develops competence. The method is
hardware systems, software systems, instruments, and
illustrated by a rigorous introductory course that puts
tools that ought to be in a laboratory. The choice of
the concepts and principles into the lectures and tech-
equipment and staffing in laboratories should be guided
nology into closely coordinated laboratories.
by the following principles:
A department cannot simply replace its current intro-
1. Laboratories should be equipped with up-to-date ductory sequence with the new one; it must redesign
systems and languages. Programming languages have the curriculum so that the new introduction is part of a
a significant effect on shaping a student’s view of coherent whole. For this reason, we recommend that
computing. Laboratories should deploy systems that the ACM establish a follow-on committee to complete
encourage good habits in students; it is especially the redesign of the core curriculum.
important to avoid outdated systems (hardware and Many practical problems must be dealt with before a
software) in core courses. new curriculum model can become part of the field.

January 1989 Volume 32 Number 1 Communications of the ACM 15

Report

For example, 4. Teaching assistants and faculty are not familiar with
the new view.
1. Faculties will need to redesign their curricula based
5. Good high school preparation in computing is rare.
on a new conceotual formulation.
2. No textbooks or educational materials based on the We recognize that many of our recommendations are
[Link] proposed here are currently available. challenging and will require substantial work to imple-
3. Most departments have inadequate laboratories, ment. We are convinced that the improvements in
facilities, and materials for the educational task computing education from the proposals here are worth
suggested here. the effort, and invite you to join us in achieving them.

APPENDIX
A DEFINITION OF COMPUTING AS A DISCIPLINE

Computer science and engineering is the systematic Bush constructed an electronic analog computer for
study of algorithmic processes-their theory, analysis, solving general systems of differential equations. In the
design, efficiency, implementation, and application- same period, electromechanical calculating machines
that describe and transform information. The funda- capable of addition, subtraction, [Link], divi-
mental question underlying all of computing is, What sion, and square root computation became available.
can be (efficiently) automated [Z, 31. This discipline was The electronic flip-flop provided a natural bridge from
born in the early 1940s with the joining together of these machines to digital versions with no moving
algorithm theory, mathematical logic, and the inven- parts.
tion of the stored-program electronic computer. Logic is a branch of mathematics concerned with cri-
The roots of computing extend deeply into mathe- teria of validity of inference and formal principles of
matics and engineering. Mathematics imparts analysis reasoning. Since the days of Euclid, it has been a tool
to the field; engineering imparts design. The discipline for rigorous mathematical and scientific argument. In
embraces its own theory, experimental method, and the 19th century a search began for a universal system
engineering, in contrast with most physical sciences, of logic that would be free of the incompletenesses ob-
which are separate from the engineering disciplines served in known deductive systems. In a complete sys-
that apply their findings (e.g., chemistry and chemical tem, it would be possible to determine mechanically
engineering principles). The science and engineering whether any given statement is either true or false. In
are inseparable because of the fundamental interplay 1931, Godel published his “incompleteness theorem,”
between the scientific and engineering paradigms showing that there is no such system. In the late 193Os,
within the discipline. Turing explored the idea of a universal computer that
For several thousand years, calculation has been a could simulate any step-by-step procedure of any other
principal concern of mathematics. Many models of computing machine. His findings were similar to
physical phenomena have been used to derive equa- Godel’s: some well-defined problems cannot be solved
tions .whose solutions yield predictions of those phe- by any mechanical procedure. Logic is important not
nomena-for example, calculations of orbital trajecto- only because of its deep insight into the limits of auto-
ries, weather forecasts, and fluid flows. Many general matic calculation, but also because of its ins:ight that
methods for solving such equations have been de- strings of symbols, perhaps encoded as numbers, can be
vised-for example, algorithms for systems of linear interpreted both as data and as programs.
equations, differential equations, and integrating func- This insight is the key idea that distinguishes the
tions. For almost the same period, calculations that aid stored program computer from calculating machines.
in the design of mechanical systems have been a princi- The steps of the algorithm are encoded in a machine
pal concern of engineering. Examples include algo- representation and stored in the memory for later de-
rithms for evaluating stresses in static objects, calculat- coding and execution by the processor. The machine
ing momenta of moving objects, and measuring code can be derived mechanically from a higher-level
distances much larger or smaller than our immediate symbolic form, the programming language.
perception. It is the explicit and intricate intertwining of the an-
One product of the long interaction between engi- cient threads of calculation and logical symb’ol manipu-
neering and mathematics has been mechanical aids for lation, together with the modern threads of electronics
calculating. Some surveyors’ and navigators’ instru- and electronic representation of information, that gave
ments date back a thousand years. Pascal and Leibniz birth to the discipline of computing.
built arithmetic calculators in the middle 1600s. In the We identified nine subareas of computing:
183Os, Babbage conceived of an “analytical engine” that
could mechanically and without error evaluate loga- 1. Algorithms and data structures
rithms, trigonometric functions, and other general 2. Programming languages
arithmetic functions. His machine, never completed, 3. Architecture
served as an inspiration for later work. In the 192Os, 4. Numerical and symbolic computation

16 Communications of the ACM Ianuary 1989 Volume 32 Number 1

 Report

5. Operating systems 1.1 Theory

6. Software methodology and engineering Major elements of theory in the area of algorithms and
7. Databases and information retrieval data structures are:
8. Artificial intelligence and robotics
9. Human-Computer communication 1. Computability theory, which defines what machines
can and cannot do.
Each has an underlying unity of subject matter, a sub- 2. Computational complexity theory, which tells how
stantial theoretical component, significant abstractions, to measure the time and space requirements of com-
and substantial design and implementation issues. The- putable functions and relates a problem’s size with
ory deals with the underlying mathematical develop- the best- or worst-case performance of algorithms
ment of the subarea and includes supporting theory that solve that problem, and provides methods for
such as graph theory, combinatorics, or formal lan- proving lower bounds on any possible solution to a
guages. Abstraction (or modeling) deals with models of problem.
potential implementations; the models suppress detail, 3. Time and space bounds for algorithms and classes of
while retaining essential features, and provide means algorithms.
for predicting future behavior. Design deals with the 4. Levels of intractability: for example, classes of prob-
process of specifying a problem, deriving requirements lems solvable deterministically in polynomially
and specifications, iterating and testing prototypes, and bounded time (P-problems); those solvable nondeter-
implementing a system. Design includes the experi- ministically in polynomially bounded time (NP-
mental method, which in computing comes in several problems); and those solvable efficiently by parallel
styles: measuring programs and systems, validating hy- machines (NC-problems).
potheses, and prototyping to extend abstractions to 5. Parallel computation, lower bounds, and mappings
practice. from dataflow requirements of algorithms into com-
Although software methodology is essentially con- munication paths of machines.
cerned with design, it also contains substantial ele- 6. Probabilistic algorithms, which give results correct
ments of theory and abstraction. For this reason, we with sufficiently high probabilities much more effi-
have identified it as a subarea. On the other hand, ciently (in time and space) than determinate algo-
parallel and distributed computation are issues that rithms that guarantee their results. Monte Carlo
pervade all the subareas and all their components (the- methods.
ory, abstraction, and design); they have been identified 7. Cryptography.
neither as subareas nor as subarea components. 8. The supporting areas of graph theory, recursive
The subsequent numbered sections provide the de- functions, recurrence relations, combinatorics, cal-
tails of each subarea in three parts-theory, abstrac- culus, induction, predicate and temporal logic, se-
tion, and design. The boundaries between theory and mantics, probability, and statistics.
abstraction, and between abstraction and design, are
necessarily fuzzy; it is a matter of personal taste where
some of the items go. 1.2 Abstraction
Our intention is to provide a guide to the discipline Major elements of abstraction in the area of algorithms
by showing its main features, not a detailed map. It is and data structures are
important to remember that this guide to the discipline 1. Efficient, optimal algorithms for important classes of
is not a plan for a course or a curriculum; it is merely a problems and analyses for best, worst, and average
framework in which a curriculum can be designed. It is performance.
also important to remember that this guide to the disci- Classifications of the effects of control and data
pline is a snapshot of an organism undergoing constant structure on time and space requirements for var-
change. It will require reevaluation and revision at reg- ious classes of problems.
ular intervals. Important classes of techniques such as divide-and-
conquer, Greedy algorithms, dynamic programming,
finite state machine interpreters, and stack machine
1. ALGORITHMS AND DATA STRUCTURES interpreters.
This area deals with specific classes of problems and Parallel and distributed algorithms; methods of parti-
their efficient solutions. Fundamental questions in- tioning problems into tasks that can be executed in
clude: For given classes of problems, what are the best separate processors.
algorithms? How much storage and time do they re-
quire? What is the tradeoff between space and time?
What is the best way to access the data? What is 1.3 Design
the worst case of the best algorithms? How well do Major elements of design and experimentation in the
algorithms behave on average? How general are algo- area of algorithms and data structures are:
rithms-i.e., what classes of problems can be dealt with 1. Selection, implementation, and testing of algorithms
by similar methods? for important classes of problems such as searching,

January 1989 Volume 32 Number 1 Communications

of the ACM 17
Report

sorting, random-number generation, and textual 3. Classification of major syntactic and semantic
pattern matching. models for program structure; e.g., procedure hierar-
2. Implementation and testing of general methods chies, functional composition, abstract data types,
applicable across many classes of problems, such as and communicating parallel processes.
hashing, graphs, and trees. 4. Abstract implementation models for each major type
3. Implementation and testing of distributed algorithms of language.
such as network protocols, distributed data updates, 5. Methods for parsing, compiling, interpretation, and
semaphores, deadlock detectors, and synchroniza- code optimization.
tion methods. 6. Methods for automatic generation of parsers, scan-
4. Implementation and testing of storage managers such ners, compiler components, and compilers.
as garbage collection, buddy system, lists, tables, and
p@w 2.3 Design
6. Extensive experimental testing of heuristic algo- Major elements of design and experimentation in the
rithms for combinatorial problems. area of programming languages are:
6. Cryptographic protocols that permit secure authen-
1. Specific languages that bring together a particular
tication and secret communication.
abstract machine (semantics) and syntax to form a
coherent implementable whole. Examples: proce-
2. PROGRAMMING LANGUAGES dural (COBOL, FORTRAN, ALGOL, Pascal, Ada, C),
This area deals with notations for virtual machines that functional (LISP), dataflow (SISAL, VAL), object-
execute algorithms, with notations for algorithms and oriented (Smalltalk, CLU), logic (Prolog), strings
data, and with efficient translations from high-level (SNOBOL), and concurrency (CSP, Occam, Concur-
languages into machine codes. Fundamental questions rent Pascal, Modula 2).
include: What are possible organizations of the virtual 2. Specific implementation methods for partic:ular
mach:ine presented by the language (data types, opera- classes of languages: run-time models, static and dy-
tions, control structures, mechanisms for introducing namic execution methods, typing checking, storage
new types and operations)? How are these abstractions and register allocation, compilers, cross compilers,
implemented on computers? What notation (syntax) and interpreters, systems for finding parallelism in
can be used effectively and efficiently to specify what programs.
the computer should do? 3. Programming environments.
4. Parser and scanner generators (e.g., YACC, LEX),
2.1 Theory compiler generators.
Major elements of theory in the area of programming 5. Programs for syntactic and semantic error checking,
languages are: profiling, debugging, and tracing.
1. Formal languages and automata, including theories 6. Applications of programming-language methods to
of parsing and language translation. document-processing functions such as c:reating
2, Turing machines (base for procedural languages), tables, graphs, chemical formulas, spreadsheets
Post Systems (base for string processing languages), equations, input and output, and data ha:ndling.
X-calculus (base for functional languages). Other applications such as statistical processing.
3. Formal semantics: methods for defining mathemati-
cal models of computers and the relationships 3. ARCHITECTURE
among the models, language syntax, and implemen- This area deals with methods of organizing hardware
tation. Primary methods include denotational, alge- (and associated software) into efficient, relialble systems.
braic, operational, and axiomatic semantics. Fundamental questions include: What are good meth-
4. As supporting areas: predicate logic, temporal logic, ods of implementing processors, memory, and commu-
modern algebra and mathematical induction. nication in a machine? How do we design and control
large computational systems and convincingly demon-
2.2 Abstraction strate that they work as intended despite errors and
Major elements of abstraction in the area of program- failures? What types of architectures can efficiently
ming languages include: incorporate many processing elements that can work
concurrently on a computation? How do we measure
1. Classification of languages based on their syntactic performance?
and dynamic semantic models; e.g., static typing,
dynamic typing, functional, procedural, object-
3.1 Theory
oriented, logic, specification, messagepassing, and
Major elements of theory in the area of architecture
dataflow.
are:
2. Classification of languages according to intended
application area; e.g., business data processing, sim- 1. Boolean algebra.
ulation, list processing, and graphics. 2. Switching theory.

18 Communications of the ACh4 Januay 1989 Volume 32 Number 1

 Report

3. Coding theory. nite processes by finite discrete processes?How do we

4. Finite state machine theory. cope with the errors arising from these approximations?
5. The supporting areas of statistics, probability, How rapidly can a given class of equations be solved for
queueing, reliability theory, discrete mathematics, a given level of accuracy? How can symbolic manipula-
number theory, and arithmetic in different number tions on equations, such as integration, differentiation,
systems. and reduction to minimal terms, be carried out? How
can the answers to these questions be incorporated into
3.2 Abstraction efficient, reliable, high-quality mathematical software
Major elements of abstraction in the area of architec- packages?
ture are:
1, Finite state machine and Boolean algebraic models 4.1 Theory
of circuits that relate function to behavior. Major elements of theory in the area of numerical and
2. Other general methods of synthesizing systems from symbolic computation are:
basic components.
3. Models of circuits and finite state machines for com- 1. Number theory.
puting arithmetic functions over finite fields. 2. Linear algebra.
4. Models for data path and control structures. 3. Numerical analysis.
5. Optimizing instruction sets for various models and 4. Nonlinear dynamics.
workloads. 5. The supporting areas of calculus, real analysis, com-
6. Hardware reliability: redundancy, error detection, plex analysis, and algebra.
recovery, and testing.
7. Space, time, and organizational tradeoffs in the
design of VLSI devices. 4.2 Abstraction
8. Organization of machines for various computational Major elements of abstraction in the area of numerical
models: sequential, dataflow, list processing, array and symbolic computation are:
processing, vector processing, and message-passing. Formulations of physical problems as models in con-
9. Identification of design levels; e.g., configuration, tinuous (and sometimes discrete) mathematics.
program, instruction set, register, and gate. Discrete approximations to continuous problems. In
this context, backward error analysis, error propaga-
3.3 Design tion and stability in the solution of linear and non-
Major elements of design and experimentation in the linear systems. Special methods in special cases,
area of architecture are: such as Fast Fourier Transform and Poisson solvers.
1. Hardware units for fast computation; e.g., arithmetic The finite element model for a large class of prob-
function units, cache. lems specifiable by regular meshes and boundary
2. The so-called von Neumann machine (the single- values. Associated iterative methods and conver-
instruction sequence stored program computer); gence theory: direct, implicit, multigrids, rates of
RISC and CISC implementations. convergence. Parallel solution methods. Automatic
3. Efficient methods of storing and recording informa- grid refinement during numerical integration.
tion, and detecting and correcting errors. Symbolic integration and differentiation.
4. Specific approaches to responding to errors: recov-
ery, diagnostics, reconfiguration, and backup proce-
4.3 Design
dures.
Major elements of design and experimentation in the
5. Computer aided design (CAD) systems and logic sim-
area of numerical and symbolic computation are:
ulations for the design of VLSI circuits. Production
programs for layout, fault diagnosis. Silicon compi- 1. High-level problem formulation systems such as
lers. CHEM and WEB.
6. Implementing machines in various computational 2. Specific libraries and packages for linear algebra,
models; e.g., dataflow, tree, LISP, hypercube, vector, ordinary differential equations, statistics, nonlinear
and multiprocessor. equations, and optimizations; e.g., LINPACK,
7. Supercomputers, such as the Cray and Cyber ma- EISPACK, ELLPACK.
chines. 3. Methods of mapping finite element algorithms to
specific architectures-e.g., multigrids on hyper-
4. NUMERICAL AND SYMBOLIC COMPUTATION cubes.
This area deals with general methods of efficiently and 4. Symbolic manipulators, such as MACSYMA and RE-
accurately solving equations resulting from mathemati- DUCE, capable of powerful and nonobvious manipu-
cal models of systems. Fundamental questions include: lations, notably differentiations, integrations, and
How can we accurately approximate continuous or infi- reductions of expressions to minimal terms.

January 1989 Volume 32 Number 1 Communications of the ACM 19

Report

5. OIPERATING SYSTEMS 6. Networking, including layered protocols, naming,

This area deals with control mechanisms that allow remote resource usage, help services, and local net-
multiple resources to be efficiently coordinated in the work protocols such as token-passing and shared
execution of programs. Fundamental questions include: buses.
Whai. are the visible objects and permissible operations
at each level in the operation of a computer system? 5.3 Design
For each class of resource (objects visible at some Major elements of design and experimentation in the
level), what is a minimal set of operations that permit area of operating systems are:
their effective use? How can interfaces be organized so
1. Prototypes of time sharing systems, automatic stor-
that users deal only with abstract versions of resources
age allocators, multilevel schedulers, memory man-
and not with physical details of hardware? What are
agers, hierarchical file systems and other important
effective control strategies for job scheduling, memory
system components that have served as bases for
management, communications, access to software re-
commercial systems.
sources, communication among concurrent tasks, relia-
2. Techniques for building operating [Link] as
bility, and security? What are the principles by which
UNIX, Multics, Mach, VMS, and MS-DOS.
systems can be extended in function by repeated appli-
3. Techniques for building libraries of utilities; e.g.,
cation of a small number of construction rules? How
editors, document formatters, compilers, linkers, and
should distributed computations be organized so that
device drivers.
many autonomous machines connected by a communi-
4. Files and file systems.
cation network can participate in a computation, with
5. Queueing network modeling and simulation pack-
the details of network protocols, host locations, band-
ages to evaluate performance of real systems.
widths, and resource naming being mostly invisible?
6. Network architectures such as ethernet, FDDI, token
ring nets, SNA, and DECNET.
5.1 Theory 7. Protocol techniques embodied in the Department of
Major elements of theory in the area of operating sys- Defense protocol suite (TCP/IP), virtual circuit pro-
tems are: tocols, internet, real time conferencing, and X.25.
1. Concurrency theory: synchronization, determinacy, 6. SOFTWARE METHODOLOGY AND
and deadlocks. ENGINEERING
2. Scheduling theory, especially processor scheduling. This area deals with the design of programs and large
3. Program behavior and memory management theory, software systems that meet specifications and are safe,
inc:luding optimal policies for storage allocation. secure, reliable, and dependable. Fundamental ques-
4. Performance modeling and analysis. tions include: What are the principles behind the de-
5. The supporting areas of bin packing, probability, velopment of programs and programming systems? How
queueing theory, queueing networks, communica- does one prove that a program or system meets its spec-
tion and information theory, temporal logic, and ifications? How does one develop specifications that
cryptography. do not omit important cases and can be [Link] for
safety? How do software systems evolve through dif-
5.2 Abstraction ferent generations? How can software be designed for
Major elements of abstraction in the area of operating understandability and modifiability?
systems are:
6.1 Theory
1. Abstraction principles that permit users to operate Major elements of theory in the area of software meth-
on idealized versions of resources without concern odology and tools are:
for physical details (e.g., process rather than proces- 1. Program verification and proof.
sor, virtual memory rather than main-secondary
2. Temporal logic.
hierarchy, files rather than disks).
5. Reliability theory.
2. Binding of objects perceived at the user interface to
4. The supporting areas of predicate calculus, axio-
internal computational structures.
matic semantics, and cognitive psychology.
3. Models for important subproblems such as process
[Link], memory management, job scheduling,
6.2 Abstraction
secondary storage management, and performance
Major elements of abstraction in the area of software
analysis.
methodology and tools are:
4. Models for distributed computation; e.g., clients and
servers, cooperating sequential processes, message- 1. Specification methods, such as predicate trans-
passing, and remote procedure calls. formers, programming calculi, abstract data types,
5. Models for secure computing; e.g., access controls, and Floyd-Hoare axiomatic notations.
authentication, and communication. 2. Methodologies such as stepwise refinement, modular

20 Communications of the ACM January 1989 Volume 32 Number 1

 Report

design, modules, separate compilation, information- formance be achieved when the data are distributed
hiding, dataflow, and layers of abstraction. among many machines? How can text be indexed and
3. Methods for automating program development; e.g., classified for efficient retrieval?
text editors, syntax-directed editors, and screen edi-
tors. 7.1 Theory
4. Methodologies for dependable computing; e.g., fault Major elements of theory in the area of databases and
tolerance, security, reliability, recovery, N-version information retrieval systems are:
programming, multiple-way redundancy, and check-
1. Relational algebra and relational calculus.
pointing.
2. Dependency theory.
5. Software tools and programming environments.
3. Concurrency theory, especially serializable transac-
6. Measurement and evaluation of programs and sys-
tions, deadlocks, and synchronized updates of multi-
tems.
ple copies.
7. Matching problem domains through software sys-
4. Statistical inference.
tems to particular machine architectures.
5. Sorting and searching.
8. Life cycle models of software projects.
6. Performance analysis
7. As supporting theory: cryptography.
6.3 Design
Major elements of design and experimentation in the
7.2 Abstraction
area of software methodology and tools are:
Major elements of abstraction in the area of databases
1. Specification languages (e.g., PSL 2, IMA JO), config- and information retrieval systems are:
uration management systems (e.g., in Ada APSE),
1. Models for representing the logical structure of data
and revision control systems (e.g., RCS, SCCS).
and relations among the data elements, including
2. Syntax directed editors, line editors, screen editors,
the relational and entity-relationship models.
and word processing systems.
2. Representations of files for fast retrieval, such as
3. Specific methodologies advocated and used in prac-
indexes, trees, inversions, and associative stores.
tice for software development; e.g., HDM and those
3. Methods for assuring integrity (consistency) of the
advocated by Dijkstra, Jackson, Mills, or Yourdon.
database under updates, including concurrent up-
4. Procedures and practices for testing (e.g., walk-
dates of multiple copies.
through, hand simulation, checking of interfaces be-
4. Methods for preventing unauthorized disclosure or
tween modules, program path enumerations for test
alteration and for minimizing statistical inference.
sets, and event tracing), quality assurance, and proj-
5. Languages for posing queries over databases of dif-
ect management.
ferent kinds (e.g., hypertext, text, spatial, pictures,
5. Software tools for program development and debug-
images, rule-sets). Similarly for information retrieval
ging, profiling, text formatting, and database manip-
systems.
ulation.
6. Models, such as hypertext, which allow documents
6. Specification of criteria levels and validation proce-
to contain text at multiple levels and to include
dures for secure computing systems, e.g., Depart-
video, graphics, and voice.
ment of Defense.
7. Human factors and interface issues.
7. Design of user interfaces.
8. Methods for designing very large systems that are
7.3 Design
reliable, fault tolerant, and dependable.
Major elements of design in the area of database and
information retrieval systems are:
7. DATABASE AND INFORMATION RETRIEVAL
SYSTEMS 1. Techniques for designing databases for relational,
This area deals with the organization of large sets of hierarchical, network, and distributed implementa-
persistent, shared data for efficient query and update. tions.
Fundamental questions include: What modeling con- 2. Techniques for designing database systems such as
cepts should be used to represent data elements and INGRES, System R, dBase III, and DB-2.
their relationships? How can basic operations such as 3. Techniques for designing information retrieval sys-
store, locate, match, and retrieve be combined into ef- tems such as LEXIS, Osiris, and Medline.
fective transactions? How can these transactions inter- 4. Design of secure database systems.
act effectively with the user? How can high-level quer- 5. Hypertext systems such as NLS, NoteCards, Interme-
ies be translated into high-performance programs? dia, and Xanadu.
What machine architectures lead to efficient retrieval 6. Techniques to map large databases to magnetic disk
and update? How can data be protected against unau- stores.
thorized access, disclosure, or destruction? How can 7. Techniques for mapping large, read-only databases
large databases be protected from inconsistencies due onto optical storage media-e.g., CD/ROM and
to simultaneous update? How can protection and per- WORMS.

January 1989 Volume 32 Number 1 Communications of the ACM 21

Report

8. AIRTIFICIAL INTELLIGENCE AND ROBOTICS 2. Techniques for expert systems in narrow domains
This area deals with the modeling of animal and hu- (e.g., Mycin, Xcon) and expert system shells that can
man (intelligent) behavior. Fundamental questions in- be programmed for new domains.
clude: What are basic models of behavior and how do 3. Implementations of logic programming (e.g,
we build machines that simulate them? To what extent PROLOG).
is intelligence described by rule evaluation, inference, 4. Natural language understanding systems (e.g., Mar-
deduction, and pattern computation? What is the ulti- gie, SHRDLU, and preference semantics).
mate performance of machines that simulate behavior 5. Implementations of neural networks and sparse dis-
by these methods? How are sensory data encoded so tributed memories.
that similar patterns have similar codes? How are 6. Programs that play checkers, chess, and other games
motor codes associated with sensory codes? What are of strategy.
architectures for learning systems, and how do those 7. Working speech synthesizers, recognizers.
systems represent their knowledge of the world? 8. Working robotic machines, static and mobile.

8.1 Theory 9. HUMAN-COMPUTER COMMUNICATION

Major elements of theory in the area of artificial intelli- This area deals with the efficient transfer of informa-
gence and robotics are: tion between humans and machines via various
human-like sensors and motors, and with information
1. Logic; e.g., monotonic, nonmonotonic, and fuzzy. structures that reflect human conceptualizations. Fun-
2. Conceptual dependency. damental questions include: What are efficient methods
3. Cognition. of representing objects and automatically creating pic-
4. Syntactic and semantic models for natural language tures for viewing? What are effective methods for re-
understanding. ceiving input or presenting output? How ca:n the risk of
5. Kinematics and dynamics of robot motion and world misperception and subsequent human error be mini-
models used by robots. mized? How can graphics and other tools be used to
6. The supporting areas of structural mechanics, graph understand physical phenomena through information
theory, formal grammars, linguistics, philosophy, stored in data sets?
and psychology.

9.1 Theory
8.2 Abstraction Major elements of theory in human-computer commu-
Major elements of abstraction in the area of artificial nication are:
intelligence and robotics are:
1. Geometry of two and higher dimensions including
1. Knowledge representation (e.g., rules, frames, logic) analytic, projective, affine, and computational
and methods of processing them (e.g., deduction, geometries.
inference). 2. Color theory.
2. Models of natural language understanding and natu- 3. Cognitive psychology.
ral language representations, including phoneme 4. The supporting areas of Fourier analysis, linear alge-
representations; machine translation. bra, graph theory, automata, physics, and analysis.
3. Speech recognition and synthesis, translation of text
to speech.
4. Reasoning and learning models; e.g., uncertainty, 9.2 Abstraction
nonmonotonic logic, Bayesian inference, beliefs. Major elements of abstraction in the area of human-
5. Heuristic search methods, branch and bound, con- computer communication are:
trol search.
1. Algorithms for displaying pictures including meth-
6. Machine architectures that imitate biological sys-
ods for smoothing, shading, hidden lines, ray tracing,
tems, e.g., neural networks, connectionism, sparse
hidden surfaces, transparent surfaces, shadows,
distributed memory.
lighting, edges, color maps, representations by
7. Models of human memory, autonomous learning,
splines, rendering, texturing, antialiasing, coherence,
and other elements of robot systems.
fractals, animation, representing pictures as hierar-
chies of objects.
8.3 Design 2. Models for computer-aided design (CAD).
Major elements of design and experimentation in artifi- 3. Computer representations of physical objects.
cial intelligence and robotics include: 4. Image processing and enhancement methods.
5. Man-machine communication, including psycholog-
1. Techniques for designing software systems for logic ical studies of modes of interaction that reduce hu-
programming, theorem proving, and rule evaluation. man error and increase human productivity.

22 Comnamications of the ACM January 1989 Volume 32 Number 1

 Report

9.3 Design 4. Graphics standards (e.g., GKS, PHIGS, VDI), graphics

Major elements of design and experimentation in the languages (e.g., PostScript), and special graphics
area of human-computer communication are: packages (e.g., MOGLI for chemistry).
Implementation of graphics algorithms on various 5. Implementation of various user interface techniques
graphics devices, including vector and raster dis- including direct manipulation on bitmapped devices
plays and a range of hardcopy devices. and screen techniques for character devices.
Design and implementation of experimental graphics 6. Implementation of various standard file interchange
algorithms for a growing range of models and phe- formats for information transfer between differing
nomena. systems and machines.
Proper use of color graphics for displays; accurate 7. Working CAD systems.
reproduction of colors on displays and hardcopy 6. Working image enhancement systems (e.g., at JPL for
devices. pictures received from space probes).

ACKNOWLEDGMENTS
Many people generously provided written comments in response to drafts of this report. Although it was not possible to
accommodate every comment in detail, we did take every comment into account in revising this report. We are grateful to the
following people for sending us their comments:
Paul Abrahams Richard Epstein J. Paul Myers
J. Mack Adams Frank Friedman Bob Noonan
Robert Aiken C. W. Gear Alan Perks
Donald Bagert Robert Glass Jesse Poore
Alan Biermann Nice Habermann Terrence Pratt
Frank Boesch Judy Hankins Jean Rogers
Richard Botting Charles Kelemen Jean Sammet
Albert Briggs, Jr. Ken Kennedy Mary Shaw
Judy Brown Elliot Koffman J. W. Smith
Rick Carlson Barry Kurtz Dennis Smolarski
Thomas Cheatham Doris Lidtke Ed Upchurch
Neal Coulter Michael Loui Garret White
Steve Cunningham Paul Luker Gio Wiederhold
Verlynda Dobbs Susan Merritt Stuart Zweben
Caroline Eastman John Motil

3. Denning, P. What is computer science? Am. Sci. 73 (Jan.-Feb. X985),

REFERENCES 16-19.
1. Abelson, H., and Sussman, G. Structure and interpretation of Computer 4. Flares, F., and Graves, M. Education. (working paper available from
Programs. MIT Press, Cambridge, Mass., 1985. Logonet, Inc., 2200 Powell Street, 11th Floor, Emeryville. Calif.
2. Arden. B., ed. See What Can Be Automated? Report of the NSF Com- 94608.)
puter Science and Engineering Research Study (COSERS). MIT 5. Newell, A., Perlis, A., and Simon, H. What is computer science? Sci.
Press, Cambridge, Mass., 1980. 157 (1967),1373-1374. (reprinted in Abacus 4, 4 (Summer 1987), 32.)

January 1989 Volume 32 Number 1 Communicationsof the ACM 23