MAD - Mergesort

For our sample program in MAD, let’s look at a classic sorting algorithm, mergesort.

The task

The task description and pseudo-code can be found at Rosetta Code.

The implementation

Let’s write this as two parts: a driver program to set up a vector of integers and the actual function to do mergesort. The mergesort function should be able to take any vector size as input.

The driver

For the driver we’ll just define a vector of integers and call the mergesort function. We could extend this to read the integers from a file if needed. We’ll also need a way to display the vector before and after the sort, which we’ll factor into a separate internal function.

     CONSTANT LENGTH = 15
     VECTOR VALUES NUMBERS = 9, 12, 3, 1, 6, 8, 2, 5, 14, 13, 11, 7, 10, 4, 0

     PRINT COMMENT "Before sort"
     DISPLAY.(NUMBERS, LENGTH)

     MERGESRT.(0, LENGTH, NUMBERS)

     PRINT COMMENT "After sort"
     DISPLAY.(NUMBERS, LENGTH)

*    Display each value in V
     INTERNAL FUNCTION DISPLAY.(V, LEN)
          INTEGER V(1), LEN
          LOOP FOR I=0, 1, I >= LEN
               PRINT RESULTS V(I)
          END LOOP
          FUNCTION RETURN
     END OF FUNCTION

     END OF PROGRAM

The mergesort function

The mergesort function is recursive, so we need to use an external function with the RECURSIVE keyword to signal this fact to the MAD compiler so it can set up a dynamic call stack. If we don’t do this, the program will still compile but will die with a protection exception when run.

     RECURSIVE EXTERNAL FUNCTION MERGESRT.(LEFT, RIGHT, V)
          INTEGER LEFT, RIGHT, V(1)
          INTEGER LSTART, LEND, RSTART, REND

*         Return if nothing left to sort
          IF (RIGHT - LEFT <= 1)
               FUNCTION RETURN
          END IF

*         Define left and right halves
          LSTART = LEFT
          LEND = (LEFT + RIGHT) / 2
          RSTART = LEND
          REND = RIGHT

*         Recursively sort left and right
          MERGESRT.(LSTART, LEND, V)
          MERGESRT.(RSTART, REND, V)

*         Merge two halves
          MERGE.(LSTART, LEND, RSTART, REND, V)
          FUNCTION RETURN
*         Merge function definition will go here; see below
     END OF FUNCTION
     END OF PROGRAM

Note that we define V as having length 1: this is to allow us to subscript V, but it’s up to us to manage its actual length.

External functions need an END OF PROGRAM as well, as they are effectively compiled separately from the main routine even if they are in the same file.

Next we need the merge subroutine. As this is private to MERGESRT., we can define it as an internal function of MERGESRT.: the definition can go inside the external function definition as shown above. The code looks like this.

          INTERNAL FUNCTION MERGE.(LSTART, LEND, RSTART, REND, V)
               INTEGER LSTART, LEND, RSTART, REND, V(1)
               INTEGER LLEN, RLEN, I, L, R
               POINTER LHALF, RHALF, LHP, RHP
               CONSTANT SZ = 4

*              Allocate a temp buffer for each half
               LLEN = LEND - LSTART
               RLEN = REND - RSTART
               ALLOCATE (LLEN * SZ)->LHALF
               ALLOCATE (RLEN * SZ)->RHALF

*              Copy values into temporaries
               LHP = LHALF
               LOOP FOR I=LSTART, 1, I >= LEND
                    LHP.IND.INTEGER = V(I)
                    LHP = LHP + SZ
               END LOOP
               RHP = RHALF
               LOOP FOR I=RSTART, 1, I >= REND
                    RHP.IND.INTEGER = V(I)
                    RHP = RHP + SZ
               END LOOP

*              Merge values back into V
               L = 0
               R = 0
               LHP = LHALF
               RHP = RHALF
               LOOP FOR I=LSTART, 1, L >= LLEN .OR. R >= RLEN
*                   If left < right, move left, else move right
                    IF (LHP.IND.INTEGER < RHP.IND.INTEGER)
                         V(I) = LHP.IND.INTEGER
                         L = L + 1
                         LHP = LHP + SZ
                    ELSE
                         V(I) = RHP.IND.INTEGER
                         R = R + 1
                         RHP = RHP + SZ
                    END IF
               END LOOP

*              Handle leftover values
               LOOP WHILE L < LLEN
                    V(I) = LHP.IND.INTEGER
                    I = I + 1
                    L = L + 1
                    LHP = LHP + SZ
               END LOOP
               LOOP WHILE R < RLEN
                    V(I) = RHP.IND.INTEGER
                    I = I + 1
                    R = R + 1
                    RHP = RHP + SZ
               END LOOP

               RELEASE LHALF
               RELEASE RHALF
               FUNCTION RETURN
          END OF FUNCTION

We need a temporary buffer to hold each half of V while merging. MAD does not allow run time dimensioning of vectors, so we can either make these fixed size or use dynamic memory. I’ve chosen the latter to make the solution more generic: we allocate a chunk of memory which is determined by the size of each half and SZ which is a constant denoting the size of a MAD integer in bytes:

               ALLOCATE (LLEN * SZ)->LHALF

We then use pointer arithmetic to read or write integers, eg

                    RHP.IND.INTEGER = V(I)
                    RHP = RHP + SZ

At the end of the function we must remember to free the allocated memory with RELEASE.

Putting it together

We’re now ready to compile and run the program.

# $run *gom scards=mergesrt.mad
  No errors in MAIN 
  No errors in MERGESRT
  No errors in MAIN 
# $run -load
  Before sort

  NUMBERS(0)      =           9 
  NUMBERS(1)      =          12 
  NUMBERS(2)      =           3 
...
  NUMBERS(12)     =          10 
  NUMBERS(13)     =           4 
  NUMBERS(14)     =           0 

  After sort

  NUMBERS(0)      =           0 
  NUMBERS(1)      =           1 
  NUMBERS(2)      =           2 
...
  NUMBERS(12)     =          12 
  NUMBERS(13)     =          13 
  NUMBERS(14)     =          14 

Final thoughts on MAD

Given that it was first designed at about the same time as FORTRAN, MAD feels much more powerful and flexible to use, while still having an easily understandable syntax, by borrowing ideas from early discussions of ALGOL/IAL. It’s a pity it did not see wider adoption as it might have made FORTRAN programmer’s lives easier.

The introduction to the GOM manual has an interesting section on why it was re-implemented for MTS:

This language is currently known as GOM (for Good Old MAD) to distinguish it from the ill-fated MAD/1 which was designed as an extensible language and which, although it provided many ideas which have been borrowed, was incredibly ugly and never extended itself into usability.

Why at this point in time resurrect the language? The main impetus was that a language was needed for writing Grungy Little Programs and pieces of the operating system. In both cases, the programs are often machine-dependent, and require matching previously established data structures and interfaces that are not “standard”, in the sense of being used by most high-level languages. Fortran is not usually general enough, and PL1 suffers from its “environment” and in many cases is not general enough either.

Rather than invent a new language, MAD was chosen as a base because it provided a happy medium between the insufficiencies of Fortran and the excesses of PL1, and because the semantic implications of the various constructs were known. That did not, however, prevent judicious tailoring of the language to better fit the current programming practices and problems.

Further information

Full source code for this program is on github.

Comments

comments powered by Disqus