ALGOL 68(ID:311/alg019)3rd generation ALGOL1968 Adriaan van Wijngaarden et al. Discussed from 1963 by Working Group 2.1 of IFIP. Definition accepted Dec 1968. ALGOL 68 was complex, and posed difficulties for both implementors and users. But it was also the first truly universal language. Structural equivalence. Automatic type conversion, including dereferencing. Flexible arrays. Generalized loops (for-from-by-to-while-do-od), if-then-elif-fi, integer case statement with 'out' clause, skip statement, goto. Blocks, procedures and user-defined operators. Procedure parameters. Concurrent execution (cobegin/coend) and semaphores. Generators heap and loc for dynamic allocation. No abstract data types, no separate compilation. a) In designing the Algorithmic Language ALGOL 68, Working Group 2.1 on ALGOL of the International Federation for Information Processing expresses its belief in the value of a common programming language serving many people in many countries. b) ALGOL 68 is designed to communicate algorithms, to execute them efficiently on a variety of different computers, and to aid in teaching them to students. Ob Dict - despite the fury of the Algol 60 afficianadoes in the face of Algol 68, it was a very well thought through experiment in language design. It is instructive to read the disgust that SHARE memebers like Bernstein felt at the arrival of Algol 60 after the beauty of Algol 58, which they thought required so little to fix it up! An imperative read is Lindsay 1972, which is a large introductory article that is also a fully functional Algol 68 Program Structures: Related languages
Samples: References: in Goodman, Richard (ed) "Annual Review in Automatic Programming" (3) 1963 Pergamon Press, Oxford view details in Numerische Mathematik, 14 1969 view details Abstract: 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. Extract: THe necesary environment 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. in SIGPLAN Notices 5(09) September 1970 view details 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''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 "a", digit five symbol by "a", if symbol by "(", "if", or "case", and becomes symbol by ": = ", " . . = ", or ". = ". 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 "a label may be rewritten as a label identifier followed by a label symbol." 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 [ "W-Grammar." 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 "elaboration"; an assignment is called an "assignation"; input/output is referred to as "transput"; and a number of newly coined words are frequently used, such as "slices," "trimscripts," "coercends," "denotations," 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. in ACM Computing Reviews 11(10) October 1970 view details in [ACM] CACM 14(01) Jan 1971 view details DOI in SIGPLAN Notices 7(12) December 1972 view details External link: Online copy Extract: Introduction 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.# in The Computer Journal 15(2) 1972 view details in [ACM] CACM 15(07) (July 1972) view details in ACM Computing Reviews 15(04) April 1974 view details in Machine Oriented Higher Level Languages (van der Poel, Maarsen, editors) North Holland 1974 view details in Machine Oriented Higher Level Languages (van der Poel, Maarsen, editors) North Holland 1974 view details in Proceedings of the ACM SIGPLAN symposium on Very high level languages, March 28-29, 1974, Santa Monica, California, United States view details in Proceedings of the ACM SIGPLAN symposium on Very high level languages, March 28-29, 1974, Santa Monica, California, United States view details in Proceedings of the ACM SIGPLAN symposium on Very high level languages, March 28-29, 1974, Santa Monica, California, United States view details in Proceedings of the ACM SIGPLAN symposium on Very high level languages, March 28-29, 1974, Santa Monica, California, United States view details External link: Online copy in The Computer Journal 19(2) May 1976 view details in The Computer Journal 19(2) May 1976 view details Extract: Introduction 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. Extract: Ackermann's function 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. Extract: Acknowledgements 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). 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 Extract: Properties of the algorithm 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. Extract: Notes on the results and Factors influencing the execution speed 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). Extract: Conclusion Conclusion. Ackermann'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 'System Implementation Languages' 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 in The Computer Journal 19(2) May 1976 view details in Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977 view details in Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977 view details in Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977 view details in Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977 view details in Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977 view details in Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977 view details in Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977 view details in Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977 view details in Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977 view details in Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977 view details in Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977 view details in Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977 view details in Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977 view details in Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977 view details in Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977 view details in Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977 view details in Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977 view details in Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977 view details in Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977 view details in Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977 view details in 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 view details in SIGPLAN Notices 13(11) Nov 1978 view details External link: Online copy in The Computer Journal 21(4) view details 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. in SIGPLAN Notices 14(07) July 1979 view details External link: Online copy in The Computer Journal 22(1) view details in Computer Languages 4(1) view details 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. in The Computer Journal 23(3) 1980 view details 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. in [ACM] CACM 24(02) February 1981 view details in Alberts, G. (ed) "Conference on the history of ALGOL 68" CWI, Amsterdam 1993 view details 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. in Alberts, G. (ed) "Conference on the history of ALGOL 68" CWI, Amsterdam 1993 view details in Alberts, G. (ed) "Conference on the history of ALGOL 68" CWI, Amsterdam 1993 view details in "History of Programming Languages", ACM Press/Addison-Wesley Publishing Company, New York (1996) ed Bergin and Gibson view details 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. Extract: Mending the fences 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. Extract: The North-Berwick meeting 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. Extract: The IFIP 1968 Congress 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. Extract: Towards Munich 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. Extract: And after 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? in Proceedings of the Second International Andrei Ershov Memorial Conference on Perspectives of System Informatics LNCS 1161 Springer-Verlag, 1996 view details in Proceedings of the Second International Andrei Ershov Memorial Conference on Perspectives of System Informatics LNCS 1161 Springer-Verlag, 1996 view details in Proceedings of the Second International Andrei Ershov Memorial Conference on Perspectives of System Informatics LNCS 1161 Springer-Verlag, 1996 view details 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. Extract: Rutishauser’s way to Stiefel 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. Extract: Stanislaus, Klammerausdrücke, ALGOL 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. Extract: Algol 60 and 68 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. in Latsis Symposium 2002 on the 50th Anniversary of the Conjugate Gradient Algorithm view details 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 External link: Online copy at UNISIS History in Latsis Symposium 2002 on the 50th Anniversary of the Conjugate Gradient Algorithm view details Resources
|