ALGOL 68

Infobox programming language
name = ALGOL 68

paradigm = multi-paradigm: concurrent • imperative
year = 1968, last revised 1973
designer = A. van Wijngaarden, B.J. Mailloux, J.E.L. Peck and C.H.A. Koster, et al.
developer =
latest_release_version =
latest_release_date =
latest_test_version =
latest_test_date =
typing = static • strong • safe • structural
implementations = ALGOL 68C • ALGOL 68G • ALGOL 68R • ALGOL 68S • FLACC • Алгола 68 Ленинград/Leningrad Unit
dialects = ALGOL 68/FR (Final Report: 1968) • Algol 68/RR (Revised Report: 1973)
influenced_by = ALGOL 60 • ALGOL Y
influenced = ALGOL 68C » C » C++ [cite web |url=http://www.research.att.com/~bs/hopl2.pdf|text=Page 12, 2nd paragraph: Algol68 [gave] operator overloading(§3.3.3), references (§3.3.4), and the ability to declare variables anywhere in a block (§3.3.1)|title=A History of C++: 1979−1991|year=1993|month=March |accessmonthday=May 6 |accessyear=2008 ] • Bourne shell » Bash • Steelman » Ada • Python [cite web |url=http://www.amk.ca/python/writing/gvr-interview |title=Interview with Guido van Rossum|year=1998 |month=July |accessmonthday=Apr 29 |accessyear=2007 ] et el.

proc: Procedures

Procedure (proc) declarations require type specifications for both the parameters and the result (void if none): proc max of r
real a, b) real: if a > b then a else b fi;or, using the "brief" form of the conditional statement: proc max of r
real a, b) real: (a>b | a | b);The return value of a proc is the value of the last expression evaluated in the procedure. References to procedures (ref proc) are also permitted. Call-by-reference parameters are provided by specifying references (such as ref real) in the formal argument list. The following example defines a procedure that applies a function (specified as a parameter) to each element of an array: proc apply = (ref [] real a, proc (real) real f): for i from lwb a to upb a do a [i] := f(a [i] ) odThis simplicity of code was unachievable in ALGOL 68's predecessor ALGOL 60.

op: Operators

The programmer may define new operators and both those and the pre-defined ones may be overloaded. The following example defines operator max with both dyadic and monadic versions (scanning across the elements of an array). prio max = 9; op max = (int a,b) int: ( a>b | a | b ); op max = (real a,b) real: ( a>b | a | b ); op max = (compl a,b) compl: ( abs a > abs b | a | b ); op max = ( [] real a) real: (real out := - max real; for i from lwb a to upb a do ( a [i] >out | out:=a [i] ) od; out)

Monadic operators

“:=:” (alternatively “is”) tests if two pointers are equal; “:/=:” (alternatively “isnt”) tests if they are unequal.

Why :=: and :/=: are needed: Consider trying to compare two pointer values, such as the following variables, declared as pointers-to-integer:

: ref int ip, jp

Now consider how to decide whether these two are pointing to the same location, or whether one of them is pointing to nil. The following expression

: ip = jp

will dereference both pointers down to values of type int, and compare those, since the “=” operator is defined for int, but not ref int. It is "not legal" to define “=” for operands of type ref int and int at the same time, because then calls become ambiguous, due to the implicit coercions that can be applied: should the operands be left as ref int and that version of the operator called? Or should they be dereferenced further to int and that version used instead? Therefore the following expression can never be made legal:

: ip = nil

Hence the need for separate constructs not subject to the normal coercion rules for operands to operators. But there is a gotcha. The following calls:

: ip :=: jp : ip :=: nil

while legal, will probably not do what you expect. They will always return false, because they are comparing the "actual addresses of the variables "ip" and "jp", rather than what they point to". To achieve the right effect, you have to write

: ip :=: ref int(jp) : ip :=: ref int(nil)

Patent application: On 14 May 2003, software patent application No. 20040230959 ["IS NOT OPERATOR" - US patent application|20040230959] was filed for the ISNOT operator by employees of Microsoft. This patent was granted on 18 November 2004.

