Below are the first 10 and last 10 pages of uncorrected machine-read text (when available) of this chapter, followed by the top 30 algorithmically extracted key phrases from the chapter as a whole.
Intended to provide our own search engines and external engines with highly rich, chapter-representative searchable text on the opening pages of each chapter. Because it is UNCORRECTED material, please consider the following text as a useful but insufficient proxy for the authoritative book pages.
Do not use for reproduction, copying, pasting, or reading; exclusively for search engines.
OCR for page 141
ADAPTING TO COMPUTER SCIENCE Saul Gorn University of Pennsylvania Introduction Although ~ am not an engineer who adapted himself to computer science but a mathematician who did so, ~ am familiar enough with the development, concepts, and activities of this new discipline to venture an opinion of what must be adapted to in it. "Computer and information science," known as "~nfonnatics" on the European continent, was born as a distinct discipline barely a generation ago. As a fresh young discipline, it is an effervescent mixture of formal dreary, empirical applications, and pragmatic design. Mathematics was just such an effervescent mixture in western culture mom the renaissance to the midge of the twenties century. It was Den Hat the dynamic effect of high speed, electronic, general purpose computers accelerated Be generalization of the mewing of the word "computation." This caused the early computer science to recruit not only mathematicians but also philosophers (especially logicians), linguists, psychologists, and economists, as well as physicists and a variety of engineers. Thus we are, perforce, discussing the changes and adaptations of individuals to disciplines and especially of people In one discipline to another. As we all know, the very word "discipline" indicates that there is an initial special effort by an individual to force himself or herself to change~to adapt one's perceptions to a special way of viewing certain aspects of the world and one's behavior in order to produce special results. For example, we are familiar with the enormous prosthetic devices that physicists have added to their natural sensors and perceptors in order to perceive minute particles and to smash atoms in order to do so (at, we might add, enormous expense and enormous stretching of computational activity). We are also familiar with the enormously intricate prosthetic devices mathematicians added to their computational effectors, the general symbol manipulators called computers. The disciplines require us, perhaps less dramatically but always more subtly, to change the way we understand, how we act, how we act in order to understand, what we 141
OCR for page 142
should understand in order to act, etc. The adaptation of a discipline over a penod of time is described by its history; this is sometimes slow, in the human scale, over Me millennia, and sometimes so fast for human beings as to be considered revolutionary, as in our two examples, or, more crucially, in the scientific revolutions whose structure was studied by Thomas S. Kuhn (19701. Because of this concern with adaptability of individuals and disciplines, it is useful to consider a rough taxonomy subdivision of disciplinary attitudes. Just as the individual's perception and behavior is a result of the flow of signals, one way from receptors to perceive and the other of commands to effecters to act, so are there two types of disciplinary signals; there are descnptions of aspects of the world, presented in declarative sentences, and there are prescriptions of what ought to be done about those aspects, In imperative sentences. Theones are logical or empirically organized systems of the former, and programs are organized systems of the latter. Some knowledge-oriented disciplines are mainly concerned with producing theories In what we might call their "object language," reserving their programmatic statements to the discussion of their methodology, in what we might call their "meta-language"; examples are pure mathematics (where We methodological language is that of logical programs) and the empirical sciences (where the methodological language is that of experimental programs). Other disciplines are mainly "ac~aon-oriented" and concerned with programs such as hunting, cooking, manufacturing, and constructing. Still other disciplines such as law, medicine, and eng~neenng-have as Weir purpose applying knowledge to achieve action. These last must be sensitive to bow He changes In knowledge and the changes In acavines; Hey therefore change more than the knowledge-onented and He act~on-onented disciplines they are bridging; and if one of these goes through a revolution, the connecting professional discipline may well follow suit. Changes in a profession caused by changes in the disciplines bridged tome the "professional change syndrome." A young discipline, like a young person, is an effervescent mixture of all die of the above-mentioned types of activity. Until the m~d-twentieth century, mathematics and physics were like this. Computer science is like this now. As time goes on, the action of perceiving for the discipline may disturb what is being perceived, especially if the perceiving and perceived elements are the same order of the magnitude; this was the case with particle physics and quantum mechanics, resulting in He indeterminacy principle. More generally, the knowledge-onented and action-onented aspects of the young discipline m11 conflict, putting the discipline Hugh a crisis and possibly a revolution. This has happened to mathematics. Engineering must adapt to both 142
OCR for page 143
the change in mathematics and the change in physics, two examples of the professional syndrome in engineering. Since the success of engineering-or engineering aspects of mathematics, physics, and computer science is measured by how many problems it solves, there is a further cause of change, what might be called the "solved problem syndrome." Here the result may be a standard technique that no longer belongs to the profession but is either relegated to the discipline that presented the action proble~for example, all of applied mathematics-or becomes a new separate discipline. In the case of engineering, an old example of the latter is plumbing. In transportation such results have been the train- "engineers", flight-"engineer", etc. Somewhat similar is the eng~neenng application of x-rays and electro-magnencs to medicine, resulting in radiology. The latter is still changing, having developed CAT-scans, PET-scans, magnetic resonance techniques, and, by another application of computer techniques, three-dimensional graphic imaging. To see how engineers must adapt to computer science, we wart first see how the engineering aspect of mathematics was originally computational. Then we will see how Hose computational aspects of mathematics developed to involve not only physical engineering but also psycho-linguistic aspects. This win lead us to enumerate the areas of computer science, each of which alone has a formal, an empirical, and a design aspect. Some of the formal aspects win be novel to engineers, adding to the mathematical background a computer engineer requires beyond the analytic background all engineers need; but all the design aspects will of course be eng~neenng-or~ented. What is more, so many of these design aspects will be not physical but, rather, psycho-lingu~stic and, hence, close enough to symbolic and human activities to be most novel to engineers. These we require the greatest adaptation. How Mathematics Separated into Pure, Applied, and Computational Because mathematics arose from the shepherd's need to count, the agricultural need for measurement and astronomical ~nforrnanon, arid the urban commercial need for both, calculation and geometric construction techniques are, of course, ancient. That summation of Pythagorean mathematics, the "elements" of Euclid, therefore contained those primitive programs, the constructions with straight-edge and compass, and those sophisticated verifications of the correctness of those programs, the formal geometric proofs. Euclid's 143
OCR for page 144
students could therefore inscribe in a circle regular polygons with 3, 4, 5, 6, 8, 10, 12, 15, 16, 20, etc., sides, thereby computing lengths-considerably more than agriculture required. Meanwhile He Greek, and later the Roman, worlds made mechanical use of counting boards (abaci) and counters (calculi) to do their counting and sums. However, it was not until the eighth century A.D. Hat the western world could begin to profit from the Hindu programming of numerical computation. It was then that Al Khowanzmi In the Arabic world made specific the algorithms of algebra; and it was only several hundred years later that the Arabs picked up the Hindu numeral notation itself it was therefore only in the renaissance that the numerical symbolism and its resulting algorithms came to be fully developed. But it already had gone beyond simple numerical calculation into algebraic and trigonometric calculations for astronomy as well as far corurnerce. Even so, the Arabic-~ndu numerical data structures and the corresponding algorithmic programs for addition and multiplication did not come into common use unto He eighteenth century! Thus, *am the renaissance until the mid-twenneth cent, at a leisurely but slowly accelerating pace, mathematicians kept expanding their symbolic notations via their algebraic expressions, number theoretic expressions and functional expressions, and computed expressions that were fonnal denvauves or exact solutions in terms of the elementary functions to differential and other functional equations. They were expanding their language of descriptive, implicit and prescriptive, explicitly programmed specifications. Solving equational problems meant converting from the first type (declarative) to the second (imperative) specification languages. Note that this was the reverse of the Euclidean verification of the imperative construction procedure by the declarative language of formal proofs mentioned before. At the same time that mathematicians were doing notational and computational innovation, they were simultaneously developing informal theory and applying both to physics and astronomy (these were the three types of activity mentioned in the in~oducuon). To name only a few in this development over the centuries, there were Vieta, Fermat, Descartes, Pascal, Newton, Leibnitz, Euler, the Bernouillis, Lagrange, Laplace, Cauchy, and Gauss. Interested not only in pure mathematics He fundamental theorem of algebra, number theory, and differential geometry but also in applied mathematics (astronomy and physics) and in symbolic invention and new extensions to computation-the congruence notation in number theory, algorithms for solving systems of linear equations, the method of least squares, and error statistics Gauss was a formidable calculator and programmer. In fact, it was his early developed theory of ruler and compass 144
OCR for page 145
construction, his specification of exactly which regular polygons could be so constructed, and his program for doing it specifically for the regular polygon with 17 sides (when he was 19 years old) that made him decide to become a mathematician rather than a linguist. Some of Gauss's predecessors had also been famous as philosophers Descartes, Pascal, and L`eibnitz, for example~oncerned with logic and the theory and practice of computation. For example, Leibnitz, on the one hand, invented the differential quotient and integral notations and infonnally derived the computational rules of the differential and integral calculus. On the other hand, he described a formal algebra of logical "and," "or," and "not" as well as predicted the future formal logical algebra that he called a "universal characteristic. " In any event, by the end of Me eighteenth century the informal concepts of "infinitesimal," "infinite summation," "continued," and "differentiability" became disturbingly paradoxical; and yet they had such fertile applications to physics that something had to be done to verify what could be verified in the symbolic procedures and to formalize them so as to safeguard them from paradoxical misuse. The whole nineteens century was occupied with this goal. This kind of problem was not new. The Pythagoreans had such great success in their reduction of measurements to counting, by the use of fractions, that they were confounded by the seeming paradox that the diagonal of a square could not be "rationally" related to the use of its side as a unit. The solution of this early mathematical crisis was the geometric theory of ratio and proportion and its application to the theory of similar triangles as given in the tenth book of Euclid; neater construction theories of the "real numbers" had to wait until the theories of Cantor, Dede~nd, and Weierstrass in the later half of the nineteenth century. The Pythagorean failure of the possibility of measuring by simple counting was only partly solved by the invention of fractions and real numbers. There still remained logical confusion in language; for example, Zeno's paradox of Achilles and the Tortoise not only concerned itself with an infinite series having a finite limit, but also muddied the water by setting up a confusing correlation of a particular linguistic description of the race between the two with the actual occurrence- the time taken to describe He race exactly had nothing to do with the tune taken to run it. The nineteenth century development of a formal logic even more severe than those employed by Aristotle and Euclid brought out more mathematical crises and logical paradoxes. For example, Boole in the early nineteenth century developed a symbolic calculus that he called "laws of thought." One such law, called "modus ponens," states that if we 145
OCR for page 146
have two declarative sentences, can them p and q, and if we know that the sentence p is true and also that the sentence of the form "if p is Rue, then so is q" is also true, then we can conclude that the sentence q is also true. Boole had a neat algebraic symbolization of this procedure, an algebraic expression: [p& (p->q) ->q]. This is, however, a functional expression in a Leibnitzian calculus of two-valued logic; it has the value T (for "true") for each of the four possible combinations of values T and F (for "false") that p and q can have. Such a function is called a tautology (i.e., always true). Lewis Carrot at the end of the century, in a paper caned "What the Tortoise said to Achilles," pointed out that to achieve the result of modus ponens would require not merely this tautology but also one that states that p and p->q, and it, [p& (p->) ->q] = Al, imply q that is, and further that A2 = [p& (p->q) & Al ->qJ, A3 = [p& (p->q) & Al & A2 ->qj, etc. other words, it takes an infinite number of these tautologies to achieve modus ponens. The law of thought, modus pollens, is not in the Boolean expression language; rather, it is a valid procedure In a prescriptive meta-language that Balks about the production of proofs in the Boolean object language. The tautologous symbolic expression had been designed to symbolize modus ponens, and the symbol was confused with what it symbolized. The tautology is no more a law of thought Han Be artist Magntte's picture of a pipe, which he entitled "this is not a pipe," is a pipe! In general, crises in mathematics were signaled by paradoxes. The paradoxes were usually resolved by finally recognizing that they were either (1) reductio all absurdum proofs that something did not exist or (2) reductio ad absurdum proofs that some goal was impossible to achieve by a finite means, or that mixing meta-language with object language caused us to confuse symbols with what was being symbolized. And even in the reducoo ad absurdum solutions, the main problem often was to find out what was presumed to exist but did not, or why it did not. For example, "the real number 2 is not rational" or "the number of prime numbers is not finite." Many of Be dramatic advances were due to lifting Be level of thinking by meta- inguisuc description, and by generalization at die meta-language level. For example, algebraic symbolization is a generalization into meta-language of Be object language of anthme~ac and analytic symbolization is a generalization into meta-language of Be algebraic language of an~metic functions (not all functions are algebraic or even 146
OCR for page 147
representable by infinite series of algebraic expressions). But Be symbolic procedures suggested at meta-language symbol level might not have valid meaning in the operations at object language level. The mixture of object language and meta-language is intuitively powerful but, like most powerful tools, is dangerously capable of misuse. This was why mathematics went even further than Euclid In carefully formalizing proofs. Archimedes and Euler intuitively handled infinite series correctly, but too many paradoxical operations, such as hidden divisions by zero in algebraic meta-language or its equivalent in continuity and differentiability discussions, made careful logic necessary. And then the paradoxes even turned up in the logic! Cantor, for example, gave a formal definition for two sets having the "same number of elements"; it was later used to give a formal definition of cardinal and ordinal numbers, even for infinite sets. He was able to show that there were just as many rational numbers between zero and one as there were natural numbers all told (i.e., that the rational numbers are countably infinite), a seeming paradox but not really one; and he capped this result with a reductio ad absurdurn proof by his "diagonal method" to show that the number of real numbers between zero and one is not countably infinite (i.e., has a larger infinity than the number of natural numbers). All this activity of fom~alizai~on to avoid paradoxes and contradictions was resulting in an extension of the Pythagorean program of reducing all mathematics to numbers; it was all being reduced to a formal theory of sets and then (by Frege and later by Whitehead and Russell) to formal logic itself, as foreseen by Leibn~tz. But, the logic itself emerged with dangerous paradoxes, beyond what Lewis Carroll had recently found In Boole's laws of thought. All this thinking about thinking and mixing meta-language with object languages seemed fraught with dangers due to self-referencing: He numbers of sets of numbers, sets of sets, etc. In fact Russell confounded Frege, immediately after Frege's publication with his famous paradox of "The set of all sets that are not members of themselves" (is it or is it not a member of itself ?!?!~. And some further paradoxes brought to the surface the relationships to language. For example, there was the Richard paradox, which first pointed out that Here could be only a countably infinite number of English phrases that specify functions of one natural number variable and then used Cantor's diagonal argument to show that this could not be true. And then there was Berry's paradox: "The least natural number not nameable in fewer than 22 syllables" is hereby named in 2 ~ syllables. Thus, by He beginning of the twentieth century, a larger and larger portion of mathematical activity was the axiomatization and presentation of mathematical theory in an even more rigid fom~alizanon than Euclid's elements. Called "pure mathematics." by Hilbert, it 147
OCR for page 148
axiomatized and presented a formal system that would cover all possible mathematical truths; any properly (i.e., mathematically) stated sentence in such a system would be formally provable or else formally contradictable. This optimistic program was formally proved to be unattainable toward the middle of the century; Godel showed that any sufficiently rich formal system was either inconsistent or incomplete in the sense that there would be statements within it that were undecidable (i.e., could neither be proved nor disproved). His proof was something like Richard's paradox, using a Cantorian diagonal argument on a formalization of a meta-language. About the same time, logicians were uncovering a number of undecidable questions and unsolvable problems by developing a number of equivalent theories of computation. All through the history of mathematics, Be word "computation" had been expanding its meaning. The formalization process of the nineteenth century accelerated it by including all the algebras, geometries, and logics. But it was the necessity to formalize the programming of computations caused by the inhuman speeds of the recent general purpose computers that made computation include all precisely specifiable symbol manipulation. Now general symbol manipulation includes the pragmatic effects of deliberate ambiguity caused by shifting interpretation-for example, between object language and meta-language. General computer programming must therefore include what mathematical logic programming must forbid. Again, the mathematical study of arithmetic is independent of the way numbers are represented; the computer program for addition depends not only on the particular computer type, but also on the number representation system used. There are so many pragmatic questions in computer theory, use, and design Mat Be area of computation and Be area of mathematics were pulled apart For a different reason, mainly what we called the "solved problem syndrome," applied mathematics also separated hum pure mathematics. By the middle of Be twentieth century, the applications of mathematics had spread to so many different disciplines that the spread was too vast for any single person's curriculum. The mathematical applications, once Be ma~emai~cal aspect of Weir disciplines had been precisely specified and handled, were relegated to the discipline of the application. A few universities were concerned wid1 a united applied mathematics group but, by and large, the discipline became restricted lo "pure mathematics." 148
OCR for page 149
How Computation Broadened its Scope and Developed a Close Relationship with Engineering, Logical Theory, and Psycho-linguistics Mechanical aids for counting became a necessity especially in urban cultures for example, around the Mediterranean in Hellenic and Roman times. And from Hose beginnings computation, like mathematics generally, developed in three interacting shanks: (~) The development of He physical aids and their psycho-linguistic aspects into machines; He physical aids development is the obvious engineering aspect, He psycho-linguistic the more subtle one; The theoretical aspect beginning with mathematics as a whole, but nay ng down to formal proofs, and then to formal logic itself; and Forming a spiral, the psycho-linguistic development of naming and specifying the data structures (at first, He number representation systems) and the expressions of the procedures for handling diem (their programs or algorithms). During the interacting development of these decree phases In computation, it was the expressions of the procedures that were turned into machines. For example, as mentioned before, in Hellenic and Roman times, counting and adding were facilitated by counting boards with lines on them for placing counters. These static devices, made mobile by Seedy calculating human fingers, were of two designs; d e first, a simpler design but more buoy, had room for 10 counters per line, while the second, a more compact one, had 5 counters per line, and intermediate lines designed for at most 2 counters to indicate the number of full hands of five fingers Hat had accumulated on the base lines. The descr~p~aon of the counting and adding procedures for the bulky counting board was, of course, much simpler. Me two types of Roman and Chinese abaci are further developments of these placid machines, where the lines are replaced first by slots and then by wires, and the counters are beaded in or on them vertically instead of being strung out horizontally; in the more compact type the intellllediate lines are vertically above the ones they relate to. The Roman symbolization of the total number counted on a board was a compact description of the picture on a compact board, using ~ and V for the first line and its associate, X and ~ for the second, C and D for He Gird, etc., and a reversing grammar to obtain extra compactness, IV for IIII, XL for XXXX, etc. The parsing of these number 149
OCR for page 150
representation phrases was fairly complicated in order to achieve compactness and representation on one line. The Hindu-Arabic symbolization especially when a symbol for an empty line, zero, was introduced-was a compact description of the bulkier abacus. This second phrase structure language used the position of the numeral to represent the position of the wire and thereby avoided the necessity of using a larger and larger alphabet for more and more wires. Moreover, the algorithm for addition in this language had a considerably simpler desa~pnon than did that for addinon In the Roman numeral phrase structure language. ~ It would seem that it took mankind 1,000 years to decide that the descriptive language for the bulkier machine was more useful. The algorithm for addition in the Arabic symbol system has a much simpler description as well as a need for only a finite alphabet. The 19-year-old Pascal assisted his tax-collecting father by designing a more mobile mechanical adding machine than Be abacus. It simulated in hardware the program for addinon in the Arabic system. And within a generation Leibnitz adapted the same technique to make the machine do multiplication, albeit with the vigorous help of the human hand (i.e., some software was still necessary). The explosion of functional equaaon-solving techniques in mathematics during He next 200 years made a more Gauss-like calculator desirable. At He beginning of the nineteenth century, Charles Babbage felt that all function table construction should be made mechanically and automatically, and he spent some decades designing a "difference engine" that would do the job. He was also convinced that a device similar to He cards condoning a Jacquard loom In textile weaving could be used to allow He descnpnons of many procedures to serve as different programs in one and the same "analytic engine." Although his mechanization ambitions were defeated because technology was not advanced enough to standardize the necessary parts' these ambitions were prophetic enough to anticipate HoDenth's punched card machines at the end of the century and the electromechanical relay machines of Konrad Zuse, Howard Aiken, and George Stibitz 100 years after his lame. In effect, Babbage had invented the concept of prog~r~ng general purpose 1Because the natural numbers form a simple chain, the same linguistic expressions, the number namers, serve the double purpose of being enumerators while the counting pond summarizers when counting ends. When we want to stress this difference, we use ordinal language instead of cardinals; their isomorphism is a deep property of finite natural enumeration. This isomorphism is lost in both infinite cardinals versus ordinals and in "tree names" as ag unst "tree addresses" in ramified slouches such as decision trees, family trees, classification systems, or organization charts. 150
OCR for page 151
calculating machines and the idea of programming languages for the specification of how to sun numerical algorithms. His message was kept alive not only by the designers of machines In the 1940s and 'SOs of this century in the United States and Britain and onto the European continent, including the Russian mathematicians and engineers following Tchebycheff, but also by the logicians in the 1930s, Yes, and 'SOB. These latter developed a general theory of computation even before electronics took over. We therefore return to the portion of He history of mathematics where an extension of He concept of computation was occurring in the nineteenth century. We have already noted that following Al Khowanzmi a meta-language for anthmetic, namely algebra, appeared and flourished. The solution of algebraic equations as explicit functions of their coefficients was sought. Where the solutions were Impossible In the number systems already available, new extensions to the number concept were invented. We have already remarked on this happening when the Pythagoreans had to deal with that anachronism of the future, x2 = 2 . Then, through the Renaissance, it resulted in the invention of the next imaginary class, the negative numbers, yielding the solution to all equations of the form ax + b = 0, except, of course, for a = 0. Then a unified solution to all quadratic equations-ax2 + bx + c = Was found as a function of a, b, and c, provided the invention of numbers was extended to include another imaginary class, first called imaginary numbers and finally accepted as the "complex numbers"; and the unified solution called for addition, subtraction, multiplication, division, and, die Pythagorean crisis having long been understood (?), the operation of taking a square root. The program, or algonthm for the construction of He solutions, was presented explicitly in an algebraic fonn. What could be said about all algebraic equations? Gauss finally proved that Complex numbers would suffice to solve them, but not by an algebraic formula. (We would now say that "the complex number system is algebraically closed") By his time the construction of the solution by addition, subtraction, multiplication, division, and the extraction of roots had been achieved for degrees 3 and 4, and no more. It was then that Galois, by studying the effect of permuting the roots of an equation, discussed the algebraic systems called groups. He found that those and only those equations were "solvable by radicals" whose Galois group has a certain restncted stn~cture; and he further found that the general algebraic equation of degree greater than or equal to five did not have this structure, called, incidentally, "solvability." Thus another condition for solvability and unsolvability emerged, as had those that prompted the invention of extensions to the number system, or Gauss's condition for solvability by straight-edge and compass construction. 151
OCR for page 160
Penzias, A. 1989. Ideas and Information~anaging in a High-Tech World. New York: W. W. Norton. Pullam, I. M. 1968. The History of the Abacus. London: Hutchinson & Company. Ralston, A. 1971. Introduction to Programming & Computer Science. New York: McGraw-Hill. Randell, B. (ed.~. 1975. The Origins of Digital Computers; Selected Paper. New York: Spr~nger-Veriag. Shelley, G. B., and T. I. Cashman. 1984. Computer Fundamentals for an Infonnation Age. Brea, CA: Anaheim Publishing Company. Wood, D. 1987. Theory of Computation. New York: Harper & Row. 160
OCR for page 161
APPENDIX A COMPUTING AS A DISCIPLINE The final report of the Task Force on the Core of Computer Science presents a new intellectualframeworkfor the discipline of computing and a new basisfor computing cwric~a. This report has been endorsed and approvedfor release by the ACM Education Bond. Peter J. Denning (Chairman), Douglas E. Comer, David Gries, Michael C. Mulder, Allen Tucker, A. Joe Turner, and Paul R. Young APPENDIX A DEFINITION OF COMPUTING AS A DISCIPLINE Computer science and engineering is the systematic study of algorithmic processes - their theory, analysis, design, efficiency, implementation, and application - that describe and transform information. The fundamental question underlying all of computing is, What can be (efficiently) automated [2.31. This discipline was born in the early 1940s with the joining together of algorithm theory, mathematical logic, and the invention of the awed-program electronic computer. The roots of computing extends deeply into mathematics and engineering. Mathematics imparts analysis to the field: engineering imparts design. The discipline embraces its own theory, experimental method, and engineering, in contrast with most physical sciences, which are separate from the engineering disciplines that apply their findings (e.g., chemistry and chemical engineering principles). The science and engineering are inseparable because of the fundamental interplay between the scientific and engineering paradigms within the discipline. For several thousand years, calculation has been a principal concern of mathematics. Many models of physical phenomena have been used to derive equations whose solutions yield predictions of those phenomena - for example, calculations of orbital trajectories, weather forecasts, and fluid flows. Many general methods for solving such equations have been devised - for example, algorithms for systems of linear equations, differential equations, and integrating functions. For almost the same period, calculations that aid in the design of mechanical systems have been a principal concern of engineering. Examples include algorithms for evaluating stresses in static objects, calculating moments of moving objects, and measuring 161 distances much lamer or smaller than our immediate perception. One product of the long interaction between engineenng and mathematics has been mechanical aids for calculating. Some surveyors' and navigators' instruments date back a thousand years. Pascal and Leibniz built arithmetic calculators in the middle 1600s. In the 1930s Babbage conceived of an "analytical engine" Eat could mechanically and without error evaluate logarithms, trigonometric functions and other general arithmetic functions. His machine, never completed, served as an inspiration for later work. In the 1920, Bush constructed an electronic analog computer for solving general systems of differential equations. In the same period, electromechanical calculating machines capable of addition, subtraction, multiplication, division, and square root computation became available. The electronic flip-flop provided a natural bridge from these machines to digital versions with no moving parts. Logic is a branch of mathematics concerned with criteria of validity of inference and formal principles of reasoning. Since the days of Euclid, it has been a tool for rigorous mathematical and scientific argument. In the 19th century a search began for a universal system of logic that would be free of the incompletenesses observed in known deductive systems. In a complete system, it would be possible to determine mechanically whether any given statement is either true or false. In 1931, Godel published his 'incompleteness theorem," showing that there is no such system. In the late 1930s, Turing explored the idea of a universal computer that could simulate any step-by-step procedure of any other computing machine. His findings were similar to Godel's: some well
OCR for page 162
. defined problems cannot be solved by any mechanical procedure. Logic is important not only because of its deep insight into the limits of automatic calculation, but also because of its insight that strings of symbols, perhaps encoded s numbers, can be interpreted both as data and as programs. This insight is the key idea that distinguishes the stored program computer from calculating machines. The steps of the algorithm are encoded in a machine representation and stored in the memory for later decoding and execution by the processor. The machine code can be derived mechanically from a higher-level symbolic.form, the programming language. It is the explicit and intricate intertwining of the ancient threads of calculation and logical symbol manipulation, together with the modern threads of electronics and electronic representation of information that gave birth to the discipline of computing. We identified nine subareas of computing: 1. Algorithms and data structures 2. Programming languages 3. Architecture 4. Numencal and symbolic computation 5. Operating systems 8. Software methodology and engineering 7. Databases and information retrieval 8. Ar~cial intelligence and robotics 9. Human-Computer communication Each has an underlying unity of subject matter, a substantial theoretical component, significant abstractions, and substantial design and implementation issues. Theory deals with the underlying mathematical development of the subarea and includes supporting theory such as graph theory, combinatorics, or fonnal languages. Abstraction (or modelling) deals with models of potential unplementations; the models suppress detail, while retaining essences features, and provide means for predicting future behavior. Design deals with he process of specifying a problem, deriving requirements and specifications, iterating and testing prototypes, and implementing a system. Design includes the experimental method, which in computing comes in several styles: measuring programs and systems, validating hypotheses, and prototyping to extend abstractions to practice. Although software methodology is essentially concerned with design, it also contains substantial elements of theory and abstraction. For this reason, we have identified it as a subarea. On the other hand, parallel and distributed computation are issues that pervades all the subareas and all their components (theory, abstraction, and design); they have been identified neither as subareas nor as subareas components. The subsequent numbered sections provide the details of each subareas in three parts--- theory, abstraction, and design. The boundaries between theory and abstraction, and between abstraction and design are necessarily fuzzy; it is a maker of personal taste where some of the items go. Our intention is to provide a guide to the discipline by showing its main features, not a detailed map. It is important to remember that this guide to the discipline is not a plan for a course or a curriculum; it is merely a framework in which a curriculum can be designed. It is also important to remember that this guide to the discipline is a snapshot of an organism undergoing constant change. It will require reevaluation and revision at regular intervals. 1. ALGORITHMS AND DATA STRUCTURES This area deals with specific classes of problems and their efficient solutions. Fundamental questions include: For given classes of problems and their efficient solutions. Fundamental questions include: For given classes of problems, what are the best algorithms: How much storage and time do they require? What is the tradeoff between space and time? What is the worst case of the best algorithms? How well do algorithms behave on average? How general are algorithms-i.e., what classes of problems can be dealt with by similar methods? 1.1 Theory Major elements of theory in the area of algorithms and data structures are: 1. Computability theory, which defines what machines can and cannot do. 2. Computational complexity theory, which tells how to measure the time and space requirements of computable functions and relates a problem's size with the best- or worst-case performance of algorithms that solve that problem, and provides methods for proving lower bounds on any possible solution to a problem. Time and space bounds for algorithms and classes of algorithms. 40 Levels of intractability: for example, classes of problems solvable deterministically in polynomially bounded time (P-problems); those solvable nondeterministically in 162
OCR for page 163
polynomially bounded time (NP-problems); and those solvable nondeterministically in polynomially bounded time (NP-problems); and those solvable efficiently by parallel machines (NC-problems). Parallel computation, lower bounds, and mappings from dataflow requirements of algorithms into communication paths of machines. 6. Probabilistic algorithms, which give results correct with sufficiently high probabilities much more efficiently (in time and space) than determinate algorithms that guarantee their results. Monte Carlo methods. 7. Cryptography. 8. The supporting areas of graph theory, recursive functions, recurrence relations, combinatorics, calculus, induction, predicate and temporal logic, semantics, probability, and statistic. 1.2 Abstraction Major elements of abstraction in the area of algorithms and data structures are: 1. Efficient, optimal algorithms for important classes of problems and analyses for best, worst and average performance. 2. Classifications of the effects of control and data structure on time and space requirements for venous classes of problems. 3. Impmant classes of techniques such as divide-and conquer, Greedy algorithms, dynamic programming, finite state machine interpreters, and stack machine interpreters. Parallel and distributed algorithms; methods of partitioning problems into tasks Hat can be executed in separate processors. 1.3 Design Major elements of design and experimentation in the area of algorithms and data structures are: 1. Selection, implementation, and testing of algorithms for important classes of problems such as searching, sorting, random-number generation, and textual pattern matching. 2. Implementation and testing of general methods applicable across many classes of problems, such as hashing, graphs, and trees. Implementation and testing of distributed algorithms such as network protocols, distributed data updates, semaphores, deadlock detectors and synchronization methods. 163 4. Implementation and testing of storage managers such as garbage collection, buddy system, lists, tables, and paging. 5. Extensive experimental testing of heuristic algorithms for combinatorial problems. 6. Cryptographic protocols that permit secure authentication and secret communication. 2. PROGRAMMING LANGUAGES This area deals with notations for virtual machines that execute algorithms, with notations for algorithms and data, and with efficient translations from high-level languages into machine codes. Fundamental questions include: What are possible organizations of the virtual machine presented by the language (data types, operations, control structures, mechanisms for introducing new types and operations)? How are these abstractions implemented on computers? What notation (syntax) can be used effectively and efficiently to specify what the computer should do? 2.1 Theory Major elements of theory in the area of programming languages are: 1. Fonnal languages and automata, including theories of parsing and language translation. Turing machines (base for procedural languages), Post Systems (base for string processing languages), l-calculus (base for functional languages). 3. Formalsemantics: methods for defining mathematical models of computers and the relationships among the models, language syntax, and implementation. Primary methods include denotational, algebraic, operational and axiomatic semantics. 4. As supporting areas: predicate logic, tempom1 logic, modern algebra and mathematical induction. 2.2 Abstraction Major elements of abstraction in the area of pro~nming languages include: 1. Classification of languages based on their syntactic and dynamic semantic models; e.g., static typing, dynamic typing, functional, procedural, object-oriented, logic, specification, message passing, and dataflow. 2. Classification of languages according to intended application area; e.g., business data processing, simulation, list processing, and graphics.
OCR for page 164
Classification of major syntactic and semantic models for program structure; e.g., procedure hierarchies, functional composition, abstract data types, and communicating parallel processes. 4. Abstract implementation models for each major type of language. 5. Methods for parsing, compiling, interpretation, and code optimization. 6. Methods for automatic generation of parsers, scanners, compiler components, and compilers. 2.3 Design Major elements of design and experimentation in the area of programming languages are: 1. Specific languages that bring together a particular abstract machine (semantics) and syntax to fonn a coherent implementable whole. Examples: procedural COBOL, FORTRAN, ALGOL, Pascal, Ada, C), functional (LISP), dataflow (SISAL, VAL), object-oriented (SmalltaLt`, CLU), logic (Prolog), strings (SNOBOL), and concurrency (CSP, Occam, Concurrent Pascal, Modula 2~. 2. Specific implementation methods for particular classes of languages: n~n-time models, static and dynamic execution methods, typing checking, storage and register allocation, compilers, cross compilers, and interpreters, systems for fading parallelism in programs. 3. Programming environments. 4. Parser and scanner generators (e.g., YACC, LEX), compiler generators. 5. Programs for syntactic and semantic error checking, profiling, debugging, and Racing. 6. Applications of programming-language methods to document-processing functions such as creating tables, graphs, chemical formulas, spreadsheets equations, input and output, and data handling. Other applications such as statistical processing. 3. ARCHITECTURE This area deals with methods of organizing hardware (and associated software3 into efficient, reliable systems. Fundamental questions include: What are good methods of implementing processors, memory, and communication in a machine? How do we design and control large computational systems and convincingly demonstrate that they work as intended despite errors and failures? What types of architectures can efficiently incorporate many processing elements that can wow concurrently on a computation? How do we measure performance? 3.1 Theory Major elements of theory in the area of architecture are: 1. Boolean algebra 2. Switching theory. 3. Coding theory. 4. Finite state machine theory. 5. The supporting areas of statistics, probability, queueing, reliability theory, discrete mathematics, number theory, and arithmetic in different number systems. 3.2 Abstraction Major elements of abstraction in the area of architecture are: 1. Finite state machine and Boolean algebraic models of circuits that relate function to behavior. 2. Other general methods of synthesizing systems from basic components. 3. Models of circuits and finite state machines for computing arithmetic functions over finite fields. 4. Models for data path and control struck. 5. Optimizing instruction sets for various models and workloads. 6. Hardware reliability: redundancy,e~ror detection, recovery, and testing. 7. Space, time, and organizational tradeoffs in the design of VLSI devices. 8. Organization of machines for various computational models: sequential, dataflow, list processing, array processing, vector processing, and message-passing. 9. Identification of design levels; e.g., configuration, program, instruction set, register, and gate. 3.3 Design Major elements of design and experimentation in the area of architecture are: 2. 3. 164 1. Hardware units for fast computation; e.g., arithmetic function units, cache. The so called van Neumann machine (the single-ins~uciion sequence stored program computer); RISC and CISC implementations. Efficient methods of storing and recording information, and detecting and correcting errors.
OCR for page 165
4. Specific approaches to responding ~ errors; 3. recovery, diagnostics, reconf~guraiion, and backup Cures. 5. Computer aided design (CAD) systems and logic simulations for the design of VLSI circuits. Production programs for layout, fault duagnosis. Silicon compilers. 6. Implementing machines in venous computational models; e.g., dataflow, Bee, LISP, hypercube, vector, and multiprocessor. 7. Supercomputers, such as the Cray and Cyber machines. 4. NUMERICAL AND SYMBOLIC COMPUTATION This area deals with general methods of efficiently and accurately soling equations resulting from mathematical models of systems. Fundamental questions include: How can we accurately approximate continuous or inDmite processes by finite discrete processes? How do we cope with the errors arising from these approximations? How rapidly can a given class of equations be solved for a given level of accuracy? How can symbolic manipulations on equations, such as integration, differentiation, and reduction to minimal teens, be carried out? How can He answers to these questions be incorporated into efficient, reluable, high~uality mathematical software packages? 4.1 Theory Major elements of theory in the area of numerical and symbolic computation are: 1. Number theory. 2. Linear algebra 3. Numerical analysis. 4. Nonlinear dynamics. 5. The supporting arms of calculus, real analysis, complex analysis, and algebra 4.2 Abstraction Major elements of abstraction in the area of numerical and symbolic computation are: 1. Formulations of physical problems as models in continuous (and sometimes discrete3 mathematics. 2. Discrete approximations to continuous problems. In this context, backward error analysis, error propagation and stability in the solution of linear and nonlinear systems. Special methods in special cases, such as Fast Fourier Transform and Poisson solvers. 165 Me finite element model for a large class of problems specifiable by regular meshes and boundary values. Associated iterative methods and convergence theory; direct, implicit, multifolds, rates of convergence. Parallel solution methods. Automatic and refinement during numerical integration. 4. Symbolic integration and differentiation. 4.3 Design Major elements of design and experimentation in the area of numerical and symbolic computation are: 1. High-level problem formulation systems such as CHUM and WEB. Specific libraries and packages for linear algebra, ordinary differential equations, statistics, nonlinear equations, and optimizations; e.g., LINPACK, EISPEACK, ELLPACK. Methods of mapping finite element algorithms to specific architectures~.g., multigrids on hypercubes. 4. Symbolic manipulators, such as MACSYMA and REDUCE, capable of powerful and nonobvious manipulations, notably differentiations, integrations, and reductions of expressions to minimal teens. 5. OPERATING SYSTEMS This area deals with control mechanisms that allow multiple resources to be efficiently coordir~i in the execution of programs. Fundamental questions include: What are the visible objects and permissible operations at each level in the operation of a computer system? For each class of resource (objects visible at some level), what is a minimal set of operations that permit their effective use? How can interfaces be organized so that users deal only with abstract versions of resources and not with physical details of hardware? What are effective control s~egies for job scheduling, memory management, communication among concurrent tasks, reliability, and security? What are the principles by which systems can be extended in function by repeated application of a small number of construction rules? How should distributed computations be organized so that many autonomous machines connected by a communication network can participate in a computation, with the details of network protocols, host locations, band-widths, and resource naming being mostly invisible?
OCR for page 166
5.1 Theory Major elements of theory in the area of operating systems are: 3. Concurrency theory; synchronization, det~ninacy, and deadlocks. Scheduling theory, especially processor scheduling. Program behavior and memory management theory, including optimal policies for storage allocation. 4. Performance modeling and analysis. 5. The supporting areas of bin packing, probability, queueing theory, queueing networks, communication and information theory, temporal logic, and cryptography. Abstraction Major elements of abstraction in the area of operating systems are: 2. 5. Abstraction principles that permit users to operate on idealized versions of resources without concern for physical details (e.g., process rather than processor, virtual memory rather than main-seconda~y hierarchy, files Other than disks). Binding of objects perceived at the user interface to internal computational structures. Models for important subproblems such as process management, memory management, job scheduling, secondary storage management, and performance analysis. 4. Models for distributed computation; e.g., clients and servers, cooperating sequential processes, message-passing, and remote Verdure cans. Models for secure computing; e.g., access controls, authentication, and · . communication. a. Networking, including layered protocols, naming, remote resource usage, help services, and local network protocols such as token-passing and shared buses. 5.3 Design Major elements of design and experimentation in the area of operating systems are: 1. 1. Prototypes of time sharing systems, automatic storage allocators, multilevel schedulers, memory managers, hierarchical file systems and other important system components that have served as bases for commercial systems. 2. Techniques for building operating systems such as UNIX, Multics, Mach, VMS, and MS-DOS. 3. Techniques for building libraries of utilities; e.g., editors, document formatters, compilers, linkers, and device drivers. 4. Files and file systems. 5. Queueing network modeling and simulation packages to evaluate perfonnance of real systems. 6. Network architectures such as ethernet, FDDI, token ring nets, SNA, and DECNET. 7. Protocol techniques embodied in the Department of Defense protocol suite (TCP/1P), virtual circuit protocols, interned real time conferencing, and X.25. 6. SOFTWARE METHODOLOGY AND ENGINEERING This area deals with the design of programs and large software systems that meet specifications and are safe, secure, reliable, and dependable. Fundamental questions include: What are the principles behind the development of programs and programming systems? How does one prove that a program or system meets its specifications? How does one develop specifications that do not omit important cases and can be analyzed for safety? How do software systems evolve through different generations? How can software be designed for understandability and modifiability? 6.1 Theory Major elements of theory in the area of software methodology and tools are: 1. Program verification and proof. 2. Temporal logic. 3. Reliability theory. 4. The supporting areas of predicate calculus. axiomatic semantics, and cognitive psychology. 6.2 Abstraction Major elements of abstraction in the area of software methodology and tools are: Specification methods, such as predicate transformers, programming calculi, abstract data types, and Floyd-Hoare axiomatic notations. 2. Methodologies such as stepwise refinement, modular design, modules, separate compilation, information-hiding, dataflow, and layers of abstraction. 166
OCR for page 167
s 3. Methods for automating program development; e.g., text editors, syntax- directed editors, and screen editors. Methodologies for dependable computing; e.g., fault tolerance, security, reliability, recovery, N -version programming, multiple-way redundancy, and check- poiniing. Software tools and programming environments. 6. Measurement and evaluation of programs and systems. 7. Matching problem domains through software systems to particular machine architectures. 8. Life cycle models of software projects. 6.3 Design Major elements of design and experimentation in the area of software methodology and tools are: 1. Specification languages (e.g., PSL 2, IMA JO), configuration management systems (e.g., in Ada APSE), and revision control systems (e.g., RCS, SCCS). 2. Syntax directed editors, line editors, screen editors, and word processing systems. 3. Specific methodologies advocated and used in practice for software development; e.g., HDM and those advocated by DiJ~St=, Jackson, Mills, or Yourdon. 4. Procedures and practices for testing (e.g., waLic-through, hand simulation, checking of interfaces between modules, program path enumerations for test sets, and event tracing), quality assurance, and project management. 5. Software tools for program development and debugging, profiling, text formatting, and database manipulation. 6. Specification of criteria levels and validation procedures for secure computing systems, e.g., Department of Defense. 4. 7. Design of user interfaces. X. Methods for designing very large systems that are reliable, fault tolerant, and dependable. 7. DATAB ASK AND INFORMATION RETRIEVAL SYSTEMS This area deals with the organization of large sets of persistent, shared data for efficient query and update. Fundamental questions include: What modeling concepts should be used to represent data elements and their relationships? How can basic operations such as store, locate, match, and retrieve be combined into effective transactions? How can these transactions interact effectively 167 with the user? How can high-level queries be translated into high-performance programs? What machine architectures lead to efficient retrieval and update? How can data be protected against unauthorized access, disclosure, or destruction? How can large databases be protected from inconsistencies due to simultaneous update? How can protection and performance be achieved when the data are distributed among many machines? How can text be indexed and classified for efficient retrieval? 7.1 Theory Major elements of theory in the area of databases and inforrnanon retrieval systems are: 1. Relational algebra and relational calculus. 2. Dependency theory. 3. Concurrency theory, especially serializable nsacuons, Cocks, and synchronized updates of multiple copies. 4. Statistical inference. 5. Sorting and searching. 6. Performance analysis. 7. As supporting theory; cryptography. 7.2 Abstraction Major elements of abstraction in the area of databases and information retrieval systems are: 1. Models for representing the logical structure of data and relations among the data elements, including the relational and entity- relationship models. 2. Representations of files for fast retrieval, such as indexes, trees, inversions, and associative stores. 3. Methods for assuring integrity (consistency) of the data base under updates, including concurrent updates of multiple copies. Methods for preventing unauthorized i~loSure or alteration and for minimizing statistical inference. 5. Languages for posing queries over databases of different kinds (e.g., hypertext, text, spatial, pictures, images, rule-sets). Similarly for information retrieval systems. 6. Models, such as hypertext, which allow documents to contain text at multiple levels and to include video, graphics, and voice. 7. Human factors and interface issues. 7.3 Design Major elements of design in the area of database and infonnanon retrieval systems are:
OCR for page 168
4. s 1. Techniques for desigrung databases for relational, hierarchical, network, and distributed implementations. Techniques for designing database systems such as INGRES, System R. dBase III, and DB-2. a. Techniques for designing information retrieval systems such as LEXIS, Osiris, and Medline. Design of secure database systems. Hypertext systems such as NLS, NoteCards, Intermedia, and Xanadu. 6. Techniques to map large databases to magnetic disk stores. 7. Techniques for mapping large, read-only databases onto optical storage media e.g., CD/ROM and WORMS. a. ARTIFICIAL INTELLIGENCE AND ROBOTICS This area deals with the modeling of animal and human (intelligent) behavior. Fundamental questions include: What are basic models of behavior and how do we build machines that simulate them? To what extent is intelligence described by rule evaluation, inference, deduction, and pattern computation? What is the ultimate performance of machines that simulate behavior by these methods? How are sensory data encode so that similar patterns have similar codes? How are motor codes associated with sensory codes? What are architectures for learning systems, and how do those systems represent their knowledge of the world? 8.1 Theory Major elements of theory in the area of aruf~cial intelligence and robotics are: 1. Logic, e.g., monotonic, nonmonotonic, and filzzy. 2. Conceptual dependency. 3. Cognition. 4. Syntactic and semantic models for natural language understanding. 5. Kinematics and dynamics of robot motion and world models used by robots. 6. The supporting areas of structural mechanics, graph theory, formal grammars, linguistics, philosophy, and psychology. S.2 Abstraction Major elements of abstraction in the area of artificial intelligence and robotics are: Knowledge representation (e.g., rules, frames, logic) and methods of processing them (e.g., deduction, inference). 2. Models of nab language understanding and natural language representations, including phoneme representations; machine translation. 3. Speech recognition and syntheses, translation of text to speech. 4. Reasoning and learning models; e.g., uncertainty, nonmonomnic logic, Bayesian inference, beliefs. 5. Heuristic search methods, branch and bound, control search. 6. Machine architectures that imitate biological systems, e.g., neural networks, connectionism, sparse distributed memory. Models of human memory, autonomous learning, and other elements of robot systems. 8.3 Design Major elements of design and experimentation in artificial intelligence and robotics include: 2. 1. Techniques for designing software systems for logic programming, theorem proving, and rule evaluation. Techniques for expert systems in narrow domains (e.g., Mycin, Xcon) and expert system shells that can be programmed for new domains. 3. Implementations of logic programming (e.g., PROLOG). 4. Natural language understanding systems (e.g., Margie, SHRDLU, and preference semantics). 5. Implementations of neural networks and sparse distributed memories. 6. Programs that play checkers, chess, and other games of strategy. 7. Working speech synthesizers, recognizers. S. Working robotic machines, static and mobile. 9. HUMAN-COMPUTER COMMUNICATION This area deals with the efficient transfer of information between humans and machines via various human-like sensors and motors, and with information structures that reflect human conceptualizations. Fundamental questions include: What are efficient methods of representing objects and automatically creating pictures for viewing? What are effective methods for receiving input or presenting output? How can the risk of misperception and subsequent 168
OCR for page 169
human error be minimized? How can graphics and other tools be used to understand physical phenomena through information stored in data sets? 9.1 Theory Major elements of theory in human-computer communication are: 1. Geometry of two and higher dimensions including analytic, projective, Refine, and computational geometries. 2. Color theory. 3. Cognitive psychology. 4. The supporting areas of Fourier analysis, linear algebra, graph theory, automats, physics, and analysis. 9.2 Abstraction Major elements of abstraction in the area of human-computer communication are: 1. Algorithms for displaying pictures including methods for smoothing, shading, hidden lines, ray Hacing, hidden surfaces, Dansparent surfaces, shadows, lighting, edges, color maps, representations by splines, rendering, textunng, antialiasing, coherence, fractals, anuma~on, representing pictures as hierarchies of objects. 2. Models for computer-sided design (CAD). 3. Computer representations of physical objects. 4. Image processing and enhancement methods. 5. Man-machine communication, including psychological studies of modes of interaction that reduce human error and increase human . productivity. 9.3 Design Major elements of design and expenmenwion in the area of human-compu~ communication are: 1. Implementation of graphics algorithms on various graphics devices, including vector and raster displays and a range of hardcopy devices. 2. Design and implementation of experunental graphics algorithms for a growing range of models and phenomena 3. Proper use of color graphics for displays; accurate reproduction of colors on displays and hardcopy devices. 4. Graphics standards (e.g., GKS, PEGS, VDI), graphics languages (e.g., PostScript), and special graphics packages (e.g., MOGLI for chemistry). 5. Implementation of various user interface techniques including direct manipulation on bitmapped devices and screen techniques for character dlevK:es. Implementation of various shard file interchange formats for information transfer between differing systems and machines. 7. Working CAD systems. 8. Worlcing image enhancement systems (e.g., at JPL for picas received from space probes). ACKNOWLED GMENTS Many people generously provided written comments in response to drafts of this report Although it was not possible to accommodate every comment in deml, we did take every comment into account In revising . . . ~ ~ ·. · . ~ . .. . this report. we are grateful to ule tollowmg people Ior senamg us user comments: Paul Ab~a~ms J. Mack Adams Robert Aiken Donald Bagert Alan Blomann Frank Bonach Richard Bouing Albert Briggs, Jr. Judy Brown Rick Carlson Thomas Cheatharn Neal Coulter Steve Cunningham Verlynda Dobbs Caroline Easunan Richard Epstein Funk Friedman C. W. Gear Robert Glass Nico Habennann Judy Hankins Charles Keleman Ken Kennedy Elliot Koffman Barry Kurtz Dons Lidlce Michael Loci Paul Lalcer Susan Merritt John Moti 169 J. Paul Myers Bob Noonan Alan Portis Jesse Poore Thence Pratt Jean Rogers Jean Sammet Mary Shaw J.W. Smith Dennis Smolarski Ed Upchurch Garret White Gio Wiederfield Stuart Zweben
OCR for page 170
References 1. Abelson, M., and Sussman, G. Structure and Interpretation of Computer Programs. MIT Press, Cambridge, Mass., 1983 2. Arden, B., ed. See What Can Be Automated? Report of the NSF Computer Science and Engineering Research Study (COSERS). MIT Press. Cambridge, Mass., 1980. 3. Denning, P. What is computer science? Am. Sci. 73 Jan.-Peb. 1985). 16-19. 4. Flores, F., and Graves, M. Education. (working paper available Tom Logonet, Inc. 2200 Powell Sweet, 11th Floor, Emeryville, Calif. 94608.) 5. Nowell, A., Perlis, A., and Simon, H. What is computer science: Sci. 157 (1987), 1373- 1374. reprinted in Abacus 4, (Summer 1987~. 32. (copied from Communications of the ACM, Jay 1989 Volume 32, Number 1, pg. 16-23) 170
Representative terms from entire chapter: