Functions in ALGOL 60

Introduction

In ALGOL 60 the unit of reusable code is the procedure. A procedure groups statements under a name so they can be called as many times as you like. ALGOL 60 draws a small but important distinction:

• A proper procedure performs an action and returns no value. You declare it with procedure. This is the ancestor of a void function in C or a void method in Java.
• A function procedure (or typed procedure) returns a value. You declare it with a type in front, such as integer procedure or real procedure. It hands a result back by assigning to its own name.

ALGOL 60 was one of the first languages to treat procedures as a fully general tool. It introduced two ideas that were revolutionary in 1960 and are now everywhere: genuine recursion (a procedure may call itself) and strict lexical scoping (a name refers to the declaration that textually encloses its use). It also kept one idea that is almost unique to ALGOL 60 - call-by-name parameters, where the actual argument expression is re-evaluated every time the parameter is touched.

This tutorial defines and calls procedures, returns values, recurses, nests procedures, and finishes with ALGOL 60’s signature call-by-name mechanism. Every example runs with GNU MARST exactly like the Hello World program.

A First Function and a Proper Procedure

A function procedure returns its result by assigning to its own name - there is no return keyword. Parameters listed in the value part are passed by value (copied), which is what you want for ordinary numeric arguments.

Create a file named functions.alg:

begin
  comment A typed procedure returns a value by assigning to its own
  name. square and cube are integer-valued functions;
  integer procedure square(n);
    value n; integer n;
  square := n * n;

  integer procedure cube(n);
    value n; integer n;
  cube := n * n * n;

  comment A real-valued function. Listing a, b in the value part
  means they are passed by value (copied);
  real procedure average(a, b);
    value a, b; real a, b;
  average := (a + b) / 2;

  comment A proper procedure performs an action but returns no value;
  procedure showpower(base);
    value base; integer base;
  begin
    outstring(1, "base ");
    outinteger(1, base);
    outstring(1, "squares to ");
    outinteger(1, square(base));
    outstring(1, "and cubes to ");
    outinteger(1, cube(base));
    outstring(1, "\n")
  end;

  showpower(2);
  showpower(5);
  outstring(1, "average of 10.0 and 7.0 is ");
  outreal(1, average(10.0, 7.0));
  outstring(1, "\n")
end

A few things to notice:

• The procedure heading lists the parameter names, then a separate specification part gives each parameter a type (integer n;, real a, b;). The optional value part names the parameters that are copied.
• A short body can be a single statement (square := n * n); a longer body is a begin ... end block, as in showpower.
• square and cube are called inside showpower, showing that procedures freely call one another.

A note on number spacing: MARST’s outinteger and outreal always print the number followed by a single space, while outstring prints text exactly as given. That trailing space conveniently separates each number from the next word, so the lines below read naturally.

Recursion

ALGOL 60 was the first widely known language to allow a procedure to call itself. The classic demonstration is the factorial function.

Create a file named recursion.alg:

begin
  comment Recursion - a procedure calling itself - was a landmark
  feature of ALGOL 60. Here factorial calls factorial;
  integer procedure factorial(n);
    value n; integer n;
  if n <= 1 then
    factorial := 1
  else
    factorial := n * factorial(n - 1);

  integer i;
  for i := 1 step 1 until 6 do
  begin
    outstring(1, "factorial of ");
    outinteger(1, i);
    outstring(1, "is ");
    outinteger(1, factorial(i));
    outstring(1, "\n")
  end
end

The body of factorial is a single if ... then ... else statement. When n reaches the base case (n <= 1) the procedure stops recursing and the chain of multiplications unwinds: factorial(6) becomes 6 * 5 * 4 * 3 * 2 * 1.

Scope and Nested Procedures

ALGOL 60 procedures may be declared inside other procedures, and inner procedures can see the variables of the block that encloses them. This is lexical scoping: a name refers to the nearest enclosing declaration of that name. Variables declared inside a procedure are local - they exist only while that procedure runs and are invisible from the outside.

Create a file named scope.alg:

begin
  comment Procedures may be nested. inner is declared inside outer
  and is visible only there. Through lexical scoping inner can read
  outer's local variable base;
  procedure outer(n);
    value n; integer n;
  begin
    integer base;

    integer procedure inner(k);
      value k; integer k;
    inner := base + k;

    base := n * 10;
    outstring(1, "with base ");
    outinteger(1, base);
    outstring(1, "inner(2) returns ");
    outinteger(1, inner(2));
    outstring(1, "\n");
    outstring(1, "inner(7) returns ");
    outinteger(1, inner(7));
    outstring(1, "\n")
  end;

  outer(5)
