ALGOL 68(ID:311/alg019)

3rd generation ALGOL 

• Array

• Primes BEGIN # Algol-68 primes numbers, functional style   27/6/85 #       # L.Allison Computer Science, University of Western Australia #       #           Computer Science, Monash University, Australia #    PROC error = (STRING s)VOID:       BEGIN print(( newline, " error:", s, newline));             GOTO stop       END;       MODE LIST = REF NODE;    MODE NODE = STRUCT(INT h, LIST t);    PROC cons = (INT n, LIST l)LIST:       HEAP NODE := (n,l);    PROC hd = (LIST l)INT:       IF l IS NIL THEN error(" hd nil"); SKIP  ELSE h OF l FI;    PROC tl = (LIST l)LIST:       IF l IS NIL THEN error(" tl nil"); SKIP  ELSE t OF l FI;    PROC show = (LIST l)VOID:       IF l ISNT NIL THEN print((" ",whole(hd(l),0))); show(tl(l)) FI;    PROC to = (INT n)LIST:       BEGIN PROC f = (INT m,n)LIST:             IF m>n THEN NIL ELSE cons(m, f(m+1,n)) FI;                f(1,n)       END;    PROC filter = (PROC(INT)BOOL p, LIST l)LIST:       IF l IS NIL THEN NIL       ELIF p(hd(l)) THEN cons(hd(l), filter(p,tl(l)))       ELSE filter(p, tl(l))       FI;    PROC sieve = (LIST l)LIST:       IF l IS NIL THEN NIL       ELSE PROC notmultiple = (INT n)BOOL:            n MOD (hd(l)) ~= 0;                 cons( hd(l), sieve( filter(notmultiple,tl(l)) ))       FI;    PROC primes = (INT n)LIST:       sieve(tl(to(n)));    show( primes(100) ) END

  
  ');"> Primes

  Tree merging BEGIN # sort-tree merging,    L. Allison 7/4/86 Dept. Computer Science, Monash University, Australia    see: L. Allison. Some Applications of Continuations.                     The Computer Journal 31(1) pp9-16, 1988 #    MODE TREE = REF NODE;    MODE NODE = STRUCT(INT e, TREE l, r);    PROC insert = (INT e, REF TREE t)VOID:       # NB inserts in t as a side effect #       IF TREE(t) IS NIL THEN t := HEAP NODE := (e, TREE(NIL), TREE(NIL))       ELIF e < e OF t THEN insert(e, l OF t)       ELIF e > e OF t THEN insert(e, r OF t)       FI;    PROC show = (TREE t)VOID:       IF t ISNT NIL THEN print(&quot;(&quot;); show(l OF t); print(e OF t); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; show(r OF t); print(&quot;)&quot;)       FI;    PROC merge = (TREE s, t)VOID:    BEGIN       MODE SCANNER = PROC(INT, SCANNER)VOID;       PROC traverse = (INT switch, TREE t, SCANNER continue, alternative)VOID: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; IF t IS NIL THEN continue(switch, alternative) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ELSE PROC goright = (INT sw, SCANNER alt)VOID: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;    trav(sw, t, continue, alt); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;      traverse(switch, l OF t, goright, alternative) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; FI;       PROC trav = (INT switch, TREE t, SCANNER continue, alternative)VOID: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; # traverse the root node and right sub-tree of t  only. # &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; IF t IS NIL THEN continue(switch, alternative) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ELIF e OF t  <=  switch THEN &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;       print(e OF t); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;       traverse( switch, r OF t, continue, alternative) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ELSE  # e OF t > switch # &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;       PROC defer = (INT sw, SCANNER alt)VOID: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;     trav(sw, t, continue, alt); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;       alternative(e OF t, defer) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; FI;       PROC m =  (TREE s, t, SCANNER scans, scant)VOID: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; IF TREE(l OF s) ISNT NIL THEN &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;    PROC travright = (INT sw, SCANNER alt)VOID: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  trav(sw, s, scans, alt); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;    m(l OF s, t, travright, scant)          ELIF TREE(l OF t) ISNT NIL THEN &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;    m(t, s, scant, scans) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ELSE # l OF s  IS  l OF t  IS  NIL, so now have their smallest elts  #             PROC scanstree = (INT sw, SCANNER alt)VOID: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;          trav( sw, s, scans, alt); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;    PROC scanttree = (INT sw, SCANNER alt)VOID: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;          trav( sw, t, scant, alt); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;    IF (e OF s) <= (e OF t) THEN scanstree( e OF t, scanttree) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;    ELSE scanttree( e OF s, scanstree) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; FI FI;       SCANNER halt = (INT sw, SCANNER a)VOID: print((&quot; the end&quot;, newline));       SCANNER fin  = (INT sw, SCANNER a)VOID: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; (print( &quot; finish: &quot;); a(max int, halt));       IF   s IS NIL THEN traverse( max int, t, halt, halt)       ELIF t IS NIL THEN traverse( max int, s, halt, halt)       ELSE m(s, t, fin, fin)       FI    END #merge#;    LOC TREE s:=TREE(NIL), t:=TREE(NIL);    LOC INT n;    WHILE read(n); n>=0 DO insert(n, s) OD;    show(s); print(newline);    WHILE read(n); n>=0 DO insert(n, t) OD;    show(t); print(newline);    merge(s, t) END

  
  ');"> Tree merging

  Matrix multiplication ( # .nf     Strassen"s O(n^log2(7)) matrix multiplication algorithm     L.Allison  wacsvax  UWA  26 June 1984     Dept. Computer Science, Monash University, Australia # OP * = ([,] INT a,b) [,]INT: IF INT all=1 UPB a; all = 1 LWB a THEN # 1x1 #    a[1,1]*b[1,1] ELSE # nxn #    INT half = all % 2;                      # i.e. all div 2 #    [,]INT a11=a[1:half,1:half],             # i.e. top left quarter of a #        a12=a[1:half,half+1:all],         # top right #        a21=a[half+1:all,1:half],         # etc. #        a22=a[half+1:all,half+1:all],        b11=b[1:half,1:half],        b12=b[1:half,half+1:all],        b21=b[half+1:all,1:half],        b22=b[half+1:all,half+1:all];    LOC[1:all,1:all]INT c;                   # c will become a*b #    REF[,]INT c11=c[1:half,1:half],           c12=c[1:half,half+1:all],           c21=c[half+1:all,1:half],           c22=c[half+1:all,half+1:all];    [,]INT m1=(a12-a22)*(b21+b22),           # NB. only 7 [,]*[,] #           m2=(a11+a22)*(b11+b22),           m3=(a11-a21)*(b11+b12),           m4=(a11+a12)*b22,           m5=a11*(b12-b22),           m6=a22*(b21-b11),           m7=(a21+a22)*b11;    c11:=m1+m2-m4+m6;    c12:=m4+m5;    c21:=m6+m7;    c22:=m2-m3+m5-m7;    c                                        # i.e. return c # FI; OP + = ([,]INT a,b)[,]INT: ( [1:1 UPB a, 1:2 UPB a]INT c;    FOR i TO 1 UPB a DO       FOR j TO 2 UPB a DO       c[i,j]:=a[i,j]+b[i,j]       OD    OD;    c ); OP - = ([,]INT a,b)[,]INT: ( [1:1 UPB a, 1:2 UPB a]INT c;    FOR i TO 1 UPB a DO       FOR j TO 2 UPB a DO          c[i,j]:=a[i,j]-b[i,j]       OD    OD;    c ); PROC show = ([,]INT a)VOID: ( print(newline);    FOR i TO 1 UPB a DO       FOR j TO 2 UPB a DO       print( whole(a[i,j],6) )       OD;       print(newline)    OD;    print(newline) ); [,]INT a=((1,2,3,4),(5,6,7,8),(9,10,11,12),(13,14,15,16)),  # a little test #        b=((17,18,19,20),(21,22,23,24),(25,26,27,28),(29,30,31,32)); show(a); show(b); show(a*b) )

  
  ');"> Matrix multiplication

1963

• van Wijngaarden, Aad (1963) van Wijngaarden, Aad "Generalized Algol" pp 17-26
        in Goodman (ed) (1963) Goodman, Richard (ed) "Annual Review in Automatic Programming" (3) 1963 Pergamon Press, Oxford

1969

• van Wijngaarden, A. (1969) van Wijngaarden, A. (ed.) et al. Report on the algorithmic language Algol 68. pp79-218 Online copy
        in (1969) Numerische Mathematik, 14 1969

1970

• Berry, Daniel M. (1970) Berry, Daniel M. "The importance of implementation models in ALGOL 68: or how to discover the concept of necessary environment" pp14-24
  '); wh.document.close();">Extract: doi

  The need for implementation models in understanding languages, Algol 68 in particular, is stressed. The model is used to demonstrate the new concept of necessary environment of a procedure.

  
  ');">Abstract

  This new concept of necessary environment may be applied to other languages which have procedure values treated as general values, and in which the non-locals are bound as in Algol 60 or 68. In some of these languages such as GEDANKEN [Reynolds] and OREGANO, which this author is developing, the non-locals are kept as long as the procedure value still exists . The usual implementation technique is to save the entire binding time environment . However, saving only the necessary environment would insure correctness while conserving storage.

  
  '); wh.document.close();">Extract: THe necesary environment
        in [SIGPLAN] (1970) SIGPLAN Notices 5(09) September 1970
  Golde, H. (1970) Golde, H. review of A. van Wijngaarden et al 1969

  Since 1963, Working Group 2.1 (WG2.1) on ALGOL of the International Federation for Information Processing (IFIP) has discussed the development of a new language, ALGOL X, as a successor to ALGOL 60. After considerable discussion and criticism within WG2.1, a subgroup prepared this report on ALGOL 68, which was subsequently submitted to IFIP with the request for widespread publication. Although a minority report from WG2.1 expressed the concern that the language and language description in this document will not lead toward better programming languages in the future, the General Assembly of IFIP approved the request for publication with the aim of subjecting the new language to close scrutiny by the computing community. The report presents both a new language and a new language description. It should be emphasized that the report is not to be considered an introduction to the language and its use, but rather an attempt to define syntax and semantics of the language formally and precisely. Anyone interested in learning the language should consult the report by S. G. van der Aleulen and C. H. Lindsay (Informal introduction to ALGOL 68). Undoubtedly other texts on ALGOL 68 will appear in due course. It is impossible to give a complete description of ALGOL 68 in this review, but a few of the major departures from ALGOL 60 should be mentioned. ALGOL 68 generalizes the data type concept to an infinity of modes, including the following: real and integer modes with single and multiple precision; Boolean and character modes; vectors, arrays, and more general structures whose components may be of the same or different types; and pointers to data to any depth, facilitating indirect addressing and list processing. ALGOL 68 is rich in operators; new operators with appropriate priorities can be defined and existing ones redefined by the user, thus making it an extensible language. Subscripting has been generalized, facilitating the selection of a subarray from an array. [?] It appears that ALGOL 68 is an extremely powerful language; many of the desirable extensions to ALGOL 60 are found in the language. It is perhaps fair to say that the step from ALGOL 60 to ALGOL 68 is similar to the step from FORTRAN to PL/I. At present it is not clear whether the language can be learned and used with ease; an assessment of the actual usability of the language must await textbooks and actual implementations. The computing community is currently in the same position with respect to ALGOL 68 as it was in 1960 with respect to ALGOL 60 and in 1964 with respect to PL/I. The language is described in a number of steps and levels. The report defines a strict language, an extended language, and a Presentation language. The strict language is defined by a grammar, using a formalized syntax and descriptive semantics. Valid programs constructed from this grammar are expressed in terms of symbols, denoted in the grammar by names such as letter a symbol, digit five symbol, if symbol, and becomes symbol. The extended language permits a number of notational changes, simplifications, contractions, and additions to the strict language, usually designed to shorten the program statements. Finally, the represe&quot;&quot;tatiorr lai~guarJe associates with each symbol of the strict and extended language one or more representations, to be used as input characters for specific implementations. For example, letter a symbol may be represented by &quot;a&quot;, digit five symbol by &quot;a&quot;, if symbol by &quot;(&quot;, &quot;if&quot;, or &quot;case&quot;, and becomes symbol by &quot;: = &quot;, &quot; . . = &quot;, or &quot;. = &quot;. The formal syntactic description of the strict language bears some resemblance to the BNF description of the ALGOL 60 report, but with notational changes and a powerful substitution mechanism. The concept of metavariable of the ALGOL 60 report is replaced by the concept of notion. The production rules of the strict language are of two types: the first type it?s a pure production such as label: label identifier, label symbol . This rule is to be interpreted as &quot;a label may be rewritten as a label identifier followed by a label symbol.&quot; It is equivalent to the BNF production < label > :: = < label identifier > < label symbol > Here, label symbol is a terminal notion, while for the notion label identifier one would expect to find another rule with this notion on its left-hand side. However, no such rule exists; we have to derive an appropriate production from a rule of the second type, which is really a prototype for a (possibly infinite) number of rules of the strict language: MABEL identifier: TAG . This rule contains two metanotions, MABEL and TAG. The report uses a finite number of such metanotions, and for each defines a context-free grammar such that we can derive a (possibly infinite) number of partial notions or protonotions from the metanotion. For example, for the metanotion MABEL there exist two productions, MABEL:MODE mode. And MABEL: label. Further, from the metanotion MODE we can derive an infinite number of protonotions; e.g., real, long integer, row of character. Similarly, from the metanotion TAG an infinite set of protonotions can be derived, namely all identifiers. Another example of a prototype production is reference to MODE assignation: reference to MODE destination, becomes symbol, MODE source. When a metanotion appears more than once in a prototype production, the same protonotion has to be substituted throughout the rule. Thus eve may substitute row of long real for each occurrence of MODE, but not row of long real for one occurrence and row of real for another. The notions have been chosen to convey a substantial amount of semantic information. Furthermore, the report contains a number of production rules that are not used in any formal derivation, but are provided to permit a more concise semantic description of each notion or set of notions. In general, the semantics are given in the English language. In applying a syntax rule in a derivation, one is confronted with the problem of ~ hich substitutions to make in the rule and which subsequent rules to apply to each of the constituents of its right-hand side. Fortunately, the authors have provided cross-references from each rule to each successor rule and to each predecessor rule, with a fen exceptions. Unfortunately, the report does not make it easy to comprehend the grammatical concepts underlying its syntax; it requires a fair amount of study and practice to fully understand their descriptive power. In this context, the paper by G. de Chastellier and A. Colmerauer [ &quot;W-Grammar.&quot; Proc. ACM 25th National Conf., 1969] provides a further introduction to this style of grammar. In general, the syntax of ALGOL 68 requires some further study; in its present formulation and use it is possibly a detriment to the understanding of the language by a large segment of the computing community. An annoying feature of the document is the phraseology used to describe the language and its interpretation. For example, the execution of a program is called &quot;elaboration&quot;; an assignment is called an &quot;assignation&quot;; input/output is referred to as &quot;transput&quot;; and a number of newly coined words are frequently used, such as &quot;slices,&quot; &quot;trimscripts,&quot; &quot;coercends,&quot; &quot;denotations,&quot; etc. This phraseology may also be a serious impediment in making the language palatable to a great many people. In summary, the report should be widely read and studied; a thorough examination of the language and grammar concepts through implementation, programming, and theoretical studies, with subsequent refinement and improvement of language description, is clearly necessary to give ALGOL 68 a fair chance of survival.

  
  ');">Abstract
        in (1970) ACM Computing Reviews 11(10) October 1970

1971

• Branquart, P.; Lewi, J.; Sintzoff, M.and P.L. Wodo (1971) Branquart, P.; Lewi, J.; Sintzoff, M.and P.L. Wodon: "The composition of semantics in Algol 68"
        in [ACM] (1971) [ACM] CACM 14(01) Jan 1971

1972

• Baecker, H. D. (1972) Baecker, H. D. "On a missing mode in ALGOL 68" pp20-30

  An ALGOL 68 mode with the effect of the PL/1 AREA attribute (both BASED & AUTOMATIC) is proposed. The advantages of the mode are presented, followed by an outline of the modifications that would be needed in the ALGOL 68 syntax and standard prelude. Finally, implementation problems and garbage-collection advantages and disadvantages are surveyed.

  
  ');">Abstract DOI
        in [SIGPLAN] (1972) SIGPLAN Notices 7(12) December 1972
  Lindsey, CH (1972) Lindsey, CH "ALGOL 68 with fewer tears" pp176-188

  ALGOL 68 is a new programming language, designed by Working Group 2.1 of IFIP - the body that produced the 1962 revision of ALGOL 60. This paper, which is intended for the reader with some familiarity with ALGOL 60, is intended as a guide to the new language, emphasising particularly the new features which give it its great power. Many implementations of ALGOL 60 are under way, and the one implementation actually running has successfully compiled this paper.

  
  ');">Abstract Online copy

  begin comment 1. INTRODUCTION. This is a program written in ALGOL 68. It is a valid program, syntactically, although it does not purport to do anything sensible. Rather, its purpose is to introduce the language ALGOL 68, which is defined in van Wijngaarden et 01. (1969) and described in more detail in Lindsey and van der Meulen (1971). There are many similarities between ALGOL 68 and ALGOL 60, and I have rather taken these for granted, concentrating my description on the facilities which are new, or changed. ALGOL 68 brings with it some new terminology, with which you ought to become familiar. For example, the familiar block structure is still there, but now we must talk of "ranges" rather than blocks when speaking of the region of a program within which a variable has its "scope". A program in ALGOL 68, then, consists of a range enclosed between begin and end. This is itself presumed to be enclosed within an outer range within which a variety of constants, built-in procedures, etc. are declared. Comments may be inserted anywhere within a program (i.e. not just between statements), except in the middle of compound characters such as begin and end. I am in the middle of a comment at the moment, and I shall terminate it by writing comment comment is also used at the beginning of a comment (I am in another one now). As an alternative to comment # may be used, at either end. Other alternatives are co 6. These four symbols, of course, cannot be used within comments. As in ALGOL 60, spaces and newlines are everywhere ignored within the program. The remainder of this paper consists of a series of inner ranges, each describing some section of the language, and each containing all the declarations that are needed for the understanding of that section. It should be noted that, as in ALGOL 60, identifiers consist of a letter, followed possibly by further letters and/or digits. Only one alphabet (either upper or lower case) is required, but implementations are at liberty to add a second, or even more.#

  
  '); wh.document.close();">Extract: Introduction
        in The Computer Journal (1972) The Computer Journal 15(2) 1972

  Rosen, S. (1972) Rosen, S. "Programming Systems and Languages 1965-1975"

  In spite of impressive gains by PL/I, Fortran and Cobol remain the languages in which most of the world"s production programs are written and will remain so into the foreseeable future. There is a great deal of theoretical interest in Algol 68 and in extensible languages, but so far at least they have had little practical impact. Problem-oriented languages may very well become the most important language development area in the next five to ten years. In the operating system area all major computer manufacturers set out to produce very ambitious multiprogramming systems, and they all ran into similar problems. A number of university projects, though not directly comparable to those of the manufacturers, have contributed greatly to a better understanding of operating system principles. Important trends include the increased interest in the development of system measurement and evaluation techniques, and increased use of microprogramming for some programming system functions.

  
  ');">Abstract DOI
        in [ACM] (1972) [ACM] CACM 15(07) (July 1972)

1973

• Sammet, Jean E. (1973) Sammet, Jean E. "Roster of Programming Languages for 1973" p147
        in (1974) ACM Computing Reviews 15(04) April 1974

1974

• Gennart, P. E.; Haentjens, R.; Horne, R.; Lathuy, (1974) Gennart, P. E.; Haentjens, R.; Horne, R.; Lathuy, L.; Mathieu, J. "Portability of an ALGOL 68 compiler"
        in van der Poel, Maarsen (eds) (1974) Machine Oriented Higher Level Languages (van der Poel, Maarsen, editors) North Holland 1974
• John Hoskyns and Co (1974) John Hoskyns and Co "Decision tables - Evaluation of programming and systems techniques" Central Computing Agency London 1974
• Leavenworth and Sammet (1974) Leavenworth, Burt M.; Sammet, Jean E. "An overview of nonprocedural languages" pp1-12

  This paper attempts to describe some of the basic characteristics and issues involving the class of programming languages commonly referred to as ?nonprocedural? or ?very high level?. The paper discusses major issues such as terminology, relativeness, and arbitrary sequencing. Five features of nonprocedural languages are described, and a number of specific languages are discussed briefly. A short history of the subject is included.

  
  ');">Abstract
        in [VHLL 1974] (1974) Proceedings of the ACM SIGPLAN symposium on Very high level languages, March 28-29, 1974, Santa Monica, California, United States

1976

• Branquart et al. (1976) Branquart et al. "An Optimized Translation Process and Its Application to ALGOL 68", LNCS 38 Springer-Verlag 1976
• Houssais B., Production systématique de tests comm (1976) Houssais B., Production systématique de tests commandée par une grammaire. Application à la validation d'un compilateur Algol 68. Thèse, IRISA, Université de Rennes, 1976
• Pagan, F.G. (1976) Pagan, F.G. "A Practical Guide to Algol 68", Wiley, 1976
• Pagan, FG (1976) Pagan, FG "On interpreter-oriented definitions of programming languages"

  The constructive approach to the formal definition of the semantics of programming languages has much in common with the notion that a language can be defined by an actual processor which compiles or interprets programs written in that language. The two approaches can be unified if the processor is written in a sufficiently powerful and expressive high-level language so that is closely models a formal definition for the processed language. The resulting processor has the conceptual clarity of the formal scheme as well as the advantages of being executable on a real computer. These points are illustrated by exhibiting a formal definition of a minilanguage using the Vienna Definition Language and an equivalent definition using ALGOL 68.

  
  ');">Abstract Online copy
        in (1976) The Computer Journal 19(2) May 1976
  (1976) The Higher Order Language Working Group (HOLWG) Working Paper on 23 exisitng programming languages
  Wichmann, B. A. (1976) Wichmann, B. A. "Ackermann's function: a study in the efficiency of calling procedures" BIT 16 (1976), pp103-110

  A six line recursive procedure is used to assess the efficiency of the procedure calling mechanism in ALGOL-like languages. The results from some 40 systems varying from ALGOL 68 and PL/I to System Implementation Languages for minicomputers are presented and compared. A hundred to one variation in performance occurs with this test, the major reasons for which are given.

  
  ');">Abstract

  Introduction There are several areas where traditional high-level languages are notably less efficient than hand-coding. Two of these areas are accessing array elements and calling procedures. Although in the former case much research has been done to improve the efficiency (resulting in the ALCOR and FORTRAN H2 compilers), little work has been published on calling procedures. In many scientific computations procedures are not called very frequently but this is not true in non-numeric work. Since modularisation by means of procedures is one of the most powerful programming tools in structuring complex problems, an inefficient calling mechanism can be very detrimental. In recent years there has been an increased use of high-level languages as assembler replacements ? the so-called "System Implementation Languages". Such languages must achieve a high degree of object code efficiency if their use is to become more widespread. The purpose of this paper is to compare the procedure calling mechanism of traditional high-level languages with both system implementation languages and machine-code.

  
  '); wh.document.close();">Extract: Introduction

  Ackermann"s function In view of the paper by Sundblad [1], a reasonable test case for study seemed to be the evaluation of Ackermann"s function. This function has the advantage of being very short and not requiring large integer values for typical cases, yet being complex enough to be a significant test. The figures given in Sundblad"s paper also provided a basis for comparison before many values had been obtained. Following Sundblad, we calculate Ackermann (3,n) for increasing n, in accordance with the complete program listing below. Three figures are determined from the test, the average execution time per call, the number of instructions executed per call and the amount of stack space required for each call. Although the average time per call can be determined from running the program, the other two figures cannot be found so easily and indeed, in many cases the figures are not available. [1]Y. Sundblad, The Ackermann function. A theoretical, computational and formula manipulative study. BIT 11 (1971), 107119.

  
  '); wh.document.close();">Extract: Ackermann's function

  Acknowledgements This work has been inspired by the International Federation for Information Processing Working Group 2.4. The desire of the group to obtain information on the performance of system implementation languages has led to tests such as this. It would not have been possible to write this paper without the active help of the following persons in running the test: ? Mr. L. Ammeraal (Mini-ALGOL 68), Dr R. Backhouse (B5500), Dr J. G. P. Barnes (RTL/2), Dr D. A. Bell (PL516), Dr H. Boom (Cyber 73 ALGOL 68), Mr P. Klint (C-UNIX), Mr R. Conradi (MARY, CYBER 74, 1108, CDC3300), Mr W. Findlay (PASCAL 1906A & machine code), Mr W. B. Foulkes (PASCAL 370/158). Professor G. Goos (B6700), Mr. V. Hath-way (BCPL MOD 1), Mr M. Healey (PL/I OPT), Professor J. J. Horning (Sue 11), Mr B. Jones (ALGOL 60, Dclft 370/165), Dr M. MeKeag (PASCAL & ALGOL 60, 1906S), Mr Z. Mocsi (R10), Dr J. Palme (DEC10 SIMULA & machine code), Mr M.J. Parsons (PALGOL), Dr M. Richards (BCPL), Professor J. S. Rohl (Manchester 1900 ALGOL), Mr P. D. Stephens (IMP), Dr P. Wetherall (ALGOL 68-R), Professor N. Wirth (PASCAL), Professor D. B. Wortman (370/165 machine code) and Professor W. A. Wulf (Bliss 10, Bliss 11 & machine code).

  
  '); wh.document.close();">Extract: Acknowledgements

  Language Computer Time per call (ms) Instructions per call Words per call Characteristic (see below) Written by (if stated) ALGOL 60 B6700 41.2 16 13 ND2VO Professor G. Goos ALGOL 60 B5500 Mk XV.l.01 135 19.5 7 NL2VO Dr R. Backhouse ALGOL 60 EMAS 4/75 46.7 21 18 ND2VO   ALGOL 60 1906A Manchester 29.2 33.5 30 ND2VR Professor J. S. Rohl ALGOL 60 KDF9 Mk2 532 68.5 10 CD2VR   ALGOL 60 1906S XALV 70.9 (120) 13 CD2TR Dr M. McKeag ALGOL 60 370/165 Delft 43.8 (142) ? CD2TR Mr B. Jones ALGOL 60 NU 1108 175 (175) 9 CD2TR Mr R. Conradi ALGOL W 360/67 Mk2 121 (74) (16-45) HD2TR   IMP ICL 4/75 46 17.5 18 ND2VO Mr P. D. Stephens SIMULA 1108 120 (120) 9 HD2TR Mr R. Conradi SIMULA DEC1O(KI1O) 317 (158) ? HD2TR Dr J. Palme SIMULA CYSEN 74 380 (800) (15) HD2TR Mr R. Conradi ALGOL 68 1907F (no heap) 134 28 15 NO2VO Mr. L. Ammeraal ALGOL 68 1907F (heap) 167 34 15 HD2VR Mr. L. Ammeraal ALGOL 68 CDC 6400(subset) 45.3 51 ? HD2VO Dr P. Wetherall ALGOL 68 Cyber 73 vl.0.8 67.8 (60) 7 HD2VR Dr H. Boom Bliss 10 DEClO(KAlO) 53.15 15 5 NLWVR Professor W. A. Wulf /Mr Z. Mocsi PL/I 360/65 OPT v1.2.2 101 (61) 68 HD2AO Mr M. Healey PL/I 360/65 F v5.4 351 (212) (70) HD2AR   PASCAL 1906S 19.1 32.5 11 HDWVR Professor N. Wirth/Mr W. Findlay/Dr M. McKeag PASCAL CDC 6400 34 38.5 6 HDWVO Professor N. Wirth PASCAL 370/158 39 42.5 30 HDWVE Professor N. Wirth/Mr W. B. Foulkes RTL/2 4/70 46 14.5 14 NLWVO Dr J. G. P. Barnes RTL/2 PDP11/20 (107) 30.5 ? CLWVH Dr J. G. P. Barnes PALGOL PDP11/20 (46) 13 3 NLWVO Mr M.J. Parsons Bliss/11 PDP11/20 OPT 31 8 2 NLWVO Professor W. A. Wulf /Professor J. J. Horning MARY SM4 105 30.5 9 COWVR Mr R. Conradi CORAL 66 MOD 1 (21) 15.5 3 NLWVO   PL516 DDP516 84.5 37 2 CLWVH Dr D. A. Bell C (UNIX) PDP 11/45 50.4 26 ? NLWVR Mr P. Klint BCPL 370/165 5.9 19 9 NLWVR Dr M. Richards BCPL PDP 11/45 48 20.5 7 NLWVO Dr M. Richards BCPL MOD 1 (35) 25 7 NLWVR Dr M. Richards/Mr. V. Hathaway Machine code Most machines ? 5-14 1-2 NLWVO Dr J. Palme/Professor D. B. Wortman /Professor W. A. Wulf

  
  '); wh.document.close();">Extract: Results of tests (altered to include authors where known)

  Program listing begin integer i, j, k, k1; real t1, t2; integer procedure Ackermann(m, n); value m, n; integer m, n; Ackermann := if m = 0 then n + l else if n = 0 then Ackermann(m -1,1) else Ackermann(m - 1, Ackermann(m, n - 1)); k:= 16; k1 := 1; for i := 1 step 1 until 6 do begin t1 := cputime; j : = Ackermann(3, i); t2 := cputime; if j = A;-3 then outtext(1, "WRONG VALUE"); outreal(1, t2 ? t1); comment Now output time per call; outreal(1, 3 x (t2 - t1)/(512 x k1 - 15 x k + 9x i + 37))); k1 := 4 x k1; k := 2 x k end end

  
  '); wh.document.close();">Extract: Program listing

  Properties of the algorithm To determine the execution characteristics of the test one needs the following properties of the algorithm (which can be easily proved by induction). The number of executions of each leg of the algorithm in calculating Ackermann (3, n) is: first leg:          (64x4|n-    72x2|n + 6xn + 26)/3 second leg:       (                     24 x 2 | n - 3 x n - 12)/3 third leg:         (64x4|n-    72x2|n + 6xn + 23)/3 total no. of calls =   (128 x4|n-   120x2|n + 9xn + 37)/3 Hence for large n, the average number of instructions per call is half the number of instructions in the first and third legs. Both legs contain the procedure entry and exit overheads and the third leg includes two unsuccessful tests for equality with zero. So the number of instructions executed per call can be found by examining the machine code produced by the compiler. Unfortunately this is not always easy and sometimes almost impossible. To provide an approximate comparative value, an estimate has been made from the time using a Gibson mix value [2] to extrapolate from a similar machine. In a few cases, the instructions executed arc known but the time has not been measured. In these cases, an estimate for the time is given based upon published instruction times. The amount of stack space required by the program is determined by the maximum depth of procedure calls. This is given by Sundblad as Ackermann(3, n) - 1 = 2 | (n + 3) - 4 and occurs when the third leg is being evaluated at all but the last of those levels. Hence the amount of stack space required doubles when n is increased by one. For a more detailed discussion on the storage requirements and the definition of the "maximum depth of recursion" see [5]. To measure this space, Sundblad observed the maximum value of 11 for which Ackermann (3, n) could be calculated using 26K words of store (which he called the "capability"). Although this measurement is easy to take, it only provides a rough estimate of the space needed per call. Examination of the machine code of the third leg of the algorithm gives the precise value. In fact, the number of words per call is the difference in the address of 4m in the inner call to the address of the parameter in the routine. It is not easy to calculate this value from the code, and so a post-mortem print may be the easiest way to find the value. Rather than give the capability, the number of words per call is listed with the results. If only the capability is known, bounds can be given for the number of words per call by assuming that between 3K and 10K words are needed out of the 26K store for the program and run-time system.

  
  '); wh.document.close();">Extract: Properties of the algorithm

  Notes on the results Estimates of missing values are included in the table in brackets and have been calculated in the manner described above. The program listing in all cases has followed the coding given very closely. The only exceptions are 1) the machine code examples, 2) the PASCAL and SUE systems which have no conditional expressions, and 3) PL516 which follows the hardware of the machine in not supporting recursion (stacking is performed by subroutines). Factors influencing the execution speed Factors influencing the call of a recursive procedure vary from inherent problems with the architecture of the machine to purely software problems on the design of the procedure calling mechanism. Against each of the results above is a sequence of letters and digits which describes the principle characteristics governing the execution performance. Recursion. On most modern machines with a few base registers and indexing facilities, the basic overhead of recursion is very small indeed. A few minicomputers do not have adequate base registers or addressing facilities to support recursion. The Honeywell DDP5l6 is of this type, hence with the high-level assembler PL516 stacking must be performed explicitly. On some machines, although the addressing logic is available an additional time penalty occurs by addressing via pointers. On the Modular 1 implementation of CORAL 66, recursion is an option. In fact the code produced with recursion is more efficient than that without recursion. The reason for this is that the short address length of the Modular 1 means that base registers must be loaded to access the variables of another procedure. This is a larger overhead than that incurred using a single stack register which only needs to he incremented and decremented by a small amount. Without recursion, the number of instructions is increased to 19.5 (30% more). Storage allocation. In order to execute this program, a stack storage scheme is necessary. It is sometimes possible on conventional hardware to use an area in the store as stack without performing an explicit software check for stack overflow. One can then rely upon a hardware address violation which should permit the output of a suitable diagnostic. Such systems are marked by an N, whereas C denotes a software stack overflow check. Languages such as ALGOL 68, PL/I and SIMULA require more than a simple stack and hence must perform an overflow check in a manner which allows a recovery to perform some garbage collection. Systems like this arc marked with an H. PASCAL permits additional storage apart from the stack but without garbage collection. Although no garbage collection is involved, PASCAL is marked with an H. Only SIMULA requires an actual garbage collection during the execution of this test. The method used to administer the stack is partly a matter of language design and partly a matter of implementation. For instance, although ALGOL 68 requires a heap, the ALGOL 68-R implementation will run a stack only if the program does not require the heap. The difference, shown above, is that an additional subroutine is called on procedure entry to check that adequate stack space is available. Complete display. Block structured languages in general require a base pointer for every block whose variables can be accessed at the relevant part of the program. This facility is marked with a D. Languages such as BCPL and Burroughs B5500 ALGOL restrict access to local and global identifiers only, permitting a significant economy in pointers. These languages are marked with an L. The actual method of implementing the display can vary independently of the language. For instance, ALGOL W and IMP have every base pointer in a register, the PASCAL implementations above backchain the display (from the local procedure) and ALGOL 68-R keeps a copy in core of the full display in the local block. In almost all cases, there will be small variations in the calling overhead depending upon the relevant positions (in the display) of the call and the procedure. Dynamic stack storage. In ALGOL 60, the sizes of arrays are not, in general, known until program execution. This facility, implemented with second order working store, requires a small overhead on the administration of stack storage even when no arrays are being used, as in this test. Languages requiring such storage are marked with a 2 whereas systems allowing only storage whose size can be determined at compile time are marked with a W. PALGOL and RTL/2 are LW languages and hence require only one stack pointer (and one pointer for static storage depending upon the addressing structure). Parameter handling. The most expensive mechanism is marked with a T which denotes a "thunk" that is required to implement the ALGOL 60 call by name [4]. A thunk can be avoided with this test by performing all parameter checking at compile time and using only the value mechanism (V). The KDF9, B5500 and Atlas ALGOL compilers all use the value mechanism. The use of the thunk mechanism by the other ALGOL 60 compilers is caused by the problem of handling the call of formal procedures whose parameters cannot be specified [3]. With value parameters, the ICL 1900 ALGOL compiler uses a simplified thunk mechanism but the Manchester ALGOL compiler uses the value mechanism. The PL/I systems use call by address which is marked with an A. With recursion, the addresses of parameters are dynamic and in consequence this method is less efficient than call by value. Open code or subroutines. Systems which handle this test entirely by open code are marked with an O, whereas the use of subroutines is marked with an R. The PL/I optimising compiler generates a subroutine call, but it is not invoked unless insufficient stack space is given (which did not happen in this case).

  
  '); wh.document.close();">Extract: Notes on the results and Factors influencing the execution speed

  Conclusion. Ackermann&quot;s function provides a simple method of comparing the efficiency of the procedure calling mechanism of a language permitting recursion. The results show a very wide variation in performance even for languages containing no inherent complications. Additional instructions required in ALGOL 68, PL/I and PASCAL to check for stack overflow are quite insignificant compared to the hundreds of extra instructions executed by the inefficient implementations of ALGOL 60. There is no doubt that &quot;System Implementation Languages&quot; give very much better results on this test without reducing the facilities to the programmer. Machine independence seems to be realised in this case without any measurable cost as BCPL shows. Does Ackermann s function represent a good test for a system implementation language? Unfortunately no statistical information is available to the author on the use of procedures in operating systems and compilers etc. Hence it is not known if, for instance, two parameters is typical. The large amount of stack space used is certainly not typical and can result in pathological situations. For instance, stack space is claimed in 64 word units under George 3 on a 1906A, but is not released. Hence during the first part of the algorithm when the stack is being increased a large operating system overhead occurs. During the second part when the stack is rarely increased beyond its previous maximum, there is no significant overhead. The computational part of testing for the equality with zero, jumping and adding or subtracting one seems very typical of non-numeric work. On the 360 computer, the fact that the the algorithm is very short ( <4K bytes) results in a small saving, but on the IMP compiler which can take advantage of this the speed was only the increased by 3%. From the better figures produced by system implementation languages, the code for Ackermann is roughly divided as follows: instructions subroutine entry and exit      2 stacking return address        1 setting up environment        3 checking for stack overflow     2 (if check made) restoring old environment      3 (on procedure exit) setting parameters          2x1=2 body of Ackermann         8 Total                   21

  
  '); wh.document.close();">Extract: Conclusion

