A history of ALGOL 68

ABSTRACT

ALGOL 68 is a language with a lot of "history." The reader will hear of discord, resignations, unreadable documents, a minority report, and all manner of politicking. But although ALGOL 68 was produced by a committee (and an unruly one at that), the language itself is no camel. Indeed, the rigorous application of the principle of "orthogonality" makes it one of the cleanest languages around, as I hope to show. Moreover, when the language came to be revised, the atmosphere was quite different, enabling a much more robust and readable defining document to be produced in a spirit of true cooperation. There are some lessons here for future language design efforts, but I am not optimistic that they have been learned.

References

1. {AB 28.1.1} News item---Tenth anniversary colloquium, Zürich, May 1968, ALGOL Bulletin AB28.1.1, Jul. 1968.]]
2. {AB 31.1.1} News item---Minority report, ALGOL Bulletin AB31.1.1, Mar. 1970.]]
3. {AB 52.3.1} Survey of viable ALGOL 68 implementations, ALGOL Bulletin AB52.3.1, Aug. 1988.]]
4. {Baecker, 1968} Baecker, H. D., ASERC---a code for ALGOL 68 basic tokens, ALGOL Bulletin AB28.3.5, Jul. 1968.]]
5. {Boom, 1972} Boom, H. J., IFIP WG 2.1 Working Paper 217 (Vienna 4), Sep. 1972.]]
6. {Branquart, 1976} Branquart, P., Cardinael, J.-P., Lewi, J., Delescaille, J.-P., and Vanbegin, M., An optimized translation process and its application to ALGOL 68, LNCS 38. New York: Springer-Verlag, 1976.]]
7. {Chastellier, 1969} De Chastellier, G., and Colmerauer, A., W-Grammar, Proc. 24th National Conference. New York: ACM Publication P-69, 1969.]]
8. {Colmerauer, 1996} Colmerauer A., and Roussel, P., The birth of Prolog, in these Proceedings.]]
9. {Dahl, 1966} Dahl, O-J, A plea for multiprogramming, ALGOL Bulletin AB24.3.5, Sep. 1966.]]
10. {Dahl, 1968} Dahl, O-J, Myhrhaug, B., and Nygaard, K., The Simula 67 Common Base Language. Oslo: Norwegian Computing Centre, Oslo, 1968.]]
11. {De Morgan, 1976a} De Morgan, R. M., Hill, I. D., and Wichman, B. A., A supplement to the ALGOL 60 revised report, Comp. Jour. 19:3, Aug. 1976, pp. 276--288; also SIGPLAN Notices 12:1, January 1977, pp. 52--66.]]
12. {De Morgan, 1976b} De Morgan, R. M., Modified report on the algorithmic language ALGOL 60, Comp. Jour. 19:4, Nov. 1976, pp. 364--379 ({Naur et al. 1962} as modified by {De Morgan 1976}).]]
13. {De Morgan, 1978} De Morgan, R. M., Hill, I. D., and Wichman, B., A. Modified ALGOL 60 and the step-until element, Comp. Jour. 21:3, Aug. 1978, p. 282 (essential errata to {De Morgan, 1976a} and Modified report {1976b}).]]
14. {Dijkstra, 1968a} Dijkstra, E. W., Cooperating sequential processes, In Programming Languages, F. Genuys, Ed., New York: Academic Press, 1968.]]
15. {Dijkstra, 1968b} Dijkstra, E. W., Goto considered harmful, letter to the Editor, Comm. ACM 11:3, Mar. 1968.]]
16. {Duncan, 1964} Duncan, F. G., and van Wijngaarden, A., Cleaning up ALGOL 60, ALGOL Bulletin AB16.3.3, May 1964.]]
17. {Garwick, 1965} Garwick, J. V., The question of I/O procedures, ALGOL Bulletin AB19.3.8, Jan. 1965.]]
18. {GOST 27974/9-88} Programming language ALGOL 68 and ALGOL 68 extended, GOST 27974-88 and GOST 27975-88, USSR State Committee for Standards, Moscow, 1989.]]
19. {Grune, 1979} Grune, D., The Revised MC ALGOL 68 test set, IW 122/79, Amsterdam: Mathematisch Centrum, 1979.]]
20. {Hansen, 1977} Hansen, Wilfred J., and Boom, Hendrik, The report on the standard hardware representation for ALGOL 68, SIGPLAN Notices 12:5, May, 1977; also Acta Informatica 9, 1978, pp. 105--119.]]
21. {Hibbard, 1977} Hibbard, P. G., A sublanguage of ALGOL 68, SIGPLAN Notices 12:5, May 1977.]]
22. {Hoare, 1964} Hoare, C. A. R., Case expressions, ALGOL Bulletin AB18.3.7, Oct. 1964.]]
23. {Hoare, 1965a} Hoare, C. A. R., Cleaning up the for statement. ALGOL Bulletin AB21.3.4, Nov. 1965.]]
24. {Hoare, 1965b} Hoare, C. A. R., Record Handling, ALGOL Bulletin AB21.3.6, Nov. 1965.]]
25. {Hoare, 1966} Hoare, C. A. R., Further thoughts on record handling AB21.3.6, ALGOL Bulletin AB23.3.2, May 1966.]]
26. {Hoare, 1968} Hoare, C. A. R., Critique of ALGOL 68, ALGOL Bulletin AB29.3.4, Nov. 1968.]]
27. {Hoare, 1981} Hoare, C. A. R., The emperor's old clothes (the 1980 ACM Turing award lecture), Comm. ACM 24:2, Feb. 1981, pp. 75--83.]]
28. {King, 1974} King, P. R., WG 2.1 subcommittee on ALGOL 68 support, ALGOL Bulletin AB37.3.1, Jul. 1974.]]
29. {Knuth et al., 1964} Knuth D. (Chairman), Bumgarner, L. L., Hamilton, D. E., Ingerman, P. Z., Lietzke, M. P., Merner, J. N., and Ross. D. T., A proposal for input-output conventions in ALGOL 60, Comm. ACM 7:5, May 1964, pp. 273--283.]]
30. {Koster, 1969} Koster, C. H. A., On infinite modes, ALGOL Bulletin AB30.3.3, Feb. 1969.]]
31. {Koster, 1971} Koster, C. H. A., Affix-grammars, in ALGOL 68 Implementation, J. E. L. Peck, Ed., North Holland, 1971, pp. 95--109.]]
32. {Lindsey, 1968} Lindsey, C. H., ALGOL 68 with fewer tears, ALGOL Bulletin AB28.3.1, Jul. 1968.]]
33. {Lindsey, 1971} Lindsey, C. H., and Van der Meulen, S. G., Informal Introduction to ALGOL 68, North Holland, 1971.]]
34. {Lindsey, 1972} Lindsey, C. H., ALGOL 68 with fewer tears, Comp. Jour. 15:2, May 1972.]]
35. {Lindsey, 1976} Lindsey, C. H., Specification of partial parametrization proposal, ALGOL Bulletin AB39.3.1, Feb. 1976.]]
36. {Lindsey, 1977} Lindsey, C. H., and Van der Meulen, S. G., Informal Introduction to ALGOL 68 Revised Edition, North Holland, 1977.]]
37. {Lindsey, 1978} Lindsey, C. H., and Boom, H. J., A modules and separate compilation facility for ALGOL 68, ALGOL Bulletin AB43.3.2, Dec. 1978; also IW 105/78, Mathematisch Centrum, Amsterdam, 1978.]]
38. {Löf, 1984} Martin-Löf, P., Constructive mathematics and computer programming, in Mathematical logic and programming languages, Hoare, C. A. R., and Shepherdson, J. C., Eds. New York: Prentice-Hall, 1985.]]
39. {Lucas, 1969} Lucas, P., and Walk, K., On the formal description of PL/1, in Annual review in automatic programming 6:3, Pergammon, 1969, pp. 105--182.]]
40. {Mailloux, 1968} Mailloux, B. J., On the implementation of ALGOL 68, Mathematisch Centrum, Amsterdam, 1968.]]
41. {McCarthy, 1964} McCarthy, J., Definition of new data types in ALGOL X, ALGOL Bulletin AB18.3.12, Oct. 1964.]]
42. {Meertens, 1969} Meertens, L. G. L. T., On the generation of ALGOL 68 programs involving infinite modes, ALGOL Bulletin AB30.3.4, Feb. 1969.]]
43. {Merner, 1966} Merner, J. M., Garwick, J. V., Ingerman, P. Z., and Paul, M., Report of the ALGOL X I-O subcommittee, IFIP WG 2.1 Working Paper 48 (Warsaw 3), July 1966.]]
44. {Milner, 1990} Milner, R., Tofte, M., and Harper, R., The definition of standard ML, Cambridge, MA: MIT Press, 1990.]]
45. {MR 76} Van Wijngaarden, A., Orthogonal design and description of a formal language. MR 76, Mathematisch Centrum, Amsterdam, Oct. 1965.]]
46. {W-2} Van Wijngaarden, A., and Mailloux, B. J., A draft proposal for the algorithmic language ALGOL X, IFIP WG 2.1 Working Paper 47 (Warsaw 2), Oct. 1966.]]
47. {MR 88} Van Wijngaarden, A., Mailloux, B. J., and Peck, J. E. L., A draft proposal for the algorithmic language ALGOL 67, MR 88, Mathematisch Centrum, Amsterdam, May 1967.]]
48. {MR 93} Van Wijngaarden, A., Ed., Mailloux, B. J., Peck, J. E. L., and Koster, C. H. A., Draft report on the algorithmic language ALGOL 68, MR 93, Mathematisch Centrum, Amsterdam, Jan. 1968.]]
49. {MR 95} Van Wijngaarden, A., Ed., Mailloux, B. J., Peck, J. E. L., and Koster, C. H. A., Working document on the algorithmic language ALGOL 68, MR 95, Mathematisch Centrum, Amsterdam, Jul. 1968.]]
50. {MR 99} Van Wijngaarden, A., Ed., Mailloux, B. J., Peck, J. E. L., and Koster, C. H. A., Penultimate draft report on the algorithmic language ALGOL 68, MR 99, Mathematisch Centrum, Amsterdam, Oct. 1968.]]
51. {MR 100} Van Wijngaarden, A., Ed., Mailloux, B. J., Peck, J. E. L., and Koster, C. H. A., Final draft report on the algorithmic language ALGOL 68, MR 100, Mathematisch Centrum, Amsterdam, Dec. 1968.]]
52. {MR 101} The first printing of {Van Wijngaarden 1969}.]]
53. {Naur et al., 1960} Backus, J. W., Bauer, F. L., Green, J., Katz, C., McCarthy, J., Naur, P. Ed., Perlis, A. J., Rutishauser, H., Samelson, K., Vauquois, B., Wegstein, J. H., Van Wijngaarden, A., and Woodger, M., Report on the algorithmic language ALGOL 60, Numerische Mathematik 2: 1960, pp. 106--136; also Comm. ACM 3:5, May 1960, pp. 299--314.]]
54. {Naur et al., 1962} Backus, J. W., Bauer, F. L., Green, J., Katz, C., McCarthy, J., Naur, P. Ed., Perlis, A. J., Rutishauser, H., Samelson, K., Vauquois, B., Wegstein, J. H., Van Wijngaarden, A., and Woodger, M., Revised report on the algorithmic language ALGOL 60, Numerische Mathematik 4: 1963, pp. 420--453; also Comm. ACM 6:1, Jan. 1963, pp. 1--17; also Comp. Jour., 5:1, Jan. 1963, pp. 349--367.]]
55. {Naur, 1964} Naur, P., Proposals for a new language, ALGOL Bulletin AB18.3.9, Oct. 1964.]]
56. {Naur, 1966} Naur, P., The form of specifications, ALGOL Bulletin AB22.3.7, Feb. 1966]]
57. {Naur, 1968} Naur, P., Successes and failures of the ALGOL effort, ALGOL Bulletin AB28.3.3, Jul. 1968.]]
58. {Naur, 1981} Naur, P., The European side of the last phase of the development of ALGOL 60, in History of Programming Languages, Richard L. Wexelblat, Ed. New York: Academic Press, 1981.]]
59. {Pair, 1970} Pair, C., Concerning the syntax of ALGOL 68, ALGOL Bulletin AB31.3.2, Mar. 1970.]]
60. {Peck, 1971} Peck J. E. L., ed., ALGOL 68 Implementation, North Holland, 1971.]]
61. {R} See {Van Wijngaarden 1969}.]]
62. {RR} See {Van Wijngaarden 1975}.]]
63. {Ritchie, 1993} Ritchie, D. M., The development of the C language, in these Proceedings.]]
64. {Ross, 1961} Ross, D. T., A generalized technique for symbol manipulation and numerical calculation, Comm. ACM, 4:3, Mar. 1961, pp. 147--50.]]
65. {Ross, 1969} Ross, D. T., Concerning a minority report on ALGOL 68, ALGOL Bulletin AB30.2.3, Feb. 1969.]]
66. {Samelson, 1965} Samelson, K., Functionals and functional transformations, ALGOL Bulletin AB20.3.3, Jul. 1965.]]
67. {Seegmüller, 1965a} Seegmüller, G., Some proposals for ALGOL X, ALGOL Bulletin AB21.3.1, Nov. 1965.]]
68. {Seegmüller, 1965b} Seegmüller, G., A proposal for a basis for a report on a successor to ALGOL 60, Bavarian Acad. Sci., Munich, Oct. 1965.]]
69. {Sintzoff, 1967} Sintzoff, M., Existence of a Van Wijngaarden syntax for every recursively enumerable set, Annales Soc. Sci. Bruxelles, II, 1967, pp. 115--118.]]
70. {Schuman, 1974} Schuman, S. A., Toward modular programming in high-level languages, ALGOL Bulletin AB37.4.1, Jul. 1974.]]
71. {Stroustrup, 1996} Stroustrup, B., A history of C++, in these Proceedings.]]
72. {TR 74-3} The first printing of {Van Wijngaarden 1975}, published as Technical Report TR74-3, Dept. of Computing Science, University of Alberta, Mar. 1974; subject to errata published in ALGOL Bulletin AB37.5 Jul. 1974, AB38.5.1 Dec. 1974, and AB39.5.1 Feb. 1976.]]
73. {Turski, 1968} Turski, W. M., Some remarks on a chapter from a document, ALGOL Bulletin AB29.2.4, Nov. 1968.]]
74. {Turski, 1981} Turski, W. M., ALGOL 68 revisited twelve years later or from AAD to ADA, in Algorithmic Languages, J. W. de Bakker and J. C. van Vliet, Eds., North Holland, 1981.]]
75. {Van der Meulen, 1978} Van der Meulen, S. G. and Veldhorst, M., TORRIX---a programming system for operations on vectors and matrices over arbitrary fields and of variable size Vol. 1, Mathematical Centre Tracts 86, Mathematisch Centrum, Amsterdam, 1978.]]
76. {Van der Poel, 1965} Van der Poel, W. L., extract from WG 2.1 Activity Report, ALGOL Bulletin AB21.1.1.]]
77. {Van der Poel, 1986} Van der Poel, W. L., Some notes on the history of ALGOL, in A quarter century of IFIP, H. Zemanek, Ed., North Holland, 1986.]]
78. {Van Vliet, 1979} Van Vliet, J. C., ALGOL 68 transput, Pt 1: Historical review and discussion of the implementation model, Pt 2: An implementation model, Mathematical Centre Tracts 110 and 111, Mathematisch Centrum, 1979.]]
79. {Van Wijngaarden, 1969} Van Wijngaarden, A., Ed., Mailloux, B. J., Peck, J. E. L., and Koster, C. H. A., Report on the algorithmic language ALGOL 68, Numerische Mathematik 14: 1969, pp. 79--218; also A. P. Ershov and A. Bahrs, transl., Kybernetica 6, 1969, and 7, 1970, bilingual; also I. O. Kerner (transl.), Bericht über die algorithmische sprache ALGOL 68, Akademie-Verlag, Berlin, 1972, bilingual; also J. Buffet, P. Arnal and A. Quéré (transl.), Définition du langage algorithmique ALGOL 68, Hermann, Paris, 1972; also Lu Ru Qian (transl.), See pdf for more details.]]
80. {Van Wijngaarden, 1975} Van Wijngaarden, A., Mailloux, B. J., Peck, J. E. L., Koster, C. H. A., Sintzoff, M., Lindsey, C. H., Meertens, L. G. L. T., and Fisker, R. G., Revised report on the algorithmic language ALGOL 68, Acta Informatica 5:1--3, 1975; also Mathematical Centre Tract 50, Mathematisch Centrum, Amsterdam; also SIGPLAN Notices 12:5, May 1977; also I. O. Kerner, (transl.), Revidierter bericht über die algorithmische sprache ALGOL 68, Akademie-Verlag, Berlin, 1978; also A. A. Bahrs (transl.) and A. P. Ershov (Ed.), Peresmotrenoye So'obszczeniye ob ALGOLE 68, Izdatelstvo "MIR," Moscow, 1979; also Lu Ru Qian (transl.), See pdf for more details.]]
81. {W-2} Van Wijngaarden, A., and Mailloux, B. J., A draft proposal for the algorithmic language ALGOL X, IFIP WG 2.1 Working Paper 47 (Warsaw 2), Oct. 1966.]]
82. {WG 2.1, 1964a} Report on SUBSET ALGOL 60 (IFIP), Numerische Mathematik 6: (1964), pp. 454--458; also Comm. ACM 7:10, Oct. 1964, p. 626.]]
83. {WG 2.1, 1964b} Report on input-output procedures for ALGOL 60, Numerische Mathematik 6: pp. 459--462; also Comm. ACM 7:10, Oct. 1964, p 628.]]
84. {WG 2.1, 1971a} Report of the subcommittee on data processing and transput, ALGOL Bulletin AB32.3.3, May 1971.]]
85. {WG 2.1, 1971b} Report of the subcommittee on maintenance and improvements to ALGOL 68, ALGOL Bulletin AB32.3.4, May 1971.]]
86. {WG 2.1, 1971c} Letter concerning ALGOL 68 to the readers of the ALGOL Bulletin, ALGOL Bulletin AB32.2.8, May 1971.]]
87. {WG 2.1, 1972a} WG 2.1 formal resolution: Revised report on ALGOL 68, ALGOL Bulletin AB33.1.1, Mar. 1972.]]
88. {WG 2.1, 1972b} Report of the subcommittee on maintenance of and improvements to ALGOL 68, August 1971, ALGOL Bulletin AB33.3.3, Mar. 1972.]]
89. {WG 2.1, 1972c} Report of the subcommittee on data processing and transput, August 1971, ALGOL Bulletin AB33.3.4, Mar. 1972.]]
90. {WG 2.1, 1972d} Report on the meeting of working group 2.1 held at Fontainebleau, ALGOL Bulletin AB34.3.1, Jul. 1972.]]
91. {WG 2.1, 1972e} Report on considered improvements, ALGOL Bulletin AB34.3.2, Jul. 1972.]]
92. {WG 2.1, 1972f} Proposals for revision of the transput section of the report, ALGOL Bulletin AB34.3.3, Jul. 1972.]]
93. {WG 2.1, 1973a} Further report on improvements to ALGOL 68, ALGOL Bulletin AB35.3.1, Mar. 1973.]]
94. {WG 2.1, 1973b} Final report on improvements to ALGOL 68, ALGOL Bulletin AB36.3.1, Nov. 1973.]]
95. {WG 2.1, 1975} IFIP WG 2.1 Working Paper 287 (TUM 10), Munich, Aug. 1975.]]
96. {WG 2.1, 1978} Commentaries on the revised report, ALGOL Bulletin AB43.3.1, Dec. 1978.]]
97. {WG 2.1, 1979} Commentaries on the revised report, ALGOL Bulletin AB44.3.1, May 1979.]]
98. {Wirth, 1965} Wirth, N., A proposal for a report on a successor of ALGOL 60, MR 75, Mathematisch Centrum, Amsterdam, Oct. 1965.]]
99. {Wirth, 1966a} Wirth, N., and Weber, H., EULER: A generalization of ALGOL, and its formal definition: Part II, Comm. ACM 9:2, Feb. 1966, pp. 89--99.]]
100. {Wirth, 1966b} Wirth, N., and Hoare, C. A. R., A contribution to the development of ALGOL, Comm. ACM 9:6, Jun. 1966, pp. 413--431.]]
101. {Wirth, 1966c} Wirth, N., Additional notes on "A contribution to the development of ALGOL," ALGOL Bulletin AB24.3.3, Sep. 1966.]]
102. {Wirth, 1968} ALGOL colloquium---closing word, ALGOL Bulletin AB29.3.2, Nov. 1968.]]

Index Terms

• Social and professional topics

  • Professional topics

    • History of computing

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language features

        • Data types and structures

        • Procedures, functions and subroutines

      • Language types

• Theory of computation

  • Logic

  • Semantics and reasoning

    • Program semantics

      • Operational semantics