An image of Heer de Beer

Heer de Beer.org

Exploring the Computational Medium

Conclusion

Summary and Conclusions

Huub de Beer

August 2006

In the introduction the question was asked: What was the importance of the ALGOL effort for the development of computer science? After having studied four phases of the ALGOL effort, Creation, Notation, Translation, and Succession, it is time to answer the question and draw conclusions. Before answering this question, however, a summary of the preceding chapters is given.

Summary

The start of the ALGOL effort

In Chapter Creation the history of the start of the ALGOL effort and the reasons for its existence were told. In the late 1950s, the need for a universal algorithmic programming language was felt. In Central Europe, a GAMM subcommittee was founded to create an algebraic language and during the development of this language the ACM in the USA was contacted. It was decided that both the GAMM subcommittee and the newly formed ACM subcommittee would create a proposal for an algorithmic language. At the Zürich meeting in 1958, both subcommittees met and they drew up a proposal for an international algebraic language: IAL.

Two questions were asked: why was there a need for a universal algorithmic language and why did it have to be IAL and not some of the already existing languages? First of all, in the USA, the field of computing became an industry in the 1950s. Computers were sold to and used by many corporations, research centres and the government. In this commercial atmosphere, using problem-oriented programming languages, like algorithmic languages or data-processing languages was needed to make profitable the use of the expensive computing machines.

These programming languages, or automatic coding systems, did have a bad name: it was believed that they were fundamentally inefficient. The FORTRAN programming system, however, proved the opposite as FORTRAN programs were efficient, although not as efficient as hand-coded programs. Problem-oriented languages were seen as a necessity and many research groups and computer companies started creating these languages for both internal use and as part of the commercial computer systems that they were selling. Unfortunately, this development resulted in the creation of many similar, but different algorithmic programming languages. In this context the cry for a universal algorithmic programming language became louder.

In Europe, the situation was totally different. The field of computing was emerging and the first larger computers were being built. The main application for these machines was scientific computing. Instructing these computers was a difficult and error prone task. To solve this problem, work was started on formula translation and eventually on an algorithmic language in the GAMM subcommittee. Instead of creating yet another algorithmic language, the members of the subcommittee proposed to jointly create one international algebraic language to the ACM.

The Americans did not base their proposal on an already existing language. IT and MATH-MATIC were not sufficient or well known. FORTRAN, on the other hand, was well known, but the American members of the committee did not want to increase the dominance of IBM. As a result, the ACM subcommittee proposed a new language. The combination of the two proposals resulted in IAL: a new algorithmic language like other algorithmic languages of that time.

This start of the ALGOL effort was important because it created a common goal among computer scientists from the USA and Europe: developing one algorithmic language. Creating one universal algorithmic language became part of the agenda of computer science.@Mahoney1997a This may not sound important, but in an emerging field, as was the case with computer science, it meant more coherence. It meant that computer scientists could identify themselves, both to each other and to the outer world, as workers in computer science.

To enable this international development, however, communication between scientists was necessary. Although they had meetings dedicated to their common goal, communication on programming languages between different groups and people with different backgrounds appeared difficult: a sufficient notation to describe and discuss programming languages was lacking.

From IAL to ALGOL 60: notation and language

A sufficient notation was developed during the two years between the publication of the draft report on IAL and the publication of the ALGOL 60 report. In Chapter Notation this development of notation is discussed. Notation is important because it enables one to formally define a language in such a way that everyone can read and interpret the definition in the same way.

The notation to describe the early programming languages, like FORTRAN and IAL, was mostly natural language combined with some patterns denoting the form of the various language elements. The problem with this notation was ambiguity. Even for simple language elements, like numbers, expressions and simple control structures, this was already a problem. For complex structures like the procedure statement and declarations it was more problematic.

To give a more formal and complete description of the syntax of IAL a new notation was invented by Backus: the Backus Normal Form. Using this simple notation, complex structures in the language could be described formally. Unfortunately, the procedure concept of IAL was too complex to be described using this notation.

The procedure concept was also the most controversial topic in the various discussions on the development of ALGOL 60. Eventually, in the ALGOL 60 report, the procedure concept was strongly simplified. Input and output parameters were removed and call-by-name and call-by-value parameters introduced. Another important aspect of the new language was the notion of a block with its own scope. This block was an extension of the compound statement from IAL. What was new was recursion, added implicitly to the language because it was not explicitly forbidden.

The ALGOL 60 report was edited by Peter Naur. He wrote the draft version and used a slightly modified version of Backus’s notation to describe the language. This draft was used as the basis for the ALGOL meeting. The final report would become the standard method of defining programming languages and the BNF became the standard method to describe the syntax of programming languages.