1977

• Bennett, M. (1977) Bennett, M. W. Implementation of a PDP11/ICL1900 cross assembler in Algol 68R pp153-156
        in [Proceedings] (1977) Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977
• Braid, I. C. and Hillyard, R. C. (1977) Braid, I. C. and Hillyard, R. C. "Geometric modelling in ALGOL 68" pp168-174

  The paper describes the experiences of a small team in writing a substantial ALGOL 68 program to model the shapes of engineering components. The application derives much advantage from structures, operators and the heap. It includes a command interpreter, graphics package, vector and matrix routines, and procedures for moving data structures on the heap to and from disc. A system has been devised to ensure safe, selective compilation of program segments.

  
  ');">Abstract
        in [Proceedings] (1977) Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977
  Craven, P. G. (1977) Craven, P. G. "Derivatives without tears in Algol 68" pp19-26

  Algol 68 is a very suitable language for tackling problems which lie somewhere between numerical calculation and algebraic manipulation. An algorithm is presented which evaluates a function of n variables and its n partial derivatives using at most C.m operations, where m is the number of operations required to evaluate the function and C is a constant independent of n. By altering mode declarations, an ordinary piece of program text written to evaluate the function can be made instead to generate the expression tree required for calculation of derivatives.

  
  ');">Abstract
        in [Proceedings] (1977) Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977

  Foster, J. (1977) Foster, J. M. and Foster, P. D. Abstract data and functors pp161-167

  The use of "functors" is proposed to generalise the ideas of abstract data and representation, and it is shown that these ideas have further uses in setting up libraries of algorithms. The properties of functors are discussed.

  
  ');">Abstract
        in [Proceedings] (1977) Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977

  (1977) Grune, Dick Towards the design of a super-language of ALGOL 68 for the Standard Prelude (Excerpt) pp78-81

  The problems concerning SIZETY definitions in an Unabridged Machine-Independent Standard Prelude for ALGOL 68 are examined and tentative solutions are given.

  
  ');">Abstract
        in [Proceedings] (1977) Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977

  Hennell, M. A.; Hedley, D.; Woodward, M. R. (1977) Hennell, M. A.; Hedley, D.; Woodward, M. R. "Quantifying the test effectiveness of Algol 68 programs" pp36-41

  In this paper we describe how a software testbed is used to determine the quality of testing of Algol 68 programs. The system monitors the execution of an Algol 68 program and obtains a run-time execution history. This history is then compared with the results of a static analysis and three levels of testing are calculated. The third level is an extension to Algol 68 of a method originally devised for analysing Fortran IV programs. The system has been used extensively in the coordination stage of the NAG Algol 68 numerical algorithms library and we quote some results obtained from an analysis of stringent tests on these library routines.

  
  ');">Abstract
        in [Proceedings] (1977) Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977

  Housden, R.J.W. (1977) Housden, R.J.W. and Kotarski, N. Character string pattern matching in Algol 68 pp144-152

  An album of modes, operators and procedures has been implemented to provide SNOBOL-like character string pattern matching facilities for the Algol 68 programmer. Most of the primitive functions and operators of SNOBOL 4 are included in the album. This paper describes some of the facilities available and briefly outlines their implementation.

  
  ');">Abstract
        in [Proceedings] (1977) Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977

  (1977) Houssais, Bernard Verification of an Algol 68 implementation pp117-128

  A tool for the systematic production of test cases for a compiler is first presented. The input of the generator are formal grammars, derived from the definition of the reference language. This tool has been applied to the generation of test programs for Algol 68. For each construction which the language possesses, the syntactic structure of the corresponding test and the semantic verifications it contains are given. The test set has begun to be employed on a specific implementation. Discovered errors related to Algol 68 constructions are analysed.

  
  ');">Abstract
        in [Proceedings] (1977) Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977

  Hunter, R. B.; McGettrick, A. D.; Patel, R. (1977) Hunter, R. B.; McGettrick, A. D.; Patel, R. "LL versus LR parsing with illustrations from ALGOL 68" pp49-53
        in [Proceedings] (1977) Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977

  Koch, Wilfried and Oeters, Christoph (1977) Koch, Wilfried and Oeters, Christoph "The Berlin ALGOL 68 implementation" pp102-108

  This paper is an introduction to the portable ALGOL 68 implementation currently developed at the Technical University of Berlin. An overview over the compiler and the other system components is given and the facilities for separate compilation and precompilation are described. Finally, the current state of the implementation is sketched.

  
  ');">Abstract
        in [Proceedings] (1977) Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977

  Pagan, Frank G. (1977) Pagan, Frank G. "Algol 68 as an implementation language for portable interpreters" pp54-62

  By making use of its advanced and highly expressive facilities, Algol 68 can be used to implement interpretive language processors with an unusual degree of conceptual clarity and machine independence. The internal representations of source programs in such a processor consist of high-level data structures which are interpreted by means of a set of readable, mutually recursive Algol 68 procedures. The technique is illustrated by applying it to the implementation of a miniature sample language. Efficiency considerations and aspects of the relevant programming methodology are discussed.

  
  ');">Abstract
        in [Proceedings] (1977) Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977

  Prudom, A.; and Hennell, M. A. (1977) Prudom, A.; and Hennell, M. A. "Some problems concerning the automatic translation of Fortran to Algol 68" pp138-143
        in [Proceedings] (1977) Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977

  (1977) Ratcliff, Bryan ALGOL 68 and structured programming for learner-programmers pp157-160

  A method is described of introducing to absolute beginners basic concepts of structured programming, including constructing programs by ?step-wise refinement?. This is interleaved with a ?top-down? description of a simple mini-subset of ALGOL 68, which is closely followed by the concepts of data structuring and procedurisation, as expressed in this language. Emphasis throughout is on the programming philosophy behind the approach controlling the teaching of ALGOL 68, rather than vice versa.

  
  ');">Abstract
        in [Proceedings] (1977) Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977

  Rayward-Smith, V. (1977) Rayward-Smith, V. J. Using procedures in list processing pp179-183

  In many situations the atoms in a list can require a considerable amount of storage space or can be difficult to evaluate. When handling algorithms which only refer to a few atoms of a list much time and space can be wasted if the whole list is stored. In this paper an attempt is made to store lists as procedures which are only evaluated if absolutely necessary. The difficulties which arise when programming such a list processor in Algol 68 are caused by inherent scoping problems. A solution is presented for linear lists together with an example based on the processing of an infinite list.

  
  ');">Abstract
        in [Proceedings] (1977) Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977

  Simonet, M. (1977) Simonet, M. An attribute description of a subset of Algol 68 pp129-137

  Among the formalisms used for the definition of programming languages, context-free grammars are widely and satisfactorily used, but their power is limited. Augmented with attributes they can express context sensitive aspects of a language. In this paper a subset of Algol 68 is described by an attribute-grammar. This is done in a way which suggests that the attribute point of view may also help reading and writing W-grammars.

  
  ');">Abstract
        in [Proceedings] (1977) Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977

  Szöke, Péter (1977) Szöke, Péter "Some remarks on new instances and garbage collection" pp42-48

  Some questions of run-time storage management for ALGOL 68 are discussed. In the first section it is shown that in many cases copying of already existing values is not necessary, in spite of the fact that the Report prescribes this. The second section gives a new approach for finding the starting points for tracing the lists of values during garbage collection. In the third section we introduce a new area (in addition to the stack and the heap) for making the garbage collection process less expensive. The fourth section describes the general memory organization: stack, heap and bubble.

  
  ');">Abstract
        in [Proceedings] (1977) Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977

  Taupin, Daniel (1977) Taupin, Daniel "The ALGOL 68 compiler of Paris-XI University (Orsay)" pp109-116

  The ALGOL-68 compiler of the University of Paris-XI (Orsay) has been implemented for Univac"s 1110-series, under EXEC-VIII. It can compile the ?full language? (including formats, unions, flexible arrays, recursive modes, parallel computation, etc.). It consists in 8 passes and yields usual relocatable code. Minor restrictions concern equivalence recognition of crossed recursive modes, multiple precision and short modes, and scope checking.

  
  ');">Abstract
        in [Proceedings] (1977) Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977

  van der Meulen, S. G. (1977) van der Meulen, S. G. "ALGOL 68 might-have-beens" pp1-18

  This paper discusses some language features which might have been in ALGOL68. They would not have complicated the compiler to any considerable extent. They would certainly have contributed to the expressive power of the language. In fact their desirability emerged from the practice of ALGOL68 programming. "Might-have-beens" are small super-language features and some of them could even be considered as "might-be"s in the sense that they still might be incorporated in existing compilers without (great) difficulty. A few of these "lost chances" have deeper roots and may contribute to the development of future languages.

  
  ');">Abstract
        in [Proceedings] (1977) Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977

  van Vliet, J. (1977) van Vliet, J. C. Towards a machine-independent transput section pp71-77

  If the transput section of an ALGOL-68 compiler is to be portable, it must be described in such a way that it is clear which aspects are machine-dependent, and which are not. There should be a clear set of primitives underlying the transput. In this report, a description is proposed which can really be used as an implementation model: the transput is described in pseudo-ALGOL 68, except for the underlying primitives, whose semantics are given in some kind of formalized English. The state of this model is by no means definitive, but may serve as a start for further discussion.

  
  ');">Abstract
        in [Proceedings] (1977) Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977

  Vansina, C. F. (1977) Vansina, C. F. "Description of dynamic manipulation of ALGOL68 values using a generative grammar." pp63-70

  This paper describes some of the techniques which can be used for managing the run time storage required for an ALGOL68 program. The emphasis is on stack storage, since garbage collection techniques would require another paper. The problems caused by some ALGOL68 constructs are described: the solutions given are mainly those adopted in the Cambridge ALGOL68C system

  
  ');">Abstract
        in [Proceedings] (1977) Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977