pecial characters for operators

The ∨, ∧, ¬, ≠, ≤, ≥, ×, ÷, ⌷, ↑, ↓, ⌊, ⌈ and ⊥ characters can be found on the IBM 2741 keyboard with the APL "golf-ball" print head inserted, these became available in the mid 1960s while ALGOL 68 was being drafted.:

transput: Input and output

Transput is the term used to refer to ALGOL 68's input and output facilities. There are pre-defined procedures for unformatted, formatted and binary transput. Files and other transput devices are handled in a consistent and machine-independent manner. The following example prints out some unformatted output to the standard output device: print ((newpage, "Title", newline, "Value of i is ", i, "and x [i] is ", x [i] , newline))Note the predefined procedures newpage and newline passed as arguments.

Books, channels and files

The transput is considered to be of books, channels and files:
* Books are made up of pages, and lines, and may be locked and selected via chains.
** A specific book can be located by name with a call to match.
* channels correspond to physical devices. eg. card punches and printers.
** There are three standard channels: stand in channel, stand out channel, stand back channel.
* A file is a means of communicating between a particular program and a book that has been opened via some channel.
** The mood of a file may be read, write, char, bin, and opened.
** transput procedures include: establish, create, open, associate, lock, close, scratch.
** position enquires: char number, line number, page number.
** layout routines include:
***space, backspace, newline, newpage.
***get good line, get good page, get good book, and proc set=(ref file f, int page,line,char)void:
** A file has event routines. eg. on logical file end, on physical file end, on page end, on line end, on format end, on value error, on char error.

formatted transput

