ALGOL 68

ALGOL 68
Paradigm(s) multi-paradigm: concurrent, imperative
Appeared in 1968, last revised 1973
Designed by A. van Wijngaarden, B.J. Mailloux, J.E.L. Peck and C.H.A. Koster, et al.
Typing discipline static, strong, safe, structural
Major implementations ALGOL 68C, ALGOL 68G, ALGOL 68R, ALGOL 68RS, ALGOL 68S, FLACC, Алгол 68 Ленинград/Leningrad Unit
Dialects ALGOL 68/FR (Final Report: 1968), Algol 68/RR (Revised Report: 1973)
Influenced by ALGOL 60, ALGOL Y
Influenced Agena, ALGOL 68C, C, C++,[1] Bourne shell, Bash, Steelman, Ada, Python[2]

ALGOL 68 (short for ALGOrithmic Language 1968) is an imperative computer programming language that was conceived as a successor to the ALGOL 60 programming language, designed with the goal of a much wider scope of application and 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 features include expression-based syntax, user-declared types and structures/tagged-unions, a reference model of variables and reference parameters, string, array and matrix slicing, and also concurrency.

ALGOL 68 was designed by IFIP Working Group 2.1. On December 20, 1968 the language was formally adopted by Working Group 2.1 and subsequently approved for publication by the General Assembly of IFIP.

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 labeled "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 aims and principles of design of ALGOL 68:
  1. Completeness and clarity of design,[3]
  2. Orthogonal design,[4]
  3. Security,[5]
  4. Efficiency:[6]
    • Static mode checking
    • Mode-independent parsing
    • Independent compilation
    • Loop optimization
    • Representations - in minimal & larger character sets

ALGOL 68 was the first (and possibly one of the last) major language for which a full formal definition was made before it was implemented.

C.H.A. Koster, [7]

ALGOL 68 has been criticized, most prominently by some members of its design committee such as C. A. R. Hoare and Edsger Dijkstra, for abandoning the simplicity of ALGOL 60 becoming a vehicle for complex or overly general ideas, and doing little to make the compiler writer's task easy, in contrast to deliberately simple contemporaries (and competitors) such as C, S-algol and Pascal.

In the 1973 revision, certain features - such as proceduring, gommas and formal bounds - were omitted.[8] c.f. The language of the unrevised report.

Though European defence agencies (in Britain Royal Signals and Radar Establishment - RSRE) promoted the use of ALGOL 68 for its expected security advantages, the American side of the NATO alliance decided to develop a different project, the Ada programming language, making its use obligatory for U.S. defense contracts.

Steve Bourne, who was on the Algol 68 revision committee, took some of its ideas to his Bourne shell (and thereby, to descendant shells such as Bash) and to C (and thereby to descendants such as C++).

The complete history of the project can be found in C.H. Lindsey's A History of ALGOL 68.[9]

For a full length treatment of the language, see Programming Algol 68 Made Easy[10] by Dr. Sian Leitch, or Learning Algol 68 Genie by Dr. Marcel van der Veer which includes the Revised Report.

Contents

Time-line of ALGOL 68

Year Event Contributor
Mar 1959 ALGOL Bulletin Issue 1 (First) Peter Naur / ACM
Feb 1968 Draft Report(DR) Published IFIP Working Group 2.1
Mar 1968 Algol 68 Final Report(FR) Presented at Munich Meeting IFIP Working Group 2.1
Jun 1968 Meeting in Tirrenia, Italy IFIP Working Group 2.1
Aug 1968 Meeting in North Berwick, Scotland IFIP Working Group 2.1
Dec 1968 Algol 68 Final Report(FR) Presented at Munich Meeting IFIP Working Group 2.1
Apr 1970 ALGOL 68R(R) under GEORGE 3 on an ICL 1907F. Royal Signals and Radar Est.
Sep 1973 Revised Report (RR)Published IFIP Working Group 2.1
1975 ALGOL 68C(C) - transportable compiler (zcode VM) S. Bourne, Andrew Birrell, and Michael Guy
Jun 1977 Strathclyde ALGOL 68 conference, Scotland ACM
May 1978 Proposals for ALGOL H - A Superlanguage of ALGOL 68 A. P. Black, V. J. Rayward-Smith
1984 Full ALGOL 68S(S) compiler for Sun, SPARC, and PCs C.H.Lindsey ea, Manchester
Aug 1988 ALGOL Bulletin Issue 52 (last) Ed. C. H. Lindsey / ACM
May 1997 Algol68 S(S) published on the internet Charles H. Lindsey
Nov 2001 ALGOL 68G(G) released (GNU GPL open source licensing) Marcel van der Veer

The Algorithmic Language ALGOL 68 Reports

"Van Wijngaarden once characterized the four authors, somewhat tongue-in-cheek, as: Koster: transputter, Peck: syntaxer, Mailloux: implementer, Van Wijngaarden: party ideologist." -- Koster.

Standardization

On December 20, 1968 the "Final Report" (MR 101) was adopted by the Working Group, then subsequently approved by the General Assembly of UNESCO's IFIP for publication. Translations of the standard were made for Russian, German, French and Bulgarian, and then later Japanese. The standard was also made available in Braille. Subsequently ALGOL 68 became one of the GOST standards in Russia.

Notable language elements

Bold symbols and reserved words

There are 61 such reserved words ( some with "brief symbol" equivalents ) in the standard sub-language:

 mode, op, prio, proc,
 flex, heap, loc, long, ref, short,
 bits, bool, bytes, char, compl, int, real, sema, string, void,
 channel, file, format, struct, union, 
 of, at "@", is ":=:", isnt ":/=:", true, false, empty, nil "∘", skip "~",
 co "¢", comment "¢", pr, pragmat,
 case in ouse ''in'' out esac "( ~ | ~ |: ~ | ~ | ~ )", 
 for from to by while do od,
 if then elif ''then'' else fi "( ~ | ~ |: ~ | ~ | ~ )", 
 par begin end "( ~ )", go ''to'', goto, exit.

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 (assignation, jump, skip, nihil). 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 reversed character sequence of the introducing keyword is used for terminating the enclosure, eg. ( 'if' ~ then ~ else ~ 'fi', 'case' ~ in ~ out ~ 'esac', for ~ while ~ 'do' ~ 'od'). This feature was reused by Stephen Bourne in the common Unix Bourne shell. An expression may also yield a multiple value, which is constructed from other values by a collateral clause. This construct just looks like the parameter pack of a procedure call.

mode: Declarations

The basic data types (called modes in ALGOL 68 parlance) are real, int, compl (complex number), bool, char, bits and bytes. For example:

GeSHi Error: GeSHi could not find the language algol68 (using path /usr/share/php-geshi/geshi/) (code 2)

You need to specify a language like this: <source lang="html4strict">...</source>

Supported languages for syntax highlighting:

abap, actionscript, actionscript3, ada, apache, applescript, apt_sources, asm, asp, autoit, avisynth, bash, basic4gl, bf, bibtex, blitzbasic, bnf, boo, c, c_mac, caddcl, cadlisp, cfdg, cfm, cil, cmake, cobol, cpp, cpp-qt, csharp, css, d, dcs, delphi, diff, div, dos, dot, eiffel, email, erlang, fo, fortran, freebasic, genero, gettext, glsl, gml, gnuplot, groovy, haskell, hq9plus, html4strict, idl, ini, inno, intercal, io, java, java5, javascript, kixtart, klonec, klonecpp, latex, lisp, locobasic, lolcode, lotusformulas, lotusscript, lscript, lsl2, lua, m68k, make, matlab, mirc, modula3, mpasm, mxml, mysql, nsis, oberon2, objc, ocaml, ocaml-brief, oobas, oracle11, oracle8, pascal, per, perl, php, php-brief, pic16, pixelbender, plsql, povray, powershell, progress, prolog, properties, providex, python, qbasic, rails, rebol, reg, robots, ruby, sas, scala, scheme, scilab, sdlbasic, smalltalk, smarty, sql, tcl, teraterm, text, thinbasic, tsql, typoscript, vb, vbnet, verilog, vhdl, vim, visualfoxpro, visualprolog, whitespace, whois, winbatch, xml, xorg_conf, xpp, z80

However, the declaration real x; is just syntactic sugar for ref real x = loc real;. That is, x is really the constant identifier for a reference to a newly generated local real variable.

Furthermore, instead of defining both float 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 or long 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.

All variables need to be declared, the declaration does not have to appear prior to the first use.

primitive-declarer: int, real, compl, complexG, bool, char, string, bits, bytes, format, file, pipeG, channel, sema

Other declaration symbols include: flex, heap, loc, ref, long, short, eventS

A new mode (type) may be declared using a mode declaration:

 int max=99;
 mode newtype = [0:9][0:max]struct (
     long real a, b, c, short int i, j, k, ref real r
 );

This has the similar effect as the following C++ code:

 const int max=99;
 typedef struct { 
     double a, b, c; short i, j, k; float *r;
 } newtype[9+1][max+1];

Note that for ALGOL 68 only the newtype mode-indication appears to the left of the equals symbol, and most notably the construction is made - and can be read - from left to right without regard to priorities.

Coercions: casting

The coercions produce a coercend from a coercee according to three criteria: the a priori mode of the coercend before the application of any coercion, the a posteriori mode of the coercee required after those coercions, and the syntactic position or "sort" of the coercee. Coercions may be cascaded.

There are six possible coercions, termed "deproceduring", "dereferencing", "uniting", "widening", "rowing" and "voiding". Each Coercion, except "uniting", prescribes a corresponding dynamic effect on the associated values. Hence, a number of primitive actions can be programmed implicitly by coercions.

Context strength - Allowed coercions:

pr & co: Pragmats and Comments

Pragmats are directives in the program, typically hints to the compiler. eg.

pragmat heap=32 pragmat
pr heap=32 pr

Comments can be inserted in variety of ways:

¢ The original way of adding your 2 cents worth to a program ¢
comment "bold" comment comment
co Style i comment co 
# Style ii comment #
£ This is a hash/pound comment for a UK keyboard £ 

Normally, comments cannot be nested in ALGOL 68. This restriction can be circumvented by using different comment delimiters (e.g. use hash only for temporary code deletions).

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 half pi, one pi; one pi := 2 * ( half pi := 2 * arc tan(1) )

This notion is present in C and Perl, among others. Note that half pi is a single identifier, i.e., blanks are ignored even within ALGOL 68 identifiers (effectively avoiding the underscores versus camel case versus all lower-case 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 Lisp, among other languages.

Compound statements are all terminated by distinctive (and somewhat reverent) closing brackets:

 if condition then statements [ else statements ] fi
 "brief" form of if statement:  ( condition | statements | statements )
 if condition1 then statements elif condition2 then statements [ else statements ] fi
 "brief" form:  ( condition1 | statements |: condition2 | statements | statements )

This scheme not only avoids the dangling else problem but also avoids having to use begin and end in embedded statement sequences.

 case switch in statements, statements,... [ out statements ] esac
 "brief" form:  ( switch | statements,statements,... | statements )
 case switch1 in statements, statements,... ouse switch2 in statements, statements,... [ out statements ] esac
 "brief" form of case statement:  ( switch1 | statements,statements,... |: switch2 | statements,statements,... | statements )

Brief choice clause example:

proc days in month = (int year, month)int: 
  (month|31,
    (year%×4=0 ∧ year%×100≠0 ∨ year%×400=0|29|28),
    31,30,31,30,31,31,30,31,30,31
  );

Bold choice clause example:

proc days in month = (int year, month)int: 
  case month in 31, 
    if year mod 4 eq 0 and year mod 100 ne 0 or year mod 400 eq 0 then 29 else 28 fi,
    31,30,31,30,31,31,30,31,30,31
  esac;

Algol68 allowed the switch to be of either type int or (uniquely) union. The latter allows the enforcing strong typing onto union variables. c.f. union below for example.

 [ for index ] [ from first ] [ by increment ] [ to last ] [ while condition ] do statements od
 The minimum form of a "loop clause" is thus: do statements od

This was considered the "universal" loop, the full syntax is:

for i from 1 by 1 to 3 while i≠4 do ~ od

There are several unusual aspects of the construct:

int sum sq:=0;
for i
while 
  print(("So far:",i,newline));
  sum sq≤1000 
do 
  sum sq+:=i↑2
od

Subsequent "extensions" to the standard Algol68 allowed the to syntactic element to be replaced with upto and downto to achieve a small optimisation. The same compilers also incorporated:

Further examples can be found in the code examples below.

struct, union & [:]: Structures, unions and arrays

ALGOL 68 supports arrays with any number of dimensions, and it allows for the slicing of whole or partial rows or columns.

 mode vector = [1:3]    real;   # vector mode declaration (typedef)  #
 mode matrix = [1:3,1:3]real;   # matrix mode declaration (typedef)  #
 vector v1  := (1,2,3);         # array variable initially (1,2,3)   #
 []real v2   = (4,5,6);         # constant array, type equivalent to vector, bounds are implied  #
 op + = (vector a,b) vector:    # binary operator definition         #
   (vector out; for i from ⌊a to ⌈a do out[i] := a[i]+b[i] od; out);
 matrix m := (v1, v2, v1+v2);  
 print ((m[,2:]));              # a slice of the 2nd and 3rd columns #

Matrices can be sliced either way, eg:

 ref vector row = m[2,];  # define a ref (pointer) to the 2nd row #
 ref vector col = m[,2];  # define a ref (pointer) to the 2nd column #

ALGOL 68 supports multiple field structures (struct) and united modes. Reference variables may point to any mode including 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),
      list = struct (node val, ref list next);

Usage example for union case of node:

Algol68 as in the 1968 Final Report
 node n := "1234";
 real r; int i; compl c; string s
 case r,i,c,s::=n in
   print(("real:", r)),
   print(("int:", i)),
   print(("compl:", c)),
   print(("string:", s))
   out print(("?:", n))
 esac
Algol68 as in the 1973 Revised Report
 node n := "1234";
  
 case n in
   (real r):   print(("real:", r)),
   (int i):    print(("int:", i)),
   (compl c):  print(("compl:", c)),
   (string s): print(("string:", s))
   out         print(("?:", n))
 esac

proc: 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 "brief" 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 expression evaluated in the procedure. 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.

op: 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 out := a[lwb a];
     for i from lwb a + 1 to upb a do ( a[i]>out | out:=a[i] ) od;
     out)

Array, Procedure and Dereference operations

priority Operation +Algol68G
effectively 11 dereferencing, deproceduring(~,~), subscripting[~], rowing[~,] & slicing[~:~] currying(~,)

Monadic operators

priority Algol68 "Worthy characters[1]" +Algol68RR +Algol68C,G +Algol68FR
10 not, up, down, lwb, upb,

-, abs, arg, bin, entier, leng, level, odd, repr, round, shorten

¬, ↑, ↓, ⌊, ⌈ ~ lws, ups, ⎩, ⎧, btb, ctb

Standard dyadic operators with associated priorities

priority Algol68 "Worthy characters" +Algol68RR +Algol68C,G +Algol68FR
9 +*, i +×, ⊥  !
8 shl, shr, **, up, down, lwb, upb ↑, ↓, ⌊, ⌈ lws, ups, ⎩, ⎧
7 *, /,  %, over,  %*, mod, elem ×, ÷, ÷×, ÷*, %×, □ ÷:
6 -, +
5 <, lt, <=, le, >=, ge, >, gt ≤, ≥
4 =, eq, /=, ne ~=
3 &, and
2 or
1 minusab, plusab, timesab, divab, overab, modab, plusto,

-:=, +:=, *:=, /:=, %:=, %*:=, +=:

×:=, ÷:=, ÷×:=, ÷*:=,  %×:= minus, plus, div, overb, modb, ÷::=, prus

Assignation and identity relations etc

These are technically not operators, rather they are considered "units associated with names"

priority Algol68 "Worthy characters" +Algol68RR +Algol68C +Algol68FR
effectively 0  :=, =:, = , :=:, :/=:, is, isnt, of, at , @  :≠:, :  :~=: ct, ::, ctab, ::=, .., is not, →

“:=:” (alternatively “is”) tests if two pointers are equal; “:/=:” (alternatively “isnt”) tests if they are unequal.

Why :=: and :/=: are needed: Consider trying to compare two pointer values, such as the following variables, declared as pointers-to-integer:

ref int ip, jp

Now consider how to decide whether these two are pointing to the same location, or whether one of them is pointing to nil. The following expression

ip = jp

will dereference both pointers down to values of type int, and compare those, since the “=” operator is defined for int, but not ref int. It is not legal to define “=” for operands of type ref int and int at the same time, because then calls become ambiguous, due to the implicit coercions that can be applied: should the operands be left as ref int and that version of the operator called? Or should they be dereferenced further to int and that version used instead? Therefore the following expression can never be made legal:

ip = nil

Hence the need for separate constructs not subject to the normal coercion rules for operands to operators. But there is a gotcha. The following expressions:

ip :=: jp
ip :=: nil

while legal, will probably not do what might be expected. They will always return false, because they are comparing the actual addresses of the variables ip and jp, rather than what they point to. To achieve the right effect, one would have to write

ip :=: ref int(jp)
ip :=: ref int(nil)

Patent application: On 14 May 2003, software patent application No. 20040230959[19] was filed for the ISNOT operator by employees of Microsoft. This patent was granted on 18 November 2004.

Special characters

Most of Algol's "special" characters (×, ÷, ≤, ≥, ≠, ¬, ⊃, ≡, ∨, ∧, →, ↓, ↑, ⌊, ⌈, ⎩, ⎧, ⊥, ⏨, ¢, ○ and □) can be found on the IBM 2741 keyboard with the APL "golf-ball" print head inserted, these became available in the mid 1960s while ALGOL 68 was being drafted. These characters are also part of the unicode standard and most of them are available in several popular fonts:

transput: 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 procedures newpage and newline passed as arguments.

Books, channels and files

The transput is considered to be of books, channels and files:

formatted transput

"Formatted transput" in ALGOL 68's transput has its own syntax and patterns (functions), with formats embedded between two $ characters. Examples:

