Namespaces
Variants
Actions

Algol-68

From Encyclopedia of Mathematics
Revision as of 17:19, 5 April 2020 by Richard Pinch (talk | contribs) (layout: removed unwanted line breaks)
Jump to: navigation, search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.


A universal algorithmic language. It was developed during 1964–1968 by a team of scientists from 12 countries, in the framework of the working group on Algol of the International Federation for Information Processing, for the exchange of algorithms, their effective realization by various computers, and as a means of their study. While similar in style to Algol-60, Algol-68 differs substantially from it in having many more constructions, which are also of a more general nature. The basic data types, in addition to the Algol-60 "real" , "integer" and "Boolean" , are "character" (for alpha-numeric information), "format" (to describe the format of the external data), names and routines (procedures). Thus, names and procedures can be "computed" when a program is executed in Algol-68, even though such a computation is limited by the necessity of selecting the value of, for example, a procedure out of a given finite population of "routine texts" . The basic types may be used to construct new, composite types by induction; these types may be homogeneous indexable sequences of data of the same type (multiple values), or else ordered lists of data of arbitrary type (structured values).

In addition to the conventional approach for defining procedures, Algol-68 contains means for defining so-called infix operators of the type $ x + y $. The presence of a priority definition makes it possible to establish priority relations between the infix operators introduced. The identity definition, which is typical of Algol-68, is a general construction for defining variables, for assigning initial values, for the transmission of actual parameters in procedures and for creating synonyms.

An expression in Algol-68 may contain an assignment statement, or any sequence of statements that produces a value. Together with the possibility of computing names and procedures, and also by the introduction of parenthesis pairs for conditional expressions, this permits Algol-68 constructions such as illustrated by the following example:

1) Algol-68:

$$ \mathbf{i f } \ x > 0 \ \mathbf{then} \ u\ \mathbf{else}\ z \ \mathbf{fi} : = a + ( m < n | \sin | \cos ) ( t : = x \uparrow 2 ) , $$

2) Algol-60:

$$ t : = x \uparrow 2 ; $$

$$ r : = a + \ \mathbf{i f }\ m < n \ \mathbf{then\ } \sin (t) \mathbf{\ else\ } \cos (t); $$

$$ \mathbf{i f \ } x > 0 \mathbf{\ then\ } u: = r \mathbf{\ else \ } z: = r. $$

An Algol-68 program consists of closed, serial, conditional and collateral clauses. The first three types of clauses generalize such Algol-60 concepts as block, compound statement and conditional expression and statement. Collateral clauses signify non-ordered sets of component phrases and are used, in particular, to indicate parallel branches in the course of execution of the program.

The description of the semantics of Algol-68 is characterized by a profound analysis of the principal concepts of algorithmic languages, which makes it possible to give a description of the execution of a program using of a small number of independent fundamental concepts. The objects may be external (with respect to the structure of the program) and internal (data, including procedures and names). The relations between external (E) and internal objects are introduced as axioms, e.g. "E1 contains E2" , "E1 identifies E2" , "E has I" , "I1 names I2" , "I1 is a component of I2" , etc. The execution of a program is described in terms of the relations thus introduced as a function of the analysis of the program.

A typical syntactic feature of Algol-68 is that it is given in the form of a two-level grammar, in which the Algol-68 production rules are themselves well-formed texts in some meta-language, defined by its own generating grammar. For example, grammatical rules of Algol-68 may have the following form:

chain of NOTIONs separated by SEPARATORs: NOTION; NOTION, SEPARATOR, chain of NOTIONs separated by SEPARATORs.

reference to MODE assignation: reference to MODE destination, becomes symbol, MODE source.

The capitalized words, called "metanotions" , are the grammatical units of the meta-language, whose production rules may have forms such as:

NOTION: identifier; operator.

SEPARATOR: comma; semi-colon.

MODE: integral; Boolean; reference to MODE.

Some of the concepts of the meta-language, such as MODE, can have an infinite number of productions. The proper production rules of Algol-68 are obtained by systematically replacing the metanotions of the meta-language in the syntax rules by some terminal production of these metanotions. The resulting rules, in the meta-linguistic notation of Algol-60, may have, for example, the following form:

< chain of identifiers separated by commas >::= < identifier > < identifier >, < chain of identifiers separated by commas >

< reference to integer assignation >::= < reference to integer destination >:= < integer source >.

The use of a two-level grammar makes it possible, first, to reduce the number of production rules of the same type and, secondly, to give a syntactic expression to the attributive information of the notions and to ensure contextual relations which must otherwise be formulated as context conditions (static semantics).

References

[1a] A. van, et al. Wijngaarden, "Report on the algorithmic language Algol 68" Num. Math. , 14 (1969) pp. 79–218
[1b] A. van, et al. Wijngaarden, "Revised report on the algorithmic language Algol 68" Acta Inform. , 5 (1975) pp. 1–236
[2] C.H. Lindsey, S.G. van der Meulen, "Informal introduction to Algol 68" , North-Holland (1977)
How to Cite This Entry:
Algol-68. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Algol-68&oldid=45160
This article was adapted from an original article by A.P. Ershov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article