HT de Beer
August 2006
download the whole history of the ALGOL effort as a pdf file (1.1 megabytes)
One of the most important contributions to computer science by the ALGOL effort was the notation to define the syntax of programming languages: the BNF. Besides the BNF the ALGOL 60 report as a whole was also important because it would set the example for the definition of programming languages. By using the BNF to define the syntax of ALGOL 60 the report itself became a clear and structured document.
The BNF was developed by Backus to be able to define the syntax of IAL in a formal way. It was an huge improvement over earlier notations to describe programming languages. These earlier notations used natural language mixed with patterns. As a result, these notations were ambiguous and unable to formally define a programming language completely.
Although Backus's notation was an improvement, Backus was not able to define the complex procedure concept with his notation. Furthermore, the notation did not gain much attention until Naur used it for the draft ALGOL 60 report. In this report, he changed Backus's notation by replacing some symbols and using complete words instead of abbreviations. With the interest generated by the ALGOL 60 report the BNF also became well known.
The use of the BNF to define the syntax of ALGOL 60 resulted in a highly structured language. Programming language concepts known from IAL were more clearly defined. This clarification of programming language concepts was most visible by the procedure concept: the complex procedure statement from IAL was transformed into an elegant, simple and powerful procedure statement in ALGOL 60.
Although the BNF was important for the definition and development of ALGOL 60, the greatest importance of the BNF lie in its general applicability: the BNF could be used to define all ALGOL-like programming languages. After the publication of the ALGOL 60 report the syntax of almost all programming languages would be defined using the BNF. The ALGOL effort had supplied computer science with a notation to define programming languages.
Another important contribution by the ALGOL effort was the introduction or popularisation of programming language concepts. Although IAL was just another algebraic programming language like other programming languages of that time, it introduced the compound statement: one or more statements enclosed by the begin and end keywords were treated as one single ``compound'' statement.
The power of this compound statement became clear in the ALGOL 60 report: the compound statement was transformed into a special case of the block concept. A block consisted of a number of declarations followed by a number of statements enclosed by the begin and end keywords. A compound statement was a block without declarations. Through these declarations a block got its own local scope known only inside the block.
The block was the building block of ALGOL 60: every ALGOL 60 program was a block containing declarations and statements wherein blocks could occur. As said earlier, the procedure concept was simplified in ALGOL 60. It now consisted of a heading and a body. The body was a block. In the heading the name, a list of arguments, and declarations of the arguments could be specified.
In the definition of the procedures of ALGOL 60 the distinction between call-by-name and call-by-value parameters was made. The call-by-value parameter is straightforward: the value of an argument was used as the value of the parameter in the body of the procedure. The call-by-name concept was different. Instead of assigning the value of the argument to the parameter in the body, the parameter in the body was substituted with the name of the argument.
The procedure concept in ALGOL 60 was also important because it made recursion possible. Although recursion was already known, ALGOL 60 popularised the concept.
During the development of a successor to ALGOL 60 other programming language concepts were introduced or popularised as well. Most notably were the case statement, the environment enquiries, orthogonality and the record concept including the reference type and call-by-reference parameter concept.
The importance of the ALGOL effort was that it made these programming language concepts mainstream. Since ALGOL 60 blocks and recursion are included in almost all programming languages, since the record proposal was made by Hoare (1965), records are common in general programming languages.
In addition, the various programming language concepts introduced in the ALGOL effort and the discussions about these concepts influenced other programming languages and thinking about programming languages in general.
Besides the BNF and new programming language concepts the ALGOL effort contributed also translation techniques. First of all, new programming language concepts like procedures, recursion, and variable sized arrays did not directly fit in the well known sequential translation technique. An execution of an IAL program was, with respect to memory usage, static in nature: at compile time all memory management was done.
ALGOL 60, however, was another matter as a result of its possible dynamic behaviour: the bounds of arrays could be unknown at compile time and recursion could be of any unknown depth (as long as there was enough memory, of course). These problems were already solved in 1960 by different people by introducing an extra runtime stack to allocate memory for those dynamic elements. This dynamic memory management was general applicable to all translators for all languages where dynamic memory management was needed.
Besides dynamic memory management the ALGOL effort started an another approach to translation of programming languages: syntax directed translation. Influenced by the structure of ALGOL 60 and the BNF research was started to exploit this structure to create ALGOL 60 translators. It appeared that similar patterns of BNF definitions could be translated by similar translation schemes. This resulted in general translator schemes applicable to all ALGOL-like languages.
All contributions by the ALGOL effort to computer science mentioned above were in itself important. The main importance of the ALGOL effort was, however, the combined contribution. The BNF, the programming language concepts, and the syntax directed translation techniques were connected by Ginsburg and Rice (1962) by proving the equivalence of languages defined by the BNF (notably ALGOL 60) and context-free languages.
With this connection a scientific field of translation was created: the practice of ALGOL became founded on a theoretical basis of formal languages. Soon research on formal languages, including programming languages, and on the connection with other mathematical theories like automata theory was started. In addition, the syntax directed translation techniques evolved rapidly by applying the new established theory. During the 1960s and 1970s, the field of translation became the best known field of computer science.
The importance of the ALGOL effort lies in its scope. Although the ALGOL effort produced several programming languages, it was not bound to these languages only. The contributions of the ALGOL effort were applicable to programming languages in general.
In the previous section the importance of the ALGOL effort for computer science is made clear. The ALGOL effort was a success. Furtermore, ALGOL 60 did become the most used programming language for man-to-man communication. On the other hand, the ALGOL effort was also a failure: the languages it produced did not become the universal algorithmic programming language in industry. Although it was used in Europe more than in the USA, it could not beat FORTRAN. FORTRAN became the de facto standard programming language for numerical work. This contradictory nature of the ALGOL effort is striking. How can something both be such a success and such a failure?
Of course, the answer on the question about success depends on the definition of success. Nonetheless, ALGOL was intended to be used as a programming language to instruct computers with and it failed in that respect. Despite its quality ALGOL was not received well in industry. From the perspective of the industry ALGOL was not a trustworthy language: it lacked a governing body. Where FORTRAN had IBM, ALGOL 60 had nothing but a bunch of scientists. The dominance of IBM and FORTRAN was also a part of the explanation of the failure of ALGOL; there were many computer manufacturers willing to implement and ship the language with its computers but they were not able to break the dominance of IBM.
The ALGOL languages, however, did become the main communication language for algorithms in many journals and publications. Furthermore, it was also often used to teach programming at universities. As a result, ALGOL became well known among computer scientists and influenced their thinking on programming languages. In addition, the ALGOL effort was the platform to discuss programming languages, and many features discussed during the development of ALGOL 68 would appear later in other programming languages. With respect to communication and influence, ALGOL was a success.
That the ALGOL languages could not become major players among the programming languages in industry did not affect its influence or its importance. On the contrary, by being a minor language there was less need for stabilisation or backwards compatability. By being an ``academic language'' ALGOL stayed object of research and development. Consequently, the ALGOL effort was able to prepare the way for a new generation programming languages, like Simula, Pascal, C, Smalltalk, etc., without the ballast of legacy.