ALGOL 68RS

ALGOL 68RS

Original author(s)	I. F. Currie, J. D. Morrison
Developer(s)	Royal Signals and Radar Establishment
Initial release	August 1977 (1977-08)
Stable release	algol68toc 1.14 / 25 August 2012 (2012-08-25)
Written in	ALGOL 68
Operating system	VMS
Platform	ICL 2900 Series, Multics, VAX
Available in	English
Type	Compiler, translator
License	Freeware, public domain (parts)
Website	algol68.sourceforge.net

ALGOL 68RS is the second ALGOL 68 compiler written by I. F. Currie and J. D. Morrison, at the Royal Signals and Radar Establishment (RSRE). Unlike the earlier ALGOL 68-R, it was designed to be portable, and implemented the language of the Revised Report.

Versions of ALGOL 68RS were written for the ICL 2900 Series, Multics, and VAX running VMS.

Subsequently, parts of this compiler were released into the public domain, as a translator from ALGOL 68 to C, as part of the public release of the hardware description language ELLA, also by the RSRE.

History

Although the ALGOL 68-R compiler, written by I.F. Currie, J.D. Morrison, and S.G. Bond, was a great success, it suffered from two major problems: it had been written for the nearly obsolete ICL 1900 computer, and it implemented an out-of-date version of the language as it was released before the Revised Report on ALGOL 68 was available.

RSRE needed a newer compiler for various internal projects, so the team of Currie and Morrison wrote a new compiler designed for cross-platform software portability between machines. The compiler dealt with the parsing of ALGOL 68, producing a high level intermediate language known as stream language that is then compiled to machine code by a translator. The compiler needed to know only the sizes of the various object machine data types and the character encoding (set) available.

The compiler was written in ALGOL 68, bootstrapped initially using the ALGOL 68-R compiler.

A team of two programmers at Oxford University Computing Services wrote a code generator for the ICL 2900 series. Martyn Thomas of South West Universities Regional Computer Centre (SWURCC) arranged that this system be sponsored by International Computers Limited (ICL) and sold as an official ICL product.

Later, the Avon Universities Joint Computer Centre, a large user of Multics requested the SWURCC team to produce a Multics version of ALGOL 68RS. A version for the Digital Equipment Corporation (DEC) VAX computer was also written.

Eventually the team at SWURCC formed a company, Praxis, initially supporting the Multics version of ALGOL 68RS.

RSRE also used the ALGOL 68RS compiler for internal projects, including the Flex machine and the ELLA hardware design language. When it was decided to make ELLA freely available, Praxis was commissioned to write an ALGOL 68 to C translator named ctrans, based on the ALGOL 68RS compiler.

Restrictions in the language compiled

Like the earlier ALGOL 68-R compiler, ALGOL 68RS was a one-pass compiler, which required some restrictions on the language compiled.

Declaration before use

The ALGOL 68 program:

PROC even = (INT number) BOOL: ( number = 0 | TRUE | odd (ABS (number - 1)));
PROC odd = (INT number) BOOL: ( number = 0 | FALSE | even (ABS (number - 1)));

would have to be re-written as:

PROC (INT) BOOL odd;
PROC even = (INT number) BOOL : ( number = 0 | TRUE | odd (ABS (number - 1)));
odd := (INT number) BOOL : ( number = 0 | FALSE | even (ABS (number - 1)));

To allow recursive declarations of modes (types) a special stub mode declaration was used to inform the compiler that an upcoming symbol was a mode rather than an operator:

MODE B,
     A = STRUCT (REF B b),
     B = [1:10] REF A;

Parallel processing

Like ALGOL 68-R, the operators PAR clause and the SEMA mode with its associated UP, DOWN, and LEVEL, were omitted.

Extensions to ALGOL 68

Straightening

One major misfeature of ALGOL 68 is that it is impossible to write the standard transput (input/output) procedures in pure ALGOL 68. The print procedure takes, for example, an array of items to print of any mode and, by a process named straightening, converts them into simple values that can be printed. For example:

STRUCT (INT a, REAL b) c := ...;

print(c);   { magically transformed to print ((a OF c, b OF c)); }

The writers of ALGOL 68RS decided to make straightening available as part of the language. A STRAIGHT mode resembles an array but has the special feature that items can be coerced to a STRAIGHT mode if their components can be coerced to the mode. For example:

STRUCT (INT a, REAL b) c;

STRAIGHT UNION (INT, REAL) z = c;

Both the fields of C can be coerced to UNION (INT, REAL) so the field "a OF c" can be accessed as z[1] and "b OF c" is z[2].

The standard print procedure can now be declared as:

MODE PRINTMODE = UNION (INT, REAL, ... STRAIGHT PRINTMODE);
PROC print = ([] PRINTMODE arguments ) VOID: ...;

Efficient array handling

