MAD(ID:92/mad001)
Michigan Algorithm Decoder
for Michigan Algorithm Decoder.
R. Graham, Bruce Arden and Bernard Galler 1959 U Michigan.
Based on IAL.
For the IBM 704, 709 and 7090, later ported to Philco, Univac and CDC machines. According tho the Multicians there was unfinished Multics port.
MAD was one of the first extensible languages: the user could define his own operators and data types and by giving assembly code for their implementation. Also supported indexed function name variables.
"MAD is perhaps most famous for the line printer picture of Alfred E. Neumann which was printed when an attempted compilation had too many errors. Underneath the picture it printed the caption: See this man about your program--He might want to publish it. He never worries--but from the looks of your program, you should" (Gray)
Featured EQUIVALENCE, ERASABLE, and PROGRAM COMMON
According to Geller 2001, many of the advanced featured of MAD were placed into Fortran IV, but this fact was only ever privately admitted. The same article suggests that a lot of value was gained by seeing the source for Fortran II, and learning from its mistakes.
Hardware:
- IBM 704 IBM
Related languages
| Fischer IT | => | MAD | Implementation | |
| IAL | => | MAD | Influence | |
| MAD | => | ALGOL C | Influence | |
| MAD | => | Data Structures Language | Dialect of | |
| MAD | => | FORTRAN IV | Incorporated some features of | |
| MAD | => | GOM | Port of | |
| MAD | => | JOVIAL | Incorporated some features of | |
| MAD | => | KLIPA | Mild Influence | |
| MAD | => | KULSRUD | Target language for | |
| MAD | => | MAD List Language | Extension of | |
| MAD | => | MAD Simulation | Extension of | |
| MAD | => | Mad/I | Evolution of | |
| MAD | => | MADBLOC | Written using | |
| MAD | => | MADBUG | Conversational system for | |
| MAD | => | MADTRAN | Targetting | |
| MAD | => | OCAL | Incorporated some features of | |
| MAD | => | PK-MAD | Extension of | |
| MAD | => | PUFFT | Influence | |
| MAD | => | RALPH | Compiled by |
Samples:
References:
in SESSION: Automatic programming: algorithm translators view details
in [ACM] CACM 2(02) February 1959 view details
Introduction
This paper describes the internal structure of a translator for the MAD language. The language is very similar to that of ALGOL 60, although it is more restricted in some respects and more general in other's. We shall assume a familiarity with the MAD language, although many of the remarks made below will be clear even to those with only a slight knowledge of the language. Throughout any discussion of the organization of a translator, it is important to understand the primary objectives that have been set for its behavior.
This translator was designed to have the following properties (in the order given):
(1) high speed of translation,
(2) generality (i.e., as few restrictions on the user as possible), and (3) object program efficiency.
Many decisions were made by means of these criteria which might have been made differently if there were other objectives. The design was also influenced to some extent, although not very much, by the organization of the computer (IBM 704) on which the translator was to operate.
in [ACM] CACM 4(01) (Jan 1961) view details
MAD AT MICHIGAN
The Michigan Algorithm Decoder (MAD), in operation since February, 1960, was developed for the specific purpose of training large numbers of university students and handling the large volume of university research problems. The primary motivation for writing this rapid translator may be traced directly to the special environment of a university computing center.
A large university should not operate its computing facility as a closed shop since the university's role is educational; moreover, it cannot operate in such a fashion since the users, students and staff, may number in the thousands. The computing implications of these facts are that large numbers of relative novices will have direct access to the machine. Like it or not, these users will work at the level of an algebraic source language?often making many compilations on programs which are not destined to become long-run production programs. What is required in this environment (which is not necessarily peculiar to universities) is an extremely rapid translator accepting a source language which has a minimum number of restrictions. MAD was written to fulfill these requirements. ALGOL 58 provided the basic pattern for the language and to the extent that ALGOL 58 is like ALGOL 60, MAD is an ALGOL translator. The design criteria were satisfactorily achieved although, undeniably, the permitted generality of expression reduced, in some instances, the object program efficiency as compared to that produced from restricted source languages.
MAD translators now exist on the IBM 704, 709, and 7090, and a recent compilation of 785 statements took one minute on the 7090, producing approximately 10,000 machine instructions. In another occasion, using the Bell Monitor System on the 7090, MAD compiled 84 programs in 20 minutes. (MAD is also available as part of the FORTRAN Monitor System.) The translator itself contains about 16,000 words, of which several hundred are diagnostic comments. Before we consider the reasons for the translation speed, we shall describe some of the features of the MAD language. Symbols consist of up to six alphanumeric characters, the first of which is a letter. Function names consist of a symbol and a terminating period, such as SIN., SQRT., and so on. Constants, as in FORTRAN, have such forms as 1.2E-3, .006, -1E7, etc., except that one may write the Boolean constants IB and OB (representing true and false, respectively), and alphabetic constants, such as $ABC$ or $=$ (up to six Hollerith characters enclosed in dollar signs). Arithmetic expressions are formed in the usual way, using +,?,*,/, .ABS., and .P., with the last two meaning "absolute value" and exponentiation, respectively. Also available are the relations <, <,? =, ¥*, >, and >, represented by .L., .LE., .E., .NE., .G., and .GE., respectively and A , V,-i , 3, =, and exclusive or, represented by .AND., .OR., -NOT., .THEN., .EQV. and .EXOR., respectively. Thus, one might write the Boolean expression
X .P.3 .L. Y .P.3 .AND. I .NE. J .OR.X * Y .G. 1 to represent the expression
X3 < Y3 * I yfc J VXY > 1
The mode of arithmetic of each variable and function (floating point, integer, Boolean, etc.) is declared by exception. For example, in MADTRAN, the FORTRAN to MAD translator which was written in MAD, all variables were of integer mode, since Hollerith constants are also of integer mode. The statement
NORMAL MODE IS INTEGER
caused all variables to be integer, and if there had been any floating point variables, they would have been so declared. There also exist programs in which the normal mode is Boolean! Mixed expressions are allowed whenever ordinary mathematical notation would allow it.
Besides the ordinary substitution statement, which has the form
x = (-B + SQRT.(B*B-4.*A*C))/(2.*A) there are many other statements. The most useful statements are the simple and compound conditionals and the two forms of the iteration statement. These are illustrated by the following:
(a) The Simple Conditional
WHENEVER I .G.J .AND. X .E. 3, TRANSFER TO BETA(I).
(b) The Compound Conditional
WHENEVER I -G. J .AND. X .E. 3
C(I) = B(J) X = 2
TRANSFER TO BETA (I) OR WHENEVER I .G. J .AND. X .E. 2
C(I) = B(J) + X X = X - 1
OTHERWISE
C(I) = B(J) - X X = X - 1
END OF CONDITIONAL
(c) The Iteration Terminated by a Boolean Expression
THROUGH A, FOR I ? BZERO, F.(I) - I, .ABS.F.(I) .L. EPSLON
This is interpreted as: Set I = BZERO, then test the Boolean expression .ABS.F.(I) .L. EPSLON. If true, the scope of the iteration is not executed at all. If false, it is executed, then I is incremented by F.(I)?I (in effect, I is replaced by F.(I) in this example) and the Boolean expression is tested again.
(d) The Range of Values Iteration
THROUGH A, FOR VALUES OF Q = 50, 25,10,5,1 In this case the scope is executed for each of the listed values (which could be arbitrary expressions) in turn.
While the dimension statement in MAD causes a fixed block of storage to be set aside for each array, the number of dimensions (Le., the number of subscripts), the range of each subscript, and the base point of the array within the block are stored as ordinary values of a vector and may all be modified or set during execution. Format . information, similar in form to that used in FORTRAN, can likewise be modified or set at execution time. On the other hand, all of this information may be pre-set by a general declarative statement which can pre-set values of any array or vector. Input-output statements which make use of a symbol table and require no format information, such as
READ DATA
have recently been added to the 709/7090 version, as well as the ability to define new operations into the language.
There are also facilities for defining internal or external functions. The latter correspond to the FORTRAN subroutine, while the former are similar to the ALGOL procedure, in that they are defined within the body of the calling program and variables not listed as arguments are common to both programs. It is possible to define recursive functions, also, and still other statements provide a pushdown list mechanism. While multiple subscripting is handled by a set of standard subroutines, the user may provide his own storage function for each array, if he chooses, by designating the name of the new function. This function, whose definition program may be written in MAD, may then allow one to store one-half of a symmetric or upper triangular array, only non-zero entries, etc.
There are many other features in MAD, such as the EQUIVALENCE, ERASABLE, and PROGRAM COMMON declarations, and so on, but let us return to the question of the reason for the speed of translation. Probably the greatest single factor in this speed is the minimization of the use of the magnetic tapes. In the 709/7090 version, programs containing under 200 statements require no tape movement other than reading the source program from the input tape and writing the translated object program onto the output tapes. (The MAD translator is itself one record on the master tape.) Longer programs require intermediate tape storage, but in a highly buffered way. Another factor is the internal structure of the translator, with a heavy dependence on just a few tables of information. Also the statement structure is such that statement types are discernable without an analytic scan. A final and, perhaps, second order reason is that the group writing the translator was small?three people. As a result the intra-group communication was good, and the program inefficiencies which are so often introduced in developing large, group-effort programs were held to a minimum. The writing of the 704 MAD translator took 2 man-years, and the rewriting for the 709/7090 took about 3 man-months. The use of this translator has made it possible to assign rather formidable problems to students. In a one-semester course assuming no computer experience, the following problems have been assigned (each one as the last problem in a different semester). (1) Symbolic differentiation, (2) An interpretive program for a simplified MAD?like language, (3) An assembly program for a language much ? like FAP for the 709/7090, (4) The complete scan and decomposition of arithmetic expressions from MAD. Usually 30-50% of the 100 or more students in the course have the program checked out by the end of the semester. The following is a portion of a solution to the analytic differentiation problem. It deals with the input expression, and might be found in any of the problems described above. It is included here to illustrate some of the symbol manipulation features of the language. Problems involving evaluation of algebraic expressions would appear much more conventional than this.
R FUNCTION CONST. THIS BOOLEAN
FUNCTION R RETURNS A VALUE OF IB (TRUE)
IF ITS ARGUMENT IS R INCLUDED IN THE SET OF CONSTANTS
0-9,A-Z (except X) R AND OB (FALSE) OTHERWISE.
INTERNAL FUNCTION (Z)
BOOLEAN CONST.
ENTRY TO CONST. SCON1 THROUGH SCON1, FOR B =
1, 1,Z.E. TAB(B) .OR. B.E. 36
WHENEVER B .L. 36
FUNCTION RETURN IB
OTHERWISE
FUNCTION RETURN OB
END OF CONDITIONAL
END OF FUNCTION
VECTOR VALUES TAB(1)=$0$,$1$,$2$,$3$, $4$,$5$,$6$,$7$,$8$,$9$,
1 $A$,$B$,$C$,$D$,$E$,$F$,$G$,$H$,$I$,
' $J$,$K$,$L$,$M$,$N$,
2 $O$,$P$,$Q$,$R$,$S$,$T$,$U$,$V$,$W$,
$Y$,$Z$, !
R FUNCTION P. THIS FUNCTION ASSIGNS A R PRECEDENCE VALUE TO THE OPERATORS. INTERNAL FUNCTION (Z) ENTRY TO P. WHENEVER Z .E. $.P.$
PREC=8 OR WHENEVER Z .E. $-U$
PREC=7 OR WHENEVER Z .£.$/$ .OR. Z .E. $*$
PREC=6 OR WHENEVER Z .£.$-$ .OR. Z .E. $+$
PREC=5 OR WHENEVER Z .E. RTEND .OR. Z .E. LFTEND
PREC=4 OTHERWISE
PRECIS
END OF CONDITIONAL FUNCTION RETURN PREC END OF FUNCTION
in Datamation 7(12) Dec 1961 view details
in The Computer Journal 4(3) October 1961 view details
The paper by J. Iliffe on "The Use of the GENIE System in Numerical Calculation" describes a mathematical programming language for the Rice University computer. The GENIE language bears a strong resemblance both to ALGOL and to the ADES language developed several years ago by the reviewer. GENIE has some of the best features of both languages. It also embodies some ideas not possessed by either of these systems or any other system of this kind. Perhaps the most important departure from .\LGOL is the extension of the domain of possible values assigned to the symbols in the language. Whereas in ALGOL values are limited to real, integer and Boolean, GENIE permits as additional domains of values other symbol sets and instruction sets. Thus, the value of the expression P(ll, a) could be a set of single-address machine instructions for performing the addition ~ + v. The claim is also made that analytical processes can be performed as well as numerical processes. Another feature, although not original in GENIE, is worth mentioning. This is the use of a table of codewords for assignment of storage to arrays. The use of codewords rather than the ALGOL array declarations (or the dimension statements in FORTRAN) permits a much more flexible and efficient handling of storage assignments for arrays both in the source language and in the compiler.
Extract: Review
The paper by R. F. Clippinger titled "FACT -- A Business- Compiler: Description and Comparison with COBOL and Commercial Translator," must be singled out as an example c(-; the kind of paper which a compendium such as this should strive to present. Clippinger's excellent paper does much more than describe the FACT system for the Honeywell 800. Avoiding the dreary style of the instruction manual which one finds in most papers on programming, Clippinger gives a well-reasoned aoJcarefully thought-out discussion of the general aspects of business data processing, shows how FACT treats each major problem area and explains the technical factors which influenced the particuls~ technique chosen. At the same time, he manages to give a good account of the details of FACT by referring to 17 exhibits placed.
in The Computer Journal 4(3) October 1961 view details
in The Computer Journal 4(3) October 1961 view details
in [ACM] CACM 4(01) (Jan 1961) view details
in [ACM] JACM 9(2) April 1962 view details
in [ACM] JACM 9(2) April 1962 view details
in ACM Computing Reviews 3(04) July-August 1962 view details
in ACM Computing Reviews 3(05) September-October 1962 view details
The technique used in the body of the text is to introduce a sequence of standard problems requiring only an elementary level of mathematical sophistication for their understanding, and to show how procedures for carrying out their solution can be written in the language under discussion.
Eight of the total of twelve chapters are directed in this way (The Change Problem; The Social Security Problem; The SecretCode Problem; Monte Carlo Methods; A Sorting Problem; The Correlation Coefficient; A Program to Produce Programs; Simultaneous Linear Equations). Many of the features of the MAD language are introduced along with the problems which illustrate their application. In addition, there are two early chapters specifically devoted to language description (Expressions; Conditional Statements and Iteration Statements) and two final chapters to round out the picture (The MAD Language; Other Computer Languages).
In his exposition, the author manages to cover quite a number of the fundamental issues bearing on algorithmic procedures, as well as to bring out many points of programming technique. The simplified applications discussed are all meaningful, though it might be wished that more explanation of their relevance to the real world had been included. A case in point is the "program producing program" example, which is presented as if it were a clever exercise without any particular practical connotation. There are also instances where the urge to simplify has led the author to omit some really essential facet of the application under discussion. For example, the treatment of sorting is entirely framed in terms of rearranging numbers, without reference to the customary context in which such numbers function as key data for a more extensive body of information.
The inclusion of problems at the end of each chapter should make the book useful as an elementary text. From this point of view, it seems unfortunate that a work of this sort (and with this title) should not contain even the barest coherent functional description of a computer and its manner of operation. In his introduction, the author explicitly justifies this omission on the grounds that he is interested in procedures and problems, not the hardware for solving them. That being the case, however, more attention should have been paid to the delineation of precisely what a procedure is, and the relation between it and the language used to specify it.
The book is written in a breezy, informal style which leads to the presentation of many key concepts in a casual parenthetical manner: "(An operand is a symbol or expression upon which an operation is performed.);" "(Generally, one refers to a string of quantities, indexed by some subscript, as a rector; we do so here, also.) ;" and ". . . the list of parameters (i.e., those variables, function names, etc., which may change from one computation to another)...." More precision and less ofthandedness would presumably have been helpful to the reader aiming to gain real insight into the concepts involved.
Finally, mention should be made of a point not relevant to the central purpose of the book, but important nonetheless: the definition of "correlation coefficient" in Chapter 8 does not agree with statisticians' usage and hence the discussion there is very misleading. For example, according to the author's definition, the correlation coefficient associated with the vectors (1, 3, 5) and ( - 5, - 1, 3) would be r = 1/5 (dot product divided by product of lengths), whereas the conventional definition (where the mean is first subtracted from each component) would give r = 1.
R. L. Ashenhurst, Chicago, III.
in ACM Computing Reviews 4(01) January-February, 1963 view details
in [ACM] CACM 6(10) (Oct 1963) view details
in [ACM] CACM 6(10) (Oct 1963) view details
in [ACM] CACM 6(10) (Oct 1963) view details
in [ACM] CACM 7(01) (Jan 1964). view details
Several quite different approaches to languages and systems for student Jobs have been used at various Universities. [... Some] feel that the language available to students should be a very rich language. It may be necessary to start by teaching only subsets of such languages, but the students will soon be in a position to do the more interesting and complicated things that a computer can do and they will want a language with greater capabilities than Standard Fortran Systems now offer. The best known example in this class is MAD developed at the University of Michigan where the enrichment of the language was combined with a high-speed low-overhead processor.
in Proceedings of the 19th ACM national conference January 1964 view details
To go on with the Algol development, the years 1958-1959 were years in which many new computers were introduced, The time was ripe for experimentation in new languages. As mentioned earlier there are many elements in common in all Algebraic languages, and everyone who introduced a new language in those years called it Algol, or a dialect of Algol. The initial result of this first attempt at the standardization of Algebraic languages was the proliferation of such languages in great variety.
A very bright young programmer at Burroughs had some ideas about writing a very fast one pass compiler for Burroughs new 220 computer. The compiler has come to be known as Balgol.
A compiler called ALGO was written for the Bendix G15 computer. At Systems Development Corporation, programming systems had to be developed for a large command and control system based on the IBM military computer (ANFSQ32). The resulting Algebraic language with fairly elaborate data description facilities was JOVIAL (Jules Schwartz' own Version of the International Algebraic Language). By now compilers for JOVIAL have been written for the IBM 7090, the Control Data 1604, the Philco 2000, the Burroughs D825, and for several versions of IBM military computers.
The Naval Electronics Laboratory at San Diego was getting a new Sperry Rand Computer, the Countess. With a variety of other computers installed and expected they stressed the description of a compiler in its own language to make it easy, among other things, to produce a compiler on one computer using a compiler on another. They also stressed very fast compiling times, at the expense of object code running times, if necessary. The language was called Neliac, a dialect of Algol. Compilers for Neliac are available on at least as great a variety of computers as for JOVIAL.
The University of Michigan developed a compiler for a language called Mad, the Michigan Algorithmic Decoder. They were quite unhappy at the slow compiling times of Fortran, especially in connection with short problems typical of student use of a computer at a University. Mad was, originally programmed for the 704 and has been adapted for the 7090 It too was based on the 1958 version of Algol.
All of these languages derived from Algol 58 are well established, in spite of the fact that the ACM GAMM committee continued its work and issued its now well known report defining Algol 60.
in [AFIPS JCC 25] Proceedings of the 1964 Spring Joint Computer Conference SJCC 1964 view details
The author distinguishes between order-dependent and orderindependent input. In the latter case the input is punched in the form A = 7.5, B = 1.95 etc. In order for this to work it is clearly necessary to have the adresses assigned to A and B available at run time. In the case of arrays, dimensioning information must also be available.
The University of Michigan System in connection with the MAD translator makes the whole symbol table available at run time, and can thus provide a more powerful format-free input system. The system described in the present paper is apparently not willing to use the space that might be required to store the whole symbol table at run time. It requires that external names be given at compile time to all variables for which format~free input is to be used.
FORTRAN II already provides an option that permits the symbol table to be made available at load time in connection with the source language DEsuG feature. In the opinion of the reviewer it would be useful to have another option that would permit the symbol table to be made available at run time for programs with sufficient unused memory space. This would permit a slightly more elegant treatment of orderindependent format-free input.
The paper is marred by a typographical error in bold-face type. The heading of paragraph 2 says order- department where it means order-dependent.
in ACM Computing Reviews 5(02) March-April 1964 view details
This edition is a major revision and extension of the first, to incorporate the changes to the (CTSS) Compatible Time-Sharing System during the past two years. The manual itself is organized into sections for easy referencing and to facilitate future expansion and modification. The manual is maintained on-line within the system in an attempt to keep all system documcutation continuously up to date. A system user can keep his manual updated by periodically inspecting a table of contents and requesting an on-line printout of those sections which have been revised since he last updated his copy.
Some features of the CTSS which are detailed in this edition are: password logic, introduction of more elaborate accounting features, inter-console message, public files, and macrocommands. A new file system was implemented to remove some previous weaknesses and to test a prototype of the file system which is proposed for the next timesharing system.
Available languagcs and subsystems include AED (modified ALGOL), BEFAP, COGO-90, COMIT, DYNAMO, ESL DisplaySystem, LAPC, GPSS, MAD, T\IADTHN, SNOBOL, STRESS, and BLOW (BLODI Diagram Compiler). The manual presents a brief description of general subroutines and a description of commands for the creation, editing, compression, printing, and housekeeping of files, program execution and debugging.
in ACM Computing Reviews 5(02) March-April 1964 view details
in Sass, M. and W. Wilkinson, eds. Computer Augmentation of Human Reasoning Spartan Books, Washington, D.C., 1965 view details
As President of the Association for Computing Machinery I welcome you to this Conference on Programming Languages and Pragmatics. Many thanks are due to the System Development Corporation for sponsoring the conference. Even more thanks are due to the computer scientists around the world who created the subject of programming systems and brought, it to the point where it merits a third major conference of this type.
You will recall that the first conference was held in Princeton in August, 1963 on the syntax of languages. A second conference on the semantics of languages was held in Vienna in September, 1964. And now this week's conference takes up the pragmatics of languages.
I am glad that it is the meeting on pragmatics to which I am privileged to address a welcome, for I am fundamentally a user of computers. As a numerical analyst, I mostly want to get my work done and my problem solved. As a teacher of elementary programming in Stanford's Computer Science Department I am most concerned that the languages be practically usable to the learner, and that the systems permit me to use the computer to help the stu-dent. I hope that pragmatics deals with those questions! Let me be specific: The two most pleasant language systems for the general scientific user that I happen to know of are both in the ALGOL 58 family: they are the Michigan MAD system and the BALGOL system for the Burroughs 220 computer (later expanded at Stanford into SUBALGOL). Let me concentrate on BALGOL, which I know better. In addition to the general features of ALGOL which most of you know, the BALGOL system had two splendid features for a user like me:
(1) The combination of language and compiler had Lhe accommodating property of "making do" in spite of programming errors. In presence of some stupid error, like the omission of a paren, the system did its best to remedy the error, write you a warning about it, and then go on to complete the compilation and enter execution. This usually meant that we could learn about the run-tim behavior of at least that part of our program which preceded syntactical error. This feature always struck me as a very reasonable and pragmatically satisfactory approach to the customer. I have been grieved to find that our ALGOL 60 compilers have not been able to supply this service. When I ask our people about it, they tell me that, ALGOL 60 isn't the kind of language you can do this with.
If this is so, it seems to represent a large pragmatic deficiency in ALGOL 60. Is ALGOL 60 a language which can deal gracefully only with programming perfection, but collapses in the face of error? Whether the answer in yes or no, I hope you will put this property of accommodation to error into your list of useful characteristics for systems to have.
(2) The other nice property of the BALGOL system was a twofold one. First, the compiler could be persuaded to generate a relocatable machine-language procedure from a BALGOL procedure declaration. (Mr. Roger Moore was the persuader.) Second, Burroughs furnished customers not just a compiler, but actually a compiler generator, so that we could at any time create a new compiler with any library for which we could furnish machine-language relocatable procedures.
With these two features together, I could write teaching and grading programs in BALGOL separately for each problem. A small amount of operator work would enable these to be compiled into the compiler's library, where the students could have access to them in a most convenient way.
I was quite disappointed to find that none of the compilers on our IBM 7090 or Burroughs B-5000 systems were able to duplicate this convenient feature, for various reasons I do not understand.
I am not here to sell you the obsolete Burroughs 220 computer system. But I am trying to illustrate some good pragmatic properties of a certain system. Such a system was conceived by a team which surely had the user's point of view clearly in front of them. And I just happen to think that the computer user is a mighty important person, and a person who is all too easily forgotten in this world of systems experts.
If computing is to become the public utility that so many of you speak of, then computer folk had better start emulating successful utilities people. Let me cite the Bell Telephone System as one successful utility, however you look at it. You will note that its changes are made gradually, after very substantial customer research and shake-down periods. You will note that the steps from research to operation are many, slow, and carefully controlled. I have heard it said that the Bell Telephone Laboratories has hundreds of people with thousands of ideas for changing the telephone system, and that any one of these people could utterly bankrupt the service, if he were left free to put his own research ideas into practice! So the Bell System has ways to keep the flow of research ideas orderly.
Let us hope that computer scientists use their imaginations and devise all kinds of interesting things in their research. But let us also devote substantial research time to finding out what languages and systems are best suited to the men with the problems to be solved. And let us strive for decision processes which will permit us to adopt the best systems, and for enough orderliness to keep change gradual. Computing has become too important in our civilization to be aJlowed the privilege of disorder in its operational progress.
I wish you the greatest of success in your conference on pragmatics!
in [ACM] CACM 9(03) March 1966 includes proceedings of the ACM Programming Languages and Pragmatics Conference, San Dimas, California, August 1965 view details
An important step in artificial language development centered around the
idea that i t is desirable to be able to exchange computer programs between
different computer labs or at least between programmers on a universal level.
In 1958, after much work, a committee representing an active European computer
organization, GAMM, and a United States computer organization, ACNI,
published a report (updated two years later) on an algebraic language called
ALGOL. The language was designed to be a vehicle for expressing the processes
of scientific and engineering calculations of numerical analysis. Equal stress was
placed on man-to-man and man-to-machine communication. It attempts to
specify a language which included those features of algebraic languages on
which it was reasonable to expect a wide range of agreement, and to obtain a
language that is technically sound. In this respect, ALGOL Set an important
precedent in language definition by presenting a rigorous definition of its syntax.
ALGOL compilers have also been written for many different computers.
It is very popular among university and mathematically oriented computer
people especially in Western Europe. For some time in the United States, it will
remain second to FORTRAN, with FORTRAN becoming more and more like
ALGOL.
The largest user of data-processing equipment is the United States Government.
Prodded in Part by a recognition of the tremendous programming investment
and in part by the suggestion that a common language would result only
if an active Sponsor supported it, the Defense Department brought together
representatives of the major manufacturers and Users of data-processing equipment
to discuss the problems associated with the lack of standard programming
languages in the data processing area. This was the start of the conference on
Data Systems Languages that went on to produce COBOL, the common business-
oriented language. COBOL is a subset of normal English suitable for expressing
the solution to business data processing problems. The language is
now implemented in various forms on every commercial computer.
In addition to popular languages like FORTRAN and ALGOL, we have
some languages used perhaps by only one computing group such as FLOCO,
IVY, MADCAP and COLASL; languages intended for student problems, a
sophisticated one like MAD, others like BALGOL, CORC, PUFFT and various
versions of university implemented ALGOL compilers; business languages in addition
to COBOL like FACT, COMTRAN and UNICODE; assembly (machine)
languages for every computer such as FAP, TAC, USE, COMPASS; languages to simplify problem solving in "artificial intelligence," such as the so-called list
processing languages IPL V, LISP 1.5, SLIP and a more recent one NU SPEAK;
string manipulation languages to simplify the manipulation of symbols rather
than numeric data like COMIT, SHADOW and SNOBOL; languages for
command and control problems like JOVIAL and NELIAC; languages to simplify
doing symbolic algebra by computer such as ALPAK and FORMAC;
a proposed new programming language tentatively titled NPL; and many,
many, more. A veritable tower of BABEL!
in [ACM] CACM 9(03) March 1966 includes proceedings of the ACM Programming Languages and Pragmatics Conference, San Dimas, California, August 1965 view details
in [ACM] CACM 9(03) March 1966 includes proceedings of the ACM Programming Languages and Pragmatics Conference, San Dimas, California, August 1965 view details
in [ACM] CACM 9(03) March 1966 includes proceedings of the ACM Programming Languages and Pragmatics Conference, San Dimas, California, August 1965 view details
in ACM Computing Reviews 8(01) January-February 1967 view details
in ACM Computing Reviews 8(01) January-February 1967 view details
in Computers & Automation 16(6) June 1967 view details
in Halpern, Mark I and Shaw Christopher J (eds) "Annual Review in Automatic Programming" (6) 1969 Pergamon Press, Oxford view details
in [ACM] CACM 12(08) (Aug 1969) view details
in [ACM] CACM 12(08) (Aug 1969) view details
The Michigan Algorithm Decoder (MAD) is a system which was developed at the University of Michigan originally for the IBM 704 and then for the 709/90/94. The work was started in the spring of 1959 by R. Graham, and subsequently he, B. Arden, and B. Galler produced the first version of MAD; this required about two man-years of work. Their original intent was to implement ALGOL 58. However, they found there were things they did not like in ALGOL 58, so some changes were made. In the summer of 1959they felt a fast compiler was needed for their IBM 704. A system which was very much along the spirit of GAT (see Section IV.2.2.3) was finished around February, 1960 and given to SHARE. It was designed to be a fast translator for the 704 and expected to be used primarily by students. The main objectives were speed of translation, generality, ease of use, few rules to learn, and ease of adding to the language.
As with many other such systems, it is still being improved by the University of Michigan, and there have been numerous versions (each containing the previous one as a subset). It has also been heavily used at M.I.T., but that version was frozen in a manual dated November, 1964. The source document used for this description is the 1966 MAD manual [UM66].
It is interesting to see that the MAD compiler has served a rather inverted purpose relative to compatibility. Because a number of people were interested in using the FORTRAN language and yet wanted to obtain the speed of the MAD compiler, a system called MADTRAN (written in MAD) was developed. MADTRAN was simply a translator from FORTRAN to MAD, which then of course compiled machine code. It was distributed through SHARE and used at several places. MADTRAN assumes correct FORTRAN programs, so it provides no diagnostics; thus if the programmer has errors, he is in trouble. It is believed, however, that any correct FORTRAN program will be correctly translated by the MADTRAN system.
The basic purpose of MAD was stated by Arden, Galler, and Graham [AR61a] as being "developed for the specific purpose of training large numbers of university students and handling the large volume of university research problems. The primary motivation for writing this rapid translator may be traced directly to the special environment of a university computing center." They then go on to say that "ALGOL 58 provided the basic pattern for the language and to the extent that ALGOL 58 is like ALGOL 60, MAD is an ALGOL translator.'' {14} In my opinion, MAD is no more of an ALGOL translator than a FORTRAN translator. MAD was motivated by ALGOL 58, but it does not resemble ALGOL 58 in any significant way.
The original language was primarily designed and implemented by the people noted at the start of this section. Maintenance and improvements have been made by these and a few other people at the University of Michigan since then. The primary documentation has been a sequence of official manuals, each including some extensions which were originally documented as addenda and minor revisions to the many printings of the first edition [UM60]. The source used for the description in this book is the August, 1966 version [UM66]. Because of the way these manuals were printed, noindividual(s) is shown as an actual author, although indications of those involved are given on the title page.
Variations of the language have been implemented for at least the IBM 7040, Philco 210-21 I, and the UNIVAC 1107. These are not necessarily compatible with the version described in the manual or in this section.
The character set consists of the 26 upper-case letters, the 10 digits, and the following special characters:
-I- - , / = ) ( $ blank
There are a number of key words.
Constants can be either integer, floating point, logical (1B = true and 0B = false), octal (written as up to 12 octal integers followed by the letter K), or alphabetic. The alphabetic constants are normally called literals and consist of up to 6 characters of any kind preceded and followed by the dollar sign, $, e.g., $ABC$, $D + 3 = $, etc. Any of the constants above can be declared to be a mode (e.g., integer, logical, etc.) other than the normallydeclared one (floating point) by following it with the letter M and a code number.
Both data names and statement labels have the same form, namely a letter followed by zero to five letters or digits. The same name cannot be used for a variable name and a statement label. Both variable and statement labels can be subscripted, and the latter are enclosed without parentheses. There is no limit on the number of subscripts. For one- or two-dimensional arrays, data name subscripts can consist of any arithmetic expression and call themselves be subscripted. However, the expressions for subscripts in an array with more than two dimensions must be integers. There are a few reserved words, primarily some function and system names. The bulk of the key words in the language are not reserved words since they are longer than six letters and the other symbols are surrounded by periods. There is, however, a standard set of abbreviations which can be used to replace the longer words. This consists of the first and last letters with an apostrophe between them, such as W'R for WHENEVER and D'N for DIMENSION.
All operators except those represented by single nonletter characters are surrounded by periods. The operators include the five arithmetic ones, + - * / and .p. (for exponentiation); the absolute value .ABS.; negation --, and the relational and logical operators. The relational operators include equal, not equal greater, greater than or equal, less than, and less than or equal; these are designated, respectively, by .E., .NE., -G., .GE., .L., and .LE.. The Boolean operators are .NOT., .OR-, .AND., .THEN,, .EQV., and .EXOR., where the last three represent, respectively, implies, equivalence, and exclusive or. There are also operations for full words, consisting of bitwise negation .N., logical and .A., logical or .V., and exclusive or .EV.. Punctuation as such has no meaning, except for commas to separate lists of items. Blanks are not significant except in literals. There are no noise words.
The input form is designed for cards, with the statement labels anywhere in columns 1 to I0, the statements beginning anywhere in columns 12 to 72, and a continuation symbol permitted in column 11. A statement or declaration must start on a new card. In my opinion, the conceptual form is a mixture of ALGOL and FORTRAN.
There are several declarations and they are described later. The smallest executable unit is any of the specific statements that exist. There is no way of grouping them. There is loop control by means of the THROUGH statement and by the use of conditional statements.
There are two main types of functions, the internal and external. A MAD procedure is merely a function with multiple inputs and/or outputs. Statement labels and function names may be used as arguments. The external functions are normally called subroutines or procedures; i.e., they are headedby the declaration EXTERNAL and the statements that follow are to be translated independently of the main program in which they are used. Internal functions are translated as they occur relative to the other parts of the program. A one-sentence definition of internal functions is permitted; e.g., the user can write
INTERNAL FUNCTION COSUM. (A,B,C) = A*B+B*C+A*C
Comments are indicated by the letter R in column 11. Declarations and comments can appear anywhere in the program. The program must end with the statement END OF PROGRAM. There is a provision for an ERROR RETURN statement which will then transfer control to the operating system.
Declarations and statements are delimited only by their card position, i.e., new statements and declarations must start on a new card. Recursive procedures and functions are permitted, although the user must do some of the saving and restoring work himself. Parameters are passed by value and can be expressions.
There are arithmetic, Boolean, statement label, function name, and alphanumeric variables. There is also a facility for performing certain operations on the bitwise representation of integers. The arithmetic done is integer, floating point, and Boolean. Fixed and floating point variables and constants can be combined in a single expression. When they are, the expression is considered to be in floating point mode. However, parts of the computation may be performed in integer arithmetic; as a consequence, the final results may differ from those which would be obtained by having the entire computation done in floating point.
There is no problem with the scope of data because there are only single statements in the language, i.e., no groups of executable units.
The basic assignment statement consists of a variable on t he left followed by an equal sign and an expression on the right, e.g., ALPHA=X+3+F.(X,Y). These must be of the same type, except that an integer or floating point expression on the right will be converted to a floating point or integer expression on the left if necessary.
The basic control transfer is of the form TRANSFER TO S where S is any statement label or any expression which defines the label of an executable statement. in particular, it is legitimate to write TRANSFER TO BETA (K + 2) since statement names can be subscripted. A subroutine is invoked either by direct use of its name or by using the word EXECUTE, with or without arguments, e.g., EXECUTE SORT. (A, B, C) or SORT. (A, B, C). A function can be used in an expression, e.g., Z = A + COS.(X)/SIN.(X-.5).
The CONTINUE statement serves as a function point in the program but causes no computation to take place. There are two types of conditional statements. The first is the simple conditional of the form WHENEVER B, Q where B is a Boolean expression and Q is any executable statement except the END OF PROGRAM, another conditional, an iteration, or a function entry; e.g,, WHENEVER X .LE. 1, Y = A + B is legal but WHENEVER X .LE. 1, WHENEVER Y .LE. 2, A = B + C is not. This is an illustration of a place where a comma must be written, as is true in other statements. A compound conditional is of the following form:
S1 WHENEVER B1 executable statements S2 OR WHENEVER B2 executable statements
OR WHENEVER Bn executable statements Sn END OF CONDITIONAL
Often the last condition is one for which the condition is always true, and in this case the programmer may write OTHERWISE. The Si are optional statement labels. The executable statements can be simple or compound conditional statements. Testing starts with the first Bi, and as soon as something with the value true is encountered, then the set of statements following it up to tile next S(i + 1) are executed. Computation then continues from the first statement after the END OF CONDITIONAL statement. Note that this means only one of the alternative computations is performed.
The loop control is handled by the THROUGH statement which has one of the two following forms:
THROUGH S, FOR VALUES OF V = E1, E2,..., En THROUGH S, FOR V = E1, E2, B
where S is a statement label. In the second case, B is a Boolean expression. Thus we can have something of the form THROUGH POKY, FOR J = N, -1,J.L.0 which means that N is to be decreased by 1 until it is less than 0. These loops can all be properly nested, and there are no restrictions on jumping into or out of the statements in the range of the iteration. A form of the iteration statement may be assigned a value and embedded into expressions.
The only error condition statement is the ERROR RETURN, which can be put into function, subroutine, and procedure definition programs.
The following is a list of input/output statements, where F is the name of a format specification vector or a literal giving the format itself, N is an expression whose value is a tape number, L is an input/output list, and the square brackets designate an optional clause:
PRINT FORMAT F, L PRINT ON LINE FORMAT F, L PUNCH FORMAT F, L READ FORMAT F, L READ BCD TAPE N, F, L WRITE BCD TAPE N, F, L READ BINARY TAPE N, L WRITE BINARY TAPE N, L LOOK AT FORMAT F, L REWIND TAPE N END OF FILE TAPE N BACKSPACE RECORD OF TAPE N [, IF LOAD POINT TRANSFER TO S] BACKSPACE FILE OF TAPE N [, IF LOAD POINT TRANSFER TO S] SET LOW DENSITY TAPE N SET HIGH DENSITY TAPE N UNLOAD TAPE N
There are also some simplified input/output statements, namely
READ DATA where the variable names and their values are punched on cards in the form VI = n1, V2= n2,..., Vn =nn or even as values in an array written V(i) = n1, n2, . . . , nn READ AND PRINT DATA PRINT COMMENT $string starting with carriage control$ PRINT RESULTS L PRINT BCD RESULTS L PRINT OCTAL RESULTS L
If any type of error occurs during an input/output statement, the subroutine ERROR is automatically entered; the subroutine sets a flag and returns control to the operating system. There is also a way for the programmer to obtain control. Flexible format specifications are provided; they bear a strong resemblance to those of FORTRAN. The list L can be a single variable or array name, a list defined by an iteration statement including some logical expressions, or various other items.
There are no facilities for library references, except the normal use of subroutines, nor any debugging statements. There are a few built-in functions of rather special kinds, e.g., SETDIM, which updates dimension information; SYMM and TRANSP, which involve matrices. There apparently is no set of basic mathematical functions officially defined in the language. Thereare a number of system subroutines available to the user which provide some connection either with the operating system or the input-output system.
There are a number of interesting statements which are included to facilitate the writing of recursive functions and procedures. These statements cause the designation and actual use of a vector for the temporary storage of data and function returns. The statements are as follows:
SET LIST TO U[,E] U is an array element name which designates the initial temporary storage location. The optional E is an expression defining the upper limit of the length of the list. SAVE DATA L L is a list of variables or arrays and the list is stored in order in the current temporary storage vector. SAVE RETURN This causes the reentry point to the calling program to be stored as the next available element of the current temporary storage vector. RESTORE DATA L The most recent n elements become the values of the n variables in the list L and are available for use by a SAVE statement. RESTORE RETURN This restores the reentry point to the program calling the function. The last element of temporary storage is then made available for use by successive SAVE statements.
The data description declarations are handled by assuming all variables and function values have normal mode unless declared otherwise, and this normal mode is considered floating point unless stated otherwise. Any of the other modes may be specified as the normal one by writing the declaration NORMAL MODE is M where M is one of the following: INTEGER, BOOLEAN, STATEMENT LABEL, FUNCTION NAME, FLOATING POINT or n, where n is a code number. Only one such declaration can appear in a program and it applies to the entire program. Anything which is to override this normal mode must be put into a specific declaration. Format descriptions are similar to those of FORTRAN.
Storage allocation declarations are DIMENSION, EQUIVALENCE, ERASABLE, and PROGRAM COMMON, The DIMENSION statement is quite flexible. It permits negative subscripts. Among other things, it also allows changing the dimensions at object time; it permits the programmer to vary the location of the initial element in an array within the overall block which has been set aside for the array; and it allows an arbitrary storage mapping to be specified.
The EQUIVALENCE declaration has essentially the same meaning as the one in FORTRAN; i,e., the named variables are to occupy the same storage locations. The ERASABLE declaration assigns the indicated variables to a special storage area which eliminates the effective previous assignmentsto this separate storage area. There is also a PROGRAM COMMON declaration which allows a main program and several EXTERNAL function programs to refer to variables and arrays by the same name. There is no interaction among EQUIVALENCE and these other declarations.
The general form of a function declaration is
INTERNAL / EXTERNAL/ FUNCTION name. (parameter list)
body of the routine FUNCTION RETURN expression END OF FUNCTION
An alternate way of writing the first two lines is by omitting the function name on the first line and writing ENTRY TO NAME. on the second. A procedure which provides several output values as parameters omits the expression. Functions can also have multiple entry points. The same function definition can be used to define any number of functions and/or procedures. They must use exactly the same set of arguments, however. Thus, the functions CPADD. (X,Y,A,B) and CPMPY. (X,Y,A,B) can be defined by one definition, but the functions SIN. (A) and COS.(B) would require separate definitions.
An interesting compiler directive is the PARAMETER declaration, which permits the assignment of values to symbols at compile time. The user writes PARAMETER Ai(B2), A2(B2) ..... A.(B.) where Ai is an identifier and Bi is an identifier or a constant. The effect is to replace Ai by Bi in any later occurrence in the program. This is of course a special case of the more general macro facility concept.
A rather unusual declaration (for its time) in MAD is the presetting of vectors; this is done by writing VECTOR VALUES A(i) = C0, C1,... , Cn, where A is an array with each element's position reduced to a single subscript value. The values of the Ci are assigned. The Ci can be constants, statement labels, or character strings.
Probably the most interesting facility in MAD is its ability to allow some language extension by permitting the user to redefine existing operators or define new operators or modes for a particular program. This can be done because of the basic philosophy that is used in the implementation of MAD, namely the concept of an operator code number followed by modes of the variables and an address where the instruction sequence for that particular operator number begins. The exact format is as follows:
operator no. mode a mode b mode r2 mode rl address
where rl and r2 represent results (although there is normally only one).
Operators have a precedence associated with them, and this must be defined for a new operator. This provides the necessary information to thetranslator so it can understand how to handle something with a new operator in it. Three new modes may be added to the existing five: Floating Point, Integer, Boolean, Function Name, and Statement Label. It is also possible to change the meaning of some of the existing operators. To help clarify this, note the above display which shows a single entry in the operator-mode table. The relevant concept here is that an additional mode is introduced to facilitate the operation of conversion wherever this is necessary. For example, if A + B is to be computed, where A is an integer and B is a floating point number, then a preliminary conversion must be undertaken to make the operands compatible for addition. The table indicates rl and r2 as new values of A and B, respectively, where one or both may be in modes different from their original form. The actual sequence of instructions that correspond to this table can be changed in certain cases. Thus any of the arithmetic operators, as well as some of the other operators, can he redefined to have a different meaning, As an example (taken from [UM66],{15} suppose that .EV. was not in the language. In order to define a binary operation .EV. with integer operands, where the result is a bitwise exclusive or of the two operands, the programmer would write
DEFINE BINARY OPERATOR -E V., PRECEDENCE SAME AS .V. MODE STRUCTURE 1 = I .EV. 1
This would be followed by the sequence of instructions necessary to carry this out. Another possibility would be to define a binary operator which had double-precision operands and which produced a double-precision product. By means of an INCLUDE statement, definition packages may be called from a disc for matrix, complex, and double-precision arithmetic.
[...]
There are two main reasons for the speed of the MAD compiler. The first is its rather unique requirement that the key words all contain more than six letters, thus making it fairly obvious when a data name is encountered. The use of abbreviations in the form indicated on p. 208 makes it easier for the programmer to write and still permits the compiler to retain its speed. Abbreviations are expanded in the compiler-produced listing. Other reasons depend specifically on the internal techniques that are used.
MAD has proved to be quite successful in the universities because it provides some interesting features that are not available in other languages and the speed of compilation makes it a very useful tool for running a large number of student problems. It has not received much industrial usage.
One contribution to the technology made by MAD is that it provided a language which made a very fast translator easy to develop. However, the more significant contributions are some of the features which have been put into other languages (although of course in a different form), notably VECTOR VALUES and the PARAMETER declarations; one feature (definitions of new operators and data types) is just beginning to be appreciated (see Section III.7.2).
in [ACM] CACM 12(08) (Aug 1969) view details
in [ACM] CACM 15(06) (June 1972) view details
in Computers & Automation 21(6B), 30 Aug 1972 view details
in ACM Computing Reviews 15(04) April 1974 view details
The exact number of all the programming languages still in use, and those which are no longer used, is unknown. Zemanek calls the abundance of programming languages and their many dialects a "language Babel". When a new programming language is developed, only its name is known at first and it takes a while before publications about it appear. For some languages, the only relevant literature stays inside the individual companies; some are reported on in papers and magazines; and only a few, such as ALGOL, BASIC, COBOL, FORTRAN, and PL/1, become known to a wider public through various text- and handbooks. The situation surrounding the application of these languages in many computer centers is a similar one.
There are differing opinions on the concept "programming languages". What is called a programming language by some may be termed a program, a processor, or a generator by others. Since there are no sharp borderlines in the field of programming languages, works were considered here which deal with machine languages, assemblers, autocoders, syntax and compilers, processors and generators, as well as with general higher programming languages.
The bibliography contains some 2,700 titles of books, magazines and essays for around 300 programming languages. However, as shown by the "Overview of Existing Programming Languages", there are more than 300 such languages. The "Overview" lists a total of 676 programming languages, but this is certainly incomplete. One author ' has already announced the "next 700 programming languages"; it is to be hoped the many users may be spared such a great variety for reasons of compatibility. The graphic representations (illustrations 1 & 2) show the development and proportion of the most widely-used programming languages, as measured by the number of publications listed here and by the number of computer manufacturers and software firms who have implemented the language in question. The illustrations show FORTRAN to be in the lead at the present time. PL/1 is advancing rapidly, although PL/1 compilers are not yet seen very often outside of IBM.
Some experts believe PL/1 will replace even the widely-used languages such as FORTRAN, COBOL, and ALGOL.4) If this does occur, it will surely take some time - as shown by the chronological diagram (illustration 2) .
It would be desirable from the user's point of view to reduce this language confusion down to the most advantageous languages. Those languages still maintained should incorporate the special facets and advantages of the otherwise superfluous languages. Obviously such demands are not in the interests of computer production firms, especially when one considers that a FORTRAN program can be executed on nearly all third-generation computers.
The titles in this bibliography are organized alphabetically according to programming language, and within a language chronologically and again alphabetically within a given year. Preceding the first programming language in the alphabet, literature is listed on several languages, as are general papers on programming languages and on the theory of formal languages (AAA).
As far as possible, the most of titles are based on autopsy. However, the bibliographical description of sone titles will not satisfy bibliography-documentation demands, since they are based on inaccurate information in various sources. Translation titles whose original titles could not be found through bibliographical research were not included. ' In view of the fact that nany libraries do not have the quoted papers, all magazine essays should have been listed with the volume, the year, issue number and the complete number of pages (e.g. pp. 721-783), so that interlibrary loans could take place with fast reader service. Unfortunately, these data were not always found.
It is hoped that this bibliography will help the electronic data processing expert, and those who wish to select the appropriate programming language from the many available, to find a way through the language Babel.
We wish to offer special thanks to Mr. Klaus G. Saur and the staff of Verlag Dokumentation for their publishing work.
Graz / Austria, May, 1973
in ACM Computing Reviews 15(04) April 1974 view details
in SIGPLAN Notices 13(11) Nov 1978 view details
A few days after this, I called Bob Langridge, who had started using computers in 1956 in connection with x-ray diffraction studies of DNA, to ask whether he knew of anyone who was already using interactive computer graphics to model proteins or other molecular structures. He told me he did not know of anyone but he became as enthused as I at the notion of being able to do this. Within about three weeks, I had learned enough programming in the language then used at Project MAC, called MAD (Michigan Algorithm Decoder), to generate the coordinates of a polypeptide chain which could be put into the form of an alphahelix or other sub structures.
As programs were being developed for the generation of protein coordinates so that displays were possible it became clear that one of the major uses of computer graphics in this work was the ease with which one could use the graphics as a way of debugging programs. The first example of this was one in which a particular bond in the peptide chain changed as the chain grew, indicating that one of the rotation matrices which I had written was not orthogonal. As soon as this was clear, it was simple to find the problem and correct it.
in SIGPLAN Notices 13(11) Nov 1978 view details
It was not long before assemblers and compilers took over the job of managing machine operations. Programs were divided into two major sections: procedures and data. The small storage capacity raised a problem: to store all numbers with the same number of bits required a choice. If the word size was small, precision was limited; if large, relatively few numbers could be stored. A compromise was reached by storing numbers in several different formats that used more storage when greater precision was required. Data-types had arrived.
It was to be a several years before the term polymorphism was applied in the computer field. An early use of the word is cited in the OED: "The various portraits of her majesty astonish by their perplexing polymorphism.. ." [1839 Fraser's Mag. XX. 699].
Compilers in the fifties required a set of declarations that preceded the executable code. The names of variables were classified into groups that specified the storage formats of their respective members. Different instruction sequences were needed to perform arithmetic on differently formatted numbers.
Nonnumeric data was a category by itself. Before long nonnumeric subcategories, i. e., data-types, were recognized. Some of them formed nested sequences, just as the early numeric types - bits, small integers, large integers, and floating point - formed a natural sequence. The domain of a function was the set of data-types on which it could operate.
A typical OOPS requires declaration of the data-types and functions that apply to them in a different way. Instead of considering functions and the data-types that they can accept, it considers data-types and the sets of functions that can use them. As in the case of FORTRAN, declarations must be complete before programming begins. The sets of functions could be thought of as function-types, although the term has been little used, if at all.
No matter just how the information on data and function types were stored in the early computer and compiler days, and no matter whether they were stored with the CPU or on disk or drum, not many thought then about arrays of functions. The Michigan Algorithm Decoder (MAD), a compiler of the late fifties, is the only place I know of which supported indexed function name variables.
Extract: Indexed function name variables
No matter just how the information on data and function types were stored in the early computer and compiler days, and no matter whether they were stored with the CPU or on disk or drum, not many thought then about arrays of functions. The Michigan Algorithm Decoder (MAD), a compiler of the late fifties, is the only place I know of which supported indexed function name variables.
in SIGPLAN Notices 13(11) Nov 1978 view details
:for values of: [MIT] A common rhetorical maneuver at MIT is to use
any of the canonical {random numbers} as placeholders for
variables. "The max function takes 42 arguments, for arbitrary
values of 42." "There are 69 ways to leave your lover, for
69 = 50." This is especially likely when the speaker has uttered
a random number and realizes that it was not recognized as such,
but even `non-random' numbers are occasionally used in this
fashion. A related joke is that pi equals 3 --- for
small values of pi and large values of 3.
Historical note: this usage probably derives from the programming
language MAD (Michigan Algorithm Decoder), an Algol-like language
that was the most common choice among mainstream (non-hacker) users
at MIT in the mid-60s. It had a control structure FOR VALUES OF X
= 3, 7, 99 DO ... that would repeat the indicated instructions for
each value in the list (unlike the usual FOR that only works for
arithmetic sequences of values).
in SIGPLAN Notices 13(11) Nov 1978 view details
I should talk a little about the history of MAD, because MAD was one of our major activities at the Computing Center. It goes back to the 650, when we had the IT compiler from Al Perlis. Because of the hardware constraints - mainly the size of storage and the fact that there were no index registers on the machine - IT had to have some severe limitations on what could be expressed in the language. Arden and Graham decided to take advantage of index registers when we finally got them on the 650 hardware. We also began to understand compilers a little better, and they decided to generalize the language a little. In 1957, they wrote a compiler called GAT, the Generalized Algebraic Translator. Perlis took GAT and added some things, and called it GATE - GAT Extended.
GAT was not used very long at Michigan. It was okay, but there was another development in 1958. The ACM [Association for Computing Machinery] and a European group cooperatively announced a "standard" language called IAL, the International Algebraic Language, later changed to Algol, Algorithmic Language, specifically Algol 58. They published a description of the language, and noted: "Please everyone, 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 that everyone would use this one wonderful language universally instead of the several hundred already developing all over the world. The cover of an issue of the ACM Communications back then showed a Tower of Babel with all the different languages on it.
John Carr was very active in this international process. When he returned to Michigan from the 1958 meeting with the Europeans, he said:
We've got to do an Algol 58 compiler. 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, and we've
done GAT. Let's see if we can help.
So we decided to do an Algol 58 compiler. I worked with Arden and Graham; Carr was involved a little but left Michigan in 1959. There were some things wrong - foolish inclusions, some things very difficult to do - with the Algol 58 language specification. When you write a compiler, you have to make a number of decisions. By the time we designed the language that we thought would be worth doing and for which we could do a compiler, we couldn't call it Algol any more; it really was different. That's when we adopted the name MAD, for the Michigan Algorithm Decoder. We had some funny interaction with the Mad Magazine people, when we asked for permission to use the name MAD. In a very funny letter, they told us that they would take us to court and everything else, but ended the threat with a P.S. at the bottom - "Sure, go ahead." Unfortunately, that letter is lost.
So in 1959, we decided to write a compiler, and at first it was Arden and Graham who did this. I helped, and watched, but it was mainly their work because they'd worked on GAT together. At some point I told them I wanted to get more directly involved. Arden was doing the back end of the compiler; Graham was doing the front end. We needed someone to do the middle part that would make everything flow, and provide all the tables and so on. I said, "Fine. That's my part." So Graham did part 1, Galler did part 2, and Arden did part 3.
A few years later when Bob Graham left to go to the University of Massachusetts, I took over part 1. So I had parts 1 and 2, and Arden had 3, and we kept on that way for several years. 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. People still tell me they remember my standing up at that meeting and saying at one of the Fortran discussions, "This is all unnecessary, what you're arguing about here. Come to our session where we talk about MAD, and you'll see why."
Q: Did they think that you were being very brash, because you were so young?
A: Of course. Who would challenge IBM? I remember one time, a little bit later, we had a visit from a man from IBM. He told us that they were very excited at IBM because 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 on the IBM 704, and we smiled. 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 for the computer to do during the 20-second rewind in the middle of their whole Fortran processor.
In developing MAD, we were able to get the source listings for Fortran on the 704. Bob Graham studied those listings to see how they used the computer. The 704 computer, at that time, had 4,000 36-bit words of core storage and 8,000 words of drum storage. The way the IBM people overcame the small 4,000-word core storage was to store their tables on the drum. They did a lot of table look up on the drum, recognizing one word for each revolution of the drum. 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's a lot of table look-up stuff in any 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, we put data out there for temporary storage and bring it back only once, when we need it. So we developed all of our tables in core. When they overflowed, we stored them out on the drum. That is, part 1 did all of that. Part 2 brought the tables in, reworked and combined them, and put them back on the drum, and part 3 would call in each table when it needed it. We did no lookup on the drum, and we were able to do the entire translation in under a second.
It was because of that that MIT used MAD when they developed CTSS, the Compatible Time-Sharing System, and needed a fast compiler for student use. It was their in-core translator for many years.
MAD was successfully completed in 1961. Our campus used MAD until the middle of 1965, when we replaced the 7090 computer with the System /360. During the last four years of MAD's use, we found no additional bugs; it was a very good compiler. One important thing about MAD was that we had a number of language innovations, and notational innovations, some of which were 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 some important notation, from MAD, but they told me that privately.
We published a number of papers about MAD and its innovations. One important thing we had was a language definition facility. People now 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. There's a lot of work in extensible languages now, and unfortunately, not a lot of people credit the work we did, partly because we delayed publishing for so long. While people knew about it and built on it, there was no paper they could cite.
in IEEE Annals of the History of Computing, 23(1) January 2001 view details
MAD was developed at the University of Michigan in 195960 for the IBM 704. It was very widely used on the IBM 7090 and 7094, the Philco 2000, and UNIVAC 1100 computers during the 1960s for the purpose of teaching programming to college students. Michigan published a reference manual, but most students learned MAD from the MAD PRIMER, written by Elliott Organick of the University of Houston and distributed by Ulrichs Book Store of Ann Arbor, Michigan. Organick also wrote a more widely used FORTRAN PRIMER. The MAD compiler for the UNIVAC 1100 computers called RALPH was developed at the University of Maryland. The name RALPH is an acronym of sorts: Reentrant Algorithmic Language Processor with H just for the H of it. (The explanation of the acronym is supplied by George Baltz, formerly at the University of Maryland.) The RALPH processor could compile either FORTRAN or MAD, depending on the option selected.
MAD is perhaps most famous for the line printer picture of Alfred E. Neumann which was printed when an attempted compilation had too many errors. Underneath the picture it printed the caption: See this man about your program--He might want to publish it. He never worries--but from the looks of your program, you should. MAD faded from the scene in the 1970s.
A very simple MAD program follows:
INTEGER A
START A = 1
WHENEVER A .G. 0
PRINT COMMENT $ A GTR 0$
OTHERWISE
PRINT COMMENT $A LEQ 0$
END OF CONDITIONAL
PRINT COMMENT $ END $
END OF PROGRAM
The WHENEVER OTHERWISE END OF CONDITIONAL is equivalent to an if-else statement External link: Online copy at UNISIS History
in IEEE Annals of the History of Computing, 23(1) January 2001 view details