1978

• Bowlden, H.J. (1978) Bowlden, H.J. "An introduction to Algol 68"
        in [HOPL I] (1979) SIGPLAN Notices 14(04) April 1979 including The first ACM SIGPLAN conference on History of programming languages (HOPL) Los Angeles, CA, June 1-3, 1978
• Sammet, Jean E (1978) Sammet, Jean E "Roster of programming languages for 1976-77" pp56-85
        in [SIGPLAN] (1978) SIGPLAN Notices 13(11) Nov 1978
• Tanenbaum, AS (1978) Tanenbaum, AS "A comparison of PASCAL and ALGOL 68"

  PASCAL and ALGOL 68 language features are critically examined, compared and contrasted with each other. The emphasis is on the differences between the two languages, primarily in the areas of data types and statement types. Shortcomings in both languages are pointed out.

  
  ');">Abstract Online copy
        in (1978) The Computer Journal 21(4)

1979

• McGettrick, Andrew D. (1979) McGettrick, Andrew D. "Aspects of the ALGOL 68 mode structure" pp62-77

  ALGOL 68 is a general purpose programming language which was originally designed, prior to 1968, "to communicate algorithms, to execute them efficiently on a variety of different computers, and to aid in teaching them to students".    The revised version of the language appeared in 1975.    Future references to ALGOL 68 in this paper refer to this Revised Report, In order to meet these aims ALGOL 68 was designed in an orthogonal fashion:  by limiting the number of new concepts but allowing them to be used in as many ways and as many places as possible the orthogonal idea evolved*    As often happens the design of a programming language and the method of formal definition are interrelated.   In the ALGOL 68 case the orthogonality is achieved by means of a two-level grammar, the two axes of orthogonality being just the two different levels of grammar. The mode structure of ALGOL 68 is fairly sophisticated.   In this paper we consider some aspects of modes which arise naturally as a result of a critical review of the mode structure.   In some cases we ask why there are restrictions on the ways in which modes can be formed and what would happen if these were relaxed, in some cases we ask why certain modes are sensible and in other cases we point out deficiencies in the mode structure itself. The remarks contained here are confined to remarks about modes in ALGOL 68.   Other features of the language do merit some discussion, criticism and/or explanation;   most of these have been mentioned elsewhere. Much of the contents of this paper is not new.   But it seemed sensible to gather together in the one paper the wide variety of remarks that have been made on the ALGOL 68 mode structure and to add some others.

  
  ');">Abstract
        in [SIGPLAN] (1979) SIGPLAN Notices 14(07) July 1979
  Pagan, FG (1979) Pagan, FG "ALGOL 68 as a metalanguage for denotational semantics"

  The possibility of using ALGOL 68 as a metalanguage for "denotational" definitions of the semantics of programming languages is considered, using the simple language LOOP as an example. The approach is found to be a viable one if the "partial parametrisation" feature is added to ALGOL 68. The advantages of using a general purpose programming language as a definitional medium are briefly discussed.

  
  ');">Abstract Online copy
        in (1979) The Computer Journal 22(1)

  Schwartz, R. L. and D. M. Berry (1979) Schwartz, R. L. and D. M. Berry "A semantic view of ALGOL 68"
        in (1979) Computer Languages 4(1)

