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. A mathematician expects to iterate these steps (e.g., We are pleased to present a new intellectual frame- when errors or inconsistencies are discovered. work for our discipline and a new basis for our The second paradigm, abstraction (modeling), is rooted curricula. 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 An engineer expects to iterate these steps (e.g., when elaborate the core: computer science focuses on analy- tests reveal that the latest version of the system does sis and abstraction; computer engineering on abstrac- not satisfactorily meet the requirements). tion and design. The phrase discipline of computing is Theory is the bedrock of the mathematical sciences: used here to embrace all of computer science and applied mathematicians share the notion that science engineering. advances only on a foundation of sound mathematics. Two important issues are outside the charter of this Abstraction (modeling) is the bedrock of the natural task force. First, the curriculum recommendations in sciences: scientists share the notion that scientific prog- this report deal only with the introductory course se- ress is achieved primarily by formulating hypotheses quence. It does not address the important, larger ques- and systematically following the modeling process to tion of the design of the entire core curriculum, and verify and validate them. Likewise, design is the bed- indeed the suggested introductory course would be rock of engineering: engineers share the notion that meaningless without a new design for the rest of the progress is achieved primarily by posing problems and core. Second, our specification of an introductory systematically following the design process to construct course is intended to be an example of an approach to introduce students to the whole discipline in a rigorous systems that solve them. Many debates about the rela- tive merits of mathematics, science, and engineering and challenging way, an “existence proof” that our def- are implicitly based on an assumption that one of the inition of computing can be put to work. We leave it to 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,tageo f 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 distinct from one another because they represent sepa- theory: 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 d.iscipline 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. Certain affinity groups in which there is scientific Division into Subareas literature are not shown as subareas because they are We grappled at some length with the question of divid- basic concerns throughout the discipline. For example, ing the discipline into subareas. We began with a pref- parallelism surfaces in all subareas (there are parallel erence for a small number of subareas, such as model versu.s implementation, or algorithm versus machine. algorithms, parallel languages, parallel architectures, etc.) and in theory, abstraction, and design. !Similar con- However, the various candidates we devised were too clusions hold for security, reliability, and performance abstract, the boundaries between divisions were too fuzzy, and most people would not have identified com- evaluation. fortably with them. Computer scientists will tend to associate with the first two columns of the matrix, and computer engi- Then we realized that the fundamentals of the disci- neers with the last two. The full description of comput- pline are contained in three basic processes-theory, 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- Competence in the Discipline ify as a subarea, a segment of the discipline must satisfy The goal of education is to develop compete:nce in a four criteria: 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 engineering: lectures emphasize enduring principles work effectively with people in other disciplines to help 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 work protocols in functional layers. In the correspond- computing field is often deemphasized, leaving many 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 running times, or instal and test network interfaces and in business data processing, a domain in which most measure their packet throughputs. computing curricula do not seek to develop compe- Within this recommendation, the first courses in tence; whether computing departments or business de- computer science would not only introduce program- partments should develop that competence is an old ming, algorithms, and data structures, but introduce controversy. Discipline-oriented thinking must be based material from all the other subdisciplines as well. on solid mathematical foundations, yet theory is not an Mathematics and other theory would be well integrated integral part of most computing curricula. The standard into the lectures at appropriate points. practices of the computing field include setting up and We recommend that the introductory course contain conducting experiments, contributing to team projects, a rigorous, challenging survey of the whole discipline. and interacting with other disciplines to support their The physics model, exemplified by the Feynman Lec- interests in effective use of computing, but most curric- tures in Physics, is a paradigm for the introductory ula neglect laboratory exercises, team projects, or inter- course we envisage. disciplinary studies. We emphasize that simply redesigning the introduc- The question of what results should be achieved by 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 lum would be a serious mistake. The experience of analysis here. We do strongly recommend that this physics departments contains many lessons for comput- question be among the first considered in the design of ing departments in this regard. new core curricula for computing. 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 Communications of 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 coh.erence 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 empha.size 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 fra.mework 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, multiplicati.on, 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 1. Computability theory, which defines what machines 9. Human-Computer communication can and cannot do. Each has an underlying unity of subject matter, a sub- 2. Computational complexity theory, which tells how to measure the time and space requirements of com- stantial theoretical component, significant abstractions, 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 with sufficiently high probabilities much more effi- ments of theory and abstraction. For this reason, we 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 1.2 Abstraction some of the items go. Major elements of abstraction in the area of algorithms Our intention is to provide a guide to the discipline and data structures are by showing its main features, not a detailed map. It is 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 interpreters. 1. ALGORITHMS AND DATA STRUCTURES 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? 1.3 Design What is the best way to access the data? What is Major elements of design and experimentation in the the worst case of the best algorithms? How well do area of algorithms and data structures are: algorithms behave on average? How general are algo- 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 Communicationosf 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 document-processing functions such as c:reating of parsing and language translation. 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- strate that they work as intended despite errors and 2.2 Abstraction 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, message passing, 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