ALGOL 68R
Encyclopedia
ALGOL 68-R was the first implementation of the Algorithmic language ALGOL 68
.
In December 1968 the report on the Algorithmic language ALGOL 68 was published. On 20–24 July 1970 a working conference was arranged by the IFIP to discuss the problems of implementation of the language, a small team from the Royal Radar Establishment
attended to present their compiler, written by I.F. Currie, Susan G. Bond and J.D. Morrison. In the face of estimates of up to 100 man-years to implement the language, using up to 7 pass compilers
they described how they had already implemented a one-pass compiler
which was in production use in engineering and scientific applications.
The first version of the compiler occupied 34K words. It was later rewritten in ALGOL 68-R, taking around 36K words to compile most programs.
ALGOL 68-R was implemented under the GEORGE 3 operating system on an ICL 1907F
. The compiler was distributed without charge by ICL
on behalf of the RRE
.
Many of these restrictions were adopted by the revised report on ALGOL 68.
The standard 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;
mode a = struct (ref b b);
mode b = [1:10] ref a;
Another case where proceduring was used was the declaration of procedures, in the declaration:
proc x plus 1 = int : x + 1;
the right hand side was a cast
of x + 1 to integer, which was then converted to procedure returning integer.
The ALGOL 68-R team found this too difficult to handle and made two changes to the language. The proceduring coercion was simply dropped and the form mode : expression was redefined as a procedure denotation, casts being indicated by an explicit val symbol:
real : x co a cast to real in ALGOL 68 co
real val x co a cast to real in ALGOL 68-R co
Code that had a valid use for call by name (For example Jensen's device
) could simply pass a procedure denotation:
proc sum = (int lo, hi, proc (int) real term) real :
begin
real temp := 0;
for i from lo to hi do
temp +:= term (i);
temp
end;
print (sum (1, 100, (int i) real: 1/i))
In the version of the language defined in the revised report these changes were accepted, although the form of the cast was slightly changed to mode (expression).
real (x) co a cast to real in revised ALGOL 68 co
: x := 3.14; co cast (x := 3.14) to void co
proc endit = goto end; co a procedure returning void co
The ALGOL 68-R team decided to use an explicit void symbol in order to simplify parsing (and increase readability):
void val x := 3.14; co cast (x := 3.14) to void co
proc endit = void : goto end; co a procedure returning void co
This modification to the language was adopted by the ALGOL 68 revised report.
[ 15 ] int a; co an actual declarer, bounds 1:15 co
ref [ 3 : ] int b = a; co This is an error co
proc x = (ref [ 1 : either] int a) : ...
The ALGOL 68-R team redefined formal declarers to be the same as virtual declarers which include no bound information. They found that this reduced the ambiguities in parsing the language and felt that it was not a feature that would be used in real programs.
If a procedure needed certain bounds for its arguments it could check them itself with the upb (upper bound) and lwb (lower bound) operators.
In ALGOL 68-R the example above could be recoded like this: (the bounds of a in the procedure would depend on the caller).
[ 15 ] int a; co an actual declarer, bounds 1:15 co
ref [] int b = a [ at 3]; co use slice so b has bounds 3:17 co
proc x = (ref [] int a) void: ... co bounds given by caller co
In the revised report on ALGOL 68 formal bounds were also removed, but the flex indication was moved in position so it could be include in formal declarers:
[ 1: flex ] int a; co original ALGOL 68, or ALGOL 68-R co
flex [ 1: ] int a; co revised ALGOL 68, co
proc x = (ref [ 1: flex ] int a) : ... co Original ALGOL 68 co
proc x = (ref [ ] int a) void: ... co ALGOL 68-R co
proc x = (ref flex [ ] int a) void: ... co Revised ALGOL 68 co
par begin
producer,
consumer
end
the procedures producer and consumer will be run in parallel. A semaphore
type (sema) with the traditional P (down) and V (up) operators is provided for synchronisation between the parts of the parallel clause,
This feature was not implemented in ALGOL 68-R.
An extension known as ALGOL 68-RT was written which used the subprogramming feature of the ICL 1900
to provide multithreading facilities to ALGOL 68-R programs with semantics similar to modern thread
libraries. No changes were made to the compiler, only the run-time library and the linker.
proc stop = : ...;
...
begin
if x > 3 then stop fi; co a jump, not a call co
...
stop:
skip
end
As ALGOL 68-R was a one pass compiler this was too difficult, so the goto symbol was made obligatory.
The same restriction was made in the official sublanguage, ALGOL 68S
.
mode ibool = union (int, bool); co an ibool is an int or a bool co
ibool a = true; co the bool value true is united to an ibool co
In standard ALGOL 68 uniting was possible in firm or strong contexts, so for example could be applied to the operands of formulas:
op istrue = (ibool a) bool: ...;
if istrue 1 co legal because 1 (int) can be united to ibool co
then ...
The ALGOL 68-R implementers found this gave too many ambiguous situations so restricted the uniting coercion to strong contexts.
The effects of this restriction were rarely important and, if necessary, could be worked around by using a cast to provide a strong context at the required point in the program.
This value was chosen because:
The same value was used to represent nil.
In source programs some stropping technique had to be used. In many ALGOL like languages before ALGOL 68-R this was accomplished by enclosing basic symbols in single quote characters ('begin' for example). In ALGOL 68-R basic symbols could be distinguished by writing the in upper case, lower case being used for identifiers.
As ALGOL 68-R was implemented on a machine with 6 bit bytes (and hence a 64 character set) this was quite complicated and, at least initially, programs had to be composed on paper tape
using a Flexowriter
.
Partly based on the experience of ALGOL 68-R the revised report on ALGOL 68 specified hardware representations for the language, including UPPER stropping.
A segment to be made available to other segments would end with a list of declarations to be made available:
graphlib co the segment name co
begin
mode graphdata = struct ( ... );
mode graph = ref graphdata;
proc new graph = ( ... ) graph : ...;
proc draw graph = (graph g) void : ...;
...
end
keep graph, new graph, draw graph
finish
And then the graph functions could be used by another segment:
myprog with graphlib from graphalbum
begin
graph g = new graph (...);
...
draw graph (g);
...
end
finish
Since ALGOL 68-R didn't compile to standard ICL semicompiled (link-ready) format it was necessary to extend the language to provide features in ALGOL 68-R to write code that would normally be written in assembler. Machine instructions could be written inside code ... edoc sections and the address manipulation operators inc, dec, dif, as were added.
An example, using a GEORGE
peri operation to issue a command:
[1 : 120] CHAR buff;
INT unitnumber;
STRUCT (BITS typemode, reply, INT count, REF CHAR address)
control area := (8r47400014,0,120,buff[1]);
...;
CODE 0,6/unitnumber; 157,6/typemode OF control area EDOC
emulator, is available at http://sw.ccs.bcs.org/CCs/g3/index.html
ALGOL 68
ALGOL 68 isan imperative computerprogramming language that was conceived as a successor to theALGOL 60 programming language, designed with the goal of a...
.
In December 1968 the report on the Algorithmic language ALGOL 68 was published. On 20–24 July 1970 a working conference was arranged by the IFIP to discuss the problems of implementation of the language, a small team from the Royal Radar Establishment
Royal Radar Establishment
The name Royal Radar Establishment was given to the existing Radar Research Establishment following a visit by Queen Elizabeth II in 1957. Both names were abbreviated to RRE. The establishment had been formed, under its first name, in 1953 by merging the Telecommunications Research Establishment ...
attended to present their compiler, written by I.F. Currie, Susan G. Bond and J.D. Morrison. In the face of estimates of up to 100 man-years to implement the language, using up to 7 pass compilers
Multi-pass compiler
A multi-pass compiler is a type of compiler that processes the source code or abstract syntax tree of a program several times. This is in contrast to a one-pass compiler, which traverses the program only once. Each pass takes the result of the previous pass as the input, and creates an intermediate...
they described how they had already implemented a one-pass compiler
One-pass compiler
In computer programming, a one-pass compiler is a compiler that passes through the source code of each compilation unit only once. In other words, a one-pass compiler does not "look back" at code it previously processed. Another term sometimes used is narrow compiler, which emphasizes the limited...
which was in production use in engineering and scientific applications.
The compiler
The ALGOL 68-R compiler was initially written in a local dialect of ALGOL 60 with extensions for address manipulation and list processing. The parser was written using J.M. Foster's Syntax Improving Device (SID) parser generator.The first version of the compiler occupied 34K words. It was later rewritten in ALGOL 68-R, taking around 36K words to compile most programs.
ALGOL 68-R was implemented under the GEORGE 3 operating system on an ICL 1907F
ICT 1900 series
ICT 1900 was the name given to a series of mainframe computers released by International Computers and Tabulators and later International Computers Limited during the 1960s and '70s...
. The compiler was distributed without charge by ICL
ICL
-Companies and organizations:* ICL, the ICAO airline code for CAL Cargo Air Lines* International Computers Limited, a British computer hardware and services company, now known as Fujitsu Services...
on behalf of the RRE
Royal Radar Establishment
The name Royal Radar Establishment was given to the existing Radar Research Establishment following a visit by Queen Elizabeth II in 1957. Both names were abbreviated to RRE. The establishment had been formed, under its first name, in 1953 by merging the Telecommunications Research Establishment ...
.
Restrictions in the language compiled
In order to allow one pass compilation ALGOL 68-R implemented a sub-set of the language defined in the original report:- Identifiers, modes and operators must be specified before use.
- No automatic proceduring.
- Explicit void mode.
- No formal declarers.
- No parallel processing.
- goto may not be omitted.
- Uniting is only valid in strong positions.
Many of these restrictions were adopted by the revised report on ALGOL 68.
Specification before use
To allow compiling in one pass ALGOL 68-R insisted that all identifiers were specified (declared) before use.The standard 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;
mode a = struct (ref b b);
mode b = [1:10] ref a;
No proceduring
In the standard language the proceduring coercion could, in a strong context, convert an expression of some type into a procedure returning that type. This could be used to implement call by name.Another case where proceduring was used was the declaration of procedures, in the declaration:
proc x plus 1 = int : x + 1;
the right hand side was a cast
Type conversion
In computer science, type conversion, typecasting, and coercion are different ways of, implicitly or explicitly, changing an entity of one data type into another. This is done to take advantage of certain features of type hierarchies or type representations...
of x + 1 to integer, which was then converted to procedure returning integer.
The ALGOL 68-R team found this too difficult to handle and made two changes to the language. The proceduring coercion was simply dropped and the form mode : expression was redefined as a procedure denotation, casts being indicated by an explicit val symbol:
real : x co a cast to real in ALGOL 68 co
real val x co a cast to real in ALGOL 68-R co
Code that had a valid use for call by name (For example Jensen's device
Jensen's Device
Jensen's Device is a computer programming technique devised by Danish computer scientist Jørn Jensen, who worked with Peter Naur at Regnecentralen, particularly on the GIER Algol compiler, one of the earliest correct implementations of ALGOL 60....
) could simply pass a procedure denotation:
proc sum = (int lo, hi, proc (int) real term) real :
begin
real temp := 0;
for i from lo to hi do
temp +:= term (i);
temp
end;
print (sum (1, 100, (int i) real: 1/i))
In the version of the language defined in the revised report these changes were accepted, although the form of the cast was slightly changed to mode (expression).
real (x) co a cast to real in revised ALGOL 68 co
Explicit void mode
In the original language the void mode was represented by an empty mode:: x := 3.14; co cast (x := 3.14) to void co
proc endit = goto end; co a procedure returning void co
The ALGOL 68-R team decided to use an explicit void symbol in order to simplify parsing (and increase readability):
void val x := 3.14; co cast (x := 3.14) to void co
proc endit = void : goto end; co a procedure returning void co
This modification to the language was adopted by the ALGOL 68 revised report.
No formal declarers
Formal declarers are the modes on the left hand side of an identity declaration, or the modes specified in a procedure declaration. In the original language they could include array bounds and specified whether the matching actual declarer was fixed, flex or either:[ 15 ] int a; co an actual declarer, bounds 1:15 co
ref [ 3 : ] int b = a; co This is an error co
proc x = (ref [ 1 : either] int a) : ...
The ALGOL 68-R team redefined formal declarers to be the same as virtual declarers which include no bound information. They found that this reduced the ambiguities in parsing the language and felt that it was not a feature that would be used in real programs.
If a procedure needed certain bounds for its arguments it could check them itself with the upb (upper bound) and lwb (lower bound) operators.
In ALGOL 68-R the example above could be recoded like this: (the bounds of a in the procedure would depend on the caller).
[ 15 ] int a; co an actual declarer, bounds 1:15 co
ref [] int b = a [ at 3]; co use slice so b has bounds 3:17 co
proc x = (ref [] int a) void: ... co bounds given by caller co
In the revised report on ALGOL 68 formal bounds were also removed, but the flex indication was moved in position so it could be include in formal declarers:
[ 1: flex ] int a; co original ALGOL 68, or ALGOL 68-R co
flex [ 1: ] int a; co revised ALGOL 68, co
proc x = (ref [ 1: flex ] int a) : ... co Original ALGOL 68 co
proc x = (ref [ ] int a) void: ... co ALGOL 68-R co
proc x = (ref flex [ ] int a) void: ... co Revised ALGOL 68 co
No parallel processing
In ALGOL 68 code can be run in parallel by writing par followed by a collateral clause, for example in:par begin
producer,
consumer
end
the procedures producer and consumer will be run in parallel. A semaphore
Semaphore (programming)
In computer science, a semaphore is a variable or abstract data type that provides a simple but useful abstraction for controlling access by multiple processes to a common resource in a parallel programming environment....
type (sema) with the traditional P (down) and V (up) operators is provided for synchronisation between the parts of the parallel clause,
This feature was not implemented in ALGOL 68-R.
An extension known as ALGOL 68-RT was written which used the subprogramming feature of the ICL 1900
ICT 1900 series
ICT 1900 was the name given to a series of mainframe computers released by International Computers and Tabulators and later International Computers Limited during the 1960s and '70s...
to provide multithreading facilities to ALGOL 68-R programs with semantics similar to modern thread
Thread (computer science)
In computer science, a thread of execution is the smallest unit of processing that can be scheduled by an operating system. The implementation of threads and processes differs from one operating system to another, but in most cases, a thread is contained inside a process...
libraries. No changes were made to the compiler, only the run-time library and the linker.
goto may not be omitted
In ALGOL 68 the goto symbol could be omitted from a jump:proc stop = : ...;
...
begin
if x > 3 then stop fi; co a jump, not a call co
...
stop:
skip
end
As ALGOL 68-R was a one pass compiler this was too difficult, so the goto symbol was made obligatory.
The same restriction was made in the official sublanguage, ALGOL 68S
ALGOL 68S
ALGOL 68S was designed as a subset of ALGOL 68 in order to permit single-pass compilation. It was mostly for numerical computation.-Implementations:...
.
Uniting is only allowed in strong positions
In ALGOL 68 uniting is the coercion that produces a union from a constituent mode, for example:mode ibool = union (int, bool); co an ibool is an int or a bool co
ibool a = true; co the bool value true is united to an ibool co
In standard ALGOL 68 uniting was possible in firm or strong contexts, so for example could be applied to the operands of formulas:
op istrue = (ibool a) bool: ...;
if istrue 1 co legal because 1 (int) can be united to ibool co
then ...
The ALGOL 68-R implementers found this gave too many ambiguous situations so restricted the uniting coercion to strong contexts.
The effects of this restriction were rarely important and, if necessary, could be worked around by using a cast to provide a strong context at the required point in the program.
F00L
The ALGOL 68-R compiler initialised unused memory to the value -6815700.This value was chosen because:
- As an integer it was a large negative value.
- As an address it was beyond the maximum address for any practical program on an ICL 1900ICT 1900 seriesICT 1900 was the name given to a series of mainframe computers released by International Computers and Tabulators and later International Computers Limited during the 1960s and '70s...
. - As an instruction it was illegal.
- As text it displayed as
F00L. - As a floating point number it had the overflow bit set.
The same value was used to represent nil.
Stropping
In ALGOL family languages it is necessary to distinguish between identifiers and basic symbols of the language. In printed texts this was usually accomplished by printing basic symbols in boldface or underlined (begin or begin for example).In source programs some stropping technique had to be used. In many ALGOL like languages before ALGOL 68-R this was accomplished by enclosing basic symbols in single quote characters ('begin' for example). In ALGOL 68-R basic symbols could be distinguished by writing the in upper case, lower case being used for identifiers.
As ALGOL 68-R was implemented on a machine with 6 bit bytes (and hence a 64 character set) this was quite complicated and, at least initially, programs had to be composed on paper tape
Punched tape
Punched tape or paper tape is an obsolete form of data storage, consisting of a long strip of paper in which holes are punched to store data...
using a Flexowriter
Friden Flexowriter
The Friden Flexowriter was a teleprinter, a heavy duty electric typewriter capable of being driven not only by a human typing, but also automatically by several methods including direct attachment to a computer and by use of paper tape....
.
Partly based on the experience of ALGOL 68-R the revised report on ALGOL 68 specified hardware representations for the language, including UPPER stropping.
Extensions to ALGOL 68
ALGOL 68-R included extensions for separate compilation and low-level access to the machine.Separate compilation
Since ALGOL 68 is a strongly typed language the simple library facilities used by other languages on the ICL 1900 system were insufficient. ALGOL 68-R was delivered with its own library format and utilities which allowed sharing of modes, functions, variables and operators between separately compiled segments of code which could be stored in albums.A segment to be made available to other segments would end with a list of declarations to be made available:
graphlib co the segment name co
begin
mode graphdata = struct ( ... );
mode graph = ref graphdata;
proc new graph = ( ... ) graph : ...;
proc draw graph = (graph g) void : ...;
...
end
keep graph, new graph, draw graph
finish
And then the graph functions could be used by another segment:
myprog with graphlib from graphalbum
begin
graph g = new graph (...);
...
draw graph (g);
...
end
finish
Low level system access
As a strongly typed high level language ALGOL 68 prevented the user from directly accessing the low level hardware, there are no operators for address arithmetic for example.Since ALGOL 68-R didn't compile to standard ICL semicompiled (link-ready) format it was necessary to extend the language to provide features in ALGOL 68-R to write code that would normally be written in assembler. Machine instructions could be written inside code ... edoc sections and the address manipulation operators inc, dec, dif, as were added.
An example, using a GEORGE
GEORGE (operating system)
GEORGE was the name given to a series of operating systems released by International Computers and Tabulators in the 1960s, for the ICT 1900 series of computers....
peri operation to issue a command:
[1 : 120] CHAR buff;
INT unitnumber;
STRUCT (BITS typemode, reply, INT count, REF CHAR address)
control area := (8r47400014,0,120,buff[1]);
...;
CODE 0,6/unitnumber; 157,6/typemode OF control area EDOC
Availability
A copy of the ALGOL 68-R compiler, runnable under David Holdsworth's George 3GEORGE (operating system)
GEORGE was the name given to a series of operating systems released by International Computers and Tabulators in the 1960s, for the ICT 1900 series of computers....
emulator, is available at http://sw.ccs.bcs.org/CCs/g3/index.html