View source for ALGOL 68-R

{{Short description|Computer programming language}}
{{Infobox software
|name = ALGOL 68R
|logo = <!-- File name only. -->
|logo alt =
|logo caption =
|screenshot = <!-- File name only. -->
|screenshot alt =
|caption =
|author = I. F. Currie, [[Susan G. Bond]], J. D. Morrison
|developer = [[Royal Radar Establishment]]
|released = {{Start date and age|1970|07|20}}
|latest release version =
|latest release date = <!-- {{Start date and age|19yy|mm|dd}} -->
|programming language = [[ALGOL 60]] (original)<br/>ALGOL 68-R (latter)
|operating system = [[GEORGE (operating system)|George 3]]
|platform = [[ICT 1900 series|ICL 1907F]]
|size = 34 K words
|language = English
|genre = [[Compiler]], [[Translator (computing)|translator]]
|license = [[Freeware]]
|website = {{URL|sw.ccs.bcs.org/CCs/g3}}
}}
'''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 [[International Federation for Information Processing]] (IFIP) to discuss the problems of implementing the language,<ref>{{citation |title=Proceedings of the IFIP working conference on ALGOL 68 Implementation |editor-first=J.E.L. |editor-last=Peck |publisher=North-Holland |place=Munich |year=1970 |isbn=0-7204-2045-8}}</ref> a small team from the [[Royal Radar Establishment]] (RRE) attended to present their [[compiler]], written by I. F. Currie, [[Susan G. Bond]],<ref>
{{cite web |url=https://ethw.org/Oral-History:Susan_Bond#Developing_the_World.E2.80.99s_First_ALGOL_68_Compiler |title=Oral-History: Susan Bond: Developing the World's First ALGOL 68 Compiler |last1=Bond |first1=Susan |author-link=Susan G. Bond |last2=Abbate |first2=Janet |date=26 September 2001 |website=Engineering and Technology History Wiki (ETHW) |publisher=[[Institute of Electrical and Electronics Engineers]] (IEEE) |via=United Engineering Foundation (UEF) |access-date=22 April 2020}}</ref>
and J. D. Morrison. In the face of estimates of up to 100 man-years to implement the language, using [[multi-pass compiler]]s with up to seven passes, they described how they had already implemented a [[one-pass compiler]] 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 (programming languages)|Syntax]] Improving Device'' (SID) [[parser generator]].
{{rquote|right|About 20K of this is program, which we feel is too large.<br/>
– Currie<ref>ALGOL 68 implementation, page 21</ref>}}
The first version of the compiler occupied 34 K words. It was later rewritten in ALGOL 68-R,<ref>{{citation |last1=Currie |first1=I. F. |last2=Bond |first2=S. G. |author2-link=Susan G. Bond |last3=Morison |first3=J. D. |contribution=ALGOL 68-R, Its Implementation and Use |title=Proc [[IFIP]] Congress 1971 (Information Processing 1971) |publisher=North-Holland |place=Ljubljana, Yugoslavia |pages=360–363 |year=1971 |isbn=0-7204-2063-6}}</ref> taking around 36 K words to compile most programs.<ref name="InstallMaintain">{{cite book |author=Anonymous |title=Algol 68-R System – Installation and Maintenance |publisher=Division of Computing and Software Research - Royal Radar Establishment |date=January 1977 |url=http://www.icl1900.co.uk/techpub/algol68im.pdf |access-date=2011-04-09}}{{Dead link|date=May 2019 |bot=InternetArchiveBot |fix-attempted=yes}}</ref>
ALGOL 68-R was implemented under the [[GEORGE (operating system)|George 3]] operating system on an [[ICT 1900 series|ICL 1907F]]. The compiler was distributed at no charge by [[International Computers Limited]] (ICL) on behalf of the [[Royal Radar Establishment]] (RRE).
==Restrictions in the language compiled==
{{rquote|right|It is a question of morality. We have a Bible and you are sinning!<br/>
– [[Barry J. Mailloux|Mailloux]]<ref>ALGOL 68 implementation, page 294</ref>}}
To allow one pass compiling, ALGOL 68-R implemented a subset of the language defined in the original report:<ref>ALGOL 68 implementation, pages 21-26</ref>
#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''' = [1:10] '''REF''' '''A''';
===No ''proceduring''===
In the standard language the ''proceduring'' [[Type conversion|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 ''[[Type conversion|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 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&nbsp;(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) : ...
{{rquote|right|I think it was a reasonable thing myself to omit the bounds from the formal-declarers but I think it was a terrible crime to omit the '''EITHER''' or the '''FLEX'''<br/>
– [[Charles H. Lindsey|Lindsey]]<ref>ALGOL 68 implementation, page 276</ref>}}
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 (programming)|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 [[ICT 1900 series|ICL 1900]] to provide multithreading facilities to ALGOL 68-R programs with semantics similar to modern [[Thread (computer science)|thread]] libraries.<ref>{{cite journal |last1=Oliver |first1=J. R. |last2=Newton |first2=R.S. |year=1979 |title=Practical experience with ALGOL 68-RT |journal=The Computer Journal |volume=22 |issue=2 |pages=114–118 |doi=10.1093/comjnl/22.2.114|doi-access=free }}</ref> No changes were made to the compiler, only the [[Runtime (program lifecycle phase)|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]].<ref>{{cite book |last1=Lindsey |first1=Charles H. |author-link=Charles H. Lindsey |last2=van der Meulen |first2=S. G. |title=informal introduction to ALGOL 68 (revised) |chapter=Appendix 4, the sublanguage |publisher=north-holland |year=1997 |isbn=0-7204-0726-5}}</ref>
===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.<ref>{{cite book |last=Raymond |first=Eric S. |author-link=Eric S. Raymond |title=The new hacker's dictionary; 3rd edition |chapter=fool |publisher=MIT Press |year=1996 |pages=200 |isbn=978-0-262-68092-9 |quote=The Algol 68-R compiler used to initialize its storage to the character string "F00LF00LF00LF00L..." because as a pointer or as a floating point number it caused a crash, and as an integer or a character string it was very recognizable in a dump.}}</ref><ref>Algol 68-R System - Installation and Maintenance, page 25</ref>
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 [[ICT 1900 series|ICL 1900]]
* As an instruction it was illegal
* As text it displayed as <code>F00L</code>
* As a floating point number it had the overflow bit set
The same value was used to represent '''NIL'''.
==Stropping==
{{rquote|right|I notice, in some of your sample programs, that you are not underlining or stropping anything.<br/>
– [[Barry J. Mailloux|Mailloux]]<ref>ALGOL 68 implementation, page 30</ref>}}
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 <u>begin</u> for example).
In [[source code]] programs, some [[Stropping (syntax)|stropping]] technique had to be used. In many ALGOL like languages, before ALGOL&nbsp;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]] [[byte]]s (and hence a 64 character set) this was quite complex and, at least initially, programs had to be composed on paper [[punched tape]] using a [[Friden Flexowriter]].
Partly based on the experience of ALGOL 68-R, the revised report on ALGOL&nbsp;68 specified hardware representations for the language, including UPPER stropping.
==Extensions to ALGOL 68==
ALGOL 68-R included extensions for [[Library (computing)|separate compiling]] and low-level access to the machine.
===Separate compiling===
Since ALGOL 68 is a [[Strong and weak typing|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''.<ref>{{cite book |last1=Woodward |first1=P. M. |author-link=Philip Woodward |last2=Bond |first2=S. G. |author2-link=Susan G. Bond |title=ALGOL 68-R Users Guide |chapter=14 - Program segmentation |publisher=[[Office of Public Sector Information|Her Majesty's Stationery Office]] (HMSO) |year=1974 |pages=87–89 |isbn=0-11-771600-6}}</ref>
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 assembler|inline]], inside '''CODE''' ... '''EDOC''' sections and the address manipulation operators '''INC''', '''DEC''', '''DIF''', '''AS''' were added.<ref>Algol 68-R System - Installation and Maintenance, pp 26-30</ref>
An example, using a [[GEORGE (operating system)|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'''
==Availability==
A copy of the ALGOL 68-R compiler, runnable under the [[GEORGE (operating system)|George 3]] operating system emulator, by David Holdsworth<!-- Do not link to English footballer. --> ([[University of Leeds]]), is available, with source code, under a [[GNU General Public License]] (GPL).<ref>{{cite web |last=Toal |first=Graham |date=September 2018 |url=http://sw.ccs.bcs.org/CCs/g3/ |title=George3: Emulation of the ICL 1900 |website=Software Preservation and Machine Emulation |access-date=2020-04-19}}</ref>
==References==
{{Reflist|2}}
==External links==
* [https://mraths.org.uk/?page_id=2862 Algol 68] – Malvern Radar and Technology History Society
{{ALGOL programming}}
[[Category:ALGOL 68 implementation|R]]
[[Category:History of computing in the United Kingdom]]