It Began with Babbage (45 page)

The design of the “new” Algol was on the agenda of this conference. However, proposals for change were still forthcoming, so yet another conference was held in January 1960, also in Paris, and attended by a group of 13—from America, Britain, Denmark, France, West Germany, Holland, and Switzerland.
⁹⁵

The new language proposed by this group was called
Algol 60
. A formal report on Algol 60 at the reference language level, edited by Naur and coauthored by all 13 members of the group, was quickly published, again in
Communications of the ACM
and
Numerische Mathematik
.
⁹⁶

Once more, inconsistencies were found in the report. Many discussions ensued. Another Algol meeting was found necessary, this being held at the IFIP Congress of 1962 in Rome. There were several changes in the composition of the committee. The product of their deliberations was the
Revised Report on the Algorithmic Language ALGOL 60
, edited by Naur and coauthored by the same group of 13 who had authored the first Algol 60 report. The
Revised Report
was published, this time, not only in
Communications of the ACM
and
Numerische Mathematik
, but also in the British
Computer Journal
, which had been launched in 1957.
⁹⁷
It became the final, “official” definition of Algol 60.

The Algol project, spanning roughly 1958 to 1962 and culminating in the publication of the Algol 60
Revised Report
, manifested vividly the role of
criticism
in the development of scientific knowledge. Austrian-British philosopher of science Sir Karl Popper had characterized this feature of science by way of the schema

P1 → TT → EE → P2.

Here, P1 is the initial problem situation (or goal), TT is a tentative theory advanced as an explanation or solution for P1, EE is the process of error identification and elimination
applied to TT relative to P1, and the outcome is a new problem situation (or revised goal) P2. The cycle renews itself until a problem situation gives rise to a tentative theory for which no error can be identified.
⁹⁸

Popper's schema was intended for the natural sciences—or rather, for any enterprise that was genuinely deemed to be called a science. We see in the succession of events in the Algol project an identical process at work in the realm of a science of the artificial.

We get a sense of the nature of the Algol 60 programming style (and can compare it with that of FORTRAN) with a small example. The Algol 60 program reads in three positive integers from an input tape and computes their
greatest common divisor
(GCD). In the program, the name
buffer
refers always to the next input value on the tape. The computation of “GCD (
first, second, third
)” is done through a subroutine, called
procedure
in Algol, that computes the GCD on pairwise numbers at a time—that is, as “GCD (GCD (
first, second
),
third
).”

The entire program is enclosed in an entity called
block
, which begins and ends with the “reserved” words
begin
and
end
respectively. (In Algol 60 and, indeed, all languages belonging to the Algol genus, reserved words were in bold type.) Five
integer
variables are declared inside the (outer) block, of which the first three serve to hold the three input integers and the last two are “internal” variables used for computation. Also declared within the outer block is a
procedure
named
gcdoftwonumbers
; it also comprises a block. The symbol := indicates assignment; inside the procedure, decision (or conditional) statements are specified:
if … then …
and
if … then … else …
. Also shown is the
goto
statement, which is an unconditional branch.

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.

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
.
⁹⁹

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
.
¹⁰⁰
Thus we find in the introductory part of the
Revised Report
, the announcement that the syntax would be specified using “metalinguistic formulae.”
¹⁰¹

What would these meta-linguistic 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 meta-linguistic variables, such as and . The symbol ::= means “defined as” or “can be”; the symbol | means “or” (and these two symbols are called
connectives
). Any symbol that is not a meta-linguistic variable or a connective stands for itself.

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.3 Syntactic Generation of the String ‘ALGOL60' from the Rules of
Table 13.2

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 , we can apply the three rules systematically and
generate
ALGOL60. One possible sequence of rules (with which rule is applied at each step shown on the right) is as noted in
Table 13.3
.

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.

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.
¹⁰²

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
.
¹⁰³
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 meta-linguistic variables in < > are symbol strings, and what the Algol 60
Revised Report
called “metalingustic formulae” are “productions.”

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,
¹⁰⁴
and then in a book titled
Syntactic Structures
(1957),
¹⁰⁵
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.
¹⁰⁶