algol60

3 posts

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.

ALGOL 60 - Language features

ALGOL 60 and the Revised Report

As mentioned in the previous post, ALGOL was designed by an international committee of computer scientists: their goal was to create a universal language for expressing algorithms without recourse to hardware specific features.

The result of their discussions was the ALGOL 60 Report, with a slightly corrected version known as the Revised Report released a few years later. This was one of the first attempts to formally specify a language, using Backus-Naur form (JW Backus and Peter Naur were both on the ALGOL committee).

Representations

ALGOL was intended as a universal language, but at the time of its creation there was no universal character set such as Unicode or even ASCII; as a result, the report defines three representations of the language:

  • A reference language used by the committee in the report to describe ALGOL
  • Publication language, which modifies the reference language for use in handwritten or published documents
  • Hardware representations, which modifies the reference language based on the character set of the hardware it is running on.

An example is the exponentiation operator.

  • In the reference language the upwards facing arrow ↑ is used, eg a ↑ b.
  • In the publication language, superscript is used for the exponent, eg ab.
  • In the hardware representation used by IBM, 'POWER' or ** is used, eg a ** b.

One of the most important differences in representation were basic symbols like begin or end. In the reference and publication language these were usually underlines, eg begin. In many hardware representations, including IBM's, they were enclosed in quotes eg 'BEGIN',

A summary of the differences between the reference language and the IBM hardware representation is shown below; in some cases there is more than once choice for the hardware representation.

Reference   Hardware       Hardware alt  
×           * 
↑           'POWER'        **
÷           '/'
>           'GREATER'      >
<           'LESS'         <  
≤           'NOTGREATER'   <=
≥           'NOTLESS'      >=
≠           'NOT EQUAL'    ¬=
≡           'EQUIV'
⊃           'IMPL'
∧           'AND'          &
∨           'OR'           |
¬           'NOT'
:            :             ..
;            ;             .,
₁₀          '
[           (/
]           /)
‘           '('
’           ')'

The "₁₀" is a scale factor like "E" in the C language, eg 1234 could be expressed as "1.234₁₀3";

In the rest of this post, I will use the reference language in the body text and the IBM hardware representation in the monospaced examples.

Blocks and statements

ALGOL 60 is free format, with statements separated by semicolons. It is possible to group statements into a block, marked by begin and end and optionally labeled. Comments are started with the keyword comment and ended with a ;; this is not needed at the end of blocks.

'COMMENT' Block example;  
'BEGIN'  
    X: 'BEGIN'
        FN1(10);
        FN1(20);
    'END' this is the end of the X block
'END' and this the unnamed block  

Types and variables

ALGOL 60 supports integer, real and Boolean types and variables. There is no restriction in the standard on variable name length, but *ALGOL limits them to six characters. All variables must be declared with their types and variable lifetime is the block. The standard does define a storage class called own, similar to C's static, but this is not supported by the IBM compiler.

The below will print "3 4 3":

'BEGIN'  
    'INTEGER' I, J;
    I := 3;
    OUTINTEGER(1, I);
    'BEGIN'
        'INTEGER' I;
        'BOOLEAN' STATE;
        I := 4;
        OUTINTEGER(1, I);
    'END'
    OUTINTEGER(1, I);
'END'  

Multi-dimensional arrays can be declared, with variable bounds:

'INTEGER' 'ARRAY' A(/-1:+1, M:N/);  
A(/0,15/) := 42;

Strings are supported only as constant parameters to function; it is not possible to declare string variables.

OUTSTRING(1, '('This is a string')');  

Expressions

The usual arithmetic expressions are available; it's possible to include an if/else in such expressions. Unusually, Boolean expressions include operators for implies and equivalent.

'BEGIN'  
    'INTEGER' X, Y;
    'BOOLEAN' A, B;
    X := 3;
    Y := 4;
    A := 'TRUE';
    B := 'FALSE';
    OUTINTEGER(1, X + Y - ('IF' A 'OR' B 'THEN' 1 'ELSE' 2));
'END'  

The above will print 6.

Control statements

As well as the regular goto statement, the switch statement allow selection of a statement label to jump to.

if ... then ... else can be used for conditional execution. Another if cannot follow the then unless it is contained in a block. to prevent ambiguity of which if then else is attached to.

The for statement is used for repetition: there are three forms:

'BEGIN'  
    'INTEGER' J;
    'FOR' J := 1, 2, 3 'DO' OUTINTEGER(1, J);
    'FOR' J := 10 'STEP' 5 'UNTIL' 20 'DO' OUTINTEGER(1, J);
    'FOR' J := 100, J*2 'WHILE' J 'LESS' 500 'DO' OUTINTEGER(1, J);
'END'  

This will print

  • 1, 2, 3
  • 10, 15, 20
  • 100, 200, 400

Procedures

Procedures support pass by value or pass by name parameters. Pass by value is familiar: a copy is made of the parameter for those identified with value in the procedure preamble. The following will print 42:

'BEGIN'  
    'INTEGER' 'PROCEDURE' ADD2(X, Y);
    'VALUE' X, Y;
    'INTEGER' X, Y;
    'BEGIN'
        ADD2 := X + Y;
    'END'

    OUTINTEGER(1, ADD2(20, 22));
'END'  

Pass by name is similar to pass by reference in C++ or Java in that it allows output to be made to parameters; it also enables Jensen's device. Take for example the below:

