mad

3 posts

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.

MAD - Language features

In this post we'll look at the MAD language (as implemented by GOM on MTS) in more detail. As MAD is quite a large language, compared to FORTRAN or BASIC, I will only go over some of its interesting or unusual features; for a good overview of the language you may want to read the Wikipedia article first.

Complete examples below (those ending with END OF PROGRAM) have been tested using *GOM on MTS D6.0; do note that initial blanks are needed for lines which do not contain statement labels.

Synonyms and abbreviations

There are a number of synonyms for MAD keywords, (eg TRANSFER TO for GO TO, and spaces are not generally needed. For example a goto label X could be expressed as:

GOTO X  
GO TO X  
TRANSFER TO X  
TRANSFERTOX  

GOTOX would not work as this is ambiguous, as it could be a references to the variable GOTOX. The TRANSFERTOX works as this is longer than a variable name could be.

Keywords can be abbreviated by taking the first and last letter and inserting a ': for example T'O for TRANSFER TO'. The compiler can optionally produce a listing of the input with these expanded by setting the sprint parameter.

Constant qualification

Constants can be qualified to a particular type or format with a suffix: some examples

  • 1B - Boolean true
  • 100@X - hex integer 100, ie decimal 256.
  • 12@L1 - one byte integer
  • "HI"@L4 - character string of length 4, right padded with blanks

Statement label vectors

As well as simple labels as seen in FORTRAN, you can have vectors of statement labels. For example, the below will print "Two":

     INTEGER J
     J = 2
     GOTO L(J)
L(1) PRINT COMMENT "One"  
     GO TO DONE     
L(2) PRINT COMMENT "Two"  
     GO TO DONE     
L(3) PRINT COMMENT "Three"  
DONE END OF PROGRAM  

Conversions

MAD does implicit conversions by assigning to a variable of different type. You can cast to another type without conversion using .AS.

     INTEGER IM, C1, C2
     FLOATING POINT F
     F = 123.45
     IM = F
     C1 = F.AS.INTEGER
     C2.AS.FLOATING POINT = F
     PRINT RESULTS IM, C1, C2
     END OF PROGRAM

This will print:

     IM = 123  C1 =  1115386675  C2 =  1115386675

Character expressions and strings

Strings are expressed as character vectors; sub-elements of a vector can be addressed using block notation, with ... standing for range, with optional first and last subscript, and | for length. For example:

     CHARACTER HELLO(5),H1(3),H2(2)
     HELLO(...) = "Hello"
     H1(...) = HELLO(2...4)
     H2(...) = HELLO(1|2)
     PRINT COMMENT H1
     PRINT COMMENT H2
     END OF PROGRAM

Will print "llo" and "el".

Conditionals

The conditional statement allows else clauses and there is an implicit block structure for each clause:

     INTEGER X
     X = 3
     IF X > 1 .AND. X <= 3
          PRINT COMMENT "Yes"
          PRINT RESULTS X
     ELSE
          PRINT COMMENT "No"
     END IF
     END OF PROGRAM

Loops

As we saw in the hello world example, the basic loop takes an initial variable, increment and condition which when true will mark the end of the loop. So the below will print "Hello, world!" five times

     LOOP FOR I=1, 1, I > 5
          PRINT COMMENT "Hello, world!"
     END LOOP
     END OF PROGRAM

There is also a THROUGH variant which is more like a FORTRAN loop: this will print "Hi" and "There" five times then "Done".

     THROUGH L, FOR I=1,1,I>5
     PRINT COMMENT "Hi"
L    PRINT COMMENT "There"  
     PRINT COMMENT "Done"
     END OF PROGRAM

and a LOOP WHILE b and LOOP UNTIL b which implement while loops.

Dynamic memory and pointers

Addresses can be referenced with .LOC. and indirection done with .IND. followed by the type (which does not have to be the original type of what is being pointed to). It's possible to do pointer arithmetic also. The below example will print the result "42".

     INTEGER Q
     Q = 0
     POINTER P
     P = .LOC.Q
     P.IND.INTEGER = 42
     PRINT RESULTS Q
     END OF PROGRAM

A dynamic record defines a simple structure made up of data fields

     DYNAMIC RECORD (POINT) X,Y
     INTEGER X, Y

To use this you need to point it at an existing memory location or allocate new space with ALLOCATE and free memory with RELEASE. You can then use : to address fields:

     DYNAMIC RECORD (POINT) X,Y
     INTEGER X, Y
     POINTER P
     ALLOCATE (POINT)->P
     P:X = 10
     P:Y = 20
     PRINT RESULTS P:Y / P:X
     RELEASE P
     END OF PROGRAM

The USING keywords allows you to select a pointer, after which references to a record's fields will be done through that pointer. As an example, the above could be rewritten as:

     DYNAMIC RECORD (POINT) X,Y
     INTEGER X, Y
     POINTER P
     ALLOCATE (POINT)->P
     USING POINTER P, FOR POINT
     X = 10
     Y = 20
     PRINT RESULTS Y / X
     RELEASE P
     END OF PROGRAM

The USING will continue until another USING replaces it, or you do STOP USING POINTER.

Functions

MAD supports external (definition can provided at link time) or internal functions. Functions have a number of interesting features:

  • Names must end with a . so they are recognised by the parser
  • Optional or variable number of arguments are supported
  • It's possible to have multiple entry points into a function
  • As well as a return value it's possible to set a return code to signal unusual conditions

A example showing how an internal function can be defined and called, using the return code feature:

     INTERNAL FUNCTION NEGATE.(X)
          NORMAL MODE IS INTEGER
          IF X = 0
               FUNCTION RETURN 0, RC=1
          ELSE
               FUNCTION RETURN - X
          END IF
     END OF FUNCTION

     INTEGER X, X1, R
     READ DATA FROM UNIT 5
     X1 = NEGATE.(X)->R
     IF R = 0
          PRINT COMMENT "Zero is still zero"
     ELSE
          PRINT RESULTS X1
     END IF
     END OF PROGRAM

Input/output

In the previous example, the READ DATA FROM UNIT 5 requires that you set unit 5 to a FDname on the run command. But how does it know where to put the input? It expects the input format to be a set of name=value pairs separated by commas and terminated by an asterisk, which it will use to set variables. So a sample run of the above program, taking input from the keyboard, would look like:

# $run -load 5=*source*
# Execution begins   10:47:49 
  X=42*

          X1      =         -42 
# Execution terminated   10:47:55  T=0.001 

You can also use READ AND PRINT DATA to input as above and then echo the values entered.

For output, PRINT RESULTS will print data in a similar way to the format used by READ DATA'; PRINT COMMENT can be used to output a string.

It's also possible to do formatted input/output, similar but not identical to FORTRAN.

Further information

See the GOM Manual for a full specification of the language and how it differs from the original version of MAD.

MAD - Introduction

In this series of posts we'll look at one of the less widely known languages available on MTS - MAD, or the Michigan Algorithm Decoder.

The MAD language

Originally developed in 1959 at UM for the IBM 704, MAD is an imperative language influenced by ALGOL. It was implemented for a number of mainframes and operating systems in the 1960s, including MIT's CTSS where it was used to develop MAIL and RUNOFF.

MAD on MTS

GOM, or Good Old MAD, is the version available on the MTS D6.0 distribution. It is a re-implementation of MAD for the IBM S/360 with some changes to the language to bring it up to date. It was used to write the messaging system on MTS.

There was also a complete redesign of MAD called MAD/I, but this is not available on D6.0 due to copyright reasons.

Prerequisites

No special installation instructions to get GOM 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 *GOM

*GOM will read source from scards (by default *source* ie standard input) and will write object files to spunch (by default the temporary file -load).

Other *GOM parameters are listed in the GOM manual.

Hello world

Here's a terminal log of how to compile and run a simple hello world program. This assumes the source code is in file hello.mad. Note that comments are introduced with a * in column 1; all other statements (apart from line labels) must not start in column 1 but otherwise indentation is not important.

# $list hello.mad
       1     * HELLO WORLD PROGRAM
       2          LOOP FOR I=1, 1, I > 5
       3               PRINT COMMENT "Hello, world!"
       4          END LOOP
       5          END OF PROGRAM
# $run *gom scards=hello.mad
  No errors in MAIN 
# $run -load
  Hello, world!
  Hello, world!
  Hello, world!
  Hello, world!
  Hello, world!

Further information

The Wikipedia article is a good overview of the language and its implementations. An article on the MTS Archive gives more background on the history of MAD.

The GOM manual can be downloaded in PDF format from the UM Deepblue archive or the original FORMAT source can be found on the D6.0 distribution tapes under component 659/22 (restore to eg file GOMMAN.WF and then $run *format scards=gomman.wf sprint=-print, copy -print *print* to get an ASCII text copy). This describes the language in detail and how it differs from MAD.

An interesting book from 1962 by one of the designers of MAD, Bernard Galler, is "The Language of Computers" which can be found at Bitsavers. This takes a number of problems and describes from first principles how these can be turned into algorithms and how we might come up with a computer language to express them - and over the course of the book elegantly explains MAD.

Eric S Raymond has produced a transpiler (MAD to C) that runs on Unixes - source code can be found at gitorious.