ALGOL 68 |
ALGOL 68 (short for ALGOrithmic Language 1968) is an imperative computer programming 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 a more rigorously defined syntax and semantics. Contributions of ALGOL 68 to the field of computer science are deep and wide ranging, although some of them were not publicly identified until they were passed, in one form or another, to one of many subsequently developed programming languages.
ALGOL 68 was defined using a two-level grammar formalism invented by Adriaan van Wijngaarden. Van Wijngaarden grammars use a context-free grammar to generate an infinite set of productions that will recognize a particular ALGOL 68 program; notably, they are able to express the kind of requirements that in many other programming language standards are labelled semantics and have to be expressed in ambiguity-prone natural language prose, and then implemented in compilers as ad hoc code attached to the formal language parser.
The main principles of design are completeness and clarity of design, orthogonality design, security, efficiency, the latter by static mode checking, mode-independent parsing, independent compilation and loop optimization.
Critics of ALGOL 68, prominently C. A. R. Hoare, point out that it abandoned the simplicity of ALGOL 60 and became a vehicle for various complex ideas of its designers. The language also did little to make the Compiler writer s task easy, in contrast to deliberately simple contemporaries (and competitors) C programming language, S-algol and Pascal programming language.
Though European defence agencies (in Britain Royal Signals and Radar Establishment - RRSE) promoted the use of ALGOL 68 for its expected security advantages, the American side of the NATO decided to develop a different project, the Ada programming language. The use of Ada was made obligate for defence contracts. Apparently there was no room for two languages of similar application range in the NATO. Perhaps the acceptance of ALGOL 68 on the Russian side, then Soviet Union, was not helpful on this, either.
The ALGOL 68 heritage is acknowledged by Scheme programming language, and by C plus plus.
For a full length treatment of the language, see [http://www.geocities.com/ernobe Programming Algol 68 Made Easy] by Dr. Sian Leitch.
=Time-line of ALGOL 68=
=Notable Language Elements=
==Bold Symbols and Reserved Words ==
There are 61 such reserved words ( some with brief symbol equivalents ) in the standard sub-language: mode, op, prio, proc, flex, heap, loc, long, ref, short, bits, bool, bytes, char, compl, int, real, sema, string, void, channel, file, format, struct, union, of, at @ , is :==: , isnt :/=: , true, false, empty, nil , skip ~ , co ¢ , comment ¢ , pr, pragmat, case in ouse in out esac ( ~ | ~ |: ~ | ~ | ~ ) , for from to by while do od, if then elif then else fi ( ~ | ~ |: ~ | ~ | ~ ) , par begin end ( ~ ) , go to, goto, exit.
==Units: Expressions ==
The basic language construct is the unit . A unit may be a formula , an enclosed clause , a routine text or one of several technically needed constructs (assignation, jump, skip, nihil). The technical term enclosed clause unifies some of the inherently bracketting constructs known as block , do statement , switch statement in other contemporary languages. When keywords are used, generally the reversed character sequence of the introducing keyword is used for terminating the enclosure (if then else fi, case in out esac, for while do od). This feature was reused by Stephen Bourne in the common Unix Bourne shell. An expression may also yield a multiple value , which is constructed from other values by a collateral clause . This construct just looks like the parameter pack of a procedure call.
==mode: Declarations==
The basic Datatypes (called modes in ALGOL 68 parlance) are real, int, compl (complex number), bool and char. For example:
int n = 2, m:=3; CO n is a fixed constant of 2, but m is variable which is initially 3 CO real avogadro = 6.022141523; CO Avogadro s number CO long long real pi = 3.14159 26535 89793 23846 26433 83279 50288 41971 69399 37510; compl square root of minus one = 0 1;
However, the declaration real x; is just syntactic sugar for ref real x = loc real;. That is, x is really the constant name for a reference to a newly generated local real variable.
Furthermore, instead of defining both float and double, or int and long and short, etc., ALGOL 68 provided modifiers , so that the presently common double would be written as long real or long long real instead, for example. Type queries of the kind of max real and min long int are provided to adapt programs to different implementations.
All variables need to be declared, the declaration does not have to appear prior to the first use.
primitive-declarer: int, real, compl, complexG, bool, char, string, bits, bytes, format, file, pipeG, channel, sema
Other declaration symbols include: flex, heap, loc, ref, long, short, eventS
A new mode (type) may be declared using a mode declaration: int max=99; mode newtype = [0:9][0:max]struct ( long real a, b, c; short int i, j, k; ref real r ); This has the similar effect as the following C++ code: const int max=99; typedef class { public: double a, b, c; short i, j, k; float &r; } newtype[10][max+1]; Note that for ALGOL 68 only the newtype name appears to the left of the equality, and most notably the construction is made - and can be read - from left to right without regard to priorities.
==Coercions: casting==
The coercions produce a coercend from a coercee according to three criteria: the a priori mode of the coercend before the application of any coercion, the a posteriori mode of the coercee required after those coercions, and the syntactic position or sort of the coercee. Coercions may be cascaded.
There are six possible coercions, termed deproceduring , dereferencing , uniting , widening , rowing and voiding . Each Coercion, except uniting , prescribes a corresponding dynamic effect on the associated values. Hence, a number of primitive actions can be programmed implicitly by coercions.
Context strength - Allowed coercions:
==prag & co: Code Pragments and Comments==
Pragmats are directives in the program, typically hints to the compiler. eg. pragmat heap=32 pragmat pr heap=32 pr
Comments can be inserted in variety of ways: ¢ The original way of adding your 2 cents worth to a program ¢ comment bold comment comment co Style i comment co # Style ii comment # £ This is a hash/pound comment for a UK keyboard £
Normally, comments cannot be nested in ALGOL 68. This restriction can be circumvented by using different comment delimiters (e.g. use hash only for temporary code deletions).
==Expressions and compound statements==
ALGOL 68 being an expression-oriented programming languages, the value returned by an assignment (programming) statement is a reference to the destination. Thus, the following is valid ALGOL 68 code: real spi, twice pi; twice pi := 2 * ( spi := 3.1415926 ); This notion is present in C programming language and Perl, among others. Note that twice pi is a single identifier, i.e., blanks are permitted within ALGOL 68 names (effectively avoiding the underscores versus camel case (programming) versus all lowercase issues at once, but at the price of introducing a cornucopia of more serious problems in software engineering).
As another example, to express the mathematical idea of a sum of f(i) from i=1 to n, the following ALGOL 68 integer expression suffices: (int sum := 0; for i to n do sum +:= f(i) od; sum) Note that, being an integer expression, the former block of code can be used in any context where an integer value can be used . A block of code returns the value of the last expression it evaluated; this idea is present in Perl, among other languages.
Compound statements are all terminated by distinctive (if somewhat irreverent) closing brackets: *if choice clauses: if condition then statements [ else statements ] fi brief form of if statement: ( condition | statements | statements ) if condition1 then statements elif condition2 then [ else statements ] fi brief form: ( condition1 | statements :| condition2 | statements | statements ) *case choice clauses: case switch in statements, statements,... [ out statements ] esac brief form: ( switch | statements,statements,... | statements ) case switch1 in statements, statements,... ouse switch2 in statements, statements,... [ out statements ] esac brief form of case statement: ( switch1 | statements,statements,... |: switch2 | statements,statements,... | statements ) *do loop clause: [ for index ] [ from first ] [ by increment ] [ to last ] [ while condition ] do statements od The minimum form of a loop clause is thus: do statements od
This scheme not only avoids the dangling else problem but also avoids having to use begin and end in embedded statement sequences. Some actual examples can be found below.
==struct, union & [:]: Structures, unions and arrays==
ALGOL 68 supports arrays with any number of dimensions, and it allows for the slicing of whole or partial rows or columns, among many other choices. mode vector = [3]real; # vector mode declaration (typedef) # mode matrix = [3][3]real; # matrix mode declaration (typedef) # vector r1 := (1,2,3); # array variable initially (1,2,3) # [ ]real r2 = (4,5,6); # constant array, length is implied # op + = (vector a,b)vector: # binary operator definition # (vector out; int i; for i from ⌊a to ⌈a do out[i]:=a[i]+b[i] od; out); matrix m:=(r1,r2,r1+r2); print ; # print the 2nd and 3rd element of each row #
Matrices can be sliced either way, eg: ref vec col:=m[ ][2] # extract a ref (pointer) to the 2nd column!! #
ALGOL 68 supports multiple field structures (struct). Union types (modes) are supported. Reference variables may point to both array slices and structure fields. For an example of all this, here is the traditional linked list declaration: mode node = union (real, int, compl, string); mode list = struct (node val, ref list next);
Usage example for union case of node :
node n:= 1234 ; case n in (real):print, (int):print, (compl):print, (string):print out print esac
==proc: Procedures==
Procedure (proc) declarations require type specifications for both the parameters and the result (void if none):
proc max of real = (real a, b) real: if a > b then a else b fi;
or, using the brief form of the conditional statement:
proc max of real = (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. Parameter (computer science)#Calling conventions 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]) od;
This 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 overloading (programming). 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);
===Special characters for operators===
The ∨, ∧, ¬, ≠, ≤, ≥, ×, ÷, ⌷, ↑, ↓, ⌊, ⌈ and ⊥ characters can be found on the IBM 2741 terminal with the APL programming language#APL symbols and keyboard layout golf-ball print head, 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:
===formatted transput===
Formatted transput in ALGOL 68 s transput has it s own syntax and patterns (functions), with formats embedded between two $ characters. Examples: printf ; ¢ prints the same as ¢ print ;
==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]bool; foot left, right; sema left toe := level left, right toe := level right; proc shoot left toe = void: ( shoot(left toe); print( Left: Ouch!! ); newline ), shoot right toe = void:( shoot(right toe); print( Right: Ouch!! ); newline ); ¢ 10 round clip in a 1955 Colt Python .357 Magnum ¢ sema rounds = level 10; ¢ the Magnum needs more barrels to take full advantage of parallelism ¢ sema aquire target = level 1; proc shoot = (ref sema target)void: ( aquire target; rounds; print( BANG! ); target; aquire target ); ¢ do shooting in parallel to cater for someone hoping to stand on just one foot ¢ par ( for toe from left to left do shoot left toe od, ¢ 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); 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) ≠ 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 (computer science) 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; INT a real int = 3; int a_real_int = 3; 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]:
== Some 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 no 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 procedure raising an exception in the runtime system.
The term nil is var always evaluates to true for any variable, 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 programming language has been criticized for over-specifying the latter.
= Comparison to C++ =
Regarding the computing features, the nearest living sibling to ALGOL 68 may be C plus plus, making this a good comparison candidate:
C++ has not:
ALGOL 68 has not:
= Variants =
Except where noted (with a superscript), the language described above is that of the Revised Report(2) .
== The language of the unrevised Report ==
The original language(1) 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); 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 ( 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:
==True ALGOL 68s Specification and Implementation Timeline==
== Implementation specific extensions ==
ALGOL 68R(R) from Royal Radar Establishment was the first ALGOL 68 subset implementation, running on the International_Computers_Ltd#1900_series. Based on the original language, the main subset restrictions were definition before use and no parallel processing. This compiler was popular in United Kingdom 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 Royal Signals and Radar Establishment was a portable compiler system written in ALGOL 68RS (bootstrapped from ALGOL 68R), and implemented on a variety of systems including the International_Computers_Ltd#2900_series, Multics and VAX. 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.
University of Cambridge ALGOL 68C(C) was a portable compiler that implemented a subset of ALGOL 68 by enforcing definition before use , restricting operator definitions and omitting garbage collection.
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 is still not conforming 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 =
=References=
=External links=
|
|