ALGOL 68

ALGOL 68 was conceived as a successor to the ALGOL 60 programming language, designed with the goal of a much wider scope of application and a more rigorously defined syntax and semantics. Long under-recognized (probably due to its mainly European origin), the contributions of ALGOL 68 to the whole field of computer science are deep and wide ranging, although many of them were not publicly identified until they were passed, in one form or another, to many subsequently developed programming languages.

Critics of ALGOL 68 point out that it abandoned the simplicity of ALGOL 60 and became a vehicle for the various complex ideas of its designers. The language also did little to make the compiler writer's task easy, in contrast to its deliberately simple contemporaries (and competitors) C and Pascal.

Today, the different dialects of the ML programming language family, such as OCAML, bear some resemblance to ALGOL 68, while being more advanced. The ALGOL 68 heritage is also acknowledged by Scheme, whose "Revised" (with an exponent) standards echo the "Revised Report" on ALGOL.

[Top]

Overview

[Top]

Block structure

The elemental unit of an ALGOL 68 program is the block (or closed clause):

begin declarations and statements end

where the keywords begin and end may be replaced by ( and ), respectively:

(declarations and statements)

The specific notation for keywords is not specified in ALGOL 68, to allow for different tastes and portability (some common options being to use all uppercase letters BEGIN, underlines begin, dot prefixes .begin, and bold type begin).

[Top]

Declarations

All variables need to be declared, but unlike most modern languages, the declaration does not have to appear prior to the first use. The basic datatypes (called modes in ALGOL 68 parlance) are real, int, compl (complex number), bool and char. For example:

real pi = 3.1415926; int n = 2;

However, the declaration real pi; is just syntactic sugar for ref real pi = loc real;. That is, pi is really the constant name for a reference to a newly generated local real variable. Furthermore, instead of defining both real and double, or int and long and short, etc., ALGOL 68 provided modifiers, so that the presently common double would be written as long real instead, for example. Type queries of the kind of max real and min long int were provided to adapt programs to different implementations.

[Top]

Expressions and compound statements

ALGOL 68 being an expression-oriented programming language, the value returned by an assignment statement is a reference to the destination. Thus, the following is valid ALGOL 68 code:

real twice pi = 2 * real pi = 3.1415926;

This notion is present in C and Perl, among others. Note that twice pi is a single identifier, i.e., blanks were permitted within ALGOL 68 names (effectively avoiding the underscores versus camel case versus all lowercase issues at once).

As another example, to express the mathematical idea of a sum of f(i) from i=1 to N, the following ALGOL 68 integer expression suffices:

(int sum := 0; for i to N do sum +:= f(i) od; sum)

Note that, being an integer expression, the former block of code can be used in any context where an integer value can be used. A block of code returns the value of the last expression it evaluated; this idea is present in Perl, among other languages.

Compound statements are all terminated by distinctive (if somewhat irreverent) closing brackets:


 if condition then statements [ else statements ] fi
 
 [ for index from first [ by inc ] to last ] [ while condition ] do statements od
 
 case switch in statements esac

This scheme not only avoids the dangling else problem but also avoids having to use begin and end in embedded statement sequences. Furthermore, the symbol pattern if...then...else...fi may be replaced by the more compact ...|...|... (see example below). The idea of terminating a compound statement with a backwards version of the keyword that started it is continued in the Bourne shell and its descendants.

[Top]

Arrays and structures

ALGOL 68 supports arrays with any number of dimensions, and it allows for the slicing of whole or partial rows or columns, among many other choices. AlGOL 68 supports multiple field structures (structs). Union types (modes) are supported. Reference variables may point to both array slices and structure fields. For an example of all this, here is the traditional linked list declaration:

mode node = union (real, int, compl, string); mode list = struct (node val, ref list next);

[Top]

Procedures

Procedure (proc) declarations require type specifications for both the parameters and the result (void if none):


 proc max of real (real a, b) real:
 
    if a > b then a else b fi;

or, using the compact form of the conditional statement:


 proc max of real (real a, b) real: (a>b | a | b);

The return value of a proc is the value of the last statement executed before the procedure returns. References to procedures (ref proc) are also permitted. Call-by-reference parameters are provided by specifying references (such as ref real) in the formal argument list. The following example defines a procedure that applies a function (specified as a parameter) to each element of an array:


 proc apply (ref [] real a, proc (real) real f):
 
    for i from lwb a to upb a do a[i] := f(a[i]) od;

This simplicity of code was unachievable not only in ALGOL 68's predecessor (ALGOL 60) but neither in many of its "successors" (Algol W, Euclid, Pascal, Modula, Modula-2, et al.) In fact, in several of these languages, the very intention of the previous piece of code is simply unexpressible. It is almost possible (no automatic determination of lower and upper array size bounds) in the C but at the expense of a more complex and cryptic syntax for function references, and without the type-safety of the ALGOL 68 example.

[Top]

Operators

