Procedures, Routine Texts & Higher-Order Programming

PROC name = routine text is an identity declaration: the identifier is bound to a routine value of mode PROC (REAL) REAL, PROC (STRING) VOID, PROC INT, etc.

31.1 Procedure declarations

PROC name = routine text is an identity declaration: the identifier is bound to a routine value of mode PROC (REAL) REAL, PROC (STRING) VOID, PROC INT, etc.

PROC square = (REAL x) REAL: x * x;

PROC greet = (STRING name) VOID:
   print(("Hello, ", name, "!", newline));

PROC factorial = (INT n) INT:
   IF n <= 1 THEN 1 ELSE n * factorial(n - 1) FI;

PROC roll die = INT: ENTIER (random * 6) + 1;       # no parameters #

31.2 Parameters

Parameters behave like identity declarations: the formal is bound to the value of the actual (call by value). For in-out parameters pass a reference:

There is no call by name: to pass an expression to be re-evaluated, pass a procedure (§31.4).

PROC swap = (REF INT a, b) VOID: (INT t = a; a := b; b := t);

PROC divmod = (INT a, b, REF INT q, r) VOID: (q := a OVER b; r := a MOD b);

INT x := 1, y := 2;
swap(x, y);              # works for any two INT variables — unlike ALGOL 60 #
INT q, r;
divmod(17, 5, q, r);

31.3 Procedure variables

PROC (REAL) REAL f := sin;
print(f(pi / 2));
f := (REAL x) REAL: x * x;     # assign a routine text #
print(f(3))

31.4 Routine texts as anonymous functions; Jensen's device revisited

The explicit routine text (INT k) REAL: 1 / k replaces ALGOL 60's implicit thunk — clearer and type-checked.

BEGIN
   PROC sum = (INT lo, hi, PROC (INT) REAL term) REAL:
   BEGIN
      REAL s := 0;
      FOR k FROM lo TO hi DO s +:= term(k) OD;
      s
   END;
   print(("H(100) = ", fixed(sum(1, 100, (INT k) REAL: 1 / k), 0, 6), newline));
   print(("sum of squares = ", fixed(sum(1, 10, (INT k) REAL: k * k), 0, 0), newline))
END

31.5 Higher-order procedures

BEGIN
   PROC map = (PROC (INT) INT f, [] INT a) [] INT:
   BEGIN
      [LWB a : UPB a] INT r;
      FOR i FROM LWB a TO UPB a DO r[i] := f(a[i]) OD;
      r
   END;

   PROC fold = (PROC (INT, INT) INT f, INT init, [] INT a) INT:
   BEGIN
      INT acc := init;
      FOR i FROM LWB a TO UPB a DO acc := f(acc, a[i]) OD;
      acc
   END;

   PROC filter = (PROC (INT) BOOL keep, [] INT a) [] INT:
   BEGIN
      FLEX [1:0] INT r;
      FOR i FROM LWB a TO UPB a DO
         IF keep(a[i]) THEN
            [UPB r + 1] INT t; t[1:UPB r] := r; t[UPB t] := a[i]; r := t
         FI
      OD;
      r
   END;

   [] INT xs = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
   print((map((INT x) INT: x * x, xs), newline));
   print((fold((INT a, b) INT: a + b, 0, xs), newline));
   print((filter((INT x) BOOL: NOT ODD x, xs), newline))
END

31.6 Scope: why ALGOL 68 routines are not full closures

A routine text may use identifiers from enclosing ranges, but its scope is limited to the smallest range containing those declarations. Returning such a routine outside that range is a scope violation:

a68g detects scope violations (at compile time where it can, otherwise at run time). This keeps ALGOL 68's stack discipline: no heap-allocated environments are needed. Workarounds:

Pass the extra data explicitly as a parameter.

Use partial parametrisation, an extension proposed for ALGOL 68 and supported by a68g (not part of the Revised Report): supply some arguments and leave others empty.

PROC make adder = (INT n) PROC (INT) INT:
   (INT x) INT: x + n;        # uses n, a parameter of make adder #
PROC (INT) INT add5 = make adder(5);   # ERROR: the routine outlives n #

PROC add = (INT n, x) INT: n + x;
PROC (INT) INT add5 = add(5, );      # a68g partial parametrisation #
print(add5(10))                       # 15 #

31.7 Nested procedures and recursion

Procedures can be declared in any serial clause, nested to any depth, and are recursive by default (an identity declaration's routine body may refer to the identifier being declared). Mutual recursion works when both procedures are declared in the same range.