1980

• Garside, GR and Pintelas, PE (1980) Garside, GR and Pintelas, PE "An ALGOL 68 package for implementing graph algorithms" pp. 237-242

  The implementation of graph-theoretic algorithms using the facilities of standard algorithmic languages is not easy since data structures and operations natural to the subject are not readily available. GRAAP (GRaph Algorithmic Applications Package) is a new system designed to solve this problem. Written in ALGOL 68-R it consists of about 150 operators and procedures which perform operations natural to graph theory and essential to the implementation of graph algorithms. These operators and procedures manipulate information representing graphs and related objects stored in suitably defined structures. GRAAP exists as an album of precompiled segments to minimise compilation time. The operations provided and the transparent internal representations of graphs of different kinds are discussed. The ease with which algorithms can be implemented is demonstrated by examples.

  
  ');">Abstract Online copy

  The implementation of graph-theoretic algorithms using the facilities of standard algorithmic languages is not easy since data struchves and operations natural to the subject are not readily available. GRAAP (GRaph Algorithmic Applications Package) is a new system designed to solve this problem. Written in ALGOL 68-R it consists of about 150 operators and procedures which perform operations natural to graph theory and essential to the implementation of graph algorithms. These operators and procedures manipulate information representing graphs and related objects stored in suitably defined structures. GRAAP exists as an album of precompiled segments to minimise compilation time. The operations provided and the transparent intern1 representations of graphs of different kinds are discussed. The ease with which algorithms can be implemented is demonstrated by examples.

  
  ');">Abstract

  Introduction A graph can be used to represent many physical situations which involve discrete objects and relations between them. The objects are represented by the nodes of the graph and the relations between them are represented by the edges of the graph. We do not repeat here the terminology associated with graphs as this can be found in the many texts now available on the subject. Two such are Deo (1974) and Christofides (1975); these also provide excellent accounts of the diverse applications of graphs. The solution to a problem whose fundamental nature can be represented by a graph may often be obtained by manipulating the graph in a number of discrete steps according to some algorithm. We shall refer to such algorithms as graph algorithms. Example 3.1 implements an algorithm for finding the cliques of a graph using the package described in this paper. In particular the cliques of the graph of Fig. 1 are found (see Fig. 5). Attempting to implement graph algorithms on a computer raises a number of programming problems. These involve the efficient representation and manipulation of a wide variety of graphs of different types and complexity. It is desirable to have facilities which directly use the objects and operations natural to the subject and this has been the aim of the graph algorithmic applications package (GRAAP) described in this paper. The package is written in ALGOL 68-R for use on ICL 1900 series machines. It should be able to cater for most needs imme- diately but the existing facilities can be used as a basis from which to extend into the user"s area of application. This potential extensibility of GRAAP makes it unlike any other package or language so far produced in the area of graph algorithms. The package, which includes structures for representing graphs and related objects as well as routines for handling them, is available as an ALGOL 68-R segmented album and so a user"s program need only include those segments specifically required for the implementation of his algorithm. The object of this paper is to outline the package and its uses; full details are given in Garside and Pintelas (1978). We first sketch the background against which GRAAP has been developed. A large number of software aids for implementing graph algorithms already exist but they are all much more limited than GRAAP. Some of the more important of these are mentioned below. Standard algorithmic languages such as FORTRAN or ALGOL 60, with their restricted data structures, are unsuitable for implementing graph algorithms, while list processing languages provide more appropriate data structures but tend to hide ths graph-theoretic nature of the algorithm and lead to slow execution and large demands for storage (see Rheinbolt, Basili and Mesztenyi, 1972). Special purpose languages and software systems have been developed to free the programmer from representational problems and assist him with the manipulation of graph structures. It would be inefticient to design a new language and write a compiler for it because of the limited application of the language and the enormous amount of time required to produce the compiler. Consequently all graph-theoretic languages are embedded in some well known high level language. There are two main approaches. The first is to extend the host language by designing extra language constructs to take care of the graph statements and expressions. This requires a preprocessor which translates the graph statements into statements of the host language. Languages using this approach are GTPL of King (1970) which is based on FORTRAN 11, GEA of Crespi-Reghizzi and Morpurgo (1968) which is an ALGOL 60 extension with digraphs as a new data type, GASP at the University of Illinois (Chase, 1970) which is an extension of PL/I and GRASPE at the University of Texas (Friedman, 1968) which is an extension language for processing digraphs and has been embedded in SNOBOL4, SLIP-FORTRAN and LISP 1.5. For a full account of existing graph processing aids the reader is referred to Pintelas (1976). The second approach requires the host language to possess facilities which enable new data structures and operations to be defined. ALGOL 68 is such a language and we have used an implementation of this, ALGOL 68-R on ICL 1900 series computers, in producing GRAAP. As far as we know, no other package is available which uses a language with these kinds of facilities. Consequently GRAAP has much wider application than any of the above-mentioned extensions and has already been used to implement many existing graph algorithms and to develop new ones in various fields. Section 2 describes the GRAAP structures and some of the rroutines for handling them, while two examples of the use of the package are given in Section 3. In conclusion Section 4 contains observations based on the experience of using the package extensively.

  
  '); wh.document.close();">Extract: Introduction
        in (1980) The Computer Journal 23(3) 1980
  Hoare, CAR (1980) Hoare, CAR "The Emperor's Old Clothes" the ACM Turing Award lecture, 1980

  During the period, August 1962 to October 1966, I attended every meeeting of the IFIP ALGOL working group. After completing our labours on the IFIP ALGOL subset, we started on the design of ALGOL X, the intended successor to ALGOL 60. More suggestions for new features were made and in May 1965, Niklaus Wirth was commissioned to collate them into a single language design. I was delighted by his draft design which avoided all the known defects of ALGOL 60 and included several new features, all of which could be simply and efficiently implemented, and safely and conveniently used. The description of the language was not yet complete. I worked hard on making suggestions for its improvement and so did many other mambers of our group. By the time of the next meeting in St Pierre de Chartreuse, France in October 1965, we had a draft of an excellent and realistic language design which was published in June 1966 as "A Contribution to the Development of ALGOL", in the Communications of the ACM. It was implemented on the IBM 360 and given the title ALGOL W by its many happy users. It was not only a worthy successor of ALGOL 60, it was even a worthy predecessor of Pascal. At the same meeting, the ALGOL committee had placed before it, a short, incomplete and rather incomprehensible document, describing a different, more ambitious and, to me, a far less attractive language. I was astonished when the working group, consisting of all the best-known international experts of programming languages, resolved to lay aside the commissioned draft on which we had all been working and swallow a line with such an unattractive bait. This happened just one week after our inquest on the 503 Mark II software project. I gave desperate warnings against the obscurity, the complexity, and over-ambition of the new design, but my warnings went unheeded. I conclude that there are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult. It demands the same skill, devotion, insight, and even inspiration as the discovery of the simple physical laws which underlie the complex phenomena of nature. It also requires a willingness to accept objectives which are limited by physical, logical, and technological constraints, and to accept a compromise when conflicting objectives cannot be met. No committee will ever do this until it is too late. So it was with the ALGOL committee. Clearly the draft which it preferred was not yet perfect. So a new and final draft of the new ALGOL language design was promised in three months" time; it was to be submitted to the scrutiny of a subgroup of four members including myself. Three months came and went, without a word of the new draft. After six months, the subgroup met in the Netherlands. We had before us a longer and thicker document, full of errors corrected at the last minute, describing yet another, but to me equally unattractive, language. Niklaus Wirth and I spent some time trying to get removed some of the deficiencies in the design and in the description, but in vain. The completed final draft of the language was promised for the next meeting of the full ALGOL committee in three months" time. Three months come and went - not a word of the new draft appeared. After six months, in October 1966, the ALGOL working group met in Warsaw. It had before it an even longer and thicker document, full of errors corrected at the last minute, describing equally obscurely yet another different, and to me equally unattractive, language. The experts in the group could not see the defects of the design and they firmly resolved to adopt the draft believing it would be completed in three months. In vain, I urged them to remove some of the technical mistakes of the language, the predominance of references, the default type conversions. Far from wishing to simplify the language, the working group actually asked the authors to include even more complex features like overloading of operators and concurrency. When any language design project is nearing completion, there is always a mad rush to get new features added before standardization. The rush is mad indeed, because it leads in to a trap from which there is no escape. A feature which is omitted can always be added later, when its design and its implications are well understood. A feature which is included before it is fully understood can never be removed later. At last, in December 1968, in a mood of black depression, I attended the meeting in Munich at which our long-gestated monster was to come to birth and receive the name ALGOL 68. By this time, a number of other members of the group had become disillusioned, but too late: The committee was now packed with supporters of the language, which was sent up for promulgation by the higher committees of IFIP. The best we could do was to send with it a minority report, stating our considered view that, "...as a tool for the reliable creation of sophisticated programs, the language was a failure." This report was later suppressed by IFIP, an act which reminds me of the lines of Hilaire Belloc,    But scientists who ought to know,    Assure us that it must be so.    Oh, let us never, never doubt    What nobody is sure about. I did not attend any further meetings of that working group.

  
  '); wh.document.close();">Extract: The birth of Algol 68
        in [ACM] (1981) [ACM] CACM 24(02) February 1981

