1. Origins of MAD: the Recollections of Bruce Arden and Bernie Galler

posted Nov 19, 2010, 2:17 PM by Jeff Ogden   [ updated Dec 25, 2011, 9:57 PM ]
Bruce Arden, Bob Graham, and Bernie Galler are the original authors of 7090 MAD.




Bruce Arden's recollections

From: Bruce Arden
Date: July 12, 2010 11:24:02 AM EDT
To: Jeff Ogden
Subject: Re: Wikipedia about the MAD language updated

Jeff,

When I get back to Ann Arbor I can probably add some more history. MAD was an important step in the evolution of compilers and it let Michigan become a leader in the academic use of computers. The Ford Foundation program to educate many university engineering professors from elsewhere was a great success. It depended on MAD. It had its origin on the IBM 650, a computer that was adopted by many, if not most, universities. Bob Graham and I wrote GAT for the 650 and it replaced the only competitor IT.  IT,  the perfect acronym, was written by  Perlis, Cheatham, and Smith who were then at Purdue and later at Carnegie-Mellon. FORTRAN was much too large and too much of a kludge to fit on a 2000 word 650. The GAT algorithm was the nucleus of MAD. There's more to the story. Later.

Bruce



From: Bruce Arden
Date: August 26, 2010 12:57:07 PM EDT
To: Jeff Ogden
Subject: MAD history

In your pursuit of history you have no doubt found that MAD was an implementation of ALGOL 58. It was a demanding task. No European groups and only two other US organizations completed it: NELIAC (from the Naval Electronics Laboratory) and JOVIAL (Jules own version of the international algebraic language by the Rand Corporation). The Europeans were major supporters of this "standard." By the time Bob Graham, Bernie, and I finished it the Europeans (mostly the Germans) had decided that they wanted something simpler and called it ALGOL 60. The three completed programs would be scrapped and started over. Not surprisingly, the three organizations declined the honor.

Bob Graham and I became UM's first professional programmers, called Research Associates, when the IBM 650 arrived at the Statistical Research Laboratory. Bob left for MIT in late 1963. Apparently MAD was used to some extent in the programming of CTSS.

Bruce



From: Bruce Arden
Date: August 28, 2010 11:12:30 AM EDT
To: Jeff Ogden
Subject: Re: MAD history

Jeff,

Sure, I see no reason for excluding memoirs. Obviously, such recollections by two different participants may not agree.

