For our ALGOL 60 sample program we'll have a quick look at implementing a solution to the Josephus problem.

The problem

Imagine n prisoners standing in a circle, numbered sequentially from 0 to n-1. An executioner walks around the circle, starting at prisoner 0, and kills every kth prisoner, removing them from the circle. As this continues, the circle becomes smaller and smaller; the last prisoner remaining is freed.

An example for n=11 prisoners and k=3. Prisoners 2, 5 and 8 will be killed on the first trip round the circle. On the second trip, it's goodbye to prisoners 0, 4 and 9. Continuing this leaves prisoner 6 as the survivor.

The task, given any n and k (both which should be greater than zero), find the prisoner who is freed.

See Rosetta Code for a full description and sample code in other languages.

Solution

There's a fairly simple iterative solution to the main function to determine the last survivor:

    'COMMENT' Find surviving prisoner from circle of N;
    'COMMENT' after killing each Kth prisoner;
    'INTEGER' 'PROCEDURE' JOSEPHUS(N, K);
    'VALUE' N, K;
    'INTEGER' N, K;
    'BEGIN'
        'INTEGER' INDEX, PRISONER;
         PRISONER := 0;
        'FOR' INDEX := 1 'STEP' 1 'UNTIL' N 'DO'
        'BEGIN'
            JOSEPHUS := PRISONER := MODULUS(PRISONER + K, INDEX);
        'END'
    'END'

It would seem that we could just use JOSEPHUS as the variable and not need PRISONER but ALGOL only allows return value variables to appear on the left hand side of an expression.

Next, we need to define the MODULUS function to give the remainder after dividing two integers

    'COMMENT' Finds the remainder of X and Y for positive values;
    'INTEGER' 'PROCEDURE' MODULUS(X, Y);
    'VALUE' X, Y;
    'INTEGER' X, Y;
    'BEGIN'
        MODULUS := X - (Y * (X '/' Y));
    'END'

Note that we use the integer division operator ÷ (written as '/' in the IBM hardware representation) as the regular division operator / on integers will round either up or down depending on the value.

Finally, for the main program we can call the JOSEPHUS function and output the integer result: we use 41 prisoners and k=3:

'BEGIN'  
    'COMMENT' Main program;
    OUTINTEGER(1, JOSEPHUS(41, 3));
'END'  

So writing this was fairly easy. Quoting all keywords still feels unnatural so I normally put them in after writing out the program in full. I had to look up the difference between the two division operators but expressing the main flow was simple. What tripped me up on first compile was the comment syntax: I was using COMMENT abc which the compiler appeared to accept but would sometimes swallow the next line. Fixing this to quote the COMMENT and terminate the line with a semicolon fixed this (eg 'COMMENT' abc;).

Running the solution

Let's see how this looks when we compile and run the program. Don't forger to destroy or empty the output object file first otherwise you will get strange results after each recompile.

# $destroy -load
 File "-LOAD" has been destroyed.

# $run *algol scards=josephus.al spunch=-load
Execution begins   21:39:02  
 i
  LEVEL 1JUL67                            OS ALGOL F                       DATE  FEB 05 1915
                                       SOURCE PROGRAM                               PAGE 001
   SC     SOURCE STATEMENT
  00000   'BEGIN'
  00000       'COMMENT' Finds the remainder of X and Y for positive values;
  00000       'INTEGER' 'PROCEDURE' MODULUS(X, Y);
  00001       'VALUE' X, Y;
  00002       'INTEGER' X, Y;
  00003       'BEGIN'
  00003           MODULUS := X - (Y * (X '/' Y));
  00004       'END'
  00004
  00004       'COMMENT' Find surviving prisoner from circle of N;
  00005       'COMMENT' after killing each Kth prisoner;
  00005       'INTEGER' 'PROCEDURE' JOSEPHUS(N, K);
  00006       'VALUE' N, K;
  00007       'INTEGER' N, K;
  00008       'BEGIN'
  00008           'INTEGER' INDEX, PRISONER;
  00009            PRISONER := 0;
  00010           'FOR' INDEX := 1 'STEP' 1 'UNTIL' N 'DO'
  00010           'BEGIN'
  00010               JOSEPHUS := PRISONER := MODULUS(PRISONER + K, INDEX);
  00011           'END'
  00011       'END'
  00011
  00011       'COMMENT' Main program;
  00012       OUTINTEGER(1, JOSEPHUS(41, 3));
  00013   'END'
 i
                                       IDENTIFIER TABLE                             PAGE 002
  PBN SC    PBN      NAME   TYPE  DM DSP       NAME   TYPE  DM DSP       NAME   TYPE  DM DSP
            SURR                  PR LN                     PR LN                     PR LN

  001 00000 000      JOSEPH I P   02 074       MODULU I P   02 070

  002 00000 001      MODULU I P   02 070       X      I  V     020       Y      I  V     028

  003 00005 001      INDEX  I        030       JOSEPH I P   02 074       K      I  V     028
                     N      I  V     020       PRISON I        034
 i
                                   STORAGE REQUIREMENTS (DECIMAL)                   PAGE 003

  OBJECT MODULE SIZE 840 BYTES.
  DATA STORAGE AREA SIZES
    PBN   BYTES       PBN   BYTES       PBN   BYTES       PBN   BYTES       PBN   BYTES
    001      36       002      48       003      68
Execution terminated   21:39:02  T=0.016

# $run -load+*algollib
Execution begins   21:39:10  
         +30



 END OF ALGOL PROGRAM EXECUTION

Execution terminated   21:39:10  T=0.003  

We can see in the compiler identifier table output that although we can use long identifiers they are truncated to six characters.

Final thoughts on ALGOL 60

There's a lot to like in ALGOL 60: the language definition is more precise than the informal descriptions used before; the block structure and variable scoping; the powerful control statements. As a programmer with a C background it appears much more familiar then FORTRAN.

However it does feel like an interim release rather than a fully developed language; I think this is partially due to its academic origins rather than from a computer company looking to sell its hardware. The different language representations and call-by-name are a bit too clever and the emphasis on machine independence went too far - the lack of any I/O means that no useful program could be portable. Another factor not evident when running MTS today is that the FORTRAN development environment and compilers are much more advanced so for any computationally expensive workload you would have been better off with FORTRAN.

With the experience of implementing compilers in ALGOL 60, the group responsible for the original report looked at what changes should be made for the next version of ALGOL. In the next post I'll look at one of these, ALGOL W.

Further information

Full source code for this program is on github.