The importance of this phase of the ALGOL effort was twofold. First of all, it resulted in a new notation which would become the standard to define and describe programming languages. Although the goal of the ALGOL effort was to create a universal algorithmic language, it also created a universal metalanguage to describe all programming languages. The scope of the effort became larger than only the development of ALGOL 60: the whole field of programming languages became the scope of the ALGOL effort.

Second, the ALGOL effort became truly international and the result, ALGOL 60, was a new programming language, substantially different from the earlier algorithmic languages. It had a clear syntax and it introduced some interesting concepts to a broader public, like blocks, procedures and recursion.

In 1958, the common goal of the ALGOL effort was shared by a small number of computer scientists from the USA and Central Europe. With the publication of the ALGOL 60 report, the common spirit was shared by many computer scientists from all over the world. Computer science had produced a potent result: ALGOL 60.

From craftsmanship to science: translating ALGOL 60

The potential of ALGOL 60 became clear during the implementation phase in the early 1960s: the ALGOL effort was a catalyst, transforming the field of translator writing from craftsmanship into a science (see Chapter Translation. This transformation started with the development and publication of a translation technique for IAL by Bauer and Samelson. They were the initiators of the ALGOL effort and started with the construction of both a language and translation technique. Although their technique was known and developed by many other computer scientists, it was the publication of their technique that made it so important.

The language was made to fit the technique, and vice versa. When Bauer and Samelson, some months before the ALGOL 60 was created, published their technique, their article became widely read. And, because of the popularity of ALGOL 60, the implementation of many translators was being started, many based upon the technique described by Bauer and Samelson. During this process, the isolated nature of efforts to create an algebraic language was finally broken: publication and referring to publications became the norm.

Although there was a translation technique for IAL, to translate ALGOL 60, the technique had to be extended. These extensions fitted into the well known translation technique. Other approaches to the translation of ALGOL were improving the technique and inventing new techniques: syntax directed translation techniques. A new technique was invented based on the structure of ALGOL. From left to right, from bottom to top, this technique was based on a metalanguage in which both syntax and semantics were to be specified. A general translator was then able, with these specifications and a program text, to translate the program into a executable version.

Although these approaches were different, the lack of a common notation, terminology, or theory was striking. Clearly, the field missed a sound theory to be able to evolve from a craft into a science. Ginsburg and Rice supplied the field with a theory: they created the connection between Chomsky’s context-free languages and ALGOL-like languages and hence connected the field of programming languages with other theories of computing and automata theory. With that, computer science received its own theoretical component.

The further development of the field of translator writing, although related to ALGOL at first, was no longer ALGOL centred. It became an active field of research, evolving independently from the ALGOL effort.

In search of a worthy successor to ALGOL 60

The ALGOL effort continued with a period of maintenance (see Chapter Succession. A formal maintenance body was necessary to become accepted, although it did not work out very well. Although ALGOL 60 was the most used programming language for man-to-man communication, it failed to truly become the universal language due to the computational context of that time: the predominance of IBM pushing FORTRAN, the legacy of applications already created and used in industry. ALGOL was a new untested language, and, especially on the American market and outside universities, it could not win the fight with FORTRAN.

Second, the ALGOL effort was moved to IFIP, solving the lack of a governing body. It was, however, too late to gain a fundamental part of the market. As part of IFIP, Working Group 2.1 created some reports on subsets, I/O, and standardisation. These results were not very interesting, and, not important for the field of programming languages or computer science.

The move to create a successor to ALGOL 60 in 1964, however, was much more important. The ALGOL effort became a platform for the best computer scientists of that period to discuss programming languages and their underlying concepts. Many proposals were made and discussed, most of them boiling down to extra types, string handling, cleaning up the statement, and other minor improvements. Major improvements were made by Hoare: the case expression which allowed the removal of designational expressions and part of the label concept.

More important was his paper on record handling. With records came references and with references, the controversial call-by-name parameter concept could be replaced with the call-by-reference parameter concept. Although records were not new, Hoare made them a general programming language concept.

There were other proposals, on overloading and the ability to (re)define operators. Furthermore, van Wijngaarden proposed orthogonality, one of the most important contributions to programming. In addition, the standard library became larger, containing not only mathematical functions, but also I/O, string handling, and type casts.

There was clearly a move from a special-purpose language towards a general programming language. Unfortunately, Working Group 2.1 was not able to define the new language with agreement of all members. The new language had to be defined in a new notatation, the van Wijngaarden grammar, which turned out to result in an unreadable report. After much delay, the draft was presented and accepted by the Working Group as the ALGOL 68 report, however, not without a Minority Report signed by almost half of Working Group 2.1. In this minority report it was stated that they considered the new language a failure. And so the ALGOL effort came to a sad end.

Conclusions: The important contributions by the ALGOL effort

The Backus Naur Form

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.

Programming language concepts

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 and the whole was 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 text 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.

Syntax directed translation and dynamic memory management

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.

The contribution of the field of translator writing

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.

Success and failure

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.

References