printf (($2l"The sum is:"x, g(0)$, m + n)); ¢ prints the same as: ¢
print ((new line, new line, "The sum is:", space, whole (m + n, 0))

par: Parallel processing

ALGOL 68 supports programming of parallel processing. Using the keyword par, a collateral clause is converted to a parallel clause, where the synchronisation of actions is controlled using semaphores. In A68G the parallel actions are mapped to threads when available on the hosting operating system. In A68S a different paradigm of parallel processing was implemented (see below).

int initial foot width = 5;
mode foot = struct(
   string name,
   sema width,
   bits toe ¢ packed vector of BOOL ¢ 
);
 
foot left foot:= foot("Left", level initial foot width, 2r11111), 
     right foot:= foot("Right", level initial foot width, 2r11111);
 
¢ 10 round clip in a 1968 Colt Python .357 Magnum ¢ 
sema rounds = level 10;
 
¢ the Magnum needs more barrels to take full advantage of parallelism ¢ 
sema acquire target = level 1;
 
prio ∧:= = 1;
op ∧:= = (ref bits lhs, bits rhs)ref bits: lhs := lhs ∧ rhs;
 
proc shoot = (ref foot foot)void: (
  ↓acquire target; 
  ↓rounds; 
  print("BANG! ");
  ↓width → foot; 
  toe → foot ∧:= ¬(bin 1 shl level width → foot);
  printf(($g": Ouch!! - "5(g)l$, name → foot, []bool(toe → foot)[bits width - initial foot width + 1:]));
  ↑acquire target
);
 
¢ do shooting in parallel to cater for someone hoping to stand on just one foot ¢ 
par (
  for toe to initial foot width do
    shoot(left foot)
  od, ¢ <= a comma is required ¢ 
  for toe to initial foot width do
    shoot(right foot)
  od
)

Examples of use

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

Operating Systems written in ALGOL 68

Note: The Soviet Era computers Эльбрус-1 (Elbrus-1) and Эльбрус-2 were created using high-level language uЭль-76 (AL-76), rather than the traditional assembly. uЭль-76 resembles Algol-68, The main difference is the dynamic binding types in uЭль-76 supported at the hardware level. uЭль-76 is used for application, job control, system programming [4].

Applications

Both ALGOL 68C and ALGOL 68R are written in ALGOL 68, effectively making ALGOL 68 an application of itself. Other applications include:

Libraries and APIs

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's reserved words are effectively in a different namespace from identifiers, and spaces are allowed in identifiers, so the fragment:

 int a real int = 3 ;

is legal. The programmer who actually writes the code does not have the option of underlining the code. Depending on hardware and cultural issues, different methods to denote these identifiers, have been devised, called stropping regimes. So all or some of the following may be possible programming representations:

 'INT' A REAL INT = 3; 
 .INT A REAL INT = 3; # the POINT stropping style #
 INT a real int = 3;# the UPPER stropping style #
 int a_real_int = 3;# the RES stropping style, there are 61 accepted reserved words #

All implementations must recognise at least POINT, UPPER and RES inside PRAGMAT sections.

The following characters were recommended for portability, and termed "worthy characters" in the Report on the Standard Hardware Representation of Algol 68:

This reflected a problem in the 1960s where some hardware didn't support lower-case, nor some other non ASCII characters, indeed in the 1973 report it was written: "Four worthy characters -- "|", "_", "[", and "]" -- are often coded differently, even at installations which nominally use the same character set."

Example of different program representations

Algol68 as typically published
¢ bold/underline typeface ¢
mode xint = int;
xint sum sq:=0;
for i while
  sum sq≠70×70
do
  sum sq+:=i↑2
od 
Quote stropping (like wikitext)
'pr' quote 'pr' 
'mode' 'xint' = 'int';
'xint' sum sq:=0;
'for' i 'while'
  sum sq≠70×70
'do'
  sum sq+:=i↑2
'od'
For a 7-bit character code compiler
.PR UPPER .PR
MODE XINT = INT;
XINT sum sq:=0;
FOR i WHILE
  sum sq/=70*70
DO
  sum sq+:=i**2
OD 
For a 6-bit character code compiler
.PR POINT .PR
.MODE .XINT = .INT;
.XINT SUM SQ:=0;
.FOR I .WHILE
  SUM SQ .NE 70*70
.DO
  SUM SQ .PLUSAB I .UP 2
.OD
Using res stropping of reserved word
.PR RES .PR
mode .xint = int;
.xint sum sq:=0;
for i while
  sum sq≠70×70
do
  sum sq+:=i↑2
od 

ALGOL 68 allows for every natural language to define its own set of keywords Algol-68. As a result, programmers are able to write programs using keywords from their native language. Below is an example of a simple procedure that calculates "the day following", the code is in two languages: English and German.

 # Next day date - English variant #
 mode date = struct(int day, string month, int year);
 proc the day following = (date x) date:
      if day of  x < length of month (month of x, year of x)
      then (day of x + 1, month of x, year of x)
      elif month of x = "December"
      then (1, "January", year of x + 1)
      else (1, successor of month (month of x), year of x)
      fi;

 # Nachfolgetag - Deutsche Variante #
 menge datum = tupel(ganz tag, wort monat, ganz jahr);
 funktion naechster tag nach = (datum x) datum:
          wenn tag von x < monatslaenge(monat von x, jahr von x)
          dann (tag von x + 1, monat von x, jahr von x)
          wennaber monat von x = "Dezember"
          dann (1, "Januar", jahr von x + 1)
          ansonsten (1, nachfolgemonat(monat von x), jahr von x)
          endewenn;      

Russian/Soviet example: In English Algol68's reverent case statement reads case ~ in ~ out ~ esac, in Cyrillic this reads выб ~ в ~ либо ~ быв.

Some Vanitas

For its technical intricacies, ALGOL 68 needs a cornucopia of methods to deny the existence of something:

skip, "~" or "?"C - an undefined value always syntactically valid,
empty - the only value admissible to void, needed for selecting void in a union,
void - syntactically like a mode, but not one,
nil or "○" - a name not denoting anything, of an unspecified reference mode,
() or specifically [1:0]int - a vacuum is an empty array (here specifically of mode []int).
undefined - a standards reports procedure raising an exception in the runtime system.
ℵ - Used in the standards report to inhibit introspection of certain types. eg sema

c.f. below for other examples of ℵ.

The term nil is var always evaluates to true for any variable (but see above for correct use of is :/=:), 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 over-specifying the latter.

Both official reports included some advanced features that were not part of the standard language. This were indicated with an ℵ and considered effectively private. Examples include "≮" and "≯" for templates, the outtype/intype for crude duck typing, and the straightout and straightin operators for "straightening" nested arrays and structures.

Extract from the 1973 report:

§10.3.2.2. Transput modes
a) modesimplout = union (≮ℒ int≯, ≮ℒ real≯, ≮ℒ compl≯, bool, ≮ℒ bits≯, 
           char, [ ] char);