The programmer may define new operators and both those and the pre-defined ones may be overloaded. The following example defines operator max with both dyadic and monadic versions (scanning across the elements of an array).


 prio max = 9;
 
 op max = (int a,b> int: (a>b|a|b);
 op max = (real a,b> real: (a>b|a|b);
 op max = (compl a,b> compl: (abs a > abs b|a|b);
 
 op max = ([]real a) real:
    (real x := - max real;
     for i from lwb a to upb a do (a[i]>x | x:=a[i]) od;
     x);

The first declaration sets the priority of <code>max to correspond to that of the proc max of real above.

[Top]

Input and output

Transput is the term used to refer to ALGOL 68's input and output facilities. There are pre-defined procedures for unformatted, formatted and binary transput. Files and other transput devices are handled in a consistent and machine-independent manner. The following example prints out some unformatted output to the standard output device:

print ((newpage, "Title", newline, "Value of i is ", i, "and x[i] is ", x[i], newline));

Note the predefined constants newpage and newline.

[Top]

Code sample

This sample program implements the Sieve of Eratosthenes to find all the prime numbers that are less than 100. The variable nil is the null pointer, as in Pascal, or a pointer with a value of zero in C. The notation x of y accesses a member x of a struct or union y.


begin # Algol-68 prime number sieve, functional style #

  proc error = (string s) void:
     (print(( newline, " error: ", s, newline)); goto stop);
  proc one to = (int n) list:
     (proc f = (int m,n) list: m>n | nil | cons(m, f(m+1,n)); f(1,n));

  mode list = ref node;
  mode node = struct (int h, list t);
  proc cons = (int n, list l) list: heap node := (n,l);
  proc hd   = (list l) int:  l is nil | error("hd nil"); skip | h of l;
  proc tl   = (list l) list: l is nil | error("tl nil"); skip | t of l;
  proc show = (list l) void: l isnt nil | print((" ",whole(hd(l),0))); show(tl(l));

  proc filter = (proc (int) bool p, list l) list:
     if l is nil then nil 
     elif p(hd(l)) then cons(hd(l), filter(p,tl(l)))
     else filter(p, tl(l))
     fi;

  proc sieve = (list l) list:
     if l is nil then nil 
     else
        proc not multiple = (int n) bool: n mod hd(l) ~= 0;
        cons(hd(l), sieve( filter( not multiple, tl(l) )))
     fi;

  proc primes = (int n) list: sieve( tl( one to(n) ));

  show( primes(100) )
end

[Top]

Compiling ALGOL 68

Compared with other languages of the time, ALGOL 68 presents several difficulties to anyone who wishes to write a compiler for it. The first is the relatively large size of its grammar, which means that the parser and semantic analyser are likely to be large as well. The second is that there is no "declaration before use" rule: although all identifiers must be declared, the declaration does not have to precede the first use. This is particularly a problem with operator declarations, because ALGOL 68 allows the programmer to change the priority of operators as well as overloading them with new meanings. This means that a statement like:

a := b * c + d;

might have its conventional meaning of:

a := (b * c) + d;

or it might mean:

a := b * (c + d);

and the compiler would not know this for sure until it reached the end of the input program. Indeed, if the declarations of the variables had not already been seen, the compiler would not know what code would be required to implement the "*" or "+" operators, or whether those operators were even defined between the modes of b, c and d. It can be argued that such practices have little or no use outside an obfuscated code contest, but there is nothing in the language specification that would prevent them. Although some modern languages allow the programmer to overload operators, they generally do not permit the operators' priorities to be changed, precisely because of this kind of problem.

One solution to the problem of unknown operator priorities is to parse the program twice according to the same grammar. In the first pass, the compiler assumes that all operators have the same priority. This is almost certainly not true, but it allows the compiler to find all the declarations and determine the program's block structure, which establishes the declarations' scopes. The second pass uses the information gathered in the first pass to assign the correct structure to all the expressions.

Many ALGOL 68 compilers work around this problem by requiring declaration before use. Although it could be argued that such a restriction makes some programs less elegant, it does not change those programs' meanings. The exception is mutually recursive modes, where the definition of some mode a contains a ref to an instance of some other mode b, and the definition of b contains a ref to an instance of a. The solution is either to forbid mutually recursive modes (the compilers which do this often have other restrictions which, so the author(s) would have us believe, make such modes impractical anyway), or to allow a mode to be declared incompletely. That is, the programmer is allowed to write just

mode m;

to tell the compiler that m exists, without saying anything more about it for the time being. The expectation is that the full definition of m will appear later, after definitions of other modes that contain ref m.

[Top]

References

Brailsford, D.F. and Walker, A.N., Introductory ALGOL 68 Programming, Ellis Horwood/Wiley, 1979
McGettrick, A.D., ALGOL 68, A First and Second Course, Cambridge Univ. Press, 1978
Peck, J.E.L., An ALGOL 68 Companion, Univ. of British Columbia, October 1971
Tanenbaum, A.S., A Tutorial on ALGOL 68, Computing Surveys 8, 155-190, June 1976 and 9, 255-256, September 1977

[Top]


View Live Article	This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License