Classic Algorithms in ALGOL 60

All programs below are complete MARST programs.

21.1 Euclid's GCD (iterative and recursive)

'begin'
    'integer' 'procedure' gcd(a, b); 'value' a, b; 'integer' a, b;
    'begin'
        'integer' t;
    loop:
        'if' b != 0 'then'
        'begin'
            t := a - b * (a % b);
            a := b; b := t;
            'goto' loop
        'end';
        gcd := a
    'end';

    'integer' 'procedure' rgcd(a, b); 'value' a, b; 'integer' a, b;
        rgcd := 'if' b = 0 'then' a 'else' rgcd(b, a - b * (a % b));

    outinteger(1, gcd(1071, 462));      'comment' 21;
    outinteger(1, rgcd(1071, 462));     'comment' 21;
    outstring(1, "\n")
'end'

21.2 Sieve of Eratosthenes

Note the inner block: the array bound n must be assigned *before* entering the block that declares prime.

'begin'
    'integer' n, i, j;
    n := 100;
    'begin'
        'boolean' 'array' prime[2:n];
        'for' i := 2 'step' 1 'until' n 'do' prime[i] := 'true';
        'for' i := 2 'step' 1 'until' n 'do'
            'if' prime[i] 'then'
            'begin'
                'for' j := i * i 'step' i 'until' n 'do' prime[j] := 'false'
            'end';
        'for' i := 2 'step' 1 'until' n 'do'
            'if' prime[i] 'then' outinteger(1, i);
        outstring(1, "\n")
    'end'
'end'

21.3 Insertion sort and binary search

Note how the goto-based loops nest inside begin ... end to avoid a dangling-else conflict (if j >= 1 then if a[j] > v ... must be wrapped).

'begin'
    'integer' 'array' a[1:10];
    'integer' i;

    'procedure' insertion sort(a, n); 'value' n; 'integer' n; 'integer' 'array' a;
    'begin'
        'integer' i, j, v;
        'for' i := 2 'step' 1 'until' n 'do'
        'begin'
            v := a[i]; j := i - 1;
        shift:
            'if' j >= 1 'then'
            'begin'
                'if' a[j] > v 'then'
                'begin'
                    a[j + 1] := a[j]; j := j - 1; 'goto' shift
                'end'
            'end';
            a[j + 1] := v
        'end'
    'end';

    'integer' 'procedure' binary search(a, n, x); 'value' n, x; 'integer' n, x; 'integer' 'array' a;
    'begin'
        'integer' lo, hi, mid;
        lo := 1; hi := n; binary search := 0;
    again:
        'if' lo <= hi 'then'
        'begin'
            mid := (lo + hi) % 2;
            'if' a[mid] = x 'then' binary search := mid
            'else'
            'begin'
                'if' a[mid] < x 'then' lo := mid + 1 'else' hi := mid - 1;
                'goto' again
            'end'
        'end'
    'end';

    a[1] := 42; a[2] := 7; a[3] := 19; a[4] := 3; a[5] := 88;
    a[6] := 25; a[7] := 61; a[8] := 14; a[9] := 50; a[10]
…

21.4 Quicksort (after Hoare's Algorithm 63/64, CACM 1961)

Hoare published *Partition* (Algorithm 63) and *Quicksort* (Algorithm 64) in ALGOL 60. A modern rendition:

The for d := 0 while B do S idiom is ALGOL 60's while B do S.

'begin'
    'integer' 'array' data[1:12];
    'integer' k;

    'procedure' quicksort(a, lo, hi);
        'value' lo, hi; 'integer' lo, hi; 'integer' 'array' a;
    'begin'
        'integer' i, j, pivot, t, d;
        'if' lo < hi 'then'
        'begin'
            i := lo; j := hi; pivot := a[(lo + hi) % 2];
            'for' d := 0 'while' i <= j 'do'
            'begin'
                'for' d := 0 'while' a[i] < pivot 'do' i := i + 1;
                'for' d := 0 'while' a[j] > pivot 'do' j := j - 1;
                'if' i <= j 'then'
                'begin'
                    t := a[i]; a[i] := a[j]; a[j] := t;
                    i := i + 1; j := j - 1
                'end'
            'end';
            quicksort(a, lo, j);
            quicksort(a, i, hi)
        'end'
    'end';

    'for' k := 1 'step' 1 'until' 12 'do'
        data[k] := 'if' k - 2 * (k % 2) = 0 'then' 100 - 7 * k 'else' 3 * k;
    quicksort(data, 1, 12);
    'for' k := 1 'step' 1 'until' 12 'do' outinteger(1, data[k]);
    outstring(1, "\n")
'end'

21.5 Matrix multiplication

'begin'
    'integer' n, i, j, k;
    n := 3;
    'begin'
        'real' 'array' a, b, c[1:n, 1:n];
        'real' s;
        'for' i := 1 'step' 1 'until' n 'do'
            'for' j := 1 'step' 1 'until' n 'do'
            'begin'
                a[i, j] := i + j;
                b[i, j] := 'if' i = j 'then' 1 'else' 0
            'end';
        'for' i := 1 'step' 1 'until' n 'do'
            'for' j := 1 'step' 1 'until' n 'do'
            'begin'
                s := 0;
                'for' k := 1 'step' 1 'until' n 'do' s := s + a[i, k] * b[k, j];
                c[i, j] := s
            'end';
        'for' i := 1 'step' 1 'until' n 'do'
        'begin'
            'for' j := 1 'step' 1 'until' n 'do' outreal(1, c[i, j]);
            outstring(1, "\n")
        'end'
    'end'
'end'

21.6 Eight queens (recursive backtracking)

This algorithm is the subject of Wirth's famous 1971 paper "Program Development by Stepwise Refinement", originally written in an ALGOL-like notation.

'begin'
    'integer' 'array' col[1:8];
    'integer' solutions;

    'boolean' 'procedure' safe(r, c); 'value' r, c; 'integer' r, c;
    'begin'
        'integer' i; 'boolean' ok;
        ok := 'true';
        'for' i := 1 'step' 1 'until' r - 1 'do'
            'if' col[i] = c 'or' abs(col[i] - c) = r - i 'then' ok := 'false';
        safe := ok
    'end';

    'procedure' place(r); 'value' r; 'integer' r;
    'begin'
        'integer' c;
        'if' r > 8 'then' solutions := solutions + 1
        'else'
            'for' c := 1 'step' 1 'until' 8 'do'
                'if' safe(r, c) 'then'
                'begin'
                    col[r] := c;
                    place(r + 1)
                'end'
    'end';

    solutions := 0;
    place(1);
    outstring(1, "solutions: ");
    outinteger(1, solutions);       'comment' 92;
    outstring(1, "\n")
'end'