It Began with Babbage
Page 31
The flow of control through the program begins with the first assignment statement (first := buffer) and flows sequentially through the statements separated by semicolons. When control reaches gcdoftwonumbers, that procedure is called and the block inside the procedure is entered for execution. On completing the procedure, control returns to the statement (y := third) following the procedure call. This same procedure is called a second time. Eventually, control returns to the print statement after which the program terminates.
XVI
But let us return to the Paris UNESCO conference of 1959. There, John Backus presented a paper titled The Syntax and Semantics of the Proposed International Algebraic Language of the Zurich ACM-GAMM Conference.99
Syntax and semantics. Backus made these terms from the realm of linguistics part of the vocabulary of programming languages. But, he not only used these terms, he also proposed a notation by which the syntax of Algol 58 could be described formally. He introduced, in other words, a meta-language for the description of the syntax of a programming language. Thus did the concept of meta-language, familiar to logicians, enter the vocabulary of computer science.
Backus’s meta-language came to be called Backus Normal Form or BNF.100 Thus we find in the introductory part of the Revised Report, the announcement that the syntax would be specified using “metalinguistic formulae.”101
What would these metalinguistic formulae look like? Table 13.2 presents a description from the very beginning of the Revised Report. Here is how the syntax of identifiers (character strings that signify allowable names—of variables, labels, subroutines—in the language) was defined.
Here, the sequence of characters enclosed in < > represent metalinguistic variables, such as
So in this meta-language, BNF, the first “formula” says that an identifier can be a letter or an identifier followed by a letter, or an identifier followed by a digit. The second formula states that a digit can be 0 or 1 or 2 or … 9. The third formula says that a letter can be a or b or … z or A or B or … Z.
TABLE 13.2 A Fragment of Algol 60 Syntactic Rules
TABLE 13.3 Syntactic Generation of the String ‘ALGOL60’ from the Rules of Table 13.2
(I)
(I)
(II)
(II)
(I)
(III)
(I)
(III)
(I)
(III)
(I)
(III)
(I)
ALGOL 60
(III)
*
These formulas establish, in fact, syntactic rules for how a programmer can write an identifier in Algol 60. Any identifier that obeys these rules is syntactically correct in the language. Any identifier that does not obey these rules is syntactically incorrect and, thus not “recognized” in Algol 60.
Consider, for example, the character string ALGOL60. Is this a syntactically correct identifier in Algol 60? We can determine this by seeing whether, beginning with the meta-lingusitic variable
In fact, it can be checked easily that the character string ALGOL 60 is not syntactically correct according to rules given because a blank (here, between the L and 6) is not a recognized character.
XVII
What was the source of Backus’s idea of this meta-language, BNF? Reflecting in 1981, he tells us of attending a course taught by mathematician Martin Davis (1928–) during which Davis talked about the work of Emil Post (1897–1954). It seemed to Backus that one of Post’s important ideas could be used to specify the syntax of Algol 58.102
Post was a Polish-born American logician who taught at the City College of New York and who developed (among much else) a model of computation in 1943 in which a computation could be realized by transforming a string of symbols into another string of symbols by following certain rewriting rules called productions.103 A Post production, in general, would be of the form
antecedent → consequence
Here, both antecedent and consequence are symbol strings, and → indicates the replacement, deletion, or addition of some part of the antecedent string to obtain the consequence string. For example, consider the single symbol 1. Then, if $ is a symbol string composed of an even number of 1s or an “empty” string, a production
$ → $11
will generate, if applied successively, the strings 11, 1111, 111111, and so on, all containing an even number of 1s.
In our example from Algol 60, we see that rule (i) can be restated as three productions:
The metalinguistic variables in < > are symbol strings, and what the Algol 60 Revised Report called “metalingustic formulae” are “productions.”
XVIII
However, BNF, the meta-language used to describe the syntax of Algol 60, bears a strong similarity to another meta-language that emerged during the mid 1950s, in the work of the linguist Noam Chomsky—so much so that it is easy to believe that Backus was stimulated by Chomsky (although, according to Backus, this was not the case). In a paper presented at a conference at MIT in 1956,104 and then in a book titled Syntactic Structures (1957),105 Chomsky laid out the beginning of a new direction in linguistics that was so influential it is sometimes referred to as the Chomskyan revolution, in the sense that, in the opinion of a later commentator, it induced a revolution in the scientific study of natural language.106
The place of Chomsky in the realm of linguistic studies is, however, not our concern here, but rather how some of his basic ideas were remarkably relevant to the development of a theory of programming (and, more generally, artificial) languages, including Algol 60. His work led to a fundamental clarification of the nature of programming languages in a number of ways.
To begin with, programming language designers before Chomsky spoke of “language,” but never quite clarified what they meant by this term. For example, in the case of Algol 60, an “algorithmic language,” it was never stated exactly which part of the Revised Report constituted the language.
Chomsky helped clarify this matter when he proposed that a language is a (possibly infinite) set of sentences, each sentence being composed of a finite set of elements.107 The “set of elements” out of which a sentence is constructed forms an “alphabet” of symbols. Thus, a sentence is a string of symbols taken from this alphabet.108 But, the sentences or symbol strings that can be formed from an alphabet of symbols are not all legitimate sentences in the language. There are rules that determine which are grammatical sentences in the language and which are not. Such rules form the grammar of that language. In fact, according to Chomsky, the grammar of a language is a device that produces all and only the sentences of that language.109
A grammar, then, is a “device of some sort” that will generate all the grammatical sentences of a language and only those grammatical sentences. Suppose the “alphabet” of symbols includes the words found in a dictionary of that language—say, English. Then, all the grammatical sentences in English are word sequences that can be generated by the grammar for English.
What would a grammar look like and how does it generate sentences? Chomsky presented three different “models” of grammar,110 b
ut the one that is most illuminating for us is exemplified by the following simple grammar:111
(i) Sentence → NP + VP
(ii) NP → T + Noun
(iii) VP → Verb + NP
(iv) T → the
(v) Noun → man|ball| …
(vi) Verb → hit|took| …
In fact, these are all “rewriting” or production rules. Each is of the form X→Y, where X is a single element and Y is a string of one or more elements. The rule X→Y is interpreted as “replace X with Y” or “rewrite X as Y.” The + in X+Y signifies the concatenation of X and Y; and the | signifies “or.”
The rules then apply as follows: starting with the symbol “sentence,” apply rule (i). This results in the string NP+VP. if any of the elements of this string can be rewritten by one of the rules (ii) to (vi), then select one such rule. Repeat this procedure until a sequence of symbols comprising only elements of the alphabet—a sentence of that language—is produced.
Thus, for example, the sentence “the man hit the ball” can be generated by this grammar by the sequence of rule applications presented in Table 13.4.
This is not the only way the rules could be applied to generate the sentence “the man hit the ball.” Nor, of course, is it the only sentence that could be generated from these rules. Such sentences as “the man hit the man,” “the man took the ball,” “the ball took the man,” “the ball took the ball,” and so on, could also be generated from these rules. They would all be syntactically correct even though some are meaningless (that is, semantically incorrect), such as “the ball took the man.”
TABLE 13.4 Parsing the Sentence ‘the man hit the ball’
Sentence
NP+VP
(by applying i)
NP+Verb+NP
(iii)
T+Noun+Verb+NP
(ii)
the+Noun+Verb+NP
(iv)
the+Noun+Verb+T+Noun
(ii)
the+man+Verb+T+Noun
(v)
the+man+Verb+T+ball
(v)
the+man+hit+T+ball
(vi)
the+man+hit+the+ball
(iv)
*
We now have a sense of what Chomsky meant by a grammar. As he tells us, a grammar comprises of a finite set of “initial strings” and a finite set of production or rewrite rules.112 In the previous example, there is only one initial string, “sentence,” although in more elaborate grammars there would be additional initial strings such as “declaration sentence,” “interrogative sentences,” and so on.
XIX
We can now see how Chomskyan theory (or a miniscule part of it) relates to programming languages. His “instruction formulas” (or productions or rewrite rules) correspond to the metalinguistic formulas of the Algol 60 Revised Report. They are the syntactic rules of Algol 60. The alphabet of symbols out of which sentences are formed in Chomsky’s scheme are the basic symbols out of which Algol 60 programs are written. Chomsky’s “grammatical sentences” are the set of syntactically correct programs that can be written using the syntactic rules defined for Algol 60. The set of basic Algol 60 symbols, together with an “initial string” (which corresponds to “sentence” in Chomsky’s example grammar), which in Algol 60 is the “procedure,” along with the entire corpus of metalinguistic formulas presented in the Revised Report constitute the Algol 60 grammar.
There was more to the Chomskyan connection, however. Each of the rules of his simple illustrative grammar (shown previously) is of the form
A → α
where A is a single symbol denoting a syntactic category (“sentence,” “NP,” and so forth) also called a nonterminal symbol (because such symbols can never appear in sentences of the language) and α is a string that can contain nonterminal symbols, connectives (+), and the symbols of the language’s alphabet (“man,” “hit,” and so on), which are called terminal symbols. A language with sentences that are generated by grammars having rules of just this type came to be called context-free languages and the corresponding grammars, context-free grammars. This was one of several language classes that Chomsky studied; he called it a “Type 2” language.113
The rules (productions) for Algol 60, as given in the Revised Report were all of this form. The left-hand side of each production is a metalinguistic variable (in other words, a single nonterminal symbol); the right-hand side is a string of nonterminal and terminal symbols. To take an example, here are a few the rules for arithmetic expressions in Algol 60114:
…
…
The irony was that Chomsky’s Type 2 grammars were utterly inadequate for the description of natural languages; but, under the name of context-free grammars, they were preeminently suitable to describing programming languages. Context-free grammars and languages became extremely consequential in computer science, although of only passing interest in linguistics.
A theory of context free-languages and the automatic recognition of sentences in such languages would emerge during the 1960s.115 One of the most fascinating topics in this realm was the problem of determining what kind of computational power was necessary for automata (including Turing machines) to recognize different classes of languages, including context-free languages. However, the interest in context-free languages was not just theoretical. There were enormous practical consequences. The “front end” of a compiler first had to ascertain the syntactic correctness (the “grammaticalness”) of the program it was compiling—a technique called syntactic analysis or parsing—and a spate of parsing algorithms for context-free programming languages were invented during the 1960s.116 Writing compliers became “scientific!”
XX
But what of semantics? What of the meaning of such things as identifiers, expressions, statements, and procedures? In the case of FORTRAN, the Programmer’s Guide used ordinary English to present the semantics of the language. So, too, with the Algol 60 Revised Report. Semantics was not amenable (yet) to the kind of precise, formal descriptions that could be used for syntax. The meta-language of semantics remained English or other natural languages. Thus, although the syntax of arithmetic expressions was written in BNF, its semantics was in English:
An arithmetic expression is a rule for computing a numerical value. In case of simple arithmetic expressions this value is obtained by executing the indicated arithmetic operations on the actual numerical values of the primaries of the expression.…117
There will come a time (as this story will tell) when the “problem of meaning” becomes a serious subject for investigation among language designers, programmers, and computing theorists. But not yet.
XXI
One of the ironies of this story of the birth of programming languages is that although, like the crocodiles and tortoises of old, FORTRAN and COBOL would survive the vicissitudes of computing technology as the lingua franca of their respective target problem environments—science/engineering in the former case, business/commerce in the latter—Algol 60 as a universal language for actually programming computers would be virtually extinct by the 1980s. The Esperanto of the computing world it was not to be (but, then, Esperanto itself did not catch on as the universal natural language).
Algol 60, as it turned out, was the first species of the genus Algol. The language gave rise to some subspecies in the 1960s—“dialects” of Algol 60 such as Algol W, EULER, and PL/360. It also spawned other distinct species within the genus, including the influential simulation language SIMULA118 and Algol 68, the official IFIP-sponsored “successor” to Algol 60 that, like its parent, went through first a Report (1969)119 and then a Revised Report (1975).120
Algol 68 was an entirely non-American affair, its designers and implementers drawn from Europe, Brit
ain, and Canada,121 and it had no influence in the United States. The sheer complexity of the language—the Revised Report was all of 230 pages—drew sharp reactions.
In the biological world, it is widely believed, evolution generally tends toward greater complexity of organisms.122 So also, historically, is the general trend in the made world. Cultural evolution, especially in the realm of practical artifacts, tends toward greater complexity.123 This was evident in the evolution from Algol 60 to Algol 68, and in the development of PL/I, a programming language developed by IBM in 1964 as a language that could be used for both scientific and business computing, and as a putative successor to FORTRAN; it was to be IBM’s own universal language. Like Algol 68, PL/I was a massive, complex language; unlike Algol 68, however, it has had a long life, although it could never usurp either FORTRAN’s or COBOL’s respective reigns.
Yet there have been exceptions to this evolutionary trend to increased complexity, even in the frantic, rambunctious world of computing. In response to what was perceived by some as the unmanageable complexity of Algol 68, Swiss computer scientist Nicklaus Wirth (1934–) created the “Algol-like” language Pascal in 1971,124 perhaps the most influential programming language, at least in the academic computing world during the 1970s.
Algol 60 may have become extinct as a practical language for programming computers, but it had massive consequences for the development of (appropriating the great Galileo’s terms) “two new sciences”—the science of programming language design and (as we will see) the science of programming. It brought to the forefront of people’s consciousness the very idea of designing languages that were genuinely machine independent, genuinely abstract. It demonstrated the efficacy of a precise language for describing, communicating, publishing, and, indeed, thinking about computer algorithms. It heralded a concern for meta-languages for describing the syntax of programming languages. It introduced entirely new concepts in language design as well as programming style that, much as Greek culture permeated the minds and consciousness of Roman and other cultures that came after them, found their ways into the languages that came after. It demonstrated the importance of the Popperian schema of proposing a design (TT) in response to a set of goals or requirement (P1), examining the design critically, identifying and eliminating flaws or errors in the design (EE), and reformulating the goals (P2). Last (although this is not a topic we will pursue further in this story), implementation of Algol 60 compilers brought into existence an entirely new class of computer architectures that came to be called stack machines.125