ALGOL

From Wikipedia for FEVERv2
Jump to navigation Jump to search

This article is about the programming language family. ALGOL_sentence_0

For other uses, see Algol (disambiguation). ALGOL_sentence_1

ALGOL_table_infobox_0

ALGOLALGOL_table_caption_0
ParadigmALGOL_header_cell_0_0_0 Procedural, imperative, structuredALGOL_cell_0_0_1
FamilyALGOL_header_cell_0_1_0 ALGOLALGOL_cell_0_1_1
Designed byALGOL_header_cell_0_2_0 Bauer, Bottenbruch, Rutishauser, Samelson, Backus, Katz, Perlis, Wegstein, Naur, Vauquois, van Wijngaarden, Woodger, Green, McCarthyALGOL_cell_0_2_1
First appearedALGOL_header_cell_0_3_0 1958; 62 years ago (1958)ALGOL_cell_0_3_1
Typing disciplineALGOL_header_cell_0_4_0 Static, strongALGOL_cell_0_4_1
ScopeALGOL_header_cell_0_5_0 LexicalALGOL_cell_0_5_1
InfluencedALGOL_header_cell_0_6_0

ALGOL (/ˈælɡɒl, -ɡɔːl/; short for "Algorithmic Language") is a family of imperative computer programming languages originally developed in 1958. ALGOL_sentence_2

ALGOL heavily influenced many other languages and was the standard method for algorithm description used by the Association for Computing Machinery (ACM) in textbooks and academic sources until object-oriented languages came around, for more than thirty years. ALGOL_sentence_3

In the sense that the syntax of most modern languages is "Algol-like", it was arguably the most influential of the four high-level programming languages among which it was roughly contemporary: FORTRAN, Lisp, and COBOL. ALGOL_sentence_4

It was designed to avoid some of the perceived problems with FORTRAN and eventually gave rise to many other programming languages, including PL/I, Simula, BCPL, B, Pascal, and C. ALGOL_sentence_5

ALGOL introduced code blocks and the begin...end pairs for delimiting them. ALGOL_sentence_6

It was also the first language implementing nested function definitions with lexical scope. ALGOL_sentence_7

Moreover, it was the first programming language which gave detailed attention to formal language definition and through the Algol 60 Report introduced Backus–Naur form, a principal formal grammar notation for language design. ALGOL_sentence_8

There were three major specifications, named after the years they were first published: ALGOL_sentence_9

ALGOL_unordered_list_0

  • ALGOL 58 – originally proposed to be called IAL, for International Algebraic Language.ALGOL_item_0_0
  • ALGOL 60 – first implemented as X1 ALGOL 60 in mid-1960. Revised 1963.ALGOL_item_0_1
  • ALGOL 68 – introduced new elements including flexible arrays, slices, parallelism, operator identification. Revised 1973.ALGOL_item_0_2

ALGOL 68 is substantially different from ALGOL 60 and was not well received, so that in general "Algol" means ALGOL 60 and dialects thereof. ALGOL_sentence_10

Important implementations ALGOL_section_0

The International Algebraic Language (IAL), renamed ALGOL 58, was highly influential and generally considered the ancestor of most of the modern programming languages (the so-called Algol-like languages). ALGOL_sentence_11

Further, ALGOL object code was a simple, compact, and stack-based instruction set architecture commonly used in teaching compiler construction and other high order languages; of which Algol is generally considered the first. ALGOL_sentence_12

History ALGOL_section_1

ALGOL was developed jointly by a committee of European and American computer scientists in a meeting in 1958 at the Swiss Federal Institute of Technology in Zurich (ETH Zurich; cf. ALGOL_sentence_13

ALGOL 58). ALGOL_sentence_14

It specified three different syntaxes: a reference syntax, a publication syntax, and an implementation syntax. ALGOL_sentence_15

The different syntaxes permitted it to use different keyword names and conventions for decimal points (commas vs periods) for different languages. ALGOL_sentence_16

ALGOL was used mostly by research computer scientists in the United States and in Europe. ALGOL_sentence_17

Its use in commercial applications was hindered by the absence of standard input/output facilities in its description and the lack of interest in the language by large computer vendors other than Burroughs Corporation. ALGOL_sentence_18

ALGOL 60 did however become the standard for the publication of algorithms and had a profound effect on future language development. ALGOL_sentence_19

John Backus developed the Backus normal form method of describing programming languages specifically for ALGOL 58. ALGOL_sentence_20

It was revised and expanded by Peter Naur for ALGOL 60, and at Donald Knuth's suggestion renamed Backus–Naur form. ALGOL_sentence_21

Peter Naur: "As editor of the ALGOL Bulletin I was drawn into the international discussions of the language and was selected to be member of the European language design group in November 1959. ALGOL_sentence_22