b) modeouttype = ¢ an actual - declarer specifying a mode united 
   from a sufficient set of modes none of which is 'void' or contains 'flexible', 
   'reference to', 'procedure' or 'union of' ¢;
c) modesimplin = union (≮ref ℒ int≯, ≮ref ℒ real≯, ≮refcompl≯, ref bool, 
           ≮ref ℒ bits≯, ref char, ref [ ] char, ref string);
d) modeintype = ¢ ... ¢;

§10.3.2.3. Straightening
a) opstraightout = (outtype x) [ ] simplout: ¢ the result of "straightening" 'x' ¢;
b) opstraightin = (intype x) [ ] simplin: ¢ the result of straightening 'x' ¢;

Comparisons with other languages

Variants

Except where noted (with a superscript), the language described above is that of the "Revised Report(RR)".

The language of the unrevised report

The original language(FR) 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 would be intended to make evaluations lazy. The most useful application could have been the short-circuited evaluation of boolean operators. In

op andf = (bool a,proc bool b)bool:(a | b | false);
op orf = (bool a,proc bool b)bool:(a | true | b);

b is only evaluated if a is true. As defined in ALGOL 68, it did not work as expected, for example in the code:

if false andf co proc bool: co ( print ("Should not be executed"); true)
then ...

against the programmers naïve expectations the print would be executed as it is only the value of the elaborated enclosed-clause after andf that was procedured. Textual insertion of the commented-out proc bool: makes it work.

Some implementations emulate the expected behaviour for this special case by extension of the language.

Before revision, the programmer could decide to have the arguments of a procedure evaluated serially instead of collaterally by using semicolons instead of commas (gommas).

For example in:

proc test = (real a; real b) :...
...
test (x plus 1, x);

The first argument to test is guaranteed to be evaluated before the second, but in the usual:

proc test = (real a, b) :...
...
test (x plus 1, x);

then the compiler could evaluate the arguments in whatever order it felt like.

Extension proposals from IFIP WG 2.1

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

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

True ALGOL 68s specification and implementation timeline

