Below is the uncorrected machine-read text of this chapter, intended to provide our own search engines and external engines with highly rich, chapter-representative searchable text of each book. Because it is UNCORRECTED material, please consider the following text as a useful but insufficient proxy for the authoritative book pages.
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
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
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
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
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
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
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
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
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
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
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
Computation now included combinatonc ones concerned with rearrangements of objects and counting arrangements fulfilling various conditions. The theory of probability had already depended upon such combinatoric processes in the study of games of chance, at least since the time of Fennat and Pascal. And Euler had considered counting and classifying paths on road maps or on edges of polyhedra in the beginnings of combinatory topology known as "analysis situs." The specification of the new algebraic groups themselves appeared in a study of strings of characters, each character representing a generator, where certain pairs of swings were identified as producing the same group elements. Computation now included the purely syntactic study of certain types of symbol manipulation (ignoring the symbolism); its application to group theory and a variety of algebras, geometries, and topologies were studied through the nineteenth century by, for example, Hamilton, Cayley, Poincare, and Burnside. At the outbreak of World War I, Thue was publishing papers on "word problems" that were forerunners of some of the general theories of computation. Cantor's diagonalization proof was a syntactic game with number representation words. The logical paradoxes were semantic games with words as well. Logicians of the Polish school, their student Herbrand, and Gentzen were also thinking in terms of syntactics and semantics of such symbol manipulation games. Flunky, after Godel's work mentioned above, the logicians of the 1930s and '40s followed three types of approach (and their mixtures) to a general theory of computation. They all produced important examples of unsolvable problems, showing the limits of such general computation; and the theories were proved to be equivalent. The first approach presented purely syntactic "rewriting systems" as in the "presentations" of groups, and the generalization toward word problems by Thue. Post's "production systems" or "semi-Thue" systems was an example, and Post presented the undecidable "correspondence problem." Some years later it was shown that the word problem for genii-groups and groups, namely determining whether two products of generators represented the same element, was undecidable. In this class, some years later, was Markov's theory of algorithms. The second approach presented formalization s of the meta-language of such syntactical symbol manipulation; the characters in the meta-language had meanings (semantic content) and were therefore really symbols, where the object language characters might not be. For example, Church, in his A calculus, eliminated the confusion in mathematical notation between symbolization of a function and symbolization of He value of a function for a general element In its domain. Rosser concerned himself with the possibility of reducing a ~ expression to a "normal form." Curry considered primitive 152
symbol manipulating operators, the "combinators", and their combinations. And Kleene formalized recursion to produce a theory of recursive functions. This approach has had a direct effect in recent studies of programming language semantics and in the theory of program verification. The third approach was more pragmatic in that it specified Be users or interpreters of Be symbols being manipulated as well as the syntactics and semantics of the manipulations. These users and interpreters were the symbol manipulating machines, and the approach was directly descended from Babbage. The prime example of This approach was that of Tunng. He specified the concept, that of Tunng machine, as any mechanism that had a fate number of states and a potentially infinite tape that, at each cell, could be read, erased, printed on, or switched to another cell depending on the state the machine was in, and had a switch to another state as part of the interpretation of the symbol. Prime illustrations of Tunng machines were concatenators of strings of symbols, copiers, and combiners. A carefully designed combination of a few of these Tunng showed to be universal in the sense that it could copy the specification of any special machine and imitate it. The tapes specifying Tunng machines served as programs for die universal Tunng machine. The concepts of program, procedure, algorithm, and machine had become identified as far as their effect was concerned, even though Heir uses of space and time might be quite different. Turing showed that it was impossible to construct a program that would accept any program and appropriate data and determine in a finite time whether or not the problem represented by the program and data would come to a halt or would continue indefinitely. During World War ~ Turing was also involved with the design and use of a machine in Bntain, the Colossus, whose main purpose seems to have been cr. ptoanalync. Next developed were general purpose machines and electronic developments. The electromechanical calculating machines were already so much faster than human computation that they required prior program preparation. Rutishauser even contemplated making the programn.ung process itself pardy automatic, foreseeing the extension of the meaning of the word "computation" that the succession of generations of machines were about to add to mathematical general symbol manipulation, namely the construction of computer programs themselves. The first electronic, general purpose calculating machine, the ENIAC, was at first programmed for special problems by hand-plugg~ng tile interconnection of the registers from which and into which data were to be moved and operated on. Later He programs were coded numerically. 153
The EDVAC, immediately after the ENIAC, was designed with a fast-access internal storage (mercury delay lines) of 1,024 words that could be either data or coded instructions. Effectively, the program was the switching design of the special purpose machine one wanted the general purpose machine to become; contents of a storage cell were data if they were sent to an adder, say, but were an instruction if they were sent to the "instruction register" to be interpreted (i.e., decoded, or parsed) as an instruction. Not infrequently, in a programmed loop, the first was done to change the address of the addend to be used, and immediately afterwards the second was done to the result. The machine was modifying its own instructions, as though self-consciously. This brings to mind the mixing of meta-language (i.e., the programmed instructions) and object language (the computational data). On the one hand, this common storage of instructions and data led to the construction of programmed compilers and interpreters of higher level languages; on the other hand, it illustrates the principle of the "logical equivalence of hardware and software." It was later modified by the introduction of standard binary codes for the complete typewriter keyboard. The data were no longer viewed as just numerical. The similarity of these electronic symbol manipulators to the universal Turing machine was now more obvious than ever. The programming of interpreters of higher level languages now forced the self- conscious examination and imitation of psycho-linguistic processes. Meanwhile, mathematics was being applied to psychology and linguistics. Mathematical psychology at first concerned itself with stochastic learning models of the reinforcement type; its only effect on computation was to sharpen the programming technique of delayed random selection. In fact it was the attempt to program problem solving with its unpredictable storage requirements, and to do it on a machine with magnetic drum storage, that prompted the invention of list structure and "push-down" storage techniques in this country. This led to dynamic storage allocation and advanced the development of the area called artificial intelligence. Mathematical linguistics introduced the Chomsky hierarchy of phrase structure languages (Luce et al., 1963). These were approximations of the linguistic procedures employed by human beings in their use of natural languages, but immediately enriched the theory of computer languages. They gave us the various types of automata, finite state, and push down, needed to parse them and models of formal languages (e.g., finite state and context-free) useful in studying and designing computer languages and analyzing the general computation process. 154
At first the coding of this computation process was done by specialists the machine coders; in addition, there were the specialists (sometimes these same machine coders) who entered the problems in the machine, ran them, and arranged for their reading and printing. The machine time was too expensive to be slowed down by the single user; the set of problems of a number of users was batched and scheduled by the operators. The advancement in machine technology came at a rapid rate' though, luckily, at a slow enough rate so that internal, fast access storage was still expensive and therefore too small to afford separating instructions from data Thus, when the magnetic auxiliary storage devices, tapes and drums were enhanced by the faster access, internal storage (the core memories), the internal storage could increase moderately. The increase was enough to permit the specialized coder to be replaced by a program, the aforementioned compiler or interpreter of some standard higher level language; it also permitted a partial replacement of the machine operator by an automatic scheduler that shared the time allotted to a number of users, their inputs, their required auxiliary storage, and their outputs. This latter software was an "operating system" that also handled the allocation of internal storage dynamically, not only to schedule the time sharing of the users but also to allocate unpredictable storage needs of the single user. Machine users needed at least two types of dynamic storage allocation: (1) recursively defined functions in such higher-level programming languages as ALGOL and LISP and (2) the unpredictable storage necessary in the automatic simulation of human problem solving in the new area of artificial intelligence. Thus the human calculating processes, even at the programming and operating level, were self- consciously examined and programmed. The prograr.nming and operating level itself was recognized as a type of calculation much like Me algebraic, analytics and symbol manipulative level. Meanwhile, Me extension of programming capability to the machine user caused the explosion of computer applications to all disciplines sophisticated enough to develop advanced symbolic manipulation including even such action-oriented disciplines as sports, with their diagrammatic simulation representable in computer graphics. The market expanded rapidly and supported the hardware, software, and application research. The machines advanced in generations of 5-10 years the transistorized generation, semi- conductor devices, large-scale integration, and the VLSI methods now used to construct microprocessing chips the size of fingernails. Simultaneous with the drastic decrease in size came a drastic increase in speed, a drastic lowering of cost, and a drastic expansion ot Me market because of a drastic extension of He meaning of computation and its applications. For example, business data processing applications were once again, as in 155
the Renaissance, an important use of machines, but now path the counters, recorders, and summarizers (i.e., the large staffs of clerks) also replaced by machines. Meanwhile, during one generation of engineers and clerical staffs, the hardware and software went through three or four generations of change. What is more, the software production is now much more expensive than the hardware and needs fully as much engineering. Far from the secrecy about computational design and use that characterized the international and intra-national relations immediately following World War IT it is now clearly more profitable for all to standardize types of machine design, language design, and infonnation interchange. The computer systems and computations, therefore, are not merely proliferating; they are actually clustering into larger and larger networks far die interchange of such computed information. It is not merely airlines that nee<! such "distnbuted system computation," but also aD extended business corporations and international academic research. In summary, the word "computation" now means "any precisely specified process of symbol manipulation," even pictorial. When restricted to computer progIalrmiing, the semantics (i.e., the meanings of symbols) is restncted to the symbol manipulative. But these meanings can be expanded to visual and other prosthetic sensing and effecting devices we choose to am to the machine's data assemblers and output reactors. This is what is done in the computations for robotics. And, indeed, some of the most humanly interactive programing techniques are now object-oriented, mixing digital video graphics and Sigma audio sound, in dis~butM computation arid ~nfom~a~aon networks. The Areas of the Discipline of Computation (Informatics) and the Parts of Each That are Engineering-Oriented Until recently it was not unusual for the same Winker to concern himself with philosophy, formal theory, empirical questions, and design problems. So far it would seem that infonnatics, unlike most other academic disciplines, requires that three types of thinking be acquired in its educational curriculum, as suggested by the Association for Computing Machinery (ACM) and the hnstitute of Electrical and Electronics Engineers (WEE): (~) formal theoretic, (2) empirical and experimental, and (3) design-ortented types of thinking (roughly, syntactic, semantic, and pragmatic). A recent discussion (Denning et al., 1989) listed nine sub-areas with these three types of thinking in each (Figure D; the authors say, "It is the explicit and intricate intertwining of the ancient Dreads of calculation 156
~ . AIgon~ms and Data Structures 2. Programing Languages 3. Architecture 4. Numerical and Symbolic Computation 5. Operating Systems 6. Software Methodology and Engineenng 7. Databases and Infold on Retrieval 8. Artificial Intelligence and Robotics 9. Human - Computer Comrnun~cation ITheoly ~ Abstraction ~ Design ~ 1 1 1 1 I I t I 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 SOURCE: Peter J. Denning, et al. 1989. Computing As a Discipline. Communications of the ACM 32(January): 16-23. Figure I. Definition matrix for the computing discipline. and logical symbol manipulation, together with the modern threads of electronics and electronic representation of information, that gave birth to the discipline of computing." Each of these nine areas has "substantial design and implementation issues" in the purview of engineering. All engineering, like all professions that transform knowledge into action, was always pragmatic, both in the popular and in the technical sense (in linguistics, "pragmatics" is concerned with resolution of ambiguity by recognition of context and appropriate interpretation). Furthermore, adaptability to human beings has always been an engineering consideration, in fact the original motivation, whence some areas have made a special study of it e.g., systems engineering, industrial engineering, and ergonomics (i.e., man-machine interaction). But it was always the relationships of material objects and surroundings to human beings that was involved; what about the design of procedures, of general and special purpose languages, of automatic scheduling of distributed devices (including computers) for a distributed audience, of editing systems, of types of communications, of types of graphics, of human sensory reactions to types of prosthetic sensing, and the like? Surely aeronautical and space engineering have been concerned with the last of these. But have we designed types of thinking before and prepared the world at large to live with them? Just as mathematics has changed into (almost) a pure "knowledge-onented" discipline, might not computer science do likewise? Because so much of it remains action- oriented, namely programming and the fact that it is equivalent in a way to machine design, must remain a professional type of discipline, just like engineering, which it overlaps. 157
Moreover it win have He "solved problem syndrome" to an even greater extent than mathematics did (with applied mathematics), because there are so many disciplines involved with symbol manipulation; there may be very many mathematical needs in other disciplines, but there are even more symbolic needs (e.g., diagrammatic plans in sports). Even in mathematics, methodological discussions concerning clumsiness or neatness of notations are examples of applied informaucs! And yet the knowledge-oriented and action- oriented parts of computer and information science will so have to remain balanced because the programming act ty and machine design activity musts due to their "logical" equivalence. Adaptation Necessary for Engineers To Participate Fully in Computer Science Professional disciplines may be expected to change faster Dan those that are almost purely knowledge-onented, or those almost purely action-oriented. Because of the professional change syndrome and the solved-problem syndrome the variety of types of engineering of Be past and present is due to the variety of knowledge-or~ented and action- onented disciplines they bndge. Essentially an the engineering types have had their share of applied mathematics, both In their theory and in their computational practice. Most of these Meowed and computations have been from analysis and from statistics, and this will naturally continue in computer science. All engineers will continue to need numerical analysis in their core education, introductory computer courses leading to computer-aided design (CAD), and probably enough graphics for both displays and to replace, for example, mechanical drawing. However, in addition to these core requirements in their early engineering education, they must still pursue continuing education to keep up with the rapidly changing computer field (the professional change syndrome again). Because of the solved-problem syndrome, they must be prepared either to change over to a resulting new discipline or to switch to new problems. For computer engineers In particular, their core requirements In mathematics must be more than the analysis courses all engineers need. Abstract algebra and logic are necessary in the understanding of programming language design and capabilities as well as the understanding of the logical limits of computation, where analysis of computational complexity would still not show what is impossible. Since, like all engineers, they must 158
concern themselves with man-machine interaction, some ergonomics should, of course, be part of their education; but because of the psycho-~nguistic effects they must be concerned with, they should go deeper into cognitive science. After all, when they design a hardware-software-peopleware system, because of the logical equivalence of hardware and software, they must decide on which parts are more efficient in hardware and which In software; but they must also be concerned with psychological interaction as well. Not only should Hey be concerned wig reasonable interaction between the user and Be rest of the system, but with the dis~bui~on of users, advisers, machines, and interactive software in extended networks. References Bell, E. T. 1937. Men of Mathematics. Mineola, N.Y.: Dover. Bayer, C. B. 1968. A History of Mathematics. New York: John Wiley & Sons. Denning, P. J., D. E. Comer, D. Ones, M. C. Mulder, A. Tucker, A. J. Turner and P. R. Young. 1989. Computing As a Discipline. Communications of the ACM 32(January): I~23. Goldsune, H. H. 1972. The Computer from Pascal to von Neumann. Princeton, N.~.: Princeton University Press. Hannon, M. 1975. Stretching Man's Mind. New York: Mason/Charter. Hofstadter, D. R. 1975. Godel, Escher, Bach: An Eternal Golden Braid. N.Y.: Basic Books. Kuhn, T. S. 1970. The Structure of Scientific Revolutions (2nd enlarged edit. Chicago: University of Chicago Press. Luce, R. D., R. R. Bush, and E. Galanter (eddy. 1963. Handbook of Mathematical Psychology. New York: John Wiley & Sons. Luce, R. D., R. R. Bush, and E. Galanter (eds.~. 1963. Readings in Mathematical Psychology. New York: John Wiley & Sons. MachIup, F., and U. Mansfield (eds.~. 1982. The Study of Information: Interdisciplinary Messages. New York: John Wiley & Sons. McNaughton, R. 1982. Elementary Computability, Formal Languages, and Automata. Englewood Cliffs, N.~.: Prentice-Hall. Metropolis, N., I. Howlett, and G. C. Rota (eds.~. 1980. A History of Computation in the Twentieth Century. New York: Academic Press. 159
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
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
. 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
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.
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.
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?
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
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:
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
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
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
