EULER(ID:256/eul002)Wirth Algolfor the Swiss mathematician Leonhard Euler (1707-1783) Generalisation of ALGOL 60 with defined transput. Significant in being (along with Algol W) a precursor of Pascal. Niklaus Wirth and Helmut Weber Stanford 1965 In the computing pioneers seminar at Berkeley, Wirth candidly suggests that although creating this was the reason he came to Stanford, many of these ideas were "wrong". He does not elaborate how - the result is left to the listener. Judgng from the acknowledgements in the 1964 article (where he pays credit to Wijngarden for greater insight and generality) it was the details that pointed to Algol 68. According to the Appendix and Acnowledgements, the initial system was written in NELIAC and used a polish notation string compiler. Related languages
References: In order to help establish a basis upon which a reasonable successor to ALGOL could be specified, this Department hereby solicits for publication papers, notes, remarks, letters and the like which have to do with one or another of the aspects of a possible successor to ALGOL. The following note by J. Garwick is typical of the kind of thing we would like to receive. The contributions will, as is usual, be refereed; however, we will seriously attempt to print any responsible position or idea. External link: Online copy in [ACM] CACM 7(07) July 1964 view details The generalized ALGOL described by Niklaus Wirth is in my opinion a major step forward toward the "next" programming language. In this remark I intend to introduce further generalizations which will make the language still more useful. I will first propose some changes of notation. The semicolon is reintroduced as statement separator. The declaration new is then terminated by semicolon and not by a point. The braces used around a list are now unnecessary and are dropped. Mr. Wirth's example on "point in polygon" will then start as a := 6,12,23,14,3,6,0; b := 1 , 0 , 9 . . . After these notational changes, consider the arrays. One difference between Wirth's arrays and those in ALGOL 60 is that Wirth always has one as lower limit in the arrays. A fixed lower limit is indeed necessary with his system, but personally I prefer zero. Mr. Wirth's arrays are not really arrays; they are lists. We will therefore not handle them only as lists, but also call them lists. A list of a single variable is also a list. All variables are therefore lists. A procedure has a list as parameter. We may therefore call it either with an explicit parameter list or with a list variable (in its usual meaning) as parameter. Example: a := b,c, (5,3),2; f(a) or f(b, c, (5, 3), 2) are then equivalent calls. The parameter (5, 3) may be the parameter list of an internally called procedure in f. In Mr. Wirth's article a quotation either contains a list of statements or a list of expressions. Let us, however, permit a mixture of these two elements. If we then write p(x, y) := 'u := x + y; u/x' The meaning is that the nonlocal variable u is put equal to x + y and the value of p is put equal to u/x. If x and y are lists with more than one element, addition is defined only if the list structures are isomorphic. It is then all addition of corresponding elements. The same is true for the other elementary operations. If a is a list, b : = a assigns the whole of a to b. We can therefore move whole arrays with one assignment statement. List elements are referenced by indices as in ALGOL 60, e.g. a[5, 3, 2] means that the fifth element on t:he list a must be a branch element. The third element on this branch must again be a branch element. The second element and the last branch may be a number which is the value of a[5, 3, 2] or a branch point. The sublist is in the latter case the value of a[5, 3, 2]. If one or more of the branches contains less elements than supposed or branch points are not found in the expected places, the value of a[5, 3, 2] is Omega. The most important generalization is achieved by remarking that the value of an expression may be a list and therefore the value of a procedure may be a list. Thus we have introduced in one stroke complex arithmetic, multiple length arithmetic, matrix algebra, tensor algebra etc. into the system. The language can be further simplified without introducing any complications. First eliminate Boolean variables. We can declare two variables true and false in the outermost block and set true : = 1; false : = 0. We can then later writea : = true; ifb = true thenetc. Next eliminate integers. Integers are used as such only in indices and as operands for the operator +. These cases are syntactically identifiable and the compiler can insert the proper rounding-off operations. Mr. Wirth touches upon the advisability of not declaring arrays since the final program will run slowly. To this one may say that: 1. It is high time we scientists began to tell the manufacturers what we want. In many cases ability to process lists efficiently is more valuable than multiple access storage modules and rapid carry propagation. 2. There are, broadly speaking, two types of problems. One type is exemplified by reactor calculations and simulation. They are few in number, but run for very long times. The other type is short and most of the time used for solving them is taken by programming and debugging. This type of problem is solved fastest by having the best possible programming language. Running efficiency here is of minor concern. As there are few problems of the first type, one can afford to use a primitive language (e.g., FORTRAN), but the second category requires the best programming language (from the users point of view) that we can produce. I am certain other scientists in this field will add their remarks to mine so that ALGOL 6x may ultimately appear. REFERENCE : 1. WIRTH, N. A generalization of ALGOL. Comm. ACM 6(09) (Sept. 1963), pp547-554. JAN V. GARWICK Norwegian Defence Research Establishment Kjeller, Norway RECEIVED FEBRUARY, 1964 External link: Online copy in [ACM] CACM 7(07) July 1964 view details I. Introduction The publication of the Report on the Algorithmic Language ALGOL 60 (1) was one of the very important and subsequently most discussed events in the field of programming techniques. ALGOL was designed to spare the programmer from the myriad of tedious detail considerations required for machine-language coding; it achieves this aim to an extremely high degree and should therefore be expected to have become the dominant tool in the art of programming, not only for publication purposes but as the actual source language of processing systems. It hardly needs to be mentioned that ALGOL has been denied this role by all those computer users which refuse to trade some efficiency of their particular progrmns against the generality for which ALGOL allows. This generality of ALGOL, which is not easily providable on present-day "generM-purpose computers," turns out to be the main obstacle to the universal acceptance of ALGOL. A further generalization appears therefore highly undesirable, and if it nevertheless is suggested in this article the reasons for it must clearly be explained. The widespread "general-purpose computer" is by no means ideally suited to the requirements of any higher level programming language. It is known that far more convenient machine organizations can readily be constructed, mad it remains to determine what new forms these organizations should assume and which elements the vocabulary of their instruction code should contain. Efforts undertaken by the author in this direction resulted in the creation of a simulating program for such a computer, which, together with a translating program (translating ALGOL text into the instruction code of the simulated machine), constitutes a complete processor of virtually unrestricted ALGOL. A second, but similar system was subsequently written for the proposed Generalized ALGOL, and--surprisingly--turned out to be considerably simpler (see Appendix) on the part of the sinmlating program, which eventually will be put into hardware, as well as especially on the part of the translator. This simplification is achieved by the systematic structure of the source language and its lack of redundancies. It is considered to be the main justification of the proposed generalization, but is clearly not the only one. From the programmer's viewpoint, a language with as few fundamental concepts as possible is desirable in order that a concise and unambiguous description may be given as well as to facilitate the learning process. A systematic structure of the language and the machine will allow for a systematic translator, which is unconditionally necessary to guarantee a reliable system. A description of the processing system is intentionally omitted here, since--in order to emphasize its relation to ALGOL--a form of definition of the language is chosen that does not refer to an actual processing algorithm. Extract: Generalization of Algol II. Generalization of Algol The proposed generalization can be summarized as the elimination of type declarations and the replacement of the procedure declaration by an assignment of a so-called quotation. These two changes, however, bear profound consequences on the entire language, many of which will not explicitly be enumerated. Type declarations in ALGOL serve to associate identifiers with quantities and to define once and forever the type of the quantity. This introduces highly implicit restrictions on the block following the declarations, since the declarations state a number of conditions which the block must satisfy. Basically the type-declaration Boolean can be regarded as superfluous, since it usually becomes evident from the way in which the variable is used, whether or not it is a logical variable; and if the meaning of a program is independent of the type associated with a variable, a specific type association with this variable would be redundant by definition. Furthermore, there is no apparent necessity to make any distinction between integer and real types. In addition to burdening the language with more special symbols, the processing system is implicitly charged with the duty of detecting possible contradictions and of inserting instructions for number conversion at the appropriate places, if a machine with different number representation for integers and real numbers is used. It would seem reasonable to let the translator perform these duties. However, this possibility has been destroyed in ALGOL by declaring the specification parts in procedure declarations as voluntary. Checking and number conversion have to be performed at execution time, which makes it clear that previous type declarations are merely restrictive. It seems to be reasonable to introduce the new symbol undefined as a result of meaningless operations (e.g., multiplication of logical values). Such a symbol may also serve other purposes: it may designate the value that variables assume immediately after their declaration. In certain problems it may even occur as the intended result. [2] Array declarations determine the subscript bounds of an array. From the user's point of view the subscript bounds may be regarded as redundant information, since it will become clear from the following program, which elements of an array will be used. If subscript bounds are omitted, then consequently the rectangular array will lose its dominant role: any form of array may occur. This generalization implies that arrays become completely dynamic, a feature which is highly desirable for certain classes of problems. There remain the procedure- and switch-declarations of ALGOL which do not only associate identifiers with quantities, but also immediately assign a constant value to this quantity. In this respect they act like an assignment statement [3]. In the case of a switch, an array of labels (in general, designational expressions) is assigned to a quantity. By introducing a set- or list-notation, a regular assignment statement can be made to replace the switch declaration. This means that by re-assignment the switch may change its value; and certainly the replacement of a static definition by a dynamic one increases the flexibility of the language. The same considerations apply to the procedure declarations. But, since an assignment statement implies that the value of an expression be assigned to a variable and not the expression itself, a symbol has to be introduced, which causes the value of the expression including this symbol to be the expression stripped of this symbol. Fortunately, a character with exactly this meaning exists in common use: the quotation mark. Two examples may show how these quotation marks would be used to replace the following ALGOL procedure-declaration by an assignment: procedure p; z := x -k y; becomes p := 'z := x + y'; real procedure r; r := s; becomes r := 's'; procedure q(x, y, z); z := x -- y; becomes q(x, y, z) := 'z := x - y'; The second example illustrates the identity of the concepts "procedure declaration" and "name substitution": The name "r" now means "s". Any statement in the program can express such a name replacement, while in ALGOL, a name substitution may only occur through a procedure statement with parameters. The meaning of an actual parameter list shall now be defined as follows: Actual parameters are evaluated, and their values are assigned to the corresponding formal parameters before the quotation (procedure) is evaluated. This implies that all parameters are "called by value." By enclosing them in quotation marks, however, one effectively obtains a "call by name," since the evaluation results in the very name. Thus, the decision whether a name- or a value-call is desired, is made at the calling side rather than at the declaration side. This yields great advantages to the programmer as well as to the system implementer. As an example, the procedure q declared above might be called by the statement q(a + b, 5, 'm'); where the first two parameters are called by value, the third by name. The explicit statement of whether an expression is called by value or name promotes the clarity of a language in general. If in ALGOL a switch element is a conditional designational expression, or if an array bound is an expression, the knowledge about the type of call may only be gained from consulting the semantics of those particular items: in the first case, name replacement, in the second, value replacement is meant! Finally, it appears that declarations serve only to associate identifiers with quantities, and to define their scope. This duty can be performed by the single declarator new. It furthermore appears highly desirable to eliminate all cases where elements have different meanings according to their context. Thus, integers will not be permitted as labels. The minus sign should be used as binary operator only. The function designator (whose meaning in ALGOL depends on its position relative to a possible assignment operator) fortunately is rendered superfluous by the new concept of quotations. The demand for a simple and systematic processor calls for the elimination of those concepts which can be expressed by means of more fundamental concepts in the language. Neither the for-statement nor the own-declaration of ALGOL will therefore be adopted. Extract: Summary and Conclusions Summary and Conclusions An algorithmic language is proposed which offers extreme flexibility in writing programs. A processing algorithm has been written in the form of a program, and could be realized in the form of an actual hardware system. Under the assumption that the language be mainly used to describe numerical computations, the elimination of the specification of array-bounds is a controversial generalization, since it causes--for any machine memory organization presently known--a considerable complication of the program execution. For command and control or artificial intelligence applications, however, the availability of completely dynamic arrays (lists) is highly desirable. The language presented is not completely void of redundancies, and it may not feature the minimal set of concepts necessary for the statement of scientific data processing algorithms. As a particular compronlise between complete generality and convenience for the user, it illustrates the principle of developing a language by generalization rather than through extensions. A fairly extensive experience with an implementation of this language at the Computer Center of the University of California at Berkeley has proved it to be a powerful and convenient programming tool. Extract: Appendix Appendix The processing algorithm was written in NELIAC for the IBM 7090 computer. Translator and interpreter, which need not be in the memory simultaneously, occupy less than 2000 machine words each. The code produced by the translator and processed by the interpreter is a Polish string of so-called syllables. The code includes 36 different syllables. The elimination of the specification of array-bounds requires the facility of dynamic storage allocation. This is realized through list-techniques. The system imposes no restrictions on the recursiveness of procedure calls and allows for full generality in the expressions or quotations which constitute the actual parameters. Input- and output-operations are performed by three procedures, which are defined by the processing system. Acknowledgment. I wish to express my debt to Professor A. van Wijngaarden, for he expressed many of the original ideas in even greater generality than they were considered in the present article [4]. in [ACM] CACM 6(09) (September 1963) view details Introduction and Summary When devising a new programming language, one inevitably becomes confronted with the question of how to define it. The necessity of a formal definition is twofold: the users of this language need to know its precise meaning, and also need to be assured that the automatic processing systems, i.e. the implementations of the language on computers, reflect this same meaning equally precisely. ALGOL 60 represented the first serious effort to give a formal definition of a programming language [l]. The structure of the language was defined in a formal and concise way (which, however, was not in all cases unambiguous), such that for every string of symbols it can be determined whether it belongs to the language ALGOL 60 or not. The meaning of the sentences, i.e. their effect on the computational process, was defined in terms of ordinary English with its unavoidable lack of precision. But probably the greater deficiency than certain known imprecise definitions was the incompleteness of the specifications. By this no reference is made to certain intentional omissions (like specification of real arithmetic), but to situations and constructs which simply were not anticipated and therefore not explained (e.g. dynamic own arrays or conflicts of names upon procedure calls). A method for defining a language should therefore be found which guarantees that no unintentional omissions may occur. How should meaning be defined? It can only be explained in terms of another language which is already well understood. The method of formally deriving the meaning of one language from another makes sense, if and only if the latter is simpler in structure than the former. By a sequence of such derivations a language will ultimately be reached where it would not be sensible to define it in terms of anything else. Recent efforts have been conducted with this principle in mind. Boehm and Landin have chosen the h-calculus as the fundamental notation whose basic element is the function, i.e. a well established concept. The motivation for representing a program in functional form is to avoid a commitment to a detailed sequence of basic steps representing the algorithm, and instead to define the meaning or effect of a program by the equivalence class of algorithms represented by the indicated function. Whether it is worth while to achieve such an abstract definition of meaning in the case of programming languages shall not be discussed here. The fact that a program consists basically of single steps remains, and it cannot even be hidden by a transliteration into a functional notation: the sequence is represented by the evaluations of nests of functions and their parameters. An unpleasant side-effect of this translation of ordinary programming languages into h-calculus is that simple computer concepts such as assignment and jumps transform into quite complicated constructs, this being in obvious conflict with the stated requirement that the fundamental notation should be simple. Van Wijingaarden describes [...] a more dynamic approach to the problem: the fundamental notation is governed by only half a dozen rules which are obvious. It is in fact so simple that it is far from being a useful programming notation whatsoever, but just capable enough to provide for the mechanism of accepting additional rules and thus expanding into any desirable programming system. This method of defining the meaning ( or, since the meaning is imperative: effect) of a language is clearly distinct from the method using functional notations, in that it explicitly makes use of algorithmic action, and thus guarantees that an evaluating algorithm exists for any sentence of the language. The essence of this algorithm consists of first scanning the ordered set of rules defining the structure of the language, and determining the applicable structural designations, i.e. performing an ' 9 applicability scan , and then scanning the set of rules for evaluating the determined structural units, i.e. performing an 6 9 evaluation scan . The rules are such that they may invoke application of other rules or even themselves. The entire mechanism is highly recursive and the question remains, whether a basically subtle and intricate concept such as recursion should be used to explain other programming languages, including possibly very simple ones. The methods described so far have in common that their basic set of fundamental semantic entities does not resemble the elementary operations performed by any computational device presently known. Since the chief aim of programming languages is their use as communication media with computers, it would seem only natural to use a basic set of semantic definitions closely reflecting the computer's elementary operators. The invaluable advantage of such an approach $s that the language definition is itself a processing system and that implementations of the language on actual machines are merely adaptations to particular environmental conditions of the language definition itself. The question of correctness of an implementation will no longer be undecidable or controversial, but can be directly based on the correctness of the individual substitutions of the elementary semantic units by the elementary machine operations. It has elsewhere been proposed to let the processing systems themselves be the definition of the language. Considering the complexity of known compiler-systems this seems to be an unreasonable suggestion, but if it is understood as a call for systemizing such processing systems and representing them in a notation independent from any particular computer, then the suggestion appears in a different light. The present paper reports on efforts undertaken in this direction. It seems obvious that the definition of the structure, i.e. the syntax, and the definition of the meaning should be interconnected, since structural orderings are merely an aid for understanding a sentence. In the presented proposal the analysis of a sentence proceeds in parallel with its evaluation: whenever a structural unit is discovered, a corresponding interpretation rule is found and obeyed. The syntactic aspects are defined - by a Phrase Structure System which is augmented by the set of interpretation rules defining the semantic aspects. Such an augmented Phrase Structure Language is subsequently called a Phrase Structure Programming Language, implying that its meaning is strictly imperative and can thus be expressed in terms of a basic algorithmic notation whose constituents are, e.g., the fundamental operations of a computer. Although in [...] the processes of syntactic analysis and semantic evaluation are more clearly separated, the analogies to the van Wijngaarden proposal are apparent. The parsing corresponds to the applicability scan, the execution of an interpretation rule to the evaluation scan. However, this proposal advocates the strict separation between the rules which define the language, i.e. its analysis and evaluation mechanisms, and the rules produced by the particular program under evaluation, while the van Wijngaarden proposal does not distinguish between language definition and program. Whether the elimination of this distinction which enables-- and forces --the programmer to supply his own language defining rules, is desirable or not must be left unanswered here. The original aim of this contribution being the development of a proposal for a standard language, it would have been meaningless to eliminate it. in [ACM] CACM 6(09) (September 1963) view details in [ACM] CACM 9(01) January 1966 view details in [ACM] CACM 10(03) (March 1967) view details Professor Burton Squires and a graduate student, Luis Urdaneta, both of Pennsylvania State University (Computer Building, University Park, Pa) are completing the first version of an implementation of Euler under 3/360. This implementation, written in G-level Fortran IV, will interpret Euler programs written in the restricted 48-character alphabet. in "More on Force-III from Honig" view details in Computers & Automation 21(6B), 30 Aug 1972 view details in ACM Computing Reviews 15(04) April 1974 view details The exact number of all the programming languages still in use, and those which are no longer used, is unknown. Zemanek calls the abundance of programming languages and their many dialects a "language Babel". When a new programming language is developed, only its name is known at first and it takes a while before publications about it appear. For some languages, the only relevant literature stays inside the individual companies; some are reported on in papers and magazines; and only a few, such as ALGOL, BASIC, COBOL, FORTRAN, and PL/1, become known to a wider public through various text- and handbooks. The situation surrounding the application of these languages in many computer centers is a similar one. There are differing opinions on the concept "programming languages". What is called a programming language by some may be termed a program, a processor, or a generator by others. Since there are no sharp borderlines in the field of programming languages, works were considered here which deal with machine languages, assemblers, autocoders, syntax and compilers, processors and generators, as well as with general higher programming languages. The bibliography contains some 2,700 titles of books, magazines and essays for around 300 programming languages. However, as shown by the "Overview of Existing Programming Languages", there are more than 300 such languages. The "Overview" lists a total of 676 programming languages, but this is certainly incomplete. One author ' has already announced the "next 700 programming languages"; it is to be hoped the many users may be spared such a great variety for reasons of compatibility. The graphic representations (illustrations 1 & 2) show the development and proportion of the most widely-used programming languages, as measured by the number of publications listed here and by the number of computer manufacturers and software firms who have implemented the language in question. The illustrations show FORTRAN to be in the lead at the present time. PL/1 is advancing rapidly, although PL/1 compilers are not yet seen very often outside of IBM. Some experts believe PL/1 will replace even the widely-used languages such as FORTRAN, COBOL, and ALGOL.4) If this does occur, it will surely take some time - as shown by the chronological diagram (illustration 2) . It would be desirable from the user's point of view to reduce this language confusion down to the most advantageous languages. Those languages still maintained should incorporate the special facets and advantages of the otherwise superfluous languages. Obviously such demands are not in the interests of computer production firms, especially when one considers that a FORTRAN program can be executed on nearly all third-generation computers. The titles in this bibliography are organized alphabetically according to programming language, and within a language chronologically and again alphabetically within a given year. Preceding the first programming language in the alphabet, literature is listed on several languages, as are general papers on programming languages and on the theory of formal languages (AAA). As far as possible, the most of titles are based on autopsy. However, the bibliographical description of sone titles will not satisfy bibliography-documentation demands, since they are based on inaccurate information in various sources. Translation titles whose original titles could not be found through bibliographical research were not included. ' In view of the fact that nany libraries do not have the quoted papers, all magazine essays should have been listed with the volume, the year, issue number and the complete number of pages (e.g. pp. 721-783), so that interlibrary loans could take place with fast reader service. Unfortunately, these data were not always found. It is hoped that this bibliography will help the electronic data processing expert, and those who wish to select the appropriate programming language from the many available, to find a way through the language Babel. We wish to offer special thanks to Mr. Klaus G. Saur and the staff of Verlag Dokumentation for their publishing work. Graz / Austria, May, 1973 in ACM Computing Reviews 15(04) April 1974 view details in TOPLAS 6(4) October 1984 Lecture Notes in computer science Vol. 174 view details |