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!
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.
Let’s look at an example of a complete program in FORTRAN and compare running it using the different compilers available on MTS.
The problem
Emirps are prime numbers that when their digits are reversed they make a different prime. An example is 13, which when reversed is the prime 31. The task on Rosetta Code is to:
show the first twenty emirps.
show all emirps between 7,700 and 8,000
show the 10,000th emirp
Writing the program
I think it’s interesting to describe how I wrote the program and got it to work. On modern systems I would tend to dive in and start writing small pieces of code and associated tests, TDD style. On MTS I favour writing the program offline first, import it into MTS and then get it working - this is partially due to being less comfortable with the MTS editor but also to match the usage pattern for MTS when it was in use; then terminal time was expensive so you would try to get more done before reaching for the computer.
So I started by sketching out what routines I’d need
Three subroutines TEST1-3to test each of the tasks given in the problem
A function EMIRP to test if a number was an emirp. This would reverse the digits and if different from the original, test if both were prime.
A function PRIME to test if a number was a prime
A function REVRSE to reverse a number
I used Emacs on my host OS to write the routines - was pleasantly surprised to find it still supports FORTRAN 66 syntax. This took around 45 minutes.
The prime number test I used was a brute force approach so not particularly efficient:
C *** TEST IF A NUMBER IS PRIME ***
LOGICAL FUNCTION PRIME(N)
INTEGER N
C DEAL WITH NUMBERS <= 3
IF (N .LE. 1) GOTO 200
IF (N .EQ. 2 .OR. N .EQ. 3) GOTO 100
C CHECK IF DIVISIBLE BY 2 OR 3
IF (MOD(N,2) .EQ. 0) GOTO 200
IF (MOD(N,3) .EQ. 0) GOTO 200
C SEE IF DIVISIBLE BY 5, 7, ..., UP TO APPROX SQRT(N)
10 DO 20 I=5,999999,2
IF (I*I .GT. N) GOTO 100
IF (MOD(N,I) .EQ. 0) GOTO 200
20 CONTINUE
100 PRIME = .TRUE.
RETURN
200 PRIME = .FALSE.
RETURN
END
Reversing the digits was done by taking the modulus of the number with 10 and then appending each digit to the end:
C *** REVERSE AN INTEGER'S DIGITS ***
INTEGER FUNCTION REVRSE(N)
INTEGER N
INTEGER M,R
C M IS COPY OF N FROM WHICH WE TAKE DIGITS
C R IS REVERSED DIGITS
M = N
R = 0
C LOOP UNTIL NO MORE DIGITS
10 IF (M .LT. 1) GOTO 100
C TAKE LAST DIGIT FROM M AND APPEND TO R
R = R * 10
R = R + MOD(M, 10)
M = M / 10
GOTO 10
100 REVRSE = R
RETURN
END
The emirp function was then a simple case of calling the two functions:
C *** TEST IF AN INTEGER IS AN EMIRP ***
LOGICAL FUNCTION EMIRP(N)
INTEGER N
C EXTERNAL FUNCTIONS
INTEGER REVRSE
LOGICAL PRIME
C R CONTAINS REVERSED DIGITS OF N
INTEGER R
R = REVRSE(N)
C N AND R MUST BOTH BE PRIME AND NOT THE SAME VALUE
IF (N .EQ. R) GOTO 200
IF (.NOT. PRIME(N)) GOTO 200
IF (.NOT. PRIME(R)) GOTO 200
100 EMIRP = .TRUE.
RETURN
200 EMIRP = .FALSE.
RETURN
END
The test functions are simple loops: here I show just the second test as an example.
C *** SHOW EMIRPS BETWEEN 7,700 AND 8,000 ***
SUBROUTINE TEST2
C EXTERNAL FUNCTION
LOGICAL EMIRP
C N IS NUMBER TO TEST
INTEGER N
10 DO 100 N=7700,8000
IF (EMIRP(N)) CALL SHOW(N)
100 CONTINUE
RETURN
END
I factored out the printing to another routine as each test needs to do this:
C *** DISPLAY AN INTEGER ***
SUBROUTINE SHOW(N)
INTEGER N
WRITE(6,50) N
50 FORMAT(I10)
RETURN
END
I then ran *IF66 and did /compile emirp.f. Lots of syntax errors - I forgot the maximum length for identifiers was 7 characters and that I needed to declare functions used externally.
Next I tried to test the individual routines - here *IF66 was very useful, as I could call eg the reverse routine with some test input and see its output immediately. Some more problems to fix here, eg function parameters seem to be pass by reference in FORTRAN. An error in the DO-loop in the prime testing function lead to an infinite loop that I could not get out of with PA2, so a trip to the operator’s console to STOP the MTS session was needed.
Finally I got it running after about another hour. The first two tasks were quick to execute but the third, to find the 10,000th emirp, ran for over 10 minutes without returning so I killed it. Time to run this using the compilers and see how they perform.
Using the compiler
First I tried it using FORTRANG:
# $run *ftn scards=emirp.f
# Execution begins 20:05:30
No errors in PRIME
No errors in REVRSE
No errors in EMIRP
No errors in SHOW
No errors in TEST1
No errors in TEST2
No errors in TEST3
No errors in MAIN
# Execution terminated 20:05:30 T=0.034
# $run -load
# Execution begins 20:05:34
13
...
948349
# Execution terminated 20:05:43 T=8.82
So just over 0.03 seconds of CPU time to compile and nearly 9s to run all tests.
Let’s try it with FORTRANH by using the opt parameter to *ftn. Note that the output of the compiler is quite different as FORTRANH is a completely different product:
# $run *ftn scards=emirp.f par=opt=h
# Execution begins 20:06:12
**** No errors for PRIME **** WED DEC 17/14 20:06:13
**** No errors for REVRSE **** WED DEC 17/14 20:06:13
**** No errors for EMIRP **** WED DEC 17/14 20:06:13
**** No errors for SHOW **** WED DEC 17/14 20:06:13
**** No errors for TEST1 **** WED DEC 17/14 20:06:13
**** No errors for TEST2 **** WED DEC 17/14 20:06:13
**** No errors for TEST3 **** WED DEC 17/14 20:06:13
**** No errors for MAIN **** WED DEC 17/14 20:06:13
# Execution terminated 20:06:12 T=0.092
# $run -load
# Execution begins 20:06:30
13
...
948349
# Execution terminated 20:06:35 T=4.607
Compilation took almost three times as long, but the program ran 48% faster so there’s definitely some good optimisation taking place. The compilation time difference may seem insignificant, but in an environment where you are paying for CPU time and working on a large program that requires many recompiles during development the costs would mount up.
Next step would probably be to improve the algorithm for testing for primeness, but I’ll leave that for now.
Final thoughts on FORTRAN
FORTRAN 66 has not aged well - its fixed format lines, lack of character/strings, unstructured design and implicit variable types make it hard to use for large scale programming. But it’s a simple language to pick up and use, and you can see that if you want to solve a numerical problem it can be very productive. Coupled with the optimising compiler and support tools available you can understand why it was the lingua franca of its time, rather like C today.
In this post I’ll look at the FORTRAN 66 language as available on MTS in more detail.
Source code format
FORTRAN originally had a fixed format for source code lines and used all upper case letters; as *FTN does not have this restriction we’ll use lower case and free format in the examples below to make them easier to read, but note that this means these examples may not work on other, non-MTS compilers.
Update 4-Dec-2015: As noted by Mike Stramba, *FTNdoes require source code to be in upper case, although *IF66 is happy with upper or lower case.
One unique feature is that whitespace is not important, so the variable BXX could also be referred to as B XX. Keywords are context sensitive, so you can write IF IF.GT.3 J=2 where the second IF is actually a variable.
Types and identifiers
FORTRAN supports INTEGER, REAL. LOGICAL and COMPLEX number types. Character types are not support directly, but can be accessed through FORMAT statements (see below).
Variable names can have up to six characters and must start with a letter. Variables can be explicitly declared with their type; if not declared, variables starting with letters I to N are treated as integers, otherwise they are treated as reals.
Variables can be initialised with the DATA statement.
integer count, count1
real temp
complex point
data i,count,temp,point/0, 10, 32.0, cmplx(1,2)/
Arrays and matrices can be created with DIMENSION and initialised with DATA then individual values can be accessed using (), first index 1, in column major order, so in the below X(2, 1) will be intialised with the value 2.0.
dimension x(2,2)
data x/1.0, 2.0, 3.0, 4.0/
Operators and expressions
The usual arithmetic operators appear, including ** for exponentiation. Logical operators look like .LT. for less than or .AND. for Boolean-and.
x = 2.0 ** 4.0
i = 5 + 3
j = x / i
y = x / i
In the result above, J will be set to 2 and y to 2.0.
Statements
Branching can be done with GOTO; there are three forms:
goto 100
goto l
goto (10,20,30) ll
The first will jump unconditionally to the line labeled with 100.
The second will jump to the label based on the value of L
The third will jump to line 10 if ll = 1, 20 if ll = 2 etc
The DO statement allows looping
j = 0
do 100 i=10,20,5
j = j + i
100 continue
k = j * 2
This will initialise I with 10 and then run the contents of the loop for values 10, 15, 20. After that it will jump to the line after the label 100. So for this example, K will end up with the value 90.
It’s possible to nest loops and jump out of loops, but not jump into them.
The IF statement has two forms, logical and arithmetic. The example of the logical version below will set k to 3 if i < j.
if (i.lt.j) k=3
The arithmetic version will branch to one of three labels based on whether the expression being tested is negative, zero or positive. For the example below it will branch to label 30 as the expression is positive.
J = -3
if (j + 4) 10,20,30
Input/output and formats
Inputs (READ) and outputs (WRITE) are associated with a FORMAT statement, a logical I/O unit and a list of variables. For example:
read(5,100) i1,x1,y1
100 format(i2,f5.2,f2.0)
with the input
1234.5678.90
will read from I/O unit 5 (the keyboard) i1=12, x1=34.56, y1=78.0.
Character constants, with a leading length identifier, can be used in READ or WRITE statements as we saw in the hello world example:
write (6,200)
200 format(13h HELLO, WORLD)
prints “HELLO, WORLD” on unit 6, the console.
Functions and subroutines
FORTRAN comes with a large number of built in functions for mathematical processing eg MOD, ABS, SIN. On MTS there is also a library of operating system specific functions that can be called but I will not go into these here.
You can define your own functions to pass parameters by reference and optionally return a value: for example to calculate the average of two values:
real function avg2(x,y)
real x, y
avg2 = (x + y) / 2.0
return
end
This could be called with
z = avg2(3.0, x)
There is also subroutines which run by using call. For example, the below would set x to 2.0:
x = 1.0
call add1(x)
subroutine add1(x)
real x
x = x + 1.0
return
end
For our second language we’ll look at FORTRAN, the most popular language run on MTS by far (40% by frequency of use in 1986 according to Introduction to programming and debugging in MTS, followed by Pascal at 35%). Due to its popularity it has the largest range of environments, libraries and tooling of any language available on MTS.
The FORTRAN language
FORTRAN is probably the oldest language still in wide use today. Originally developed at IBM in the early 1950s, it spread to many platforms in the 1960s and become the language of choice for scientific and mathematical applications. The first standardised version, FORTRAN 66, was a simple unstructured imperative language; later versions such as Fortran 77 and 90 added modular features and even object orientated programming constructs.
FORTRAN on MTS
Available with the D6.0 distribution are the two IBM FORTRAN IV (ie FORTRAN 66) compilers, FORTRANG and FORTRANH. The former includes better debugging support whereas the latter produces more efficient object code. Both of these compilers are available via the *FTN front end.
There is also *IF66, an innovative FORTRAN interpreter developed at the University of British Columbia, which is useful for developing and testing programs.
Due to copyright restrictions, the University of Waterloo compilers WATFOR and WATFIV are not available - these featured a unique compile-and-go model where compiler output was directly executed rather than writing an object file, which allows better diagnostic messages and reduced compilation costs.
FORTRAN 66 was already obsolete in 1986 and most new development in FORTRAN had moved on to FORTRAN 77 which was supported in MTS by the IBM compiler FORTRANV5 and UBC interpreter *IF77 - however neither of these are available in the D6.0 distribution due to copyright restrictions.
Also available are a number of FORTRAN preprocessors, such as RATFOR, and tools, such as the *DAVE data flow analyser, which I will cover in a later series of posts.
Prerequisites
No special installation instructions to get FORTRAN 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 *FTN
You can invoke FORTRANG and FORTRANH directly, but it’s much easier to use the MTS front end *FTN.
*FTN 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 options can be provided using par= on the command line or interactively.
format determines the source code input format: options are IBM, LINE, EDITED or LONG with the default being EDITED. IBM format is the traditional FORTRAN fixed format shown at the diagram at the top of this post; LONG is IBM format with the maximum line length limit lifted; LINE is free format. EDITED is a compromise where the front end will try to guess what format the input is in.
opt determines the optimisation level. Choices are G, which will cause the FORTRANG compiler to be used, or 0/1/2 which will select the FORTRANH compiler with increasing levels of optimisation. H is an alias for FORTRANH with level 2 optimisation. The default for opt is G.
Other *FTN parameters are listed in the online help or MTS Volume 6.
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.f.
# $list hello.f
1 C *** HELLO WORLD PROGRAM ***
2 C
3 DO 10 I=1,5
4 WRITE (6,20)
5 10 CONTINUE
6 STOP
7 20 FORMAT(13H HELLO, WORLD)
8 END
# $run *ftn scards=hello.f
No errors in MAIN
# $run -load
HELLO, WORLD
HELLO, WORLD
HELLO, WORLD
HELLO, WORLD
HELLO, WORLD
The *IF66 FORTRAN interpreter
If you’ve used the UM BASIC interpreter, the *IF66 FORTRAN interpreter will appear familiar, with the ability to switch between editing, running and debugging programs. It integrates well with the MTS environment, allowing you to use the full MTS editor and is fully compatible with the FORTRAN compilers. It supports running of arbitrary FORTRAN statements or routines and debugging features such as atpoints, where code can be run when a breakpoint is reached.
A quick demo, using the file hello.f from before:
# $run *if66
* IF(NOV80)
* /compile hello.f
ROUTINE NAME: MAIN
* /list main
* 1. C *** HELLO WORLD PROGRAM ***
* 2. C
* 3. DO 10 I=1,5
* 4. WRITE (6,20)
* 5. 10 CONTINUE
* 6. STOP
* 7. 20 FORMAT(13H HELLO, WORLD)
* 8. END
+ /edit main
You are now in the MTS editor and can type v to enter visual mode and make changes; press PA2 to exit out of the editor. I’ll now show how to run the program and also *IF66’s immediate execution of FORTRAN statements:
* /run main
HELLO, WORLD
HELLO, WORLD
HELLO, WORLD
HELLO, WORLD
HELLO, WORLD
/MAIN:6./ - /STOP /
+ x=40.0
+ y=sqrt(x)
+ print,y
6.324555
+ /stop
Definitely a useful and powerful tool, and I don’t think any other platform had such an advanced FORTRAN interpreter at that time.
In the next post, I’ll take a look at the FORTRAN language in more detail.
Further information
MTS Volume 6 describes *FTN and *IF66 in full detail, along with the other FORTRAN tools available.
Digital Computing, FORTRAN IV, WATFIV, and MTS (with *FTN and *WATFIV) is a good contemporary introduction to programming FORTRAN on MTS from two authors at the Chemical Engineering department at UM. A number of different editions were produced; the linked one is from 1976. It also includes a useful description of the IBM S/360 architecture from the viewpoint of a non-systems programmer.
IF, an interactive FORTRAN compiler (link not working as of August 2023) is a paper from 1973 giving background information on why *IF66 was developed and a demo of its use.
A narcissistic number is a integer where the sum of each digit raised to the power of the number of digits equals the number itself. For example, 153 is narcissistic: it has three digits 1, 5 and 3, and 1³ + 5³ + 3³ = 1 + 125 + 27 = 153.
The goal of the program is to print the first 25 narcissistic numbers.
First version
The algorithm is fairly simple
Look at each positive integer in turn
Find number of digits
Sum up each digit raised to the power of the number of digits
Compare to the number and if equals, print it
Stop after 25 narcissistic numbers found
To find the number of digits we can convert the number to a string and take its length. To extract each digit we need to divide by 10, take the integer part and multiply by 10 again and subtract the original number as there is no modulus operator.
100 rem UM BASIC program to print the first 25 narcissistic numbers
110 let c = 0 /* Count of narcissistic numbers found
120 *
130 rem Start of loop to find and print narcissistic numbers
140 for n = 0 to 10000000 /* Number to check for narcissism
150 if c >= 25 then: stop /* End after 25 numbers
160 *
170 let nn = nts(n) /* Number as a string
180 let d = len(nn) /* Number of digits
190 let x = n /* Copy of number
200 let y = 0 /* Result of narcissistic calculation
210 *
220 rem Start of loop to calculate narcissistic number
230 for i = 1 to d /* For each digit
240 let x1 = int(x/10) /* Get all but last digit of x
250 let x0 = x - (10 * x1) /* Get last digit of x
260 let y = y + (x0 ** d) /* Accumulate digit ** num digits
270 let x = x1 /* Shift off last digit from x
280 next i
290 *
300 if int(y) <> n then 400 /* Not a narcissistic number, jump next
310 print n /* Print narcissistic number
320 let c = c + 1 /* Increase count found
330 *
400 next n /* Try next number
410 *
500 stop /* Fall through
Unfortunately this takes a long time to run - 6 minutes and 46 seconds of CPU time - so let’s see how we can improve this.
Faster version
There are several optimisations we can try:
Precompute a ** b, for a and b between 0 and 9, as we do this for each digit in the inner loop and it is likely to be an expensive operation. The precomputed powers are stored in a 2D matrix p by the routine starting on line 600. This saves 123 seconds.
Exit early from the calculation inner loop when the accumulated total is larger than the number being tested. This saves 32 seconds.
Use integer comparison to find the number of digits rather than converting to a string. This saves 54 seconds.
Here’s the final listing, taking 3m17s. There are probably further optimisations that can be made - any suggestions?
100 rem UM BASIC program to print the first 25 narcissistic numbers
110 rem Second, faster version
120 *
130 let c = 0 /* Count of narcissistic numbers found
140 dim p(9, 9) /* p(x, y) will contain x ** y
150 gosub 600 /* Precompute p
160 *
170 rem Start of loop to find and print narcissistic numbers
180 for n = 0 to 10000000 /* Number to check for narcissism
190 if c >= 25 then: stop /* End after 25 numbers
200 *
210 gosub 700 /* Get number of digits in d
220 let x = n /* Copy of number
230 let y = 0 /* Result of calculation
240 *
250 rem Start of loop to calculate narcissistic number
260 for i = 1 to d /* For each digit
270 let x1 = int(x/10) /* Get all but last digit of x
280 let x0 = x - (10 * x1) /* Get last digit of x
290 let y = y + p(x0, d) /* Accumulate digit ** num digits
300 if y > n then 400 /* Bail out if too big already
310 let x = x1 /* Shift off last digit from x
320 next i /* Loop for next digit
330 *
340 if y <> n then 400 /* Not a narcissistic number, jump next
350 print n /* Print narcissistic number
360 let c = c + 1 /* Increase count found
370 *
400 next n /* Try next number
410 *
500 stop /* Fall through
510 *
520 *
599 rem Subroutine to populate p(a, b) with a ** b
600 for a = 0 to 9 /* Digit
610 p(a, 0) = 0 /* a ** 0 = 0
620 p(a, 1) = a /* a ** 1 = a
630 for b = 2 to 9 /* Power to raise to
640 p(a, b) = p(a, b-1) * a /* Calc next power in series
650 next b /* Loop power
660 next a /* Loop digit
670 return
698 *
699 rem Subroutine to get number of digits in n
700 if n >= 1000000 then 800
710 if n >= 100000 then 810
720 if n >= 10000 then 820
730 if n >= 1000 then 830
740 if n >= 100 then 840
750 if n >= 10 then 850
760 goto 860
800 let d = 7
801 return
810 let d = 6
811 return
820 let d = 5
821 return
830 let d = 4
831 return
840 let d = 3
841 return
850 let d = 2
851 return
860 let d = 1
861 return
Closing thoughts on BASIC
The strength and weaknesses of the BASIC language are that it is, well, basic. With only a handful of features it is hard to get lost, but doing anything more complex than the above would be painful. From a modern programming viewpoint, the need for line numbers, restrictions on variable names and lack of types makes it quite different from what we would do now so despite some nostalgia for 80s home computing I can see why this is a bad choice for even a beginner’s programming language today. But it’s also clear to see how revolutionary BASIC was when first introduced and how it opened the door to programming for a whole new set of people.
Likewise, the self contained environment for UM BASIC makes it easy to start writing code without having to know much about MTS, but you lose the access to useful tools like a full screen editor. I think this, and the fact that better languages were available, explains why BASIC was not a popular choice for general users of MTS - according to Introduction to programming and debugging in MTS, only 2% by frequency of use in 1984.
Diagram showing fixed format for lines of FORTRAN source code, from