For our ALGOL 60 sample program we'll have a quick look at implementing a solution to the Josephus 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.
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
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.
Full source code for this program is on github.