PL/I - Radix sort

For the final part of this series on the PL/I programming language as implemented on MTS, let’s implement radix sort from Rosetta Stone.

The problem

Radix sort is intended as a fast way to sort an array of integers by grouping them by digits that share the same value. Digits can be defined depending on the numeric base and the sort can take place from either the most significant digit or the least. Here we’ll sort by most significant digit and use base 2. so we are comparing by bits.

The algorithm we’ll use sorts in place. Starting at the largest bit it will group the numbers into one range where the bit is 1 and another where it is 0 by swapping values in the array. It will then recursively sort each range by the next smallest bit.

The solution

Here’s how the implementation looks; this was based on the C version at Rosetta Code.

RADIX_SORT: PROCEDURE(FROM, TO, BIT, ARR) RECURSIVE;
  DECLARE (FROM, TO) FIXED DECIMAL;
  DECLARE BIT FIXED BINARY(16);
  DECLARE ARR(*) FIXED BINARY(16);

  DECLARE (LEFT, RIGHT) FIXED DECIMAL;
  DECLARE TEMP FIXED BINARY(16);

  /* Exit early if bit down to zero or range is zero */
  IF (BIT = 0) | (TO <= FROM) THEN RETURN;

  LEFT = FROM;
  RIGHT = TO;

  LOOP:
  /* Find the leftmost with the bit set */
  DO WHILE ((LEFT < RIGHT) & ((ARR(LEFT) & BIT) = 0));
    LEFT = LEFT + 1;
  END;

  /* Find the rightmost with the bit not set */
  DO WHILE ((LEFT < RIGHT) & ((ARR(RIGHT) & BIT) ¬= 0));
    RIGHT = RIGHT - 1;
  END;

  /* If found one of each, swap and loop again to look for more */
  IF LEFT < RIGHT THEN BEGIN;
    TEMP = ARR(LEFT);
    ARR(LEFT) = ARR(RIGHT);
    ARR(RIGHT) = TEMP;
    GO TO LOOP;
  END;

  /* If nothing found, make the first sub search do the full range */
  IF ((BIT & ARR(LEFT)) = 0) & (LEFT <= TO) THEN
    LEFT = LEFT + 1;

  /* The two ranges bounded by LEFT are now sorted by BIT.
   * Sort each range by the next least significant bit */
  BIT = BIT / 2;
  CALL RADIX_SORT(FROM, LEFT-1, BIT, ARR);
  CALL RADIX_SORT(LEFT, TO, BIT, ARR);
END RADIX_SORT;

The definition of the function is marked as RECURSIVE, similar to other languages like ALGOL, as otherwise calling the function from itself will not work.

We pass in an array of fixed point numbers of up to 16 bits in length with the dimensions of the array bounded by FROM and TO. The initial call will set BIT to be 2^15. To handle an array of any size we can use * in the declaration DECLARE ARR(*) FIXED BINARY(16);.

Although PL/I has logical operators - and is &, or is |, not is ¬ - it does not seem to have the Boolean not operator like ! in C, so we have to write (ARR(LEFT) & BIT) = 0 rather than something like ! (ARR(LEFT) & BIT).

We’ll also need a procedure to print the array which will be called before and after the sort.

SHOW_ARR: PROCEDURE(LABEL, ARR);
  DECLARE LABEL CHARACTER(80) VARYING;
  DECLARE ARR(*) FIXED BINARY(16);
  PUT FILE (SCARDS) LIST(LABEL);
  PUT FILE (SCARDS) SKIP;
  PUT FILE (SCARDS) LIST(ARR);
  PUT FILE (SCARDS) SKIP;
END SHOW_ARR;

Finally, we set up the main function

TEST: PROCEDURE OPTIONS(MAIN);
  DECLARE RADIX_SORT ENTRY (FIXED DECIMAL, FIXED DECIMAL,
                            FIXED BINARY(16),);

  DECLARE NUMS(10) FIXED BINARY(16);
  NUMS(1) = 3;       NUMS(6) = 1630;
  NUMS(2) = 42;      NUMS(7) = 4;
  NUMS(3) = 910;     NUMS(8) = 2721;
  NUMS(4) = 3241;    NUMS(9) = 684;
  NUMS(5) = 99;      NUMS(10) = 11;

  CALL SHOW_ARR('Before', NUMS);
  CALL RADIX_SORT(1, 10, 1000000000000000B, NUMS);
  CALL SHOW_ARR('After', NUMS);

  /* Definition of RADIX_SORT and SHOW_ARR follow inside TEST here. */
END TEST;

Note that we need to declare the signature of RADIX_SORT before we use it.

We can now compile and run the program.

# $run *pl1f scards=radix.pl1 spunch=-load
# Execution begins   20:03:01 

  PROCEDURE TEST: SYNTAX CHECK COMPLETED. COMPILATION CONTINUES.


   NO ERRORS OR WARNINGS DETECTED.
# Execution terminated   20:03:02  T=0.128 

# $run -load+*pl1flib
# Execution begins   20:03:03 
  'Before' 
          3        42       910      3241        99      1630         4      2721
        684        11 
  'After' 
          3         4        11        42        99       684       910      1630
       2721      3241 
   
# Execution terminated   20:03:03  T=0.003

Final thoughts about PL/I

To a C programmer, PL/I appears the most familiar of the languages we’ve seen so far, from the comments style and semicolon as line terminators to the storage classes and system level access, but with a more ALGOLy syntax. Writing the above I certainly found it expressive and easy to use, but it lacks even the minimal type checking found in C and I wasn’t quite sure what conversions were going on behind the scenes.

In its historical context, PL/I never really took off - it was tough to implement a compiler and too much identified with IBM to be adopted widely. It was important in the development of MULTICS and it nearly had a renaissance when it was made available for OS/2 in the 1990s, but ultimately it did not gain enough adoption from programmers to be truly successful.

For MTS at UM, according to the Introduction to programming and debugging in MTS, it was the third most popular language (8% by frequency of use) in 1984, but way behind FORTRAN and PASCAL. It would be interesting to know what types of users it had - teaching, business or scientific research? It does not seem to have been used by MTS system programmers much, going by the lack of components in PL/I on the D6.0 tapes.

Further information

Full source code for this program is on github.

Go back to the first article in the series on PL/I or see the other languages being looked at.

Comments

comments powered by Disqus