Algol 60 John Cowan N Languages in N Months Meetup June 7, 2016

Presentation on theme: "Algol 60 John Cowan N Languages in N Months Meetup June 7, 2016"— Presentation transcript:

1 Algol 60 John Cowan N Languages in N Months Meetup June 7, 2016
Copyright 2016 by John Cowan Licensed under the GNU GPL v3

2 Hoare on Algol 60 “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.”

3 Reports Report on the Algorithmic Language Algol 60
Revised Report (1962) Mostly cleanup and clarification What is described here Modified Report (1973) Closes some long-standing issues Too little and too late (Then again, Algol 68 was too much and too soon)

4 Good old factorial begin integer procedure factorial(n)
value n; integer n; begin if n = 0 then factorial := 1 else factorial := factorial(n – 1) * n end

5 Syntax Literals : identifiers, numbers, strings
Expressions: arithmetic, Boolean, designational Statements: assignment, go to, procedure Complex statements: if, for, begin Declarations: variable, procedure, switch All syntax defined in Backus-Naur Form Used and defined for the first time ever

6 Basic symbols Letters, digits, 10 Logical values: true, false
+ - × / ÷ ↑ < ≤ = ≥ > ≠ ≡ ⊃ ∧ ∨ ¬ , . : ; := ( ) [ ] “ ” go to, if, then, else, for, step, until, while, do begin, end, Boolean, integer, real, array switch, string, label, procedure, value

7 Basic symbols vs. identifiers
if is not if Every computer had a different character set Hardware representations: if is 'if', if is if if is IF, if is if if is if, if is unusable begin ... end could be { ... } ≡ could be eqv (in any representation) Can't use e for 10 (5e4 would be 5 followed by e4)

8 Variable declarations
Used for both procedure parameters and local variables integer i, j, k; real a, b, c; No implicit declarations No “God is real, Jesus is an integer” rule

9 Assignments, arrays and conditionals
x := y + z integer array x[0:5] real array x[1:3, -5:5] c[i] = a[i] - b[i] for x[i] := … What happens if i is assigned within the loop? Modified report bans array element as loop variable if p = q then x := y else x := z x := if p = q then y else z

10 Go to and switch go to finished go to if p = q then a else b
switch x = a, b, c, d; go to x[a] switch y = e, f, x[n], if maybe() then c else d go to y[3] go to p; comment p is a procedure argument

11 Procedure calls and declarations
procedure add(a, b, c); real a, b, c; c := a + b; procedure add(a) to: (b) giving: (c); … add(2, 3, k) add(2) to: (3) giving: (k) add(2) foo: (3) bar: (k) Procedures can be nested Procedure arguments can be procedures, strings, and even labels

12 Call by name Substitute the actual arguments for the formal parameters textually Substitute the body of the procedure for its call Procedure call ≡ macro expansion Implemented using thunks (zero-argument procedures) “Thunk is the past tense of think at 4 A.M.”

13 Jensen's device real procedure GPS(I, N, Z, V); real I, N, Z, V; begin
for I := 1 step 1 until N do Z := V; GPS := 1 end; Z := 0; I := GPS (I, N, Z, Z+A[I] × B[I])

14 The recursion wars Recursion is powerful (Europeans & Lispers)
Non-recursion is efficient (Fortranites) Local variables and return address can be static Compromise: add recursive keyword Compromise rejected, ambiguously “Any occurrence of the procedure identifier within the body of the procedure other than in a left part in an assignment statement denotes activation of the procedure.”

15 Strings “a b c”: five symbols “if then else”: five symbols
“if “this is a nested string”!”: five symbols! Modified Report: strings contain characters, nested strings are used for escapes “line 1“NL”line 2” Strings can only be passed to procedures They bottom out in non-Algol code

16 For loops for j := 1, 1, 2, 3, 5, 8, 13 do … for j := 1 step 2 until 9 do … for j := 1, j + 1 while j < 20 do … for dummy := 0 while go on() do … comment classic while loop; for j : = 5 step -1 until 0 do … What happens if step changes sign? Modified Report: step is eager, until is lazy

17 Own variables own x ≡ own real x
Visible only in the declared scope, like local variables Value survives exit from the scope Dynamic own arrays: own real array x[i:j] What does it mean on the next entry?

18 Own vs. recursion procedure call myself(k); value k; integer k; begin
own integer j; if k = 1 then begin j := 1; call myself(2); call myself(3); end else j := j + 1; comment what is j? end

19 What killed Algol? Not enough support in the U.S.
IBM was pushing Fortran hard Burroughs built Algol hardware, but not popular No structures except arrays No effective portability between machines Too many representations Too many subsets No standard I/O until the Modified Report

20 Structures in 1960 01 MAILING-RECORD. 05 COMPANY-NAME PIC X(30).
05 CONTACTS. 10 PRESIDENT. 15 LAST-NAME PIC X(15). 15 FIRST-NAME PIC X(8). 10 VP-MARKETING. 10 ALTERNATE-CONTACT. 15 TITLE PIC X(10). 05 ADDRESS PIC X(15). 05 CITY PIC X(15). 05 STATE PIC XX. 05 ZIP PIC 9(5).

21 Algol family IAL > Algol 58 > Algol 60 > RR > MR
Algol was heavily used for published algorithms Forks: Simula > Simula 67 > (C++) Algol 68 Algol W > Pascal > Ada Scheme (in spirit) CPL > BCPL > B > C > C++, D, Java, C#, etc.

22 Algol implementations today
GNU Marst (compiler to C) Nase A60 (interpreter) Algol60i (interpreter written in Python) Racket Algol 60 (compiler to Scheme) Cim (Simula 67 compiler, near-superset)