"Formatted transput" in ALGOL 68's transput has its own syntax and patterns (functions), with formats embedded between two $ characters.Examples: printf (($2l"The sum is:"x, g(0)$, m + n)); ¢ prints the same as: ¢ print ((new line, new line, "The sum is:", space, whole (m + n, 0))
* [http://www.xs4all.nl/~jmvdveer/syntax.html#formats Format syntax in ALGOL 68G]

par: Parallel processing

"ALGOL 68" supports programming of parallel processing. Using the keyword par, a "collateral clause" is converted to a "parallel clause", where the synchronisation of actions is controlled using semaphores. In A68G the parallel actions are mapped to threads when available on the hosting operating system. In A68S a different paradigm of parallel processing was implemented (see below). mode foot = [5] bits; &cent; packed vector of bool &cent; foot left, right; sema left toe = level &lceil;left, right toe = level &lceil;right; proc shoot left toe = void: ( shoot(left toe); print("Left: Ouch!!"); newline ), shoot right toe = void:( shoot(right toe); print("Right: Ouch!!"); newline ); &cent; 10 round clip in a 1955 Colt Python .357 Magnum &cent; sema rounds = level 10; &cent; the Magnum needs more barrels to take full advantage of parallelism &cent; sema acquire target = level 1; proc shoot = (ref sema target)void: ( &darr; acquire target; &darr; rounds; print("BANG! "); &darr; target; &uarr; acquire target ); &cent; do shooting in parallel to cater for someone hoping to stand on just one foot &cent; par ( for toe from &lfloor;left to &lceil;left do shoot left toe od, &cent; <= this comma is important &cent; for toe from &lfloor;right to &lceil;right do shoot right toe od )

Code sample

This sample program implements the Sieve of Eratosthenes to find all the prime numbers that are less than 100. nil is the ALGOL 68 analogue of the "null pointer" in other languages. The notation "x" of "y" accesses a member "x" of a struct "y".

begin # Algol-68 prime number sieve, functional style # proc error = (string s) void: (print(( newline, " error: ", s, newline)); goto stop); proc one to = (int n) list: (proc f = (int m,n) list: (m>n | nil | cons(m, f(m+1,n))); f(1,n)); mode list = ref node; mode node = struct (int h, list t); proc cons = (int n, list l) list: heap node := (n,l); proc hd = (list l) int: ( l is nil | error("hd nil"); skip | h of l ); proc tl = (list l) list: ( l is nil | error("tl nil"); skip | t of l ); proc show = (list l) void: ( l isnt nil | print((" ",whole(hd(l),0))); show(tl(l))); proc filter = (proc (int) bool p, list l) list: if l is nil then nil elif p(hd(l)) then cons(hd(l), filter(p,tl(l))) else filter(p, tl(l)) fi; proc sieve = (list l) list: if l is nil then nil else proc not multiple = (int n) bool: n mod hd(l) &ne; 0; cons(hd(l), sieve( filter( not multiple, tl(l) ))) fi; proc primes = (int n) list: sieve( tl( one to(n) )); show( primes(100) ) end

Program representation

A feature of ALGOL 68, inherited from ALGOL tradition, is its different representations. There is a representation language used to describe algorithms in printed work, a "strict language" (rigorously defined in the Report) and an official "reference language" intended to be used in actual compiler input. In the examples above you will observe underlined words. This is the formal representation of the language. ALGOL 68's reserved words are effectively in a different namespace from identifiers, and spaces are allowed in identifiers, so the fragment: int a real int = 3 ;is legal. The programmer who actually writes the code does not have the option of underlining the code. Depending on hardware and cultural issues, different methods to denote these identifiers, have been devised, called "stropping regime"s. So all or some of the following may be possible programming representations: 'INT' A REAL INT = 3; .INT A REAL INT = 3; # the POINT stropping style # INT a real int = 3;# the UPPER stropping style # int a_real_int = 3;# the RES stropping style, there are 61 accepted reserved words #All implementations must recognise at least POINT, UPPER and RES inside PRAGMAT sections.

The following characters were recommended for portability, and termed "worthy characters" in the [http://www.fh-jena.de/~kleine/history/languages/Algol68-RR-HardwareRepresentation.pdf Report on the Standard Hardware Representation of Algol 68] :
*Worthy Characters: ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789 "#$%'()*+,-./:;<=>@ [ ] _
This reflected a problem in the 1960s where some hardware didn't support lowercase, nor some other non ASCII characters, indeed in the 1973 report it was written: "Four worthy characters -- "|", "_", " [", and "] " -- are often coded differently, even at installations which nominally use the same character set."
* Base characters: "Worthy characters" are a subset of "base characters".

Example of different program representations

ALGOL 68 allows for every natural language to define its own set of keywords Algol-68. As a result, programmers are able to write programs using keywords from their native language. Below is an example of a simple procedure that calculates "the day following", the code is in two languages: English and German. # Next day date - English variant # mode date = struct(int day, string month, int year); proc the day following = (date x) date: if day of x < length of month (month of x, year of x) then (day of x + 1, month of x, year of x) elif month of x = "December" then (1, "January", year of x + 1) else (1, successor of month (month of x), year of x) fi;

# Nachfolgetag - Deutsche Variante # menge datum = tupel(ganz tag, wort monat, ganz Jahr); funktion naechster tag nach = (datum x) datum: wenn tag von x < monatslaenge(monat von x, jahr von x) dann (tag von x + 1, monat von x, jahr von x) wennaber monat von x = "Dezember" dann (1, "Januar", jahr von x + 1) ansonsten (1, nachfolgemonat(monat von x), jahr von x) endewenn;

ome Vanitas

For its technical intricacies, ALGOL 68 needs a cornucopia of methods to deny the existence of something:

skip, "~" or "?"^C - an undefined value always syntactically valid, void - syntactically like a mode, but not one, nil or "∘" - a name not denoting anything, of an unspecified reference mode, empty - the only value admissible to void, needed for selecting void in a union, [1:0] int - an empty array of integral values, with mode [] int, "undefined" - a standards reports procedure raising an exception in the runtime system. &alefsym; - Used in the standards report to inhibit introspection of certain types. eg sema

c.f. below for other examples of &alefsym;.

The term nil is "var" always evaluates to true for any variable (but see above for correct use of is :/=:), whereas it is not known to which value a comparison "x" < skip evaluates for any integer "x".

ALGOL 68 leaves intentionally undefined what happens in case of integer overflow, the integer bit representation, and the degree of numerical accuracy for floating point. In contrast, the language Java has been criticized for over-specifying the latter.

Both official reports included some advanced features that were not part of the standard language. This were indicated with an &alefsym; and considered effectively private. Examples include "≮" and "≯" for templates, the outtype/intype for crude duck typing, and the straightout and straightin operators for "straightening" nested arrays and structures.

Extract from the 1973 report: §10.3.2.2. Transput modes a) mode &alefsym; simplout = union (≮ℒ int≯, ≮ℒ real≯, ≮ℒ compl≯, bool, ≮ℒ bits≯, char, [ ] char); b) mode &alefsym; outtype = ¢ an actual - declarer specifying a mode united from a sufficient set of modes none of which is 'void' or contains 'flexible', 'reference to', 'procedure' or 'union of' ¢; c) mode &alefsym; simplin = union (≮ref ℒ int≯, ≮ref ℒ real≯, ≮ref ℒ compl≯, ref bool, ≮ref ℒ bits≯, ref char, ref [ ] char, ref string); d) mode &alefsym; intype = ¢ ... ¢; §10.3.2.3. Straightening a) op &alefsym; straightout = (outtype x) [ ] simplout: ¢ the result of "straightening" 'x' ¢; b) op &alefsym; straightin = (intype x) [ ] simplin: ¢ the result of straightening 'x' ¢;