end

Here inner reads base, a local variable of outer, without base being passed as a parameter. Because base and inner are both local to outer, neither name exists in the outer program block - try to use them there and the translator reports an undeclared identifier.

Call-by-Name: ALGOL 60’s Signature Feature

By default, an ALGOL 60 parameter that is not listed in the value part is passed by name. Instead of copying the argument once, the procedure substitutes the actual argument expression wherever the parameter appears and re-evaluates it on every use. When the argument is itself a variable, assigning to the parameter assigns to that variable.

This enables a famous trick known as Jensen’s device: pass a loop variable and an expression built from it, both by name, to a general summation procedure.

Create a file named callbyname.alg:

begin
  comment Call-by-name is ALGOL 60's signature parameter mechanism.
  A formal parameter that is NOT in the value part is passed by name:
  the actual argument expression is re-evaluated on every use;

  real procedure sum(i, lo, hi, term);
    value lo, hi;
    integer i, lo, hi; real term;
  begin
    real s;
    s := 0;
    for i := lo step 1 until hi do
      s := s + term;
    sum := s
  end;

  integer k;

  comment k and the expression k*k are passed by name. Each time the
  loop assigns to i (which is really k), term is recomputed;
  outstring(1, "sum of k for k=1..10 is ");
  outreal(1, sum(k, 1, 10, k));
  outstring(1, "\n");
  outstring(1, "sum of k*k for k=1..4 is ");
  outreal(1, sum(k, 1, 4, k * k));
  outstring(1, "\n")
end

Inside sum, the parameter i is bound by name to the global variable k, so the loop for i := lo step 1 until hi actually drives k. The parameter term is bound by name to the expression k * k, which is therefore recomputed with the current k on every iteration. A single sum procedure can add up any series you can write as an expression - no need to write a new loop each time. Only lo and hi are passed by value, since they are fixed bounds.

Running with Docker

Use the same GNU MARST image as the rest of this series. Pull it once:

1

docker pull codearchaeology/algol60:latest

Then compile and run each example with algol60-run:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

# A first function and a proper procedure
docker run --rm -v $(pwd):/app -w /app codearchaeology/algol60:latest algol60-run functions.alg

# Recursion
docker run --rm -v $(pwd):/app -w /app codearchaeology/algol60:latest algol60-run recursion.alg

# Scope and nested procedures
docker run --rm -v $(pwd):/app -w /app codearchaeology/algol60:latest algol60-run scope.alg

# Call-by-name (Jensen's device)
docker run --rm -v $(pwd):/app -w /app codearchaeology/algol60:latest algol60-run callbyname.alg

Expected Output

functions.alg:

base 2 squares to 4 and cubes to 8
base 5 squares to 25 and cubes to 125
average of 10.0 and 7.0 is 8.5

recursion.alg:

factorial of 1 is 1
factorial of 2 is 2
factorial of 3 is 6
factorial of 4 is 24
factorial of 5 is 120
factorial of 6 is 720

scope.alg:

with base 50 inner(2) returns 52
inner(7) returns 57

callbyname.alg:

sum of k for k=1..10 is 55
sum of k*k for k=1..4 is 30

Key Concepts

• Two kinds of procedure: procedure declares a proper procedure that returns no value; prefixing a type (integer procedure, real procedure) declares a function that returns a value.
• Returning a value: a function procedure has no return statement - it assigns the result to its own name, e.g. factorial := n * factorial(n - 1).
• Parameter specification: the heading lists parameter names, and a separate specification part types them (integer n;, real a, b;).
• Pass by value vs. by name: parameters named in the value part are copied; any parameter left out of the value part is passed by name and its argument expression is re-evaluated on every use.
• Recursion is fully supported - a procedure may call itself, which ALGOL 60 pioneered for mainstream languages.
• Lexical scope and nesting: procedures can be declared inside other procedures, and inner code sees the variables of the enclosing block; variables declared inside a procedure are local to it.
• Jensen’s device: passing a control variable and an expression by name lets one generic procedure (like sum) evaluate many different series - a hallmark of ALGOL 60’s expressive parameter model.
• Output formatting: outinteger and outreal print the number followed by a space; outstring prints text verbatim - keep this in mind when laying out a line.