1993

• Bulyonkov, Mikhail A.; Rar, Alexandre F. and Terek (1993) Bulyonkov, Mikhail A.; Rar, Alexandre F. and Terekhov, Andrey N. "Algol 68 - 25 years in USSR" Online copy
        in Alberts, G. (ed) (1993) Alberts, G. (ed) "Conference on the history of ALGOL 68" CWI, Amsterdam 1993
• (1993) IEEE Oral History Interview with Ernst Denert 1993

  My colleague, Reinhold Franck, who is now dead, and I.  We used Algol 68 as a programming language to explain the data structures and algorithms.  As you know, Algol 68 was unsuccessful in the sense that it was never widely used and is not used today.  But it was a very good language for understanding and explaining a lot of concepts.

  
  '); wh.document.close();">Extract: Algol 68
  Meertens, L. (1993) Meertens, L. "The design of elegant languages" pp53-64
        in Alberts, G. (ed) (1993) Alberts, G. (ed) "Conference on the history of ALGOL 68" CWI, Amsterdam 1993

1996

• C.H. Lindsey (1996) C.H. Lindsey "A HISTORY OF ALGOL 68"
        in [HOPL] (1996) "History of Programming Languages", ACM Press/Addison-Wesley Publishing Company, New York (1996) ed Bergin and Gibson
