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. Contributions of ALGOL 68 to the field of computer science are deep and wide ranging, although some of them were not publicly identified until they were passed, in one form or another, to one of many subsequently developed programming languages.

ALGOL 68 was defined using a two-level grammar formalism invented by Adriaan van Wijngaarden. Van Wijngaarden grammars use a context-free grammar to generate an infinite set of productions that will recognize a particular ALGOL 68 program; notably, they are able to express the kind of requirements that in many other programming language standards are labelled "semantics" and have to be expressed in ambiguity-prone natural language prose, and then implemented in compilers as ad hoc code attached to the formal language parser.

The main principles of design are completeness and clarity of design, orthogonal design, security, efficiency, the latter by static mode checking, mode-independent parsing, independent compilation and loop optimization.

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

The ALGOL 68 heritage is acknowledged by Scheme, and by C++.

For a full length treatment of the language, see Programming Algol 68 Made Easy (http://www.geocities.com/ernobe) by Dr. Sian Leitch.

Notable Language Elements

Units (Expressions)

The basic language construct is the unit. A unit may be a formula, an enclosed clause, a routine text or one of several technically needed constructs. The technical term enclosed clause unifies some of the inherently bracketting constructs known as block, do statement, switch statement in other contemporary languages. When keywords are used, generally the inversed character sequence of the introducing keyword is used for terminating the enclosure ( IF - FI, CASE - ESAC, DO - OD). This feature was reused in the common UNIX Bourne shell.

Declarations

All variables need to be declared, 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 are provided to adapt programs to different implementations.

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 spi, twice pi; twice pi := 2 * ( spi := 3.1415926 );

This notion is present in C and Perl, among others. Note that twice pi is a single identifier, i.e., blanks are permitted within ALGOL 68 names (effectively avoiding the underscores versus camel case versus all lowercase issues at once, but at the price of introducing a cornucopia of more serious problems in software engineering).

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
 shorthand form of if statement:  (condition|statements|statements)
 
 [ for index from first [ by inc ] to last ] [ while condition ] do statements od
 
 case switch in statements, statements,... out statements esac
 shorthand form of case statement:  (switch|statements,statements,...|statements)

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).

Arrays, structures and unions

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.

 mode vec =    [3]real;    # vector mode declaration (typedef) #
 mode matrix = [3][3]real; # matrix mode declaration (typedef) #
 vec r1 :=   (1,2,3);      # array variable #
 []real r2 = (4,5,6);      # array constant, length is implied #
 op + = (vec a,b)vec:      # binary operator definition #
   (vec out; int i; for i from ⌊a to ⌈a do out[i]:=a[i]+b[i] od; out);
 matrix m:=(r1,r2,r1+r2);  
 print ((m[][2:3]));  # print the 2nd and 3rd element of each row #

Matrices can be sliced either way, eg:

 ref vec col:=m[][2]  # extract a ref (pointer) to the 2nd column!! #

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);

Usage example for union case of node:

 node n:="1234";

 case n in
   (real):print(("real:",n)),
   (int):print(("int:",n)),
   (compl):print(("compl:",n)),
   (string):print(("string:",n))
   out print ((n,"?"))
 esac

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 in ALGOL 68's predecessor ALGOL 60.

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);

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.

Parallel processing

A little used feature of ALGOL 68 (and in fact, rarely implemented by compiler designers) was parallel processing.

 proc romeo speaks = void:
        print(("R: shall I speak at this?",newline)),
      juliet speaks = void:
        print(("J: wherefore art thou Romeo?",newline));
                                                                               
 # the semaphore to ensure neither talk at once #
 sema lead = level 1;
                                                                               
 # the semaphore to ensure neither gets too far ahead #
 sema romeo cue = level 2,
      juliet cue = level 2;
 
 par (
   to 16 do # romeo's side of the conversation #
     ↓ lead; romeo speaks; ↑ lead;
     ↑ juliet cue; ↓ romeo cue
   od, # <= The comma is important! #
   to 16 do # juliet's side of the conversation #
     ↓ lead; juliet speaks; ↑ lead;
     ↑ romeo cue; ↓ juliet cue
   od
 )

Code sample

This sample program implements the Sieve of Eratosthenes to find all the prime numbers that are less than 100. nil is the ALGOL 68 analogue of the null pointer in other languages. 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

Program representation

A feature of ALGOL 68, inherited from ALGOL tradition, is its different representations. There is a representation language used to describe algorithms in printed work, a strict language (rigorously defined in the Report) and an official reference language intended to be used in actual compiler input. In the examples above you will observe underlined words. This is the formal representation of the language. ALGOL 68 has no reserved words, and spaces are allowed in identifiers, so the fragment:

 int<u> a real int = 3 ;

 'INT' A REAL INT = 3; 
 .INT A REAL INT = 3;
 INT a real int = 3;
 int a_real_int = 3;

<u>skip - an undefined value always syntactically valid,
void - syntactically like a mode, but not one,
nil - a name not denoting anything, of no mode,
empty - the only value admissible to void, needed for selecting void in a union,
[1:0]int - an empty array of intergral values, with mode []int,
undefined - a procedure raising an exception in the runtime system.

