ALGOL 68-R was the first implementation of the Algorithmic Language
ALGOL 68
ALGOL 68 (short for ''Algorithmic Language 1968'') is an imperative 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 d ...
.
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
International Federation for Information Processing
The International Federation for Information Processing (IFIP) is a global organisation for researchers and professionals working in the field of computing to conduct research, develop standards and promote information sharing.
Established in 196 ...
(IFIP) to discuss the problems of implementing the language, a small team from the
Royal Radar Establishment
The Royal Radar Establishment was a research centre in Malvern, Worcestershire in the United Kingdom. It was formed in 1953 as the Radar Research Establishment by the merger of the Air Ministry's Telecommunications Research Establishment (TRE) a ...
(RRE) attended to present their
compiler
In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs tha ...
, 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
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 previ ...
s with up to seven passes, they described how they had already implemented a
one-pass compiler
In computer programming, a one-pass compiler is a compiler that passes through the parts of each compilation unit only once, immediately translating each part into its final machine code. This is in contrast to a multi-pass compiler which conver ...
which was in production for engineering and scientific uses.
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
In computer science, a compiler-compiler or compiler generator is a programming tool that creates a parser, interpreter, or compiler from some form of formal description of a programming language and machine.
The most common type of compiler- ...
.
The first version of the compiler occupied 34 K words. It was later rewritten in ALGOL 68-R, taking around 36 K words to compile most programs.
ALGOL 68-R was implemented under the
George 3 operating system on an
ICL 1907F. The compiler was distributed at no charge by
International Computers Limited (ICL) on behalf of the
Royal Radar Establishment
The Royal Radar Establishment was a research centre in Malvern, Worcestershire in the United Kingdom. It was formed in 1953 as the Radar Research Establishment by the merger of the Air Ministry's Telecommunications Research Establishment (TRE) a ...
(RRE).
Restrictions in the language compiled
To allow one pass compiling, ALGOL 68-R implemented a subset 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 rewritten 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 =
:10REF 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
In a programming language, an evaluation strategy is a set of rules for evaluating expressions. The term is often used to refer to the more specific notion of a ''parameter-passing strategy'' that defines the kind of value that is passed to the f ...
.
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
Cast may refer to:
Music
* Cast (band), an English alternative rock band
* Cast (Mexican band), a progressive Mexican rock band
* The Cast, a Scottish musical duo: Mairi Campbell and Dave Francis
* ''Cast'', a 2012 album by Trespassers William
...
'' 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 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
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 : EITHERINT 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 working 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 type (SEMA) with the traditional ''P'' (DOWN) and ''V'' (UP) operators is provided for sysynchronizing between the parts of the parallel clause,
This feature was not implemented in ALGOL 68-R.
An extension named 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
runtime 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.
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 1900
* 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
ALGOL (; short for "Algorithmic Language") is a family of imperative computer programming languages originally developed in 1958. ALGOL heavily influenced many other languages and was the standard method for algorithm description used by the ...
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 code
In computing, source code, or simply code, is any collection of code, with or without comments, written using a human-readable programming language, usually as plain text. The source code of a program is specially designed to facilitate the w ...
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 68-R, basic symbols could be distinguished by writing them in upper case, lower case being used for identifiers.
As ALGOL 68-R was implemented on a machine with 6-
bit
The bit is the most basic unit of information in computing and digital communications. The name is a portmanteau of binary digit. The bit represents a logical state with one of two possible values. These values are most commonly represente ...
byte
The byte is a unit of digital information that most commonly consists of eight bits. Historically, the byte was the number of bits used to encode a single character of text in a computer and for this reason it is the smallest addressable uni ...
s (and hence a 64 character set) this was quite complex and, at least initially, programs had to be composed on paper
punched tape
Five- and eight-hole punched paper tape
Paper tape reader on the Harwell computer with a small piece of five-hole tape connected in a circle – creating a physical program loop
Punched tape or perforated paper tape is a form of data storage ...
using a
Friden Flexowriter
The Friden Flexowriter produced by the Friden Calculating Machine Company, 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 atta ...
.
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 compiling and low-level access to the machine.
Separate compiling
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 prevents programs from directly accessing the low level hardware. No operators exist 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
assembly language. Machine instructions could be written
inline, inside CODE ... EDOC sections and the address manipulation operators INC, DEC, DIF, AS were added.
An example, using a
George
George may refer to:
People
* George (given name)
* George (surname)
* George (singer), American-Canadian singer George Nozuka, known by the mononym George
* George Washington, First President of the United States
* George W. Bush, 43rd Presid ...
''peri'' operation to issue a command:
: 120CHAR buff;
INT unitnumber;
STRUCT (BITS typemode, reply, INT count, REF CHAR address)
control area := (8r47400014,0,120,buff
;
...;
CODE 0,6/unitnumber; 157,6/typemode OF control area EDOC
Availability
A copy of the ALGOL 68-R compiler, runnable under the
George 3 operating system emulator, by David Holdsworth (
University of Leeds
, mottoeng = And knowledge will be increased
, established = 1831 – Leeds School of Medicine1874 – Yorkshire College of Science1884 - Yorkshire College1887 – affiliated to the federal Victoria University1904 – University of Leeds
, ...
), is available, with source code, under a
GNU General Public License
The GNU General Public License (GNU GPL or simply GPL) is a series of widely used free software licenses that guarantee end users the four freedoms to run, study, share, and modify the software. The license was the first copyleft for general ...
(GPL).
References
External links
Algol 68– Malvern Radar and Technology History Society
{{ALGOL programming
R
History of computing in the United Kingdom