• Koster, Cornelis H. A. (1996) Koster, Cornelis H. A. "The Making of Algol 68" pp55-67

  The Committee My first direct contact with IFIP Working Group 2.1, the Committee, was the meeting in Tirrenia, near Pisa, in June 1968. At the start, the Authors were asked to summarize the reactions to MR93 that had been received, and van Wijngaarden took this opportunity to describe the changes that had been made to the language since the previous meeting (saying "The changes are based on the reactions"). The Committee was much less positive than I expected. Peter Landin deplored that the name "Algol" appeared on the document ("some of my colleagues switched from Algol to Fortran"). Gerhard Seegmueller and Brian Randell took exception to the name "Algol 68" | as if the language had already been accepted by the Committee. Van Wijngaarden was adamant and unrepentant: "I have been asked by the IFIP council to give at the IFIP Congress 68 a talk on "Algol 68"". Salt in the wounds! Van Wijngaarden pressed for a decision by WG2.1 at the next meeting, in North Berwick. "Here is the document on Algol 68. Stamp it under the provision that after two years, in which it is planned to implement, teach and make primers, the language is subject to possible revision as result of this effort. Big companies wouldn"t implement without this stamp." Gerhard Seegmueller then formulated four conditions for acceptance of the Report: 1. Clarification and expansion of the syntax 2. Formalization of the semantics in competitive descriptions 3. Implementation of the language 4. an Informal Introduction. Apart from the Authors, the Committee agreed with these conditions. Van Wijngaarden, dramatically: "Does anybody know of a language of world-wide scope (such as Algol 60, Fortran, PL/1), that has been published after a compiler"? Landin: "Lisp is an example". The discussion returned to technical matters. The coercion mechanism, at that time still using some explicit coercion operators, was criticized as unclear, not fundamental enough and superfluous due to the overloading of operators. The transput proposal was discussed, briefly but quite constructively, I thought. A special evening session was held with the small number of members really interested in the subject: Merner, Seegmueller, Goos and myself. The main outcome was that formats had to be made more general, including dynamic replicators. The dynamic checking of array bounds and scopes of references was discussed. It is striking to note the great concern for micro efficiency, which has in many respects hampered the development of Algol 68. At this point the desire to avoid bound checks still led to awkward syntax, like proc ([1:int n] real vec):, an integer constant- declaration within a formal bound to obtain the size of the array vec. Similarly, a discussion of dynamic scope checks (rightly considered unavoidable in some cases), followed by a discussion on procedures delivering procedures (in some cases limited by scope problems) did not lead to the obvious conclusion to do away totally with the (statically unenforceable) scope restrictions. Algol 68, which has higher-order functions, narrowly missed having Currying, which would have made it possess a complete functional sublanguage, even though Gerhard Goos saw no problem in implementing it. In fact, the drastic and simple proposal to give every object an infinite scope was made by Hans Bekic at a later meeting (where, I do not recall), but this beautifully simple and effective proposal was not accepted for reasons of efficiency. Another chance at more generality that was missed was the extension of operator overloading to procedures, mentioned briefly by Peter Landin. Unfortunately, the discussion veered off from this subject. At various points in the discussion, a sore point in the description came up: the question of infinite productions (such as ALEPH), infinite modes (caused by recursive type declarations) and an infinite number of Context-Free production rules. Van Wijngaarden, who was a purely constructive mathematician, surprised me by his flippancy on the subject. When Nobuo Yoneda and Peter Landin critizised him, he responded: "This problem has puzzled us (not me). My machine may execute steps in geometrically decreasing time intervals". Of course this would also allow "his machine" to prove or disprove Fermat"s Theorem in finite time, so this caused general laughter. Nobuo Yoneda deplored that the unions in MR93 were not commutative and not cumulative, so that union (int, real) was not equivalent to union (real, int) and to union (int, union (int, real)). The Committee decided that unions should be made both commutative and accumulative. Van Wijngaarden protested that this was damned difficult, it would cause a terrible amount of work. Amid general catcalls that his description method was to blame, he promised a revised syntax. "We have only one life. Of course, if one of us gets ill ... { you are drawing such strong time limits on us! Give me time till after lunch." That night, he and John Peck started scribbling, and the next morning he showed us one page of syntax which solved the problem, a nice little nondeterministic automaton. Then came the last phase of the meeting: what would happen next. The majority of the Committee seemed to want to thank the Authors politely for their trouble, and invite others to make alternative definitions. Against this mood van Wijngaarden fought valiantly, pressing for a decision to be taken in the next meeting. At one point, he told the Committee: "This Working Group has worn out its first editor, Peter Naur. Then it has worn out two authors, Wirth and Hoare. If I understand right, it has now worn out four authors." Against tremendous opposition, using every rethorical device 6 he managed to commit WG2.1 to a definite resolution: The authors are invited to undertake to edit a document based on MR93, taking into account the questions and remarks received before, on, and possibly after, this meeting to the best of their power in the time they can afford for this job. This document will be submitted to the members of WG2.1 before 1 October, 68. This document will be considered by WG2.1. Either WG2.1 accepts this document, i.e. submits it to TC 2 as Report on Algol 68, or it rejects it. Even though a large part of the meeting had been very constructive, it ended on a sour note. The behaviour of the great scientists present showed me that the progress of science is not just a matter of objective truths but also strongly in uenced by human emotions. I concluded, still naively, that only a very good language defined in a very clear report could convince the members of WG2.1.

  
  '); wh.document.close();">Extract: The Committee

  Mending the fences We had barely 7 weeks to make a new version of the Report, for the Committee to vote on in North Berwick. In this short time we completely revised the coercion mechanism (so that all coercions were now implicit), as well as the syntax and semantics of arrays. Unions were made commutative and absorbing. Formatted transput was made much more flexible, taking up ever more pages in the Report (and code in eventual implementations). In order to help the reader of the Report, all syntax rules were adorned with compact but helpful crossreferences. A vast number of small examples and explanations were spread as pragmatic remarks all over the text, which therefore grew appreciably in size. All in all, I felt quite satisfied with our work, as I was driving over the appropriately named A68 to meet WG2.1 in North Berwick, with 50 copies of the revised Draft Report [?] in the back of my deux cheveaux. The Authors had done what they had been instructed to do.

  
  '); wh.document.close();">Extract: Mending the fences

  The North-Berwick meeting The meeting started off badly. Since only 15 of the Workinggroup members (out of 34) had been present at Tirrenia, there had been no quorum. The validity of the Resolutions taken, and therefore even the legality of the present meeting, was in doubt. After much debate they were re-voted, and accepted. I wondered whether an illegal meeting could legalize itself by re-voting history. Now and then, all parties took time off to blame the Chairman, Willem Louis van der Poel, for procedural errors or well-meaning remarks that managed to throw oil on the troubled flames. In fact, shouting at the Chairman seemed to be the only activity in which the WG2.1 members found themselves united. A few hours of desultory technical discussion led to the main issue: a discussion of future work. Until then, the future had been clear: after finishing Algol X (apparently with X = 68), the Committee would turn to the study of Algol Y, the language which was to include self-extension. Edsger Dijkstra now proposed a complicated experiment in soulsearching, which led to a heated debate: who would like to do what, and with whom? A small majority considered the finalization and maintenance of Algol 68 the most important, a large minority (including Hoare, Dijkstra and Turski) had wider plans. Actually what was happening was the birth of WG 2.3 7.The overwhelming interest was in "primitives", i.e. elements of semantics. Tony Hoare suggested the production of a brief document by each of the Members on each of his favourite subjects. Van Wijngaarden: "I like to thank Hoare for the distinction between the members who supply us with documents and those who do not." This remark did nothing to clear the atmosphere. Heinz Zemanek gave a stirring address, describing what TC2 expected from WG2.1: "You have to admit either that the document you have in your hands is the new Algol or that the editors have failed. In the second case you may charge the editors with further work or abandon the project. In the latter case you may decide that the contents is O.K. but the description has to be changed. You may also select new authors or issue the document as a preliminary one. You have, however, to make some decision, you cannot escape your responsibility, you cannot get rid of the problem." It was at this point that Doug Ross expressed his desire for a Minority Report, to be part of the Report. Immediately, people started discussing the modalities and timescale for preparation of such a report, rather than its desireability. Van  Wijngaarden protested that at all earlier occasions, the Algol Working Committee had done without a minority report, although there was no one who agreed in every respect with the documents. But the ominous M-word was there to stay. Discussion went on to technical subjects, array bounds and efficiency, the implementer"s burden and the Bauer Principle. The proposal to enforce definition before application (which later led to a number of Algol 68 subsets) was rejected because it would eliminate recursive modes. The same fate befell a suggestion to consider operators as macros rather than procedures. Micro eciency, again. Back we were, on the question of decision to be taken in December, the publication of the Report and the Minority Report and the use of the name Algol 68 in courses and seminars. Most members seemed to like the language described, but this was not the case for the description. Hoare and van Wijngaarden both mentioned the possibility that the Report be published (first) under the names of the Authors, without WG2.1 responsibility, but it was preferred to accompany the Report with an eventual Minority Report, to be drawn up by the end of the next meeting. Van Wijngaarden then brought up the fact that Peter Naur had published in AB28 a paper very critical ofWG2.1 and Algol 68, sparked off by MR93. "As a Council member I will have to bring up the subject of AB28. It contains a piece of mud. IFIP pays the money for AB. I would suggest to the Council to reconsider the money appropriated for editing AB." He was all the more offended, because it was reproduced and distributed by the Mathematical Centre. Why he chose to put this matter before WG2.1, I do not know. His remarks were of course very unfair to Frazer Duncan, the Editor of the AB, and led to a heated discussion, covering most of the morning, regarding censorship, refereeing of articles and duties towards the Computing Community. Van Wijngaarden could make himself either greatly liked or immensely impopular. Barry Mailloux had to say "Chucks, fella"s" many times in his most reconciliatory tone before order was restored. Later, in the absence of van Wijngaarden, Barry felt it necessary to apologize for him. "He did not refuse to reproduce AB, he wanted to express his personal dislike, but nothing more. The second thing is that his statement "I am offended" is a technical and not a personal remark. On my own behalf, I would like to say the following: it was suggested that I and some other people seek fame, credit and fortune. I would like to deny it. I did a lot of work because I do believe in the language and believe strongly enough to wish to propagate it." Thus ended the meeting, which had brought little technical progress but which had prepared the stage for the drama to be enacted in Munich, in December 1968.

  
  '); wh.document.close();">Extract: The North-Berwick meeting

  The IFIP Congress The IFIP 1968 Congress took place that August in Edinburgh, just a few hours drive away from North Berwick. Van Wijngaarden"s invited lecture on Algol 68 was to me the high point of the conference, and not only to me. The auditorium was packed, people were standing on all sides, even in the corridors and outside, in front of the hall. Van Wijngaarden appeared in the centre, smiling radiantly. "Let me sell you a language", he started, and proceeded to outline the ideas behind the language. He showed some examples. "Can you define triangular arrays?" someone (Tony Hoare?) interrupted. "Not just triangular, but even elliptical" replied Aad, and showed how. He carried the listeners with him, from scepsis to enthusiasm. There was a prolonged applause. Vehemently discussing, people streamed out of the hall. A small man pushed through the throng, straight at me. "Conkratulations, your Master hass done it" said Niklaus Wirth in his inimitable Swiss-German English.

  
  '); wh.document.close();">Extract: The IFIP 1968 Congress

  Towards Munich At Munich, it was then, that the ultimate choice would be made. Again Van Wijngaarden, Mailloux and I went over the whole text, making the last changes in the language and its description, cleaning up various dark formulations, correcting small errors and in the process retyping everything. Van Wijngaarden loved the freedom in typefonts offered by the new IBM "golfball" printer, and introduced outlandish symbols for various operators with boldface names (e.g. ELEM and UPB). He found a use for every symbol on the APL-typeball. He would have loved TEX and the possibilities to define new typefonts! There existed no wordprocessing software to speak of, and we had not even the support of an editor to mechanize the production of the Report. How many times have I glued small strips of white paper over Snopake-encrusted originals? By now even sometimes the wording of sentences was influenced by the fact that they had to fit within a given space. The nearer the deadline, the more frantic the work became. We were joined by Lambert Meertens, but still things went too slowly. The text kept changing, always for good reasons, and there was no chance to leave the normal period for an orderly offset production. The printer taught us to make matrices for the offset machine. In the end we had to learn how to bind and glue the whole document. Van Wijngaarden took time off to design and produce a suitable cover. It showed a pattern built out of hundreds of elem-signs - and one little commercial at-sign, his personal mark. On the morning of the last day, after a frantic night and just before our flight left, the work was finished: we had produced the first printing of the Final Draft[ ?]. No time to catch up on sleep. Lambert and I found ourselves sitting in front of the plane, dog tired. What would the Committee decide? We were too tired even to speculate. The stewardess brought us, unbidden, two baby bottles of champagne each, from a Gentleman in the back. We looked over the back of our seats: Van Wijngaarden sat there, besides a sleeping Barry Mailloux, prim as a daisy, and waved his hand at us. The Authors had done their job.

  
  '); wh.document.close();">Extract: Towards Munich

  And after Algol 68 was accepted by WG2.1 as its own child at the Munich meeting in December 1968, but it was a Pyrrhus victory for van Wijngaarden: a large minority dissented, and wrote a minority report. Translations of the Report in many languages appeared, as well as an Informal Introduction and textbooks explaining the two-level formalism. Implementations were slow in coming, apart from some (limited but successful) subset implementations. Before implementations of the full language became available, the state-of-the-art in compiler making had to be advanced quite a lot. The language was used in many courses. Its effect, through teaching, on the minds of a generation of computer scientists was much greater than its utility in practical applications. The announced Revision of Algol 68 started almost immediately and took until 1974. It resulted in an exemplarily clear, precise and consistent description of an elegant and orthogonal language that was at that time already classical but dead - the Ilias and Odyssee of Computer Science. What has gone wrong? Many convincing reasons can be found. The lack of timely implementations (but those people who have actually programmed in Algol 68  remember it as a beautiful means of expression); the obscurity of the description (which is denied by virtually anyone who has bothered to study it); the lack of political and industrial backing (the fate of Algol 60, all over again). I think that Algol 68 was the result and the conclusion of a decade of search for the ideal Algorithmic Language, but that the time for a unique programming language was already over when it appeared. In the seventies, research went on to other problems: Software Engineering, System Implementation Languages, Databases and Computer Graphics. Algol 68 lives on, not only in the minds of people formed by it but also in very unlikely places, like C and C++, whose concepts and terminology at numerous places give a weird echo of Algol 68, even though the orthogonality in the syntax, elegance and security have been mostly lost. A whole new generation of programmers uses coercions and casts. In fact, the boisterous discussions in the programming community about the shortcomings of C++ and solutions to overcome them gives me a strong feeling of deja vu, reminding me of the making of Algol 68. The Far West of Computer Science. In 1974, during an IFIP WG2.4 Meeting in Berlin, I was stopped in the corridor by Jean Ichbiah, the author of the language LIS and designer of what was to become ADA, on his way to the success that brought him the Legion d"Honneur. He said to me with great emphasis: "We are going to do right what Algol 68 has done wrong". Have they really, I wonder?

  
  '); wh.document.close();">Extract: And after
        in [Proceedings] (1996) Proceedings of the Second International Andrei Ershov Memorial Conference on Perspectives of System Informatics LNCS 1161 Springer-Verlag, 1996
  Ritchie, Dennis M. (1996) Ritchie, Dennis M. "The development of the C programming language" in "History of Programming Languages", ACM Press/Addison-Wesley Publishing Company, New York (1996) ed Bergin and Gibson