Regarding Jean Sammet [the comment "While MAD was motivated by ALGOL 58, it does not resemble ALGOL 58 in any significant way" appears on page 205 of Jean Sammet's 1969 book Programming Languages: History and Fundamentals], she may have conflated the two version[s] of IAL (58 and 60). Unlike the later version, the 58 version said nothing about what words (or language) should be used to identify conditional and transfer statements, which led for parsing reasons to words like WHENEVER. Also there were some additional features in MAD that went beyond the 58 specs. Since any symbol could be an array element, it was possible to do an indexed transfer to statements and subroutines. That was before program readability became important.

I don't know where MAD history begins. For me it was when Bob and I programmed GAT (Gaham/Arden Translator or Generalized Algebraic Translator for the world). It was, I think, the first instance of operator precedence parsing. GAT replaced IT and FORTRANSIT (Perlis et al.) in most of the university 650s -- including Perlis' at Carnegie Mellon.  We thought the really big contribution was fitting it in 2000 words of memory.

Bruce


A portion of An Interview with Bernard A. Galler

From An Interview with Bernard A. Galler, Charles Babbage Institute, Center for the History of Information Processing, University of Minnesota, Minneapolis, 1991, OH 236, pages 18-22:

Maybe I should talk a little about the history of MAD, along this period [1960 to 1965], because MAD was one of
our major activities at the [UM] Computing Center.

It goes back to the 650, when I mentioned that we had the IT compiler from Al Perlis. IT, because of its constraints,
mainly the size of storage, and the fact that there were no index registers on the machine, had to have some severe
limitations on what could be expressed in the language. And Arden and Graham decided to take advantage of index
registers when we got them on the hardware and also to ... we began to understand compilers a little better, and they
decided to generalize the language a little bit, and so they wrote the compiler called GAT, the Generalized Algebraic
Translator, which Perlis then took; by that time he had gone to Carnegie-Mellon ... it may have been Carnegie at the
time. Perlis took GAT and added some things to it to call it GATE - GAT Extended - and he went on to add a few
things to it in that direction.

GAT was not used very long at Michigan. It was okay, but there was another development, because in 1958, there
was the ALGOL development in the European-American cooperation between ACM and the European group, and
they announced a standard language called ... well, first it was IAL, the International Algebraic Language, but they
changed the name to ALGOL, Algorithmic Language, ALGOL 58. They published a description of the language, and
said, "Please everybody, implement this, let's find out what's wrong with it. In two years we'll meet again and make
corrections to the language," in the hope of getting everybody to use this one wonderful language universally
instead of the several hundred which were already developing all over the world. Everybody was doing his own
thing; there was an issue of the ACM where the cover showed a Tower of Babel with all the different languages on it,
and so on. So the attempt was to try to get a universal language. John Carr was very active in this process, and he
came back to Michigan and said, "We've got to do an ALGOL 58. To help the process, let's find out what's wrong
with the language. We know how to write language compilers, we've already worked with IT, we've done GAT, and
so on. Let's see if we can help." So we decided - I was involved, and Arden and Graham, and John Carr a little bit,
but he never really was very involved. He left in 1959. We decided to do an ALGOL 58 compiler. It turned out that
there were some things wrong with the ALGOL 58 language specification. There were some things that were very
difficult to do, very foolish inclusions and so on, and when you actually write a compiler, you discover that you have
to make a number of decisions, and so by the time we designed the language that we thought would be worth doing,
and we could do a compiler for, we said we couldn't call it ALGOL any more; it really was different. What should we
call it? And so that's when we adopted the name MAD, for the Michigan Algorithm Decoder, and we had some
funny interaction with the Mad Magazine people, who finally gave us permission, in a very funny letter, which told
us that they would take us to court and everything else, but had a P.S. at the bottom - "Sure, go ahead."
Unfortunately, that letter was lost. But we decided to write a compiler, and at first it was Arden and Graham who did
all of this. I was helping, watching and so forth, but it was mainly their work because they had worked on GAT
together. And then at some point I said, "I want to take over part of this thing, too, and really join the group." And
they said fine. Arden was doing the back end of the compiler, Graham was doing the front end of the compiler. We
needed someone to do the middle part which would glue the pieces together and make everything flow and provide
all the tables and so on, and I said, "Fine. That's my part." So Graham did Part I, Galler did Part II, and Arden did Part
III.

A few years later when Bob Graham left and went to the University of Massachusetts where he is now, I took over
Part I. So I had Parts I and II, and Arden had III, and we kept on that way. I was very glad that Graham had
developed some very powerful macros in Part I which made my job a lot simpler, and for which I want to absolutely
give Bob credit for doing a good job.

So we did the MAD compiler in 1959 and 1960, and I think it was 1960 when we went to that famous SHARE meeting
and announced that we had a compiler that was in many ways better and faster than FORTRAN. It was a better
language, and so on. There are people who still come up to me and tell me they rememb er my standing up at that
meeting and saying at one of the FORTRAN discussions, "This is all unnecessary, what you're doing here, because
you've got to come to our session where we talk about MAD and you'll see why." And people remember that,
because it was true. I remember one ...

E. GALLER: Did they think that you were being very ...

B. GALLER: Brash?

E. GALLER: ... brash, because you were so young?

B. GALLER: Of course, and well, who would challenge IBM? But okay. I remember one time, a little bit later, we had
a visit from a guy from IBM at Michigan. He came to Ann Arbor, and we went to lunch, and he was telling us that
they were so excited; they had discovered how to have the computer do some useful work during the 20-second
rewind of the tape in the middle of the FORTRAN translation process, and we sort of smiled. And he said, "Why are
you smiling?" And we said, "That's sort of funny, because the whole MAD translation takes one second." And
here he was trying to find something useful to do during the 20-second rewind in the middle of their whole
FORTRAN processor.

What happened in developing MAD that was important was that we were able to get the source listings for
FORTRAN on the 704, and Bob Graham studied those listings as to how they used the computer. The 704 computer,
at that time, had 4,000 words of core storage and, I think, 8,000 words of drum storage. And the way the IBM people
overcame the small core storage, the 4,000 words, was to store their tables on the drum. And they did a lot of table
look-up on the drum, recognizing one word for each revolution of the drum, and if that wasn't the word they wanted,
then they'd wait until it came around, and they'd look at the next word. Graham recognized this and said, "That's one
of the main reasons they're slow, because there is a lot of table look-up stuff in a compiler. You look up the symbols,
you look up the addresses, you look up the types of variables, and so on." So we said: "Fine. The way to organize a
compiler then is to use the drum, but to use it the way drums ought to be used. That is, you put stuff out there for
temporary storage, and you bring it back once and you use it again when you need it." And so we developed all of
our tables in core; when they overflowed we stored them out on the drum. That is, Part I did all of that. Part III, then,
would call in the relevant table when it needed it and use it. We did no look-up on the drum, and we were able to do
the entire translation in under a second. It was because of that that MIT, when they developed their time-sharing
system, which they called CTSS, the Compatible Time-Sharing System, and they needed a fast compiler for student
use, used MAD, and it was their in-core translator for many years. So we developed, then, MAD in 1959, 1960. It
really got finally working in 1961. In January ... well, February, I guess, 1961, we went to New York. Our 709 had
arrived, or was about to arrive. We went to New York, the three of us, in the middle of that big snowstorm, to debug
the new MAD version, the 709 version of MAD. And we were using the Socony Mobil 709 at night after they used it
in the daytime. So we would sleep most of the day and work at night. And we got the 709 version of MAD
debugged, so that when our machine arrived, we were able to use it. Our campus used MAD until the middle of 1965,
when the 7090 computer, which we had by that time, left. I think during the last four years of its life, we found no
additional bugs; it was a very good compiler. And the important thing about it, of course, was that we had a number
of language innovations, and notational innovations which were, some of them, picked up by the FORTRAN group
to put into FORTRAN IV and its successors later on. They never really advertised the fact that they got ideas and in
effect got some important notation from MAD, but they told me that privately.

So MAD was very important. We published a number of papers. One important thing we did was we had a language
definition facility. Now people refer to it as an extensible language facility. It was useful and important, and it worked
from 1961 on, but somehow we didn't appreciate how important it was, so we didn't really publish anything about it
until about 1969. And I was later lectured to by John Reynolds - I think he was at Argonne, an important language
guy - who told me that we were very derelict in not publishing it sooner because it was so important, and the world
should have known about it sooner. Well, in hindsight, yes. There is a lot of work in extensible languages now, and
unfortunately, not a lot of people credit the work we did, partly because we didn't publish it for so long, and while
people knew about it and built on it, there was no paper they could cite.

So we think the work on MAD was very important, and the work on the operating system stuff was important. That
was the foundation of Michigan's Computing Center activity.


Bruce Arden recalls a week of nights in NYC debugging MAD

From: Bruce Arden
Date: July 6, 2010 2:30:50 PM EDT
To: Mike Alexander
Cc: Jeff Ogden, Scott Gerstenberger
Subject: Re: another memory test

 . . .

Bernie, Bob Graham and I spent a week of nights using the 7090 in NYC at the TIME/LIFE building debugging in anticipation of the arrival of the 7090. We learned how programming ability decays when severe fatigue sets in.

Bruce
Comments