In this capacity I was the editor of the ALGOL 60 report, produced as the result of the ALGOL 60 meeting in Paris in January 1960." ALGOL_sentence_23

The following people attended the meeting in Paris (from 1 to 16 January): ALGOL_sentence_24

ALGOL_unordered_list_1

Alan Perlis gave a vivid description of the meeting: "The meetings were exhausting, interminable, and exhilarating. ALGOL_sentence_25

One became aggravated when one's good ideas were discarded along with the bad ones of others. ALGOL_sentence_26

Nevertheless, diligence persisted during the entire period. ALGOL_sentence_27

The chemistry of the 13 was excellent." ALGOL_sentence_28

ALGOL 60 inspired many languages that followed it. ALGOL_sentence_29

Tony Hoare remarked: "Here is a language so far ahead of its time that it was not only an improvement on its predecessors but also on nearly all its successors." ALGOL_sentence_30

The Scheme programming language, a variant of Lisp that adopted the block structure and lexical scope of ALGOL, also adopted the wording "Revised Report on the Algorithmic Language Scheme" for its standards documents in homage to ALGOL. ALGOL_sentence_31

ALGOL and programming language research ALGOL_section_2

As Peter Landin noted, ALGOL was the first language to combine seamlessly imperative effects with the (call-by-name) lambda calculus. ALGOL_sentence_32

Perhaps the most elegant formulation of the language is due to John C. Reynolds, and it best exhibits its syntactic and semantic purity. ALGOL_sentence_33

Reynolds's idealized ALGOL also made a convincing methodologic argument regarding the suitability of local effects in the context of call-by-name languages, in contrast with the global effects used by call-by-value languages such as ML. ALGOL_sentence_34

The conceptual integrity of the language made it one of the main objects of semantic research, along with Programming Computable Functions (PCF) and ML. ALGOL_sentence_35

IAL implementations timeline ALGOL_section_3

To date there have been at least 70 augmentations, extensions, derivations and sublanguages of Algol 60. ALGOL_sentence_36

The Burroughs dialects included special Bootstrapping dialects such as ESPOL and NEWP. ALGOL_sentence_37

The latter is still used for Unisys MCP system software. ALGOL_sentence_38

Properties ALGOL_section_4

ALGOL 60 as officially defined had no I/O facilities; implementations defined their own in ways that were rarely compatible with each other. ALGOL_sentence_39

In contrast, ALGOL 68 offered an extensive library of transput (input/output) facilities. ALGOL_sentence_40

ALGOL 60 allowed for two evaluation strategies for parameter passing: the common call-by-value, and call-by-name. ALGOL_sentence_41

Call-by-name has certain effects in contrast to call-by-reference. ALGOL_sentence_42

For example, without specifying the parameters as value or reference, it is impossible to develop a procedure that will swap the values of two parameters if the actual parameters that are passed in are an integer variable and an array that is indexed by that same integer variable. ALGOL_sentence_43

Think of passing a pointer to swap(i, A[i]) in to a function. ALGOL_sentence_44

Now that every time swap is referenced, it is reevaluated. ALGOL_sentence_45

Say i := 1 and A[i] := 2, so every time swap is referenced it will return the other combination of the values ([1,2], [2,1], [1,2] and so on). ALGOL_sentence_46

A similar situation occurs with a random function passed as actual argument. ALGOL_sentence_47

Call-by-name is known by many compiler designers for the interesting "thunks" that are used to implement it. ALGOL_sentence_48

Donald Knuth devised the "man or boy test" to separate compilers that correctly implemented "recursion and non-local references." ALGOL_sentence_49

This test contains an example of call-by-name. ALGOL_sentence_50

ALGOL 68 was defined using a two-level grammar formalism invented by Adriaan van Wijngaarden and which bears his name. ALGOL_sentence_51

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. ALGOL_sentence_52

Examples and portability issues ALGOL_section_5

Code sample comparisons ALGOL_section_6

ALGOL 60 ALGOL_section_7

(The way the bold text has to be written depends on the implementation, e.g. 'INTEGER'—quotation marks included—for integer. ALGOL_sentence_53

This is known as stropping.) ALGOL_sentence_54

Here is an example of how to produce a table using Elliott 803 ALGOL. ALGOL_sentence_55

PUNCH(3) sends output to the teleprinter rather than the tape punch. ALGOL_sentence_56

SAMELINE suppresses the carriage return + line feed normally printed between arguments. ALGOL_sentence_57

ALIGNED(1,6) controls the format of the output with 1 digit before and 6 after the decimal point. ALGOL_sentence_58

ALGOL 68 ALGOL_section_8

The following code samples are ALGOL 68 versions of the above ALGOL 60 code samples. ALGOL_sentence_59

ALGOL 68 implementations used ALGOL 60's approaches to stropping. ALGOL_sentence_60

In ALGOL 68's case tokens with the bold typeface are reserved words, types (modes) or operators. ALGOL_sentence_61

