Algol-60 Report

views updated

Algol-60 Report

The Algol-60 report was written between 1959 and 1960 by a team of programming language experts consisting of editor Peter Naur and several educators and practitioners from Europe and the United States. The purpose of the report was to develop a complete description of an international algorithmic language for expressing numerical processes in a form suitable for translation into computer programming languages. It was not intended to be a programming language, although it was subsequently implemented as a language and became popular in Europe.

Many versions of the Algol programming language were implemented in the 1960s and early 1970s. It also led to the development of several other programming languages, such as Pascal, implemented by Niklaus Wirth in the early 1970s, and C.

The report introduced the notions of a reference language, a publication language, and a hardware representation. The reference language was the standard for the report, compiler writers, and hardware implementation. It dictated the form of the language and its syntax . The publication language used the reference language with minor adjustments for publication variations across countries and printing and writing variations such as the handling of subscripts, superscripts, and other notation. The hardware representation took into consideration the characteristics of the machine. The reference language was the defining language, and the publication language and hardware representation had to be translatable into it.

The purpose of the report and the language was to give an unambiguous representation to various computer concepts—in particular, algorithm design, or ALGOrithmic Language 1960. A subsequent version, Algol68, was not as popular or widely implemented as Algol-60, although it was more powerful.

Algol is a structured language, incorporating while statements, if-then-else-statements, and other constructs that implement selection, iteration, basic statements, block structure, and recursion. Although it was developed only a few years after FORTRAN (FORmula TRANslator), released in 1957 by IBM, it incorporated features missing from FORTRAN—namely the recursion and the structured language—and was a major advance in the programming arena.

One of the descendants of Algol and FORTRAN was BASIC (Beginner's All-purpose Symbolic Instruction Code) language, developed by John Kemeny and Thomas Kurtz of Dartmouth University. BASIC was a sort of format-statement-free version of FORTRAN for interactive and beginning computing. BASIC enjoyed a long reign from the 1970s to the 1980s and has recently been implemented in a quite different form, Visual Basic.

A descendent of Algol was Pascal, which also enjoyed a long reign as a popular language for implementing data structures and studying compilers . It was not a production language, but a teaching tool. C was a system's language and led to the development of C, an object-oriented language that is still popular.

The Algol language was described in a notation called Backus normal or Backus-Naur form (BNF). The notation was suggested by John Backus, who based it on a notation by E. L. Post, a famous logician in the 1930s. It was similar to the notation developed by Noam Chomsky in 1957 for linguistics, which was used to implement grammars. A grammar is a succinct, unambiguous way of describing languages. The use of a formal notation in language theory was a major advance.

The evolution of programming languages was striking, but not as stunning as the evolution of compiler theory. Shortly after the Algol-60 report, several compiler theorists used the grammar notation to implement compilers in an "automatic" fashion. These compilers were known as compiler-compilers. Similar efforts were the development of Lex, a lexical analyzer, and Yacc ("Yet another compiler-compiler") at Bell Laboratories in the mid-1970s.

Understanding Programming Language

English grammar has certain constructs, such as a noun phrase, which is composed of other constructs, such as a noun and a modifier. Programming languages have constructs such as while-statements, and arithmetic expressions. These constructs are indicated by special symbols called the nonterminal or meta symbols of the language.

The symbols that actually appear in the language are called terminal symbols. The terminology comes from the data structures, or parse trees, used to implement the language.

An example is:

This grammar indicates that an arithmetic expression, E, consists of other arithmetic expressions and terms, T, added together (E-->E T). A term, T, is composed of a term times a factor, F, so that T-->T*F. Finally, a factor, F, is the most basic expression, consisting of parenthesized expressions (the parenthesized E), identifiers (user-defined identifier or variables), id, and numeric constants (num). The grammar gives the form of the arithmetic expressions.

The example gives a flavor of the notation. The items on the left of the arrow are composed of the items on the right. In this case, the E, T, and F are the meta-symbols. The other symbols,, *, (, ), and, in this case, id and num, appear in the language. They are the words of the language. In this case, E is the start symbol or first non-terminal symbol. It is the most general expression being defined. Although the notation may seem awkward at first, it is useful in language design, compiler theory, and implementation.

The development of grammars in computer science gave a great impetus to programming language design and implementation.

see also Algorithms; Procedural Languages; Programming.

Roger R. Flynn