'BEGIN'  
    'PROCEDURE' INC(A, B);
    'INTEGER' A, B;
    'BEGIN'
        A := A + 1;
        B := B + 1;
    'END'

    'INTEGER' 'ARRAY' X(/10/);
    'INTEGER' J;

    X(/1/) := 10;
    X(/2/) := 20;

    J := 1;
    INC(J, X(/J/));

    OUTINTEGER(1, J);
    OUTINTEGER(1, X(/2/));
'END'  

This will print 2 (as J has been incremented by the line A := A + 1) and 21 (as X[J] was passed in by name, it was evaluated as X[2] in the line B := B + 1).

Standard functions and input/output

There are a small number of standard functions defined by the language, mostly mathematical (eg ABS, SIGN, SQRT, SIN, LN). The ENTIER function accepts a real number as parameter and returns an integer.

No input/output functions are defined at all in the standard, due to the desire for the language to be device independent and as at the time there was no common agreement of what input/output facilities could be provided across all available hardware. The IBM compiler provides PUT and GET for low level I/O, SYSACT for stream manipulation and a number of functions for input or output of variables, eg ININTEGER, OUTREAL.

Further information

The Revised Report on the Algorithmic Language Algol 60 is the standard for the language. Donald Knuth wrote an article on the remaining troublespots in ALGOL 60 on some of the ambiguities in the standard.

The original IBM documentation for the compiler contains most of the text of the Revised Report annotated with examples using IBM's representation.

Updated 6-Feb-2015 to fix comment syntax

ALGOL 60 - Introduction

In this series of posts we'll look at ALGOL, one of the foundational languages for modern programming, and the ALGOL 60 implementation on MTS.

The ALGOL family of languages and ALGOL 60

Most programming languages spring from a single person or a company; ALGOL is fairly unique in that it was originally designed by a committee of European and American computer scientists in the mid 1950s. The first version to be widely implemented was ALGOL 60, which is what we will look at here. A large number of improvements to ALGOL 60 were proposed or developed: one, by Niklaus Wirth, became ALGOL W. The next standardised version was ALGOL 68 but this was not widely adopted.

Although it is not in wide use today, ALGOL introduced many influential concepts to programming languages, such as block scoping, so can be considered the ancestor of languages such as Pascal and C.

ALGOL 60 on MTS

The ALGOL compiler provided by IBM for S/360 machines is available on MTS under the name *ALGOL. This follows the ALGOL 60 specification fairly closely. A number of small changes were made to the compiler to make it work under MTS.

There are also ALGOL W and ALGOL 68 compilers on MTS, the former being the most popular version in use at the time of D6.0; I will look at these in later posts.

Prerequisites

No special installation instructions to get ALGOL 60 running - just do the standard D6.0 setup as described in this guide and then sign on as a regular user such as ST01.

Compiling using *ALGOL

*ALGOL will read source from scards (by default *source* ie standard input) and will write object files to spunch. Unlike some other MTS compilers you need to provide a filename for spunch as there is no default.

One gotcha is that *ALGOL will not clear out the file used for writing object code, so you need to run $empty on it before recompiling each time.

Other *ALGOL compilation parameters are listed in MTS Volume 2X.

To run ALGOL 60 programs you need to concatenate the runtime library *ALGOLLIB with the object file. Say your object code is in the file -load then to run it you would do:

# $run -load+*algollib

Hello world

Here's a simple program to print "Hello, world!" five times.

'BEGIN'  
'COMMENT' Hello World program for ALGOL 60;  
    'INTEGER' I;
    'FOR' I := 1 'STEP' 1 'UNTIL' 5 'DO'
    'BEGIN'
         OUTSTRING(1, '('Hello, world!')');
         SYSACT(1, 14, 1);
    'END'
'END'  

Indentation is not important except to make the program readable. Note the quotation marks around keywords like 'INTEGER' to distinguish them from identifiers: this is known as stropping.

OUTSTRING and SYSACT are not part of ALGOL 60 but are library functions provided by IBM; the SYSACT call here is used to start a new line on the output device.

Here's a terminal log of how to compile and run the program. This assumes the source code is in file hello.al.

# $run *algol scards=hello.al spunch=-load
 i
  LEVEL 1JUL67                            OS ALGOL F                       DATE  JAN 11 1915
                                       SOURCE PROGRAM                               PAGE 001
   SC     SOURCE STATEMENT
  00000   'BEGIN' 
  00000       'COMMENT' Hello World program for ALGOL 60; 
  00000       'INTEGER' I;
  00001       'FOR' I := 1 'STEP' 1 'UNTIL' 5 'DO'
  00001       'BEGIN'
  00001           OUTSTRING(1, '('Hello, world!  ')');
  00002           SYSACT(1, 14, 1);
  00003       'END'
  00003   '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      I      I        018
 i
                                   STORAGE REQUIREMENTS (DECIMAL)                   PAGE 003

  OBJECT MODULE SIZE 540 BYTES.
  DATA STORAGE AREA SIZES
    PBN   BYTES       PBN   BYTES       PBN   BYTES       PBN   BYTES       PBN   BYTES
    001      48

# $run -load+*algollib
 Hello, world!
 Hello, world!
 Hello, world!
 Hello, world!
 Hello, world!

 END OF ALGOL PROGRAM EXECUTION

If you change the source file and want to recompile, remember to do %empty -load.

Further information

As always, the Wikipedia page provides a good overview of the language's history and key features.

There is no MTS Volume on ALGOL 60 (there is one on ALGOL W, however). Some information on the *ALGOL compiler and *ALGOLLIB library can be found in the MTS Volume on obsolete commands.

The original IBM documentation for the compiler can be found at Bitsavers.

Updated 6-Feb-2015 to fix comment syntax.