Name Year Purpose State Description Target CPU Licencing Implementation Language
Generalized ALGOL 1962 Scientific NL ALGOL for generalised grammars
ALGOL YY 1966 Draft proposal Intl First version of Algol 68 Specification ACM
ALGOL 68DR 1968 Draft proposal Intl IFIP WG 2.1 Draft Report Specification - March ACM
ALGOL 68FR 1968 Standard Intl IFIP WG 2.1 Final Report Specification - August ACM
ALGOL 68RR 1970 Military UK ICL 1900 ALGOL 60
EPOS ALGOLE 1971 Scientific
ALGOL 68RSRS 1972 Military UK Portable compiler system ICL 2900/Series 39, Multics, VMS & C generator (1993) Crown Copyright ALGOL 68RS
Algol 68 with areas 1972 Experimental & other UK Addition of areas to Algol 68
Mini ALGOL 68 1973 Research NL "An interpreter for simple Algol 68 Programs" Portable interpreter Mathematisch Centrum ALGOL 60
OREGANO 1973 Research US "The importance of implementation models." UCLA
ALGOL 68CC 1975 Scientific UK Cambridge Algol 68 ICL, IBM 360, PDP 10 & Unix, Telefunken, Tesla & Z80(1980)[7] Cambridge ALGOL 68C
ALGOL 68 RevisedRR 1975 Standard Intl IFIP WG 2.1 Revised Report Specification ACM
Algol HH 1975 Experimental & other UK Proposed extensions to the mode system of Algol 68 Specification ALGOL W
Odra Algol 68 1976 practical uses USSR/Poland Odra 1204/IL Soviet ALGOL 60
Oklahoma ALGOL 68 1976 programming instruction USA Oklahoma State University implementation [8] IBM 1130 and System/370/158 Unknown ANSI Fortran 66
Berlin ALGOL 68 1977 Research DE "The Berlin ALGOL 68 implementation" & [9] An Abstract ALGOL 68 Machine - machine independent Compiler Technical University of Berlin CDL 2
FLACCF 1977 Multi-purpose CA Revised Report complete implementation with debug features System/370 lease, Chion Corporation Assembler
ALGOL 68-RTRT 1979 Scientific UK Parallel ALGOL 68-R
RS Algolrs 1979 Scientific UK
ALGOL 68+ 1980 Scientific NL Proposed superlanguage of ALGOL 68 [10]
M-220 ALGOL 68 USSR M-220 Soviet EPSILON
ALGOL 68 LGUL 1980 Telecommunications USSR Full Language + Modules IBM, DEC, CAMCOH, PS 1001 & PC Soviet
Interactive ALGOL 68I 1983 UK Incremental compilation PC Noncommercial shareware
ALGOL 68SS 1985 Scientific Intl Sun version of ALGOL 68 Sun-3, Sun SPARC (under SunOS 4.1 & Solaris 2), Atari ST (under GEMDOS), Acorn Archimedes (under RISC OS), VAX-11 under Ultrix-32
Algol68toC [11](ctrans) 1985 Electronics UK ctrans from ELLA ALGOL 68RS Portable C generator  Open Sourced & Public Domained 1995 ALGOL 68RS
MK2 Interactive ALGOL 68 1992 UK Incremental compilation PC Noncommercial shareware [12]
ALGOL 68GG 2001 Full Language NL Includes standard collateral clause Portable interpreter GPL C
ALGOL 68G Version 2.0.0 2010 Full Language NL Portable interpreter; optional compilation of selected units GPL C

The S3 programming language that was used to write the ICL VME operating system and much other system software on the ICL 2900 Series was a direct derivative of Algol 68. However, it omitted many of the more complex features, and replaced the basic modes with a set of data types that mapped directly to the 2900 Series hardware architecture.

Implementation specific extensions

ALGOL 68R(R) 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(RS) 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/Series 39, 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(S) 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(C) was a portable compiler that implemented a subset of ALGOL 68, restricting operator definitions and omitting garbage collection, flexible rows and formatted transput.

ALGOL 68G(G) by M. van der Veer is an ALGOL 68 implementation for today's computers and operating systems. A minor restriction is that (formatted) transput does not fully conform to the Revised Report.

"Despite good intentions, a programmer may violate portability by inadvertently employing a local extension. To guard against this, each implementation should provide a PORTCHECK pragmat option. While this option is in force, the compiler prints a message for each construct that it recognizes as violating some portability constraint."[13]

Quotes

See also

