FIGURE 15.1 The Structure of a Sequential Circuit.
IV
Sequential machines were also called finite automata—finite because the number of possible states such a machine can have is finite. A sequential machine, then, has finite memory. In contrast, the Turing machine (see Chapter 4, Section IV), with its infinite tape, has infinite memory. So even though the control part of a Turing machine can only have a finite number of states, the machine as a whole is an “infinite automaton.” The “machines” involved here were not physical devices; they were not material computational artifacts. The Turing machine (as previously pointed out in Chapter 4, Section IV) is a purely abstract artifact, having no physical reality. A sequential machine, in contrast, has the same liminal quality a program has. It is fundamentally abstract. Like the Turing machine, it is a mathematical entity, and can be studied, analyzed, and manipulated entirely in the abstract as mathematical objects are, as the Turing machine can be. On the other hand, a sequential machine can serve as a design for a physical digital circuit. The implementation of a sequential machine design would be a material artifact.
Collectively, the study of sequential machines and infinite automata came to be called automata theory, a field of study that came into its own during the 1950s.9 Automata theory treats both such machines as abstract artifacts. By the end of the next decade, its status as a subparadigm within the computer science paradigm was firmly established. A marker was the publication of texts during the second half of the 1960s—texts that became seminal in characterizing the “state of the art” of the field, most notably Marvin Minsky’s Computation: Finite and Infinite Machines (1967),10 Michael Arbib’s Theories of Abstract Automata (1969),11 and Formal Languages and Their Relation to Automata (1969) by John Hopcroft and Jeffrey Ullman.12
The study of Turing machines, of course, was concerned with the fundamental problem that had led Alan Turing to create his abstract machine in the first place: what does it mean to compute? Computability, decidability, solvability were the issues with which automata theorists remained concerned. The theory of computing was the broad term that encompassed this subsubparadigm (as it were) of automata theory, and a number of key books explored this subsubparadigm between the late 1950s through the 1960s.13
V
However, there was another face to automata theory that had more practical appeal, and this went back to Noam Chomsky’s celebrated monograph Syntactic Structures (1957) (see Chapter 13, Section XVIII). We recall that the focus of that book was the nature and form of grammar (syntactic rules) that would generate and account for sentences of a natural language such as English. Early in the book, Chomsky explored the idea of a grammar as a machine.
Imagine a finite-state machine with, possibly, a very large set of possible states. It has an “initial” or “starting” state and a “final” state. Beginning in its starting state, the machine goes from one state to another in sequence, each change of state being accompanied by the production of a symbol (say, an English word), until it reaches the final state and stops. We can call the sequence of symbols produced by the machine a sentence. Each distinct path from a starting state to a final state thus generates a distinct sentence. We can call the set of all such sentences producible by this machine a language.
Chomsky called any language that can be produced by this sort of a finite-state machine a finite-state language, and the machine itself, a finite-state grammar.14
Chomsky’s finite-state grammar is, in fact, a finite-state or sequential machine wherein there is no input, and the outputs (words) are produced as a function of the state only. It is, in fact, a Moore machine. Chomsky would go on to describe several types of grammars and characterize the languages they would generate.15
In identifying grammars with automata, Chomsky summoned up a question of great interest—not to linguists, but to computer scientists interested in the theory and design of compilers for programming languages. One of the language types Chomsky identified he labeled “Type 2” came to be known to computer scientists as context-free languages (see Chapter 13, Section XIX). The grammars that produce context-free languages came to be called context-free grammars. As we have seen, the syntax of Algol 60 was defined by a context-free grammar (see Chapter 13, Section XIX). And because a programming language’s compiler’s first task is to ensure the syntactic correctness of a program written in that language, the segment of a compiler responsible for this task—called a parser—must be able to “recognize” that programs in a language like Algol 60 are, in fact, context free.
A parser is itself a computational device. And the question was raised: what kind of a computational machine is needed to recognize a context-free programming language? More generally, if there are several types of grammars, what must be the power of an automaton that it can recognize a particular type of language?
Thus, a subfield of the automata theory that emerged during the 1960s concerned itself with the study of automata that corresponded to these different types of languages. A finite automaton (a sequential machine) can recognize only finite-state languages (called by Chomsky “Type 3 language”) that had a grammar with syntactic rules (productions) of the form
A → α
A → αB
where A, B are nonterminal symbols and α is a terminal symbol (see Chapter 13, Section XIX). A context-free language has a grammar with productions of the form
A → α
where A is a nonterminal symbol and α is a string of nonterminal and/or terminal symbols. A more general type of language known as context-sensitive language (Chomsky’s Type 1) has productions of the form
αAβ → απβ
where A is a nonterminal symbol and α, β, π are strings of terminal and/or nonterminal symbols.
Thus, a second area of interest in automata theory that emerged during the 1960s was the determination of the kind of automata that corresponded to context-free and context-sensitive grammars. A finite automaton would recognize only finite-state languages. The other types of languages required more powerful automata—infinite machines. Turing machines of different kinds were explored as representing different types of grammars.16
Of course, no practical parsing algorithms would be designed along such machine principles because Turing machines consume a great deal of “time” moving back and forth along their tapes. But automata theory provided a normative standard by which to compare the different types of languages and their automatic recognition.
VI
A compiler is a programming system—meaning that it does not implement a single algorithm but, rather, a collection of algorithms that interact with one another in some fashion. To put this in another way, a compiler’s overall goal is to translate programs written in some high-level, machine-independent programming language into object code for a particular computer. This task is complex enough to be decomposable into several subtasks or subgoals, each of which necessitates an algorithmic solution of its own (Figure 15.2). The compiling task begins with what came to be called lexical analysis. The linguistic origin of this term is clear because a lexeme is the technical term for the smallest meaningful unit of sound—words. In lexical analysis, the input source program is transformed into a string of symbols in which all the (usually) multicharacter or variable-length identifiers appearing in the source program (such as reserved words in Algol such as begin and end, and variable identifiers) are replaced by single or fixed-length symbols. The output of lexical analysis (which will also include a “symbol table” that records the correspondence of fixed-length symbols with the original identifiers) is passed on to the parser, which performs syntax analysis to confirm that the program is legal syntactically, obeying the grammar of the original programming language. Assuming syntactic correctness, the parser’s output in some appropriate form is passed to the “code generator,” which produces object code for the target machine. As part of the code generator or as a subsequent compiler phase, there is the task of “code optimization,�
�� which makes the object code more efficient in terms of the amount of memory space required to store the object code or the amount of time required to execute the object code.
FIGURE 15.2 Structure of a Compiler.
These different subtasks, in turn, may demand other subsubtasks; these engender their own problems, such as deciding which data structures should be used to represent the program and its data at various stages of the compiling process and how best to access elements from these data structures, how to represent the syntax of a programming language that leads to more efficient parsing algorithms, how best to analyze a source program for the purpose of parsing, how to represent a parser’s output that facilitates efficient code generation strategies.
Thus, as a class of system programs, compilers spawned a whole range of research problems during the 1960s having to do with the invention of (especially context-free) grammars,17 algorithms for parsing,18 code generation strategies,19 and code optimization techniques.20 The first books on compilers appeared both on compiling techniques for particular programming languages21 and, more generally, on compiling algorithms and strategies.22 Surveys and overview papers on particular aspects of compilers were published.23
Inventing algorithms for various components of the compiling task was not the only issue of interest. There was the practical problem of writing compilers.
Compilers were usually written in assembly languages and, thus, was a long, tedious, and potentially error-prone process. Inevitably, compiler writing became an object of inquiry of intrinsic focus. The idea of compiler writing systems—more commonly called, catchily but a bit confusingly, compiler-compilers—emerged. Ideally, a compiler-compiler is a programming tool/language that takes as input the syntactic and semantic definition of a programming language and a description of a target machine, and produces as output a compiler for the language–machine combination. In practice, because semantics was hardly ever defined formally (although, as we shall see, inventing meta-languages for defining semantics was yet another subparadigm of this decade), compiler-compilers were largely restricted to the generation of lexical analyzers and parsers from a BNF description of the programming language of concern.
The first working compiler-compiler was developed in 1960 for the Atlas computer by a team at the University of Manchester led by Tony Brooker.24 The topic of “compiler generation systems” became of sufficient interest that a book on the subject was published in 1970.25
It is fair to say that research on both compiling algorithms and compiler writing and implementing represented a distinct subparadigm within the overall paradigm, spawning a plethora of research problems in all aspect of compiling: designing/inventing context-free grammars for programming languages that enabled the task of efficient parsers, inventing algorithms for lexical analysis and parsing, and discovering procedures for code generation and code optimization. Each of these broad problem areas generated a variety of solutions. All of this was might be seen as normal science à la Kuhn, but it was far from “puzzle-solving” or “mopping up,” as Kuhn would describe normal science.26
VII
We noted that the technique of microprogramming invented by Maurice Wilkes in 1951 properly came of age during the early 1960s with the design and implementation of the IBM System/360 series of computers (see Chapter 12, Sections VII and VIII). The IBM 360 also marked the beginning of the discipline and subparadigm of computer architecture.
Recall that John von Neumann’s celebrated 1945 report on the EDVAC described what von Neumann called the logical design of the stored program computer (see Chapter 8, Section III). The idea was to frame the conceptual structure and organization of what a computer should be like based on the stored-program principle. Specifics of the physical aspects of such a machine were left largely unstated, although possibilities (and von Neumann’s own preferences) were discussed.
This logical design became the essence of the new paradigm. It was assimilated by people like Wilkes, Williams, and Turing in England, and von Neumann and his collaborators in America into a common mental schema (see Chapter 8, Section V), which was interpreted, elaborated, and refined in different ways by these various researchers as implementations of actual physical computers.
The term computer architecture was not used by von Neumann or any of these other pioneers then and for years later, but we are left in no doubt that what would later be called computer architecture was anticipated by von Neumann when he laid emphasis on the logical design of computers.
It was one of several achievements of the designers of the IBM System/360 (in particular, Gene Amdahl [1922–], Frederick Brooks [1931–], and Gerrit Blaauw [1924–]) to first use the term “architecture” in the context of computers. Their original meaning was the collection of functional attributes of a computer, as seen by the programmer—that is, the conceptual structure and functional behavior of the computer as distinct from its internal organization and physical implementation—the outer façade of the computer, as it were.27
The IBM System/360 was not a specific physical computer. Rather, System/360 referred to an architecture: a liminal artifact. Actual implementation of this architecture would entail the creation of any one of a range or family of physical computers, the System/360 family. Each resulting machine was a material computational artifact (called a model in IBM parlance, each identified by a model number), with its own cost–performance characteristic, depending on the physical technology and specific internal organization and design. To put this in another way, distinct physical machines each with its own physical, organizational, and technological characteristics could serve as hosts to implement the same System/360 architecture. As it happened, the efficacy of this approach was ensured by microprogramming the different hosts so that they each appeared as a System/360 “virtual” machine. This technique was called emulation28—a term first introduced in this context in 196529 (Figure 15.3).
FIGURE 15.3 IBM System/360 Emulation Schema.
To the user (the programmer), these different physical computers were functionally identical. This meant that a program written for the “virtual” System/360 “computer” could be executed on any of the physical machines; or, a program executing on one of the models (say, Model 40) could be transported to another model (say Model 67). The major difference would lie in the performance of the computers; a higher numbered model had better performance (speed of processing) than a lower numbered model. Naturally, the faster machine was more costly than the slower one. This scheme allowed owners of System/360 physical machines to “upgrade” their systems to higher performing models if so desired without any substantial changes in the programs that would be transported from the old to the new.
The System/360 designers thus introduced the concept of computer architecture during the early to mid 1960s. The concept would evolve and become more complex in the decade that followed. A discipline of computer architecture as a branch of computer science would be established, also in the 1970s, and the first of a (still continuing) series of annual international conferences on computer architecture was launched in 1974. The first anthology of papers on the subject was published in 1972,30 but the seeds of this subparadigm were planted during the 1960s.31
VIII
Among the ways in which a science assumes its identity is by way of publications of definitive books proclaiming what the subject matter is about at some moment in time. Of special status are those books that are seminal—the first textbook in a particular subject or a text that stamps its authority on the field. They become indispensable to those who study or work in that field.
In 1968 to 1969, Donald Knuth (1938–), professor of computer science at Stanford University, published the first two volumes of a planned series called, collectively, The Art of Computer Programming. The first volume was titled Fundamental Algorithms (1968)32; the second, Seminumerical Algorithms (1969).33 These works became “immediate classics.” As sometimes happens, that texts come to be referred by a generally accept
ed abbreviation of some sort, Knuth’s first two volumes of The Art of Computer Programming were simply referred to as ‘Knuth Volume 1’ and ‘Knuth Volume 2’, respectively.34
Knuth was only 30 when Fundamental Algorithms was published. Both before and after these two books, he had and would have many significant contributions to different subparadigms in computer science—in the realms of programming languages, programming style and methodology, algorithms, the history of programming and programming languages, and philosophical aspects of computer science. During the 1980s, he made pioneering contributions to the development of computerized typography.35 However, it is his Art of Computer Programming for which he has been most recognized.
These books were about algorithms. The concept of an algorithm (if not the term), of course, reaches back to antiquity. Euclid’s great work Elements described an algorithm to find the greatest common divisor of two numbers. As Knuth tells us, the word “algorithm” itself originated in the name of a ninth-century Arabic mathematics textbook writer al-Khowârazmi as “algorism.”36 The earliest reference the Oxford English Dictionary has for algorithm was in 1695 in an article in the Philosophical Transactions of the Royal Society.37
As we have seen, ever since Charles Babbage and Ada Lovelace, people have been inventing algorithms not for humans to perform, but suitable for automatic execution on computing machines. Mathematicians and logicians had concerned themselves with algorithms under the term effective procedure—“a set of rules which tells us how to behave,” as another significant text of the late 1960s put it.38 In fact, Turing, in his celebrated paper of 1936, proposed that any procedure that seems intuitively effective can be carried out by the kind of machine he constructed—Turing machines (see Chapter 4, Section IV). In 1950, Soviet mathematician Andrei A. Markov (1903–1979) published a book that, in English translation, was titled The Theory of Algorithms; its concern was to inquire whether effective procedures did or did not exist for certain kinds of problems.39
It Began with Babbage Page 36