Note: lower (⌊) and upper (⌈) bounds of an array, and array slicing, are directly available to the programmer. ALGOL_sentence_62

Timeline: Hello world ALGOL_section_9

The variations and lack of portability of the programs from one implementation to another is easily demonstrated by the classic hello world program. ALGOL_sentence_63

ALGOL 58 (IAL) ALGOL_section_10

Main article: ALGOL 58 ALGOL_sentence_64

ALGOL 58 had no I/O facilities. ALGOL_sentence_65

ALGOL 60 family ALGOL_section_11

Main article: ALGOL 60 ALGOL_sentence_66

Since ALGOL 60 had no I/O facilities, there is no portable hello world program in ALGOL. ALGOL_sentence_67

The next three examples are in Burroughs Extended Algol. ALGOL_sentence_68

The first two direct output at the interactive terminal they are run on. ALGOL_sentence_69

The first uses a character array, similar to C. The language allows the array identifier to be used as a pointer to the array, and hence in a REPLACE statement. ALGOL_sentence_70

A simpler program using an inline format: ALGOL_sentence_71

An even simpler program using the Display statement. ALGOL_sentence_72

Note that its output would end up at the system console ('SPO'): ALGOL_sentence_73

An alternative example, using Elliott Algol I/O is as follows. ALGOL_sentence_74

Elliott Algol used different characters for "open-string-quote" and "close-string-quote": ALGOL_sentence_75

Here is a version for the Elliott 803 Algol (A104) The standard Elliott 803 used 5 hole paper tape and thus only had upper case. ALGOL_sentence_76

The code lacked any quote characters so £ (UK Pound Sign) was used for open quote and ? ALGOL_sentence_77

(Question Mark) for close quote. ALGOL_sentence_78

Special sequences were placed in double quotes (e.g. ALGOL_sentence_79

££L?? ALGOL_sentence_80

produced a new line on the teleprinter). ALGOL_sentence_81

The ICT 1900 series Algol I/O version allowed input from paper tape or punched card. ALGOL_sentence_82

Paper tape 'full' mode allowed lower case. ALGOL_sentence_83

Output was to a line printer. ALGOL_sentence_84

The open and close quote characters were represented using '(' and ')' and spaces by %. ALGOL_sentence_85

ALGOL 68 ALGOL_section_12

Main article: ALGOL 68 ALGOL_sentence_86

ALGOL 68 code was published with reserved words typically in lowercase, but bolded or underlined. ALGOL_sentence_87

In the language of the "Algol 68 Report" the input/output facilities were collectively called the "Transput". ALGOL_sentence_88

Timeline of ALGOL special characters ALGOL_section_13

The ALGOLs were conceived at a time when character sets were diverse and evolving rapidly; also, the ALGOLs were defined so that only uppercase letters were required. ALGOL_sentence_89

1960: IFIP – The Algol 60 language and report included several mathematical symbols which are available on modern computers and operating systems, but, unfortunately, were unsupported on most computing systems at the time. ALGOL_sentence_90

For instance: ×, ÷, ≤, ≥, ≠, ¬, ∨, ∧, ⊂, ≡, ␣ and ⏨. ALGOL_sentence_91

1961 September: ASCII – The ASCII character set, then in an early stage of development, had the \ (Back slash) character added to it in order to support ALGOL's boolean operators /\ and \/. ALGOL_sentence_92

1962: ALCOR – This character set included the unusual "᛭" runic cross character for multiplication and the "⏨" Decimal Exponent Symbol for floating point notation. ALGOL_sentence_93

1964: GOST – The 1964 Soviet standard GOST 10859 allowed the encoding of 4-bit, 5-bit, 6-bit and 7-bit characters in ALGOL. ALGOL_sentence_94

1968: The "Algol 68 Report" – used extant ALGOL characters, and further adopted →, ↓, ↑, □, ⌊, ⌈, ⎩, ⎧, ○, ⊥, and ¢ characters which can be found on the IBM 2741 keyboard with typeball (or golf ball) print heads inserted (such as the APL golf ball). ALGOL_sentence_95

These became available in the mid-1960s while ALGOL 68 was being drafted. ALGOL_sentence_96

The report was translated into Russian, German, French, and Bulgarian, and allowed programming in languages with larger character sets, e.g., Cyrillic alphabet of the Soviet BESM-4. ALGOL_sentence_97

All ALGOL's characters are also part of the Unicode standard and most of them are available in several popular fonts. ALGOL_sentence_98

2009 October: Unicode – The ⏨ (Decimal Exponent Symbol) for floating point notation was added to Unicode 5.2 for backward compatibility with historic Buran programme ALGOL software. ALGOL_sentence_99

See also ALGOL_section_14

Credits to the contents of this page go to the authors of the corresponding Wikipedia page: en.wikipedia.org/wiki/ALGOL.