1998

• Koster, C H :A Shorter History of Algol 68 (1998) Koster, C H :A Shorter History of Algol 68", nd retrieved 1998 Online copy

2002

• Bauer (2002) Bauer, Friedrich L. "My Years with Rutishauser" pdf

  Rutishauser gave a seminal lecture entitled ?Automatische Rechenplanfertigung bei programmgesteuerten Rechenmaschinen? at the GaMM meeting in Freiburg in Breisgau, at the end of March, 1951, which I missed?I was still assistent of Fritz Bopp, the University of Munich Theoretical Physicist, successor of the famous Arnold Sommerfeld. I became aware of the lecture when it was published mid-1952 as an ETH-Mitteilung. Therefore, when I met Heinz Rutishauser in February 1952 for the first time, I was absolutely ignorant about his success, and we did not talk about the subject. It just happens that we met on February 19, 1952; tomorrow it will be 50 years ago.

  
  '); wh.document.close();">Extract: Introduction

  Rutishauser"s way to Stiefel When Rutishauser"started his academic studies, he could not yet knowthat it would lead him to computers. Born on January 30, 1918, son of the headmaster of the thurgauische Kantonsschule in Frauenfeld, he lost his father in 1931 and his mother in 1934. Heinz Rutishauser and his younger brother and sister found a new home at the house of their uncle. In 1936, Heinz earned his Matura and was (I quote from the curriculum vitae) "befahigt zum Studium an der ETH, das er, mit Unterbrechungen durchWehrdienst bei der Festungsartillerie im Gotthardgebiet, 1942 mit dem Diplom alsMathematiker abschloß". Subsequently, he was for three years assistent of professor Walter Saxer at the ETH. During this time, he also acquired the doctors degree with a dissertation "summa cum laude" in the field of the theory of complex functions. After the end of the war, Rutishauser became a mathematics teacher at the gymnasiums in Glarisegg and in Trogen; in 1948 he became, together with Ambros Speiser, an assistent at the newly founded "Institut fur angewandte Mathematik" of the ETH. Thus, he entered the sphere of influence of Eduard Stiefel, a topologist who had before the war written a sensational paper on homology classes and had a high reputation, but now had changed his field. Following his stay in the United States, Rutishauser aimed for "Habilitation". This led to the already mentioned work on "Automatische Rechenplanfertigung" that followed the vague traces of Zuse"s Plankalkul, but was concrete and, compared with the "Programmator" of Zuse (published in 1952), more realistic.

  
  '); wh.document.close();">Extract: Rutishauser’s way to Stiefel

  STANISLAUS, a Formula-programmed Relay Calculator and Rutishauser"s "Automatische Rechenplanfertigung" My interest in Rutishauser"s "Automatischer Rechenplanfertigung" was established by my little relay calculator for formulas of propositional logic in Polish (parenthesis-free) notation, which I had baptized with the name of the Polish saint STANISLAUS. Under the influence of the 1949 paper by Claude Shannon, The synthesis of Two-Terminal Switching Circuits, I had started to look for a relay realization of a device for evaluating a well-formed formula, which was to be typed in directly. This allowed a direct evaluation of a propositional formula for instantiations of the variables by "true" or "false"; the test for well-formedness turned out to be a byproduct of such a "formula-programmed relay calculator for parentheses-free propositional formulas". Around the turn of the year 1950/51, during a stay in Davos, in Switzerland, I made the wiring diagram for the relay calculator. Then I started to collect material for the construction of the device. In October 1951 I entered into a consulting contract with the Siemens company in Munich; now from time to time I could help myself from the surplus bin of the Siemens & Halske AG Central Laboratory in the Munich Hoffmannstraße, where relays and keyboards were to be found. Again and again, my former Munich logic professor Britzlmayr urged me to start with the actual construction, but I had too many other obligations. It was only in 1954 that I started, under the attentive eyes of my colleague and friend Klaus Samelson and helped by Heinz Schecher, to wire the first segments. Then, after having seen how it would work, my interest waned, and it was only after very urgent admonition from Britzlmayr that in 1956 STANISLAUS was finished. It was shown on December 3, 1956 at a colloquium in Munster and presented on January 8, 1957 to the Munich academic public; it met with the delight of Britzlmayr. Samelson and myself did not think so highly of the apparatus: in the meantime we had greater joy with the PERM computer. STANISLAUS is now exhibited in the Deutsches Museum, Munich. Rutishauser"s seminal Habilitationsschrift of 1951 gave the evidence that the "Automatische Rechenplanfertigung" for a given, sufficiently flexible computing machine could be carried through with just the same machine (Andrei Ershov coined for this the expression "programming program"). Rutishauser had no chance to do it immediately on the Z4. However, progress in building the PERMinMunich was such that we could start in 1955 programming a "formula translator", based on the so-called "cellar principle" of my Formelrechner STANISLAUS. This translation method was an essential improvement over the Rutishauser method of 1951, as it was much faster. Moreover, external circumstances had the effect that I filed in March 1957 jointly with Klaus Samelson a patent application for a formula-controlled computer with hardware realizing the cellar principle. Rutishauser, on the other hand, with the experience he had already made on the Z4, programmed a run-time organization for the ERMETH, in particular the treatment of subroutine returns - a "last in, first out"-type organisation, i.e. the cellar principle applied to program structure. (Fortunately, the German Patent Office did not find out about this, which even could have been traced back to Turing and van der Poel.) The ERMETH, by the way, was ready about one year after the PERM. Hence, it was natural that Rutishauser, Samelson (who extended the cellar principle to storage allocation) and I did intensify more and more our cooperation in the area of what became called compiler-building. This had the consequence that we were forced to agree on language constructs, and again the lead of four years in practical programming Rutishauser had, thanks to the Z4, was his great asset. Rutishauser"s reputation also had the effect that his appeal at theGaMM-meeting in 1955 to create a common programming language found the support of the GaMM president; within the "Fachausschuss Programmieren" a working group with Zurich, Munich and later Mainz members was established that pushed the language creation. Rutishauser was not less active than Samelson and myself: the first larger working meeting of the group that meanwhile called itself ZMD-Gruppe (D for Darmstadt: Hermann Bottenbruch) took place in autumn 1957 in Lugano, organized by Rutishauser. At that meeting it was decided, in the name and with the approval of the GaMM, to approach the US-american ACM and the British Computer Society with the proposal of a joint conference for the creation of an internationally-based programming language for scientific computation. Unfortunately, the BCS did not react; the ACM, however, under its president John Carr III was cheerful and it came to a one-week ACM-GaMM conference in May 1958 at the ETH Zurich, thanks to the support Eduard Stiefel had given. While the English working title was IAL (International Algebraic Language), the name Algorithmic Language ALGOL was already chosen in the publication, edited by A. J. Perlis and K. Samelson, in the newly founded Springer journal "Numerische Mathematik", Vol 1 (1959). The further course of development of ALGOL saw Heinz Rutishauser also taking part in the conference held January 11-16, 1960 with thirteen experts from the USA, Germany, Switzerland, Netherlands, England, Danmark, and France in Paris. It produced ALGOL 60, a milestone. Rutishauser"s share was more than a thirteenth.

  
  '); wh.document.close();">Extract: Stanislaus, Klammerausdrücke, ALGOL

  With ALGOL 60, the 60"s had opened, the Golden Years of Programming had gone. Rutishauser took part in the further developments within the frame of the IFIP Working Group 2.1 ALGOL; however because of his health no longer with full activity. In particular, he did not dare to travel by airplane to the USA. He also disliked (like Samelson and myself) several faux pas that occured mainly in the attempts to create ALGOL 68. The fiasco of ALGOL 68 is to be blamed on others. Rutishauser prefered to concentrate on the description of standardized numerical algorithms in ALGOL 60; this led to a good part later to the LINPACK and EISPACK collection. He also wrote Volume I, Part A "Description of ALGOL 60" of the Handbook for Automatic Computation" published by Springer, that contained many representative examples of algorithms.

  
  '); wh.document.close();">Extract: Algol 60 and 68
        in (2002) Latsis Symposium 2002 on the 50th Anniversary of the Conjugate Gradient Algorithm
  George Gray (2002) George Gray "UNIVAC and ALGOL" Unisys History Newsletter 6(2) June 2002

  MAD was developed at the University of Michigan in 195960 for the IBM 704. It was very widely used on the IBM 7090 and 7094, the Philco 2000, and UNIVAC 1100 computers during the 1960s for the purpose of teaching programming to college students. Michigan published a reference manual, but most students learned MAD from the MAD PRIMER, written by Elliott Organick of the University of Houston and distributed by Ulrichs Book Store of Ann Arbor, Michigan. Organick also wrote a more widely used FORTRAN PRIMER. The MAD compiler for the UNIVAC 1100 computers called RALPH was developed at the University of Maryland. The name RALPH is an acronym of sorts: Reentrant Algorithmic Language Processor with H just for the H of it. (The explanation of the acronym is supplied by George Baltz, formerly at the University of Maryland.) The RALPH processor could compile either FORTRAN or MAD, depending on the option selected. MAD is perhaps most famous for the line printer picture of Alfred E. Neumann which was printed when an attempted compilation had too many errors. Underneath the picture it printed the caption: See this man about your program--He might want to publish it. He never worries--but from the looks of your program, you should. MAD faded from the scene in the 1970s. A very simple MAD program follows:                                                                                  INTEGER A                                                           START      A = 1                                                                           WHENEVER A .G. 0                                                                 PRINT COMMENT $ A GTR 0$                                                         OTHERWISE                                                                       PRINT COMMENT $A LEQ 0$                                                         END OF CONDITIONAL                                                               PRINT COMMENT $ END $                                                           END OF PROGRAM The WHENEVER OTHERWISE END OF CONDITIONAL is equivalent to an if-else statement

  
  '); wh.document.close();">Extract: Information Online copy at UNISIS History

• Algol 68 home page
  
• Algol 68 resources (Algol68 Genie)