References

  1. ^ "A History of C++: 1979−1991" (PDF). March 1993. http://www.research.att.com/~bs/hopl2.pdf. Retrieved May 6, 2008. 
  2. ^ "Interview with Guido van Rossum". July 1998. http://www.amk.ca/python/writing/gvr-interview. Retrieved April 29, 2007. 
  3. ^ http://vestein.arb-phys.uni-dortmund.de/~wb/RR/rr0.html#011
  4. ^ http://vestein.arb-phys.uni-dortmund.de/~wb/RR/rr0.html#012
  5. ^ http://vestein.arb-phys.uni-dortmund.de/~wb/RR/rr0.html#013
  6. ^ http://vestein.arb-phys.uni-dortmund.de/~wb/RR/rr0.html#014
  7. ^ "A Shorter History of Algol68". Archived from the original on August 10, 2006. http://web.archive.org/web/20060810103448/http://npt.cc.rsu.ru/user/wanderer/ODP/ALGOL68.txt. Retrieved September 15, 2006. 
  8. ^ http://vestein.arb-phys.uni-dortmund.de/~wb/RR/rr0.html#03B
  9. ^ Lindsey, Charles H. (1996). T.J. Bergin & R.G. Gibson. ed. A History of ALGOL 68. History of Programming Languages-II. also in ACM SIGPLAN Notices 28(3), March 1993. (Includes a comprehensive bibliography of the meetings and discussions before, during and after the development of ALGOL 68.). ACM Press. ISBN 0-201-89502-1. 
  10. ^ "PAME". Archived from the original on 2009-10-24. http://www.webcitation.org/5klVUTHVc. 
  11. ^ "Draft Report on the Algorithmic Language ALGOL 68". March 1968. Archived from the original on September 30, 2007. http://web.archive.org/web/20070930181523/http://archive.computerhistory.org/resources/text/algol/algol_bulletin/AS26/INDEX.HTM. Retrieved June 22, 2007. 
  12. ^ "Penultimate Draft Report on the Algorithmic Language ALGOL 68 - Chapters 1-9" (PDF). October 1968. http://repos.project.cwi.nl:8888/cwi_repository/docs/I/09/9180A.pdf. Retrieved June 22, 2007. 
  13. ^ "Penultimate Draft Report on the Algorithmic Language ALGOL 68 - Chapters 10-12" (PDF). October 1968. http://repos.project.cwi.nl:8888/cwi_repository/docs/I/09/9179A.pdf. Retrieved June 22, 2007. 
  14. ^ "Report on the Algorithmic Language ALGOL 68" (PDF). December 1968. http://www.fh-jena.de/~kleine/history/languages/Algol68-Report.pdf. Retrieved December 30, 2007. 
  15. ^ Lindsey, Charles H. (1996). T.J. Bergin & R.G. Gibson. ed. A History of ALGOL 68. History of Programming Languages-II. also in ACM SIGPLAN Notices 28(3), March 1993. (Includes a comprehensive bibliography of the meetings and discussions before, during and after the development of ALGOL 68.). ACM Press. p. 7. ISBN 0-201-89502-1. 
  16. ^ "Revised Report on the Algorithmic Language Algol 68". September 1973. Archived from the original on September 27, 2007. http://web.archive.org/web/20070927191700/http://burks.brighton.ac.uk/burks/language/other/a68rr/rrtoc.htm. Retrieved April 30, 2007. 
  17. ^ "GOST 27974-88 Programming language ALGOL 68 - Язык программирования АЛГОЛ 68" (in Russian) (PDF). GOST. 1988. http://vak.ru/lib/exe/fetch.php/book/gost/pdf/gost-27974-88.pdf. Retrieved November 15, 2008. 
  18. ^ "GOST 27975-88 Programming language ALGOL 68 extended - Язык программирования АЛГОЛ 68 расширенный" (in Russian) (PDF). GOST. 1988. http://vak.ru/lib/exe/fetch.php/book/gost/pdf/gost-27975-88.pdf. Retrieved November 15, 2008. 
  19. ^ "IS NOT OPERATOR" - US application 20,040,230,959 
  20. ^ David Holdsworth (Winter 2009/10). "KDF9 Time Sharing: Eldon 2 is not EGDON!". Computer RESURRECTION - Number 49. Computer Conservation Society. http://www.cs.man.ac.uk/CCS/res/res49.htm#e. Retrieved October 3, 2010. 
  21. ^ Lindsey, C.H.; Boom, H.J. (Dec. 1978). "A Modules and Separate Compilation facility for ALGOL 68". ALGOL Bulletin (43). doi:10.1145/1061719.1061724. http://0-portal.acm.org.millennium.lib.cyut.edu.tw/citation.cfm?id=1061724. Retrieved 2011-05-05. 
  22. ^ Dennis Ritchie (April 1993). "The Development of the C Language" (PDF). http://cm.bell-labs.com/cm/cs/who/dmr/chist.pdf. Retrieved April 26, 2007. 
  23. ^ Dennis Ritchie (June 1988). "usenet:comp.lang.misc "C and Algol 68"". http://groups.google.co.uk/group/comp.lang.misc/browse_thread/thread/1e6d4bb30659b78d/f57b6f5c81502cf5. Retrieved September 15, 2006. 
  24. ^ C.H.A. Koster (1993). "The Making of Algol 68" (PDF). http://www.cs.ru.nl/~kees/home/papers/psi96.pdf. Retrieved April 28, 2007. 
  25. ^ E.W. Dijkstra. "To the EDITOR ALGOL 68 Mathematische Centrum". http://www.cs.utexas.edu/users/EWD/transcriptions/EWD02xx/EWD230.html. Retrieved April 28, 2007. 
  26. ^ Guido van Rossum (June 2005). "Python-Dev Wishlist: dowhile". http://mail.python.org/pipermail/python-dev/2005-June/054225.html. Retrieved April 28, 2007. 
  27. ^ "ALGOL Bulletin (referred to in AB30.1.1.1)". March 1970. Archived from the original on September 30, 2007. http://web.archive.org/web/20070930230048/http://archive.computerhistory.org/resources/text/algol/algol_bulletin/A31/P111.HTM. Retrieved March 1, 2007. 
  • Brailsford, D.F. and Walker, A.N., Introductory ALGOL 68 Programming, Ellis Horwood/Wiley, 1979
  • Lindsey, C.H. and van der Meulen, S.G., Informal Introduction to ALGOL 68, North-Holland, 1971
  • 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
  • Woodward, P.M. and Bond, S.G., ALGOL 68-R Userssic Guide, London, Her Majesty's Stationery Office, 1972

External links