Comparison to contemporary programming languages

* [http://comjnl.oxfordjournals.org/cgi/content/abstract/21/4/316 A comparison of PASCAL and ALGOL 68] - Andrew S. Tanenbaum - June 1977.
* Comparison of ALGOL 68 and C++.

Variants

Except where noted (with a ^superscript), the language described above is that of the "Revised Report^(RR)".

The language of the unrevised Report

The original language^(FR) differs in syntax of the "mode cast", and it had the feature of "proceduring", i.e. coercing the value of a term into a procedure which evaluates the term. Proceduring effectively can make evaluations "lazy". The most useful application could have been the short-circuited evaluation of boolean operators. In op andf = (bool"a",proc bool "b")bool:("a" | "b" | false); op orf = (bool"a",proc bool "b")bool:("a" | true | "b");"b" is only evaluated if "a" is true.As defined in ALGOL 68, it did not work as expected. Most implementations emulate the correct behaviour for this special case by extension of the language.

Before revision, the programmer could decide to have the arguments of a procedure evaluated serially instead of collaterally by using semicolons instead of commas (" [http://vestein.arb-phys.uni-dortmund.de/~wb/RR/gommas.mail gomma] "s).

Extension proposals from IFIP WG 2.1

After the revision of the report, some extensions to the language have been proposed to widen the applicability:
* "partial parametrisation" (aka Currying): creation of functions (with fewer parameters) by specification of some, but not all parameters for a call, e.g. a function logarithm of two parameters, base and argument, could be specialised to natural, binary or decadic log,
* "module extension": for support of external linkage,
* "mode parameters": for implementation of limited parametrical polymorphism (most operations on data structures like lists, trees or other data containers can be specified without touching the pay load).So far, only partial parametrisation has been implemented, in ALGOL68G.

True ALGOL 68s specification and implementation timeline

The S3 programming language that was used to write the ICL VME operating system and much other system software on the ICL 2900 Series was a direct derivative of Algol 68. However, it omitted many of the more complex features, and replaced the basic modes with a set of data types that mapped directly to the 2900 Series hardware architecture.

Implementation specific extensions

ALGOL 68R^(R) from RRE was the first ALGOL 68 subset implementation,running on the ICL 1900.Based on the original language, the main subset restrictions were "definition before use" and no parallel processing.This compiler was popular in UK universities in the 1970s, where many computer science students learnt ALGOL 68 as their first programming language; the compiler was renowned for good error messages.

ALGOL 68RS^(RS) from RSRE was a portable compiler system written in ALGOL 68RS (bootstrapped from ALGOL 68R), and implemented on a variety of systems including the ICL 2900/Series 39, Multics and
DEC VAX/VMS.The language was based on the Revised Report, but with similar subset restrictions to ALGOL 68R.This compiler survives in the form of an Algol68-to-C compiler.

In ALGOL 68S^(S) from Carnegie Mellon University the power of parallel processing was improved by adding an orthogonal extension, "eventing". Any variable declaration containing keyword event made assignments to this variable eligible for parallel evaluation, i.e. the right hand side was made into a procedure which was moved to one of the processors of the C.mmp multiprocessor system. Accesses to such variables were delayed after termination of the assignment.

Cambridge ALGOL 68C^(C) was a portable compiler that implemented a subset of ALGOL 68, restricting operator definitions and omitting garbage collection, flexible rows and formatted transput.

ALGOL 68G^(G) by M. van der Veer implements a usable ALGOL 68 interpreter for today's computers and operating systems. A minor restriction is that "(formatted) transput" does not fully conform to the "Revised Report".

"Despite good intentions, a programmer may violate portability by inadvertently employing a local extension. To guard against this, each implementation should provide a PORTCHECK pragmat option. While this option is in force, the compiler prints a message for each construct that it recognizes as violating some portability constraint." [http://www.fh-jena.de/~kleine/history/languages/Algol68-RR-HardwareRepresentation.pdf]

Quotes

*"... The scheme of type composition adopted by C owes considerable debt to Algol 68, although it did not, perhaps, emerge in a form that Algol's adherents would approve of. The central notion I captured from Algol was a type structure based on atomic types (including structures), composed into arrays, pointers (references), and functions (procedures). Algol 68's concept of unions and casts also had an influence that appeared later." Dennis Ritchie Apr 1993. [cite web | title = The Development of the C Language | author=Dennis Ritchie | year=1993|month=Apr| url = http://cm.bell-labs.com/cm/cs/who/dmr/chist.pdf | accessmonthday = Apr 26 | accessyear = 2007 ]
* "... C does not descend from Algol 68 is true, yet there was influence, much of it so subtle that it is hard to recover even when I think hard. In particular, the union type (a late addition to C) does owe to A68, not in any details, but in the idea of having such a type at all. More deeply, the type structure in general and even, in some strange way, the declaration syntax (the type-constructor part) was inspired by A68. And yes, of course, "long"." Dennis Ritchie, 18 June 1988 [cite web | title = usenet:comp.lang.misc "C and Algol 68" | url = http://groups.google.co.uk/group/comp.lang.misc/browse_thread/thread/1e6d4bb30659b78d/f57b6f5c81502cf5 | author=Dennis Ritchie| year=1988 | month=Jun|accessmonthday = Sep 15 | accessyear = 2006 ]
*"Congratulations, your Master has done it" - Niklaus Wirth [cite web | title = The Making of Algol 68 | author=C.H.A. Koster| year=1993 | url = http://www.cs.ru.nl/~kees/home/papers/psi96.pdf | accessmonthday = Apr 28 | accessyear = 2007 ]
*"The more I see of it, the more unhappy I become" - E.W. Dijkstra, 1968 [cite web | title = To the EDITOR ALGOL 68 Mathematische Centrum | author=E.W. Dijkstra| url = http://www.cs.utexas.edu/users/EWD/transcriptions/EWD02xx/EWD230.html | accessmonthday = Apr 28 | accessyear = 2007 ]
* " [...] it was said that A68's popularity was inversely proportional to [...] the distance from Amsterdam" - Guido van Rossum [cite web | title = Python-Dev Wishlist: dowhile | author= Guido van Rossum | year=2005|month=Jun | url=http://mail.python.org/pipermail/python-dev/2005-June/054225.html | accessmonthday = Apr 28 | accessyear = 2007 ]
* 1980 quote: ' [...] The best we could do was to send with it a minority report, stating our considered view that, "... as a tool for the creation of sophisticated programs, the language was a failure." [...] ' - , Oct 1980, re: "Dec 1968"
* Original 1968 version: " [...] More than ever it will be required from an adequate programming tool that it assists, by structure, the programmer in the most difficult aspects of his job, viz. in the reliable creation of sophisticated programs. In this respect we fail to see how the language proposed here " [Algol68] " is a significant step forward: on the contrary, we feel that its implicit view of the programmer's task is very much the same as, say, ten years ago. This forces upon us the conclusion that, regarded as a programming tool, the language must be regarded as obsolete. [...] " Signed by: DIJKSTRA, DUNCAN, GARWICK, HOARE, RANDELL, SEEGMUELLER, TURSKI, WOODGER. And then on Dec. 23, 1968, Jan V. Garwick [cite web | title = ALGOL Bulletin (referred to in AB30.1.1.1) |year=1970|month=Mar| url = http://archive.computerhistory.org/resources/text/algol/algol_bulletin/A31/P111.HTM| accessmonthday = Mar 1 | accessyear = 2007 ]

References

* Brailsford, D.F. and Walker, A.N., "Introductory ALGOL 68 Programming", Ellis Horwood/Wiley, 1979
* Lindsey, C.H., "A History of ALGOL 68", ACM SIGPLAN Notices 28(3), March 1993. (Includes a comprehensive bibliography of the meetings and discussions before, during and after the development of ALGOL 68.)
* Lindsey, C.H. and van der Meulen, S.G., "Informal Introduction to ALGOL 68", North-Holland, 1971
* McGettrick, A.D., "ALGOL 68, A First and Second Course", Cambridge Univ. Press, 1978
* Peck, J.E.L., "An ALGOL 68 Companion", Univ. of British Columbia, October 1971
* Tanenbaum, A.S., "A Tutorial on ALGOL 68", Computing Surveys 8, 155-190, June 1976 and 9, 255-256, September 1977, http://vestein.arb-phys.uni-dortmund.de/~wb/RR/tanenbaum.pdf
* Woodward, P.M. and Bond, S.G., "ALGOL 68-R Users^sic Guide", London, Her Majesty's Stationery Office, 1972

ee also

* ALGOL 60
* ALGOL Y
* ALGOL 68C
* ALGOL 68G
* C
* C++
* Bourne shell
* Bash
* Steelman
* Ada
* Python

External links

* [http://vestein.arb-phys.uni-dortmund.de/~wb/RR/rr.pdf Revised Report on the Algorithmic Language ALGOL 68] The official reference for users and implementors of the language
* [http://vestein.arb-phys.uni-dortmund.de/~wb/RR/rrTOC.html Revised Report on the Algorithmic Language ALGOL 68] HTML version of the above
* [http://www.xs4all.nl/~jmvdveer/report_contents.html Revised Report on the Algorithmic Language ALGOL 68] Enhanced HTML version, based on the version above
* [http://www.cs.man.ac.uk/~chl/index.html Charles Lindsey's paper on the development of ALGOL 68 for the second History of Programming Languages conference proceedings]
* [http://portal.acm.org/citation.cfm?id=356671 "A Tutorial on Algol 68"] , by Andrew S. Tanenbaum, in "Computing Surveys", Vol. 8, No. 2, June 1976, with [http://portal.acm.org/citation.cfm?id=356706 Corrigenda] (Vol. 9, No. 3, September 1977)
* [http://www.xs4all.nl/~jmvdveer/algol.html Algol 68 Genie - a GNU GPL Algol 68 interpreter]
* [http://www.fh-jena.de/~kleine/history/languages/Algol68-RR-HardwareRepresentation.pdf Algol68 Standard Hardware representation (.pdf)]
* [http://www.computer-museum.ru/histsoft/algol68.htm Из истории создания компилятора с Алгол 68]
* [http://www.computer-museum.ru/english/algol68.htm Algol 68 &ndash; 25 Years in the USSR]
* [http://ant.tepkom.ru/newsite/disser/doc/Ruchlin.htm Система программ динамической поддержки для транслятора с Алгола 68]
* [http://cm.bell-labs.com/cm/cs/who/dmr/chist.html C history with Algol68 heritage]