0.1. Aims and principles of design 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.
c) This present Revision of the language is made in response to the directive of the parent committee, I.F.I.P. TC 2, to the Working Group to “keep continually under review experience obtained as a consequence of this {original} publication, so that it may institute such corrections and revisions to the Report as become desirable”. In deciding to bring forward this Revision at the present time, the Working Group has tried to keep in balance the need to accumulate the maximum amount of experience of the problems which arose in the language originally defined, as opposed to the needs of the many teams at present engaged in implementation, for whom an early and simple resolution of those problems is imperative.
d) Although the language as now revised differs in many ways from that defined originally, no attempt has been made to introduce extensive new features and, it is believed, the revised language is still clearly recognizable as “ALGOL 68”. The Working Group has decided that this present revision should be “the final definition of the language ALGOL 68”, and the hope is expressed that it will be possible for implementations at present in preparation to be brought into line with this standard.
e) The Working Group may, from time to time, define sublanguages and extended capabilities, by means of Addenda to this Report, but these will always be built on the language here defined as a firm foundation. Moreover, variants more in conformity with natural languages other than English may be developed. To coordinate these activities, and to maintain contact with implementers and users, a Subcommittee on ALGOL 68 Support has been established by the Working Group.
f) The members of the Group, influenced by several years of experience with ALGOL 60 and other programming languages, have always accepted the following as their aims:
0.1.1 Completeness and clarity of description The Group wishes to contribute to the solution of the problems of describing a language clearly and completely. The method adopted in this Report is based upon a formalized two-level grammar, with the semantics expressed in natural language, but making use of some carefully and precisely defined terms and concepts. It is recognized, however, that this method may be difficult for the uninitiated reader.
0.1.2 Orthogonal design The number of independent primitive concepts has been minimized in order that the language be easy to describe, to learn, and to implement. On the other hand, these concepts have been applied “orthogonally” in order to maximize the expressive power of the language while trying to avoid deleterious superfluities.
0.1.3 Security ALGOL 68 has been designed in such a way that most syntactical and many other errors can be detected easily before they lead to calamitous results. Furthermore, the opportunities for making such errors are greatly restricted.
0.1.4 Efficiency ALGOL 68 allows the programmer to specify programs which can be run efficiently on present-day computers and yet do not require sophisticated and time-consuming optimization features of a compiler; see, e.g., 11.7.
0.1.4.1 Static mode checking The syntax of ALGOL 68 is such that no mode checking during run time is necessary, except when the programmer declares a UNITED-variable and then, in a conformity-clause, explicitly demands a check on its mode.
0.1.4.2 Mode-independent parsing The syntax of ALGOL 68 is such that the parsing of a program can be performed independently of the modes of its constituents. Moreover, it can be determined in a finite number of steps whether an arbitrary given sequence of symbols is a program.
0.1.4.3 Independent compilation The syntax of ALGOL 68 is such that the main-line programs and procedures can be compiled independently of one another without loss of object-program efficiency provided that, during each independent compilation, specificatio of the mode of all nonlocal quantities is provided: see the remarks after 2.2.2.c.
0.1.4.4 Loop optimization Iterative processes are formulated in ALGOL 68 in such a way that straightforward application of well-known optimization techniques yields large gains during run time without excessive increase of compilation time.
0.1.4.5 Representations Representations of ALGOL 68 symbols have been chosen so that the language may be implemented on computers with a minimal character set. At the same time implementers may take advantage of a larger character set, if it is available.
0.2 Comparison with ALGOL 60 a) ALGOL 68 is a language of wider applicability and power than ALGOL 60. Although influenced by the lessons learned from ALGOL 60, ALGOL 68 has not been designed as an expansion of ALGOL 60 but rather as a completely new language based on new insight into the essential, fundamental concepts of computing and a new description technique.
b) The result is that the successful features of ALGOL 60 reappear in ALGOL 68 but as special cases of more general constructions, along with completely new features. It is, therefore, difficult to isolate differences between the two languages: however, the following sections are intended to give insight into some of the more striking differences.
0.2.1 Values in ALGOL 68 a) Whereas ALGOL 60 has values of the types integer, real and Boolean, ALGOL 68 features an infinity of “modes”, i.e., generalizations of the concept “type”.
b) Each plain value is either arithmetic, i.e., of ‘integral’ or ‘real’ mode and then it is of one of several sizes, or it is of ‘boolean’ or ‘character’ or ‘void’ mode. Machine words, considered as sequences of bits or of bytes, may also be handled.
c) In ALGOL 60, values can be composed into arrays, whereas in ALGOL 68, in addition to such “multiple” values, also “structured” values, composed of values of possibly different modes, are defined and manipulated. An example of a multiple value is the character array, which corresponds approximately to the ALGOL 60 string; examples of structured values are complex numbers and symbolic formulae.
d) In ALGOL 68 the concept of a “name” is introduced, i.e., a value which is said to “refer to” another value; such a name-value pair corresponds to the ALGOL 60 variable. However, a name may take the value position in a name-value pair, and thus chains of indirect addresses can be built up.
e) The ALGOL 60 concept of procedure body is generalized in ALGOL 68 to the concept of “routine”, which includes also the formal parameters, and which is itself a value and therefore can be manipulated like any other value.
f) In contrast with plain values, the significance of a name or routine is, in general, dependent upon the existence of the storage cells referred to or accessed. Therefore, the use of names and routines is subject to some restrictions related to their “scope”. However, the syntax of ALGOL 68 is such that in many cases the check on scope can be made at compile time, including all cases where no use is made of features whose expressive power transcends that of ALGOL 60.
0.2.2 Declarations in ALGOL 68 a) Whereas ALGOL 60 has type declarations, array declarations, switch declarations and procedure declarations, ALGOL 68 features the identity-declaration whose expressive power includes all of these, and more. The identity-declaration, although theoretically sufficient in itself, is augmented by the variable-declaration for the convenience of the user.
b) Moreover, in ALGOL 68, a mode-declaration permits the construction of a new mode from already existing ones. In particular, the modes of multiple values and of structured values may be defined in this way; in addition, a union of modes may be defined, allowing each value referred to by a given name to be of any one of the uniting modes.
c) Finally, in ALGOL 68, a priority-declaration and an operation-declaration permit the introduction of new operators, the definition of their operation and the extension of the class of operands of, and the revision of the meaning of, already established operators.
0.2.3 Dynamic storage allocation in ALGOL 68 Whereas ALGOL 60 (apart from “own dynamic arrays”) implies a “stack”-oriented storage-allocation regime, sufficient to cope with objects having nested lifetimes (an object created before another object being guaranteed not to become inaccessible before that second one), ALGOL 68 provides, in addition, the ability to create and manipulate objects whose lifetimes are not so restricted. This ability implies the use of an additional area of storage, the “heap”, in which garbage-collection techniques must be used.
0.2.4 Collateral elaboration in ALGOL 68 Whereas, in ALGOL 60, statements are “executed consecutively”, in ALGOL 68, phrases are “elaborated serially” or “collaterally”. This latter facility is conducive to more efficient object programs under many circumstances, since it allows discretion to the implementer to choose, in many cases, the order of elaboration of certain constructs or even, in some cases, whether they are to be elaborated at all. Thus the user who expects his “side effects” to take place in any well determined manner will receive no support from this Report. Facilities for parallel programming, though restricted to the essentials in view of the none-too-advanced state of the art, have been introduced.
0.2.5 Standard declarations in ALGOL 68 The ALGOL 60 standard functions are all included in ALGOL 68 along with many other standard declarations. Amongst these are “environment enquiries”, which make it possible to determine certain properties of an implementation, and “transept” declarations, which make it possible, at run time, to obtain data from and to deliver results to external media.
0.2.6 Some particular constructions in ALGOL 68 a) The ALGOL 60 concepts of block, compound statement and parenthesized expression are unified in ALGOL 68 into the serial-clause. A serial-clause may be an expression and yield a value. Similarly, the ALGOL 68 assignation, which is a generalization of the ALGOL 60 assignment statement, may be an expression and, as such, also yield a value.
b) The ALGOL 60 concept of subscripting is generalized to the ALGOL 68 concept of “indexing”, which allows the selection not only of a single element of an array but also of subarrays with the same or any smaller dimensionality and with possibly altered bounds.
c) ALGOL 68 provides row-displays and structure-displays, which serve to compose the multiple and structured values mentioned in 0.2.1.c from other, simpler, values.
d) The ALGOL 60 for statement is modified into a more concise and efficient loop-clause.
e) The ALGOL 60 conditional expression and conditional statement, unified into a conditional-clause, are improved by requiring them to end with a closing symbol whereby the two alternative clauses admit the same syntactic possibilities. Moreover, the conditional-clause is generalized into a case-clause, which allows the efficient selection from an arbitrary number of clauses depending on the value of an integral-expression, and a conformity-clause, which allows a selection depending upon the actual mode of a value.
f) Some less successful ALGOL 60 concepts, such as own quantities and integer labels, have not been included in ALGOL 68, and some concepts, like designational expressions and switches, do not appear as such in ALGOL 68 but their expressive power is included in other, more general, constructions.
0.3 Comparison with the language defined in 1968 The more significant changes to the language are indicated in the sections which follow. The revised language will be described in a new edition of the “Informal Introduction to ALGOL 68” by C.H. Lindsey and S.G. van der Meulen, which accompanied the original Report.
0.3.1 Casts and routine texts Routines without parameters used to be constructed out of a cast in which the cast-of-symbol (:) appeared. This construct is now one of the forms of the new routine-text, which provides for procedures both with and without parameters. A new form of the cast has been provided which may be used in contexts previously not possible. Moreover, both void-casts and procedure-PARAMETY-yielding-void-routine-texts must now contain an explicit void-symbol.
0.3.2 Extended ranges The new range which is established by the enquiry-clause of a choice-clause (which encompasses the old conditional- and case-clauses) or of a while-part now extends into the controlled serial-clause or do-part.
0.3.3 Conformity clauses The conformity-relation and the case-conformity which was obtained by extension from it are now replaced by a new conformity-clause, which is a further example of the choice-clause mentioned above.
0.3.4 Modes of multiple values A new class of modes is introduced, for multiple values whose elements are themselves multiple values. Thus one may now write the declarer [ ] string.
Moreover, multiple values no longer have “states” to distinguish their flexibility. Instead, flexibility is now a property of those names which refer to multiple values whose size may change, such names having distinctive modes of the form ‘reference to flexible ROWS of MODE’.
0.3.5 Identification of operators Not only may two operators, related to each other by the modes of their operands, not be declared in the same range, as before, but now, if two such operators be declared in different reaches, any attempt to identify from the inner reach the one in the outer reach will fail. This gives some benefit to the implementer and removes a source of possible confusion to the user.
0.3.6 Representations The manner in which symbols for newly defined mode-indications and operators are to be represented is now more closely defined. Thus it is clear that the implementer is to provide a special alphabet of bold-faced, or “stropped”, marks from which symbols such as person may be made, and it is also clear that operators such as >> are to be allowed.
0.3.7 Standard prelude In order to ease the problems of implementers who might wish to provide variants of the language suitable for environments where English is not spoken, there are no longer any field-selectors known to the user in the standard-prelude, with the exception of re and im of the mode COMPL. The identifiers and other indicators declared in the standard-prelude could, of course, easily be defined again in some library-prelude, but this would not have been possible in the case of field-selectors.
0.3.8 Line length in transput The lines (and the pages also) of the “book” used during transput may now, at the discretion of the implementer, be of varying lengths. This models more closely the actual behaviour of most operating systems and of devices such as teleprinters and paper-tape readers.
0.3.9 Internal transput The transput routines, in addition to sending data to or from external media, may now be associated with row-of-character-variables declared by the user.
0.3.10 Elaboration of formats The dynamic replicators contained in format-texts are now elaborated as and when they are encountered during the formatted transput process. This should give an effect more natural to the user, and is easier to implement.
0.3.11 Features removed Certain features, such as proceduring, gommas and formal bounds, have not been included in the revision.
0.4 Changes in the method of description In response to the directive from the Working Group “to make its study easier for the uninitiated reader”, the Editors of this revision have rewritten the original Report almost entirely, using the same basic descriptional technique, but applying it in new ways. It is their hope that less “initiation” will now be necessary.
The more significant changes in the descriptional technique are indicated below.
0.4.1 Two-level grammar a) While the syntax is still described by a two-level grammar of the type now widely known by the name “Van Wijngaarden”, new techniques for using such grammars have been applied. In particular, the entire identification process is now described in the syntax using the metanotion “NEST”, whose terminal metaproductions are capable of describing, and of passing on to the descendent constructs, all the declared information which is available at any particular node of the production tree.
b) In addition, extensive use is made of “predicates”. These are notions which are deliberately made to yield blind alleys when certain conditions are not met, and which yield empty terminal productions otherwise. They have enabled the number of syntax rules to be reduced in many cases, while at the same time making the grammar easier to follow by reducing the number of places where a continuation of a given rule might be found.
It has thus been possible to remove all the “context conditions” contained in the original Report.
0.4.2 Modes a) In the original Report, modes were protonotions of possibly infinite length. It was assumed that, knowing how an infinite mode had been obtained, it was decidable whether or not it was the same as some other infinite mode. However, counterexamples have come to light where this was not so. Therefore, it has been decided to remove all infinities from the process of producing a finite program and, indeed, this can now be done in a finite number of moves.
b) A mode, essentially, has to represent a potentially infinite tree. To describe it as a protonotion of finite length requires the use of markers {‘MU definition’s} and pointers back to those markers {‘MU application’s} within the protonotion. However, a given infinite tree can be “spelled” in many ways by this method, and therefore a mode becomes an equivalence class comprised of all those equivalent spellings of that tree. The equivalence is defined in the syntax using the predicates mentioned earlier.
0.4.3 Extensions The need for many of the extensions given in the original Report had been removed by language changes. Some of the remainder had been a considerable source of confusion and surprises. The opportunity has therefore been taken to remove the extension as a descriptional mechanism, all the former extensions now being specified directly in the syntax.
0.4.4 Semantics a) In order to remove some rather repetitious phrases from the semantics, certain technical terms have been revised and others introduced. The grammar, instead of producing a terminal production directly, now does so by way of a production tree. The semantics is explained in terms of production trees. Paranotions, which designate constructs, may now contain metanotions and “hypernotions” have been introduced in order to designate protonotions.
b) A model of the hypothetical computer much more closely related to a real one has been introduced. The elaboration of each construct is now presumed to take place in an “environ” and, when a new range is entered (and, in particular, when a routine is called), a new “locale” is added to the environ. The locale corresponds to the new range and, if recursive procedure calls arise, then there exist many locales corresponding to one same routine. This supersedes the method of “textual substitution” used before, and one consequence of this is that the concept of “protection” is no longer required.
c) The concept of an “instance” of a value is no longer used. This simplifies certain portions of the semantics where, formerly, a “new instance” had to be taken, the effects of which were not always clear to see.
0.4.5 Translations The original Report has been translated into various natural languages. The translators were not always able to adhere strictly to the descriptional method, and so the opportunity has been taken to define more clearly and more liberally certain descriptional features which caused difficulties (see 1.1.5 ).