The term nil is var always evaluates to true for any variable, whereas it is not known to which value a comparison x < skip evaluates for any integer x.

ALGOL 68 leaves intentionally undefined, what happens in case of integer overflow, the integer bit representation, and the degree of numerical accuracy for floating point. In contrast, the language Java has been criticized for overspecifying the latter.

Comparison to C++

Regarding the computing features, the nearest living sibling to ALGOL 68 may be C++, making this a good comparison candidate:

C++ has not:

• nested functions,
• definable operator symbols and priorities,
• garbage collection,
• use before define,
• formatted transput using complex formatting declarations,
• assignment operation symbol (to avoid confusion with equal sign),
• arrays (and slice operations on them, but in layered libraries),
• automatic UNIONs,
• CASE expressions,
• nonlocal GOTO (not a good idea in most cases, anyway).
• intuitive declaration syntax due to its origin from C.

ALGOL 68 has not:

• public/private access protection,
• overloaded procedures (in contrast to operators),
• explicit memory allocation and deallocation,
• forward declarations,
• textual preprocessing (header files),
• confusion between &- and pointer-style,
• comment lines (only bracketed comments),
• hierarchical classes.

Variants

The language described above is that of the "Revised Report". The original language differs in syntax of the mode cast, and it had the feature of proceduring, i.e. coercing the value of a term into a procedure which evaluates the term. Proceduring effectively can make evaluations lazy. The most useful application could have been the short-circuited evaluation of boolean operators. In

op andf = (boola,proc boolb)bool:(a | b | a);

b is only evaluated, if a is true. As defined in ALGOL 68, it did not work as expected. Most implementations emulate this behaviour by extension of the language.

After the revision of the report, some extensions to the language have been proposed to widen the applicability:

• partial parametrisation: creation of functions (with less parameters) by specification of some, but not all parameters for a call, e.g. a function logarithm of two parameters, base and argument, could be specialised to natural, binary or decadic log,
• module extension for support of external linkage,
• mode parameters for implementation of limited parametrical polymorphism (most operation on data structures like lists, trees or other data containers can be specified without touching the pay load).

So far, only partial parametrisation has been implemented, in ALGOL68G.

ALGOL 68R from RRE was the first ALGOL 68 subset implementation, running on the ICL 1900. Based on the original language, the main subset restrictions were definition before use and no parallel processing. This compiler was popular in UK universities in the 1970s, where many computer science students learnt ALGOL 68 as their first programming language; the compiler was renowned for good error messages.

ALGOL 68RS from RSRE was a portable compiler system written in ALGOL 68RS (bootstrapped from ALGOL 68R), and implemented on a variety of systems including the ICL 2900, Multics and DEC VAX/VMS. The language was based on the Revised Report, but with similar subset restrictions to ALGOL 68R. This compiler survives in the form of an Algol68-to-C-Compiler.

In ALGOL 68S from Carnegie_Mellon_University the power of parallel processing was improved by adding an orthogonal extension, eventing. Any variable declaration containing keyword event made assignments to this variable eligible for parallel evaluation, i.e. the right hand side was made into a procedure which was moved to one of the processors of the C.mmp multiprocessor system. Accesses to such variables were delayed after termination of the assignment.

Cambridge ALGOL 68C was a portable compiler that implemented a subset of ALGOL 68 by enforcing definition before use, restricting operator definitions and omitting garbage collection.

ALGOL 68G by M. van der Veer implements a usable Algol68 interpreter for today's computers and operating systems. A minor restriction is that formatted transput is still not conforming to the Revised Report.

Quotes

• [...] it was said that A68's popularity was inversely proportional to [...] the distance from Amsterdam [1] (http://mail.python.org/pipermail/python-dev/2005-June/054225.html)
• ... C does not descend from Algol 68 is true, yet there was influence, much of it so subtle that it is hard to recover even when I think hard. In particular, the union type (a late addition to C) does owe to A68, not in any details, but in the idea of having such a type at all. More deeply, the type structure in general and even, in some strange way, the declaration syntax (the type-constructor part) was inspired by A68. And yes, of course, "long". Dennis Ritchie, 18 June 1988 [2] (http://groups.google.co.uk/group/comp.lang.misc/browse_thread/thread/1e6d4bb30659b78d/f57b6f5c81502cf5?q=%22algol+68%22+dmr&rnum=6&hl=en#f57b6f5c81502cf5)

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, http://vestein.arb-phys.uni-dortmund.de/~wb/RR/tanenbaum.pdf

External links

• Revised Report on the Algorithmic Language ALGOL 68 (http://vestein.arb-phys.uni-dortmund.de/~wb/RR/rrTOC.html) The official reference for users and implementors of the language

• Charles Lindsey's paper on the development of ALGOL 68 for the second History of Programming Languages conference proceedings (http://www.cs.man.ac.uk/~chl/index.html)
• Algol 68 Genie - a GNU GPL Algol 68 subset interpreter (http://www.xs4all.nl/~jmvdveer/algol.html)de:Algol 68