User:HughesJohn/Sandbox/ALGOL 68RS

ALGOL 68RS is the second ALGOL 68 compiler written by I.F. Currie and J.D. Morrison at the Royal Signals and Radar Establishment. Unlike the earlier ALGOL 68R it was designed as a portable compiler and implemented the language of the revised Report.

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

Subsequently portions of this compiler were put into the public domain - as an ALGOL 68 to C translator - as part of the public release of ELLA.

History

Although the ALGOL 68R 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 machine independence. The compiler itself dealt with the parsing of ALGOL 68, producing a high level intermediate language known as stream language that would then be compiled to machine code by a translator. The compiler only needed to know the sizes of the various object machine types and the character set available.

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

A team of two programmers at Oxford University Computing Services wrote a code generator for the ICL 2900 series. Martyn Thomas of SWURCC arranged that this system be sponsored by 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 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 and ALGOL 68 to C translator, ctrans, based on the ALGOL 68RS compiler.

Restrictions in the language compiled

Like the earlier ALGOL 68R 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 up-coming symbol was a mode rather than an operator:

mode b,
     a = struct (ref b b),
     b = [1:10] ref a;

Parallel processing

Like ALGOL 68R the par clause and the sema mode with it's associated up, down and level operators 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 for example takes an array of items to print of any mode and, by some magic known as straightening converts them into simple values that can be printed. For example:

struct (int a, real b) c := ...;

print(c);   { magicaly 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) void: ...;

Efficient array handling

The ALGOL 68 array modes are very powerful, including multiple dimensions, defined upper and lower bounds, trimming (the ability to make a new array by taking a contiguous sub-set of an array), slicing (the ability to make a new array by removing one dimension from an array) and rowing (the ability to make a new array by adding a dimension to an existing 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

ALGOL68 already included fixed length structures for efficient handling of 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 tothe 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 compilation

ALGOL 68RS provided a mechanism for building libraries similar to the separate compilation facilities of ALGOL 68R and a mechanism for building 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 his 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

In order 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 system 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.

It is currently available from SourceForge: http://sourceforge.net/projects/algol68/files/algol68toc/