ALGOL 60 - Josephus problem
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.