ALGOL 68 Overview Block Structure Declarations Expressions And

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.

1 Overview

1.1 Block structure

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

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

1.2 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:

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.

1.3 Expressions and compound statements

This notion is present in C and PerlImage:Programming-republic-of-perl. gif|right|framed|Programming Republic of logo]] Perl also Practical Extraction and Report Language (a backronym, see below), is a programming language released by Larry Wall on December 18, 1987 that borrows features fr, 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:

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 PerlImage:Programming-republic-of-perl. gif|right|framed|Programming Republic of logo]] Perl also Practical Extraction and Report Language (a backronym, see below), is a programming language released by Larry Wall on December 18, 1987 that borrows features fr, among other languages.

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

This scheme not only avoids the dangling elseThe dangling else is a well-known problem in computer programming in which a seemingly well-defined grammar can become ambiguous. In many programming languages you can write code like this: if a then if b then s1 else s2 which can be understood in two way 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 shellThe Bourne shell or sh was the default Unix shell of Unix Version 7, and replaced the original Unix shell, whose executable file had the same name, sh . It was developed by Stephen Bourne, of AT&T Bell Laboratories, and first released in 1977 in the Versi and its descendants.

1.4 Arrays and structures

ALGOL 68 supports arrayIn computer programming, an array also known as a vector or list, is one of the simplest data structures. Arrays hold a fixed number of equally-sized data elements, generally of the same data type. Individual elements are accessed by index using a consecus 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);

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

1.6 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 max to correspond to that of the proc max of real above.

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

1.8 Parallel processing
A little used feature of ALGOL 68 (and in fact, rarely implemented by compiler designers) was parallel processing. The programmer simply wrote 


  par ( something, something else , another thing )


and each statement (typically a procedure call or block) would be executed. No promises were made about the order of execution, only that all would eventually complete. Each statement could use local variables, or share those already declared. If multiple processors were available, the statements might execute in parallel; control could also switch between them at any time. Programmers could sychronise using a special semaphore type sema.  
This idea turned up again in the Concurrent Pascal language, but did not widely catch on. However, most contemporary operating systems offer threads, which offer exactly the same facilities, arguably with less elegance. Threads are generally accessed via runtime library calls outside the language, and concurrency can place a strain on conventional compilers.

2 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



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

4 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

5 External links
 Revised Report on the Algorithmic Language ALGOL 68 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
 Algol 68 Genie - a GNU GPL Algol 68 subset interpreter

 Programming languages
 Major programming languages
 Imperative programming languages





<Hide>

Home > ALGOL 68

1 Overview

1.1 Block structure

1.2 Declarations

1.3 Expressions and compound statements

1.4 Arrays and structures

1.5 Procedures

1.6 Operators

1.7 Input and output

1.8 Parallel processing

2 Code sample

3 Compiling ALGOL 68

4 References

5 External links

Topics: ALGOL 68, Overview, Block Structure, Declarations, Expressions...