The ALGOL 68 array modes are very powerful, including multiple dimensions, defined upper and lower bounds, trimming (making a new array by taking a contiguous subset of an array), slicing (making a new array by removing one dimension from an array), and rowing (making a new array by adding a dimension to an extant array.

For example:

[5:23, -7:7] INT a;               { a two dimensional array }
REF [,] INT b = a [ 6:21, 0:3 ]   { a slice of a }
REF [] INT c = a [5]              { just one row of a }

While the compiler made all efforts to generate optimal code for all cases, it was felt that adding some simpler facilities would allow better code in some cases. To this end ALGOL 68RS included indexable structures (i-structs), vectors, and the FORALL statement.

Indexable structures

ALGOL 68 already included fixed length structures to efficiently handle characters and bit-data on word-based machines, the BYTES and BITS modes. A BYTES variable held one machine word of characters, a BITS variable held the bits of one machine word.

ALGOL 68RS generalised these ideas. A STRUCT 4 CHAR variable held exactly 4 chars. The size was part of the type. On most ALGOL 68RS systems, the mode BYTES was equivalent to STRUCT 4 CHAR.

MODE BYTES = STRUCT 4 CHAR;
OP ELEM = (INT index, BYTES val) CHAR: val[index];
...
BYTES b = "abcd";
...
print (2 ELEM b);

The ALGOL 68RS compiler would compile any string constant to an appropriate STRUCT n CHAR.

In contexts where a VECTOR or array was wanted, an i-struct could be widened to the appropriate VECTOR or array type.

Vectors

A VECTOR is a simplified array, with only one dimension and a lower bound fixed at 1.

VECTOR [4] INT a;     { similar to [1:4] INT a; }

In any context where an array was required a VECTOR could be converted to an array.

FORALL statement

The FORALL statement allows efficient stepping through the elements of an array.

[12] INT a := ...;

FORALL xa IN a
DO xa := xa * 2
OD

xa will be a reference to each element of a in turn. FORALL can step through multiple arrays in parallel, and be controlled by a WHILE clause:

[12] INT a, b;
...
FORALL xa IN a,
       xb IN b
WHILE xa > xb
DO
    f(xa, xb)
OD

Separate compiling

ALGOL 68RS provided a mechanism to build libraries similar to the separate compiling facilities of ALGOL 68-R and a mechanism to build programs in a top-down manner similar to those of ALGOL 68C.

Declaration modules

Libraries in ALGOL 68RS are written using declaration modules which consist of a sequence of MODE, variable, operator and procedure declarations followed by a keep list which defines which declarations are visible to other segments.

The library user then adds a USE header that tells the compiler to make the symbols of one or more declaration libraries available to the program.

For example, a graphics library might be written as:

DECS graphlib
USE some other library

MODE GRAPHDATA = STRUCT ( ... );
MODE GRAPH = REF GRAPHDATA;
PROC new graph = ( ... ) GRAPH : ...;
PROC draw graph = (GRAPH g) VOID : ...;
   ...

KEEP GRAPH, new graph, draw graph
FINISH

And a user program to use this library would look like:

PROGRAM myprog
USE graphlib
BEGIN
    GRAPH g = new graph (...);
    ...
    draw graph (g);
    ...
END
FINISH

Nested modules

To support a top-down programming style, ALGOL 68RS provided the HERE and CONTEXT facilities.

A program could be written with parts to be filled in later marked by a HERE tag followed by a keeplist of declarations to be made available.

PROGRAM (pass1, pass2) compiler
BEGIN
   STRING source := ...;
   TREE parsetree;
...
   HERE pass1 (source, parsetree);
...
   INSTRUCTIONS insts;
   HERE pass2 (parsetree, insts);
...
END
FINISH

The code to be executed in the context of the HERE tags would be written as:

PROGRAM pass1 implementation
CONTEXT pass1 IN compiler
BEGIN
  ...   { code using "source" and "parsetree" }
END
FINISH

HERE is similar to the ALGOL 68C ENVIRON and CONTEXT is equivalent to the ALGOL 68C USING.

Code and alien access

ALGOL 68RS was intended to be usable for low level systems programming. To allow this, facilities were included for access to machine code and non-ALGOL 68RS objects.

Code was inserted with the CODE construct:

SOMEMODE CODE (item1, item2, ...) "...code..."

Where the items are ALGOL 68RS values to be made available to the code insertion and SOMEMODE is the mode returned. The mode can be omitted if the code returns no value.

Access to non-ALGOL68 objects was available with the ALIEN insertion:

SOMEMODE name = ALIEN "external-name"

Any simple ALGOL 68RS object could be cast into a VECTOR of characters using the SPELL operator:

STRUCT (INT a, REAL b) c = ...;

print (("internal repr = ", SPELL c, newline));

A simple object is one that contains no arrays or VECTORs.

Availability

The ALGOL 68 to C translator written by Praxis for the ELLA system contains most of the ALGOL 68RS compiler. The notable exception is the code for handling FORMATs.

As of September 2020, ALGOL 68RS is available from SourceForge.