GAT(ID:409/gat001)Generalized Algebraic TranslatorGeneralized Algebraic Translator. Improved version of IT. Derived initially from a translator from IT to FOTRTRAN. "The Generalized Algebraic Translator (GAT) was written at the University of Michigan Statistical and Computing Laboratory for a 650 with index registers, floating point arithmetic, and special characters" Places Hardware:
Related languages
Samples: References: in Preprints of papers presented at the 13th national meeting of the Association for Computing Machinery, June 11-13, 1958, Urbana, Illinois view details The Generalized Algebraic Translator (GAT) was written at the University of Michigan Statistical and Computing Laboratory for a 650 with index registers, floating point arithmetic, and special characters. Some of the main features of the Translator are: (a) Single pass. Optimized five/card machine instructions are produced directly from the original statements. Floating point and indexing instructions are generated. (b) Variables. Variable names are subscripted letters, as in IT, although a larger set of letters is allowed. Variables are either fixed point integers or floating point, and subscription is recursive. (c) Constants. Constants may be written in a statement and may be either floating, :fixed, or alphabetic. (d) Subroutines. Subroutines are called by using arbitrary alphanumeric names. All subroutines are relocatable. (e) Conventional operational hierarchy. Unparenthesized expressions are interpreted according to the commonly accepted algebraic conventions. (f) Input-output. Either numeric or alphanumeric information, identified by its appropriate symbolic labels, may be read or produced as output during execution of the object program. (g) Mixed arithmetic. Variables or constants of fixed point integer and floating point form may be included in the same expression (h) Iteration statements. Iteration variables may be fixed or floating and it is possible to make an arbitrary transformation of the designated variable. Also the initial and final values may be arbitrary expressions. (i) Matrix manipulation. The base variable and row length may be specified in a dimension statement as integer variables. Thus, during execution, regions may be essentially reassigned and sub-matrices may be considered as independent matrices. The translation techniques employed in GAT may be considered as a special ease of what seems to be a good, general translation scheme. pdfin [ACM] CACM 2(07) July 1959 view details in SESSION: Automatic programming: algorithm translators view details Shortly after FORTRAN was made available on the 650 in the form of FORTRANSIT, we ran seminars on it. I t was felt that the high mnemonic value of the FORTRAN language would be a further aid to programming. This turned out to be the case for those students or faculty members who were already familiar with the Bell System or with machine language. However, it appeared to us that those without some previous computer background did not take to the FORTRANSIT compiler system as well as they did to the Bell General Purpose Interpretive System. Students with the appropriate background and with more complex problems were pleased with the ease with which they could program their problems using FORTRANSIT. It was about this stage that we decided that we would try to make the FORTRAN system available on our 1101. Also about this time the ElectroData Division of Burroughs Corporation indicated that they planned to make the FORTRAN system available on their forthcoming 220. Thus we felt that, by writing FORTRAN for the 1101, we would be able to program a problem in the FORTRAN language and run it on any one of our three machines. In this manner we would then be able to equalize the load on our three machines. Consequently, a year ago this past summer two of our programmers started writing FORTRAN for the 1101. They continued this work until they attended the seminar on compilers held last February 18-20, 1959, at Carnegie Institute of Technology, which was jointly sponsored by Carnegie, Case, and the University of Michigan. After returning from this seminar, these two boys reviewed their work and the compiler systems presented at this conference. They then recommended that the course of their work be changed from making FORTRAN available to making the RUNCIBLE system available for the three computers. As most of you probably know, the RUNCIBLE system of Case is the result of several revisions of Dr. A. J. Perlis' IT system. Our boys felt that RUNCIBLE was logically far more complete and much more flexible in its use. It was felt that these two major advantages were sufficiently great to overcome the loss of higher mnemonic value of FORTRAN. It was thus decided that the RUNCIBLE system would be used instead of the FORTRAN system. Since RUNCIBLE is more complete logically, it would be a relatively easy task to put a translator in front of RUNCIBLE to be able to handle the FORTRAN language if it was later decided that this was desirable. Our decision to adopt RUNCIBLE rather than FORTRAN has been further justified by the fact that the ElectroData people appeared to have set aside their project to write FORTRAN for the 220. In the meantime, our programmers have also been able to run the RUNCIBLE on the 220 by use of the 650 Simulator. The simulator was written by the ElectroData people for the 220 and appears to be very efficient in the cases where we have employed it. It is true that this is not an exceedingly efficient use of the 220, but it is also true that in our case we will probably not run many compiler programs on the 220. It currently appears that we have enough people willing and able to write the machine language to keep the 220 busy. Even though we only installed the 220 early this year, we are already running two shifts on it. Most of this work is either sponsored research work or faculty-graduate student research projects that require the larger machine. Essentially, no one-shot small problems have been put on the 220. We are currently running our third seminar on the RUNCIBLE system. The attendance at these seminars has varied. This quarter our Bell seminar drew the usual sixty people, and the RUNCIBLE seminar only seven. However, the two previous RUNCIBLE seminars had about twenty each. In order that we may not be accused of being out of date relative to the current push on compilers, we are considering the possibility of offering only the RUNCIBLE seminar next quarter. Perhaps this will help overcome the mass momentum that has developed relative to the Bell System. I still have, however, the strong feeling in my own mind that, for the smaller one-shot computer projects of the uninitiated, the actual time elapsed between problem initiation and problem solution may be considerably less in using the Bell System. I had the experience of sitting down with a sharp faculty person one afternoon and describing the Bell System to him. The next day he came back with a moderately complex integration problem completely programmed and ran it on the 650. I have not had the exact set of circumstances to try the RUNCIBLE system, but I doubt that the same degree of success could be achieved. It seems very clear to me that an undisputed value for a compiler system such as RUNCIBLE or FORTRAN is for the larger-scale problems and for experimental mathematical studies, where the model is sufficiently changed to make it unfeasible efficiently to employ a simple interpretive scheme. My current feeling is that, within an educational research situation such as ours, there will always be a place for interpretive systems such as the Bell System. I t seems to me that, in learning such a system, one gets a better feeling for the way in which the machine actually functions. After all, the interpretive schemes are not too far removed from machine-language programming and yet still have many advantages over such programming. It appears that, the wider the basic knowledge that a student has, the more useful he will be when he goes out into industry, even though there his computer work may be confined to the use of a compiler. I would also concur in the continued inclusion of machine-language programming in the basic programming courses offered for credit by the Mathematics Department, the Electrical Engineering Department, or whatever department happens to offer these courses, someone has to have a sufficiently strong background to be able to build compilers. Extract: Not using GAT L. T. KNIGHT (Bendix Products Division-Missiles): I too was at that conference in Pittsburgh last February, and I was quite taken with GAT, as presented by the people from Michigan. We have not had a chance, owing to our other work load, to investigate it, as probably you have. How does it compare for scientific applications with RUNCIBLE? MR. ATCHISON: I believe that GAT is written for tape input-output. We do not have a tape system, so we were not able to use it. Extract: Not using assemblers (SOAP, STAR) You probably have noted by now that I have made no direct mention of assembly routines. This lack of reference reflects our situation at Georgia Tech. Small use has been made of them. No seminars have been run on their use. A few people have used SOAP on the 650. A very few are using STAR I on the 220. An assembly program was written for our 1101, but it was purely for intermediate purposes and had no direct use. I currently see no necessity of ever running a non-credit seminar on assembly routines, but I would advocate their inclusion in the credit courses in programming. in Proceedings of the 1959 Computer Applications Symposium, Armour Research Foundation, Illinois Institute of Technology, Chicago, Ill., Oct. 29, 1959 view details in Proceedings of the 1959 Computer Applications Symposium, Armour Research Foundation, Illinois Institute of Technology, Chicago, Ill., Oct. 29, 1959 view details in SESSION: Automatic programming: compilers view details DOI in [ACM] CACM 3(12) December 1960 view details Univac LARC is designed for large-scale business data processing as well as scientific computing. This includes any problems requiring large amounts of input/output and extremely fast computing, such as data retrieval, linear programming, language translation, atomic codes, equipment design, largescale customer accounting and billing, etc. University of California Lawrence Radiation Laboratory Located at Livermore, California, system is used for the solution of differential equations. [?] Outstanding features are ultra high computing speeds and the input-output control completely independent of computing. Due to the Univac LARC's unusual design features, it is possible to adapt any source of input/output to the Univac LARC. It combines the advantages of Solid State components, modular construction, overlapping operations, automatic error correction and a very fast and a very large memory system. [?] Outstanding features include a two computer system (arithmetic, input-output processor); decimal fixed or floating point with provisions for double precision for double precision arithmetic; single bit error detection of information in transmission and arithmetic operation; and balanced ratio of high speed auxiliary storage with core storage. Unique system advantages include a two computer system, which allows versatility and flexibility for handling input-output equipment, and program interrupt on programmer contingency and machine error, which allows greater ease in programming. in [ACM] CACM 3(12) December 1960 view details in ACM Computing Reviews 2(04) July-August 1961 view details in [ACM] CACM 6(03) (Mar 1963) view details in [ACM] CACM 6(03) (Mar 1963) 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] CACM 6(03) (Mar 1963) view details The compiler was called GAT - internally for Graham-Arden Translator but, more modestly (?), externally as the Generalized Algebraic Translator (Arden and Graham 19593). It became operational in 1958 and, importantly, it was the training ground for the subsequent implementation on the 704 of the widely used ALGOL 58 compiler called MAD (Michigan Algorithm Decoder) (Arden, Galler, and Graham 1961). Perhaps the most significant innovation was the use of an operator-precedence scan and the accompanying use of a stack. In those days it was called the "jiggling scan" because of the movement of the pointer in the text string. In retrospect, tracing exactly the origins of that algorithm is difficult. The decomposition of a fully parenthesized string was the first step, followed by the development of an algorithm to insert parentheses. Joe Smith, a colleague of Al Perlis and Tom Cheatham, made, I believe, the observation that the insertion could be eliminated by properly analyzing adjacent operators. That observation probably had its origin in the character-pair approach, but not adjacent characters. Clearly, the origins of the general approach to parsing were present. In hindsight that development seems trivially obvious, but in the context of the small machines and short history of programming, it was exciting. I remember vividly a discussion with Bob Barton of Burroughs in the Dirty Sock Building on parsing and the use of stacks. The general applicability of stacks became clear, as did the possibility of executing directly from hardware-implemented stacks. The growing acceptance of these algorithms certainly played a role in subsequent machine design. Other features of GAT were embryonic operating system capabilities, and they contributed to later operating system developments. A compact symbol table was the key to some of these features. It was not possible with 2000 locations to deal with arbitrary strings for variable names. In a manner similar to IT, variables were essentially all array elements, designated by a single leading character followed by a subscript. The leading character specified floating point or integer type. With scalar variables the subscript was always an integer (e.g., X4). For arrays, parenthesized expressions could be used-for example, X(I2,J3), Y(I1+3). Unparenthesized strings could also be used, such as KKJ4 to indicate a nesting of subscripts on an integer variable. The point of this little tutorial is that the symbol table was very small and was preserved during execution. Hence, variable-named input and output was possible, including post-mortems and snapshot dumps. To give some feeling for the language and the compiler output, the first example in the GAT manual (annotated) (Arden and Graham 1959a) is included as an appendix. Index register hardware was required (also floating-point hardware), and it was easy to make the compiler serially reentrant. As a result, batch compiling from a single loading of the compiler was straightforward. Similarly, the code produced was not self-modifying; therefore checkpointing could be incorporated conveniently. The one-pass implementation of GAT required an up-front declaration of the number of labeled statements so that forward references could be made indirectly through a transfer vector. The existence of a GOTO (integer expression) statement then made the inclusion of a branch-conditional trace feature simple. (This was aforerunner of statement-label and procedure-name vectors in MAD.) in Annals of the History of Computing, 08(1) January 1986 (IBM 650 Issue) view details At Carnegie Tech (now CMU) the 650 arrived in July 1956. Earlier in the spring I had accepted the directorship of a new computation center at Carnegie that was to be its cocoon. Joseph W. Smith, a mathematics graduate student at Purdue, also came to fill out the technical staff. A secretary-keypuncher, Peg Lester, and a Tech math grad student, Harold Van Zoeren, completed the staff later that summer. The complete annual budget -- computer, personnel, and supplies -- was $50,000. During the tenure of the 650, the center budget never exceeded $85,000. Before the arrival of the computer, a few graduate students and junior faculty in engineering and science had been granted evening access to a 650 at Mellon National Bank. In support of their research, the 650, largely programmed using the Wolontis-Bell Labs three-address interpreter system, proved invaluable. The success of their efforts was an important source of support for the newly established Computation Center. The 650 operated smoothly almost immediately. The machine was quite reliable. Even though only a one-shift maintenance contract was in force, by the start of fall classes the machine was being used on the second shift, as well as weekends. The talented user group, the stable machine, two superb software tools -- SOAP (Poley 1957) and Wolontis (see Technical Newsletter No. 11 in this issue) -- and an uninhibited open atmosphere contributed to make the center productive and, even more, an idea-charged focus on the campus for the burgeoning insights into the proper -- nay, inevitable -- role of the computer in education and research. Other than the usual financial constraints, the only limits were lack of time and assistance. The center was located in the basement of the Graduate School of Industrial Administration (GSIA). Its dean, Lee Bach, was an enthusiastic supporter of digital computation. Consequently, he was not alarmed at the explosion in the use of the center by his faculty and graduate students, and he acceded graciously to the pressure, when it came, to support the center in its requests to the administration for additional space and equipment. From its beginning the center, its staff, and many of the users were engaged in research on programming as well as with programming. So many problems were waiting to be solved whose programs we lacked the resources to write: We were linguistically inhibited, so that our programs were too often exercises in stuttering fueled by frustration. Before coming to Carnegie, Smith and I had already begun work on an algebraic language translator at Purdue intended for use on the ElectroData Datatron computer, and we were determined to continue the work at Carnegie. The 650 proved to be an excellent machine on which to pursue this development. Indeed, the translator was completed on the 650 well before the group at Purdue finished theirs. The 650 turned out to have three advantages over the Datatron for this particular programming task: punched cards being superior to paper tape, simplicity in handling alphanumerics, and SOAP. The latter was an absolutely crucial tool. Any large programming task is dominated by the utility with which its parts can be automatically assembled, modified, and reassembled. The translator, called IT for Internal Translator (see Perlis and Smith 1957), was completed shortly after Thanksgiving of 1956. In the galaxy of programming languages IT has become a star of lesser magnitude. IT'S technical constructs are of historical interest only, but its existence had enormous consequences. Languages invite traffic, and use compels development. Thus IT became the root of a tree of language and system developments whose most important consequence was the opening of universities to programming research. The 650, already popular in universities, could be used the way industry and government were soon to use FORTRAN, and education could turn its attention to the subject of programming over and above applications to the worlds of Newton and Einstein. The nature of programming awaited our thoughts. No other moment in my professional life has approached the dramatic intensity of our first IT compilation. The 650 accepted five cards (see Figure 1) and produced 42 cards of SOAP code (see Figure 2) evaluating a polynomial. The factor of 8 was a measure of magic, not the measure of a poor code generator. For me it was the latest in a sequence of amplifiers, the search for which exercises computation. The 650 implementation of IT had an elastic quality: it used 1998 of the 2000 words of 650 storage, no matter what new feature was added to the language. Later in 1957 IT-2 was made available and bypassed the need for SOAP completely. IT-2 translated the IT language directly into machine code. By the beginning of 1958 IT3 became available. It was identical to IT-2 except that all floating-point arithmetic was performed in double precision. For its needs GSIA produced IT-2- S which was IT-2 using scaled fixed-point arithmetic. The installation of the FORTRAN character set prompted the replacement of IT-9 by IT-2- A-S, which used both the FORTRAN character set and floating-point hardware. With IT-2-A-S the work on IT improvements came to an end at Carnegie. While the IT developments were being carried out within our Computation Center, parallel efforts were under way on our machine in the development of list-processing languages under the direction of Allen Newell and Herbert Simon. The IPL family and the IT family have no linguistic structure in common, but they benefited from each other's existence through the continual interaction of the people, problems, and ideas within each system. The use of Wolontis decreased. Soon almost all computation was in IT, and use expanded to three shifts. By the end of the summer of 1957, IT was in the hands of a number of other universities. Case and Michigan made their own improvements and GAT, developed by Michigan, became available in 1958 (see Arden and Graham 1958). It bypassed SOAP, producing machine code directly, and used arithmetic precedence. We were so impressed by GAT that we immediately embarked on its extension and produced GATE (GAT Extended) by spring of 1959. GATE was later transported to the Bendix G-20 when that computer replaced the 650 at Carnegie in 1961. The increased use of the machine and the increased dependence on IT and its successors as a programming medium pressured the computing center into continual machine expansion. As soon as IBM provided enhancements to the 650 that would improve the use of our programming tools, our machine absorbed them: the complete FORTRAN character set, index registers, floating point, 60 core registers, masking and format commands and, most important, a RAMAC disk unit. All but the last introduced trivial modifications to our language processors. There was the usual grumbling from some users because the enhancements pressured (not required) them to modify both the form and logic of their programs. The users were becoming computer-bound by choice as well as need, though, and they had learned the first, and most important, lesson of computer literacy: In man-machine symbioses it is the human who must adjust, adapt, and learn as the computer evolves along its own peculiar gradients. Getting involved with a computer is like having a cannibal as a valet. Most universities opted for magnetic tape as their secondary storage medium; Carnegie chose disks. Our concern with the improvement of the programming process had thrust upon us the question: How do programs come into being? Our answer: Pure reasoning and the artful combination of programs already available, understood, and poised for modification and execution. It is not enough to be able to write programs easily; one must be able to assemble new ones from old ones. Sooner or later everyone accepts this view -- first mechanized so admirably on the EDSAC almost 40 years ago (Wilkes, Wheeler, and Gill 1957). Looked at in hindsight, our concern with the process of assembly was an appreciation of the central role evolution plays in the man-computer dialogue: making things fit is a crucial part in making things work. It was obvious that retention and assembly of programs was more easily realized with disk than with tape. Like everything else associated with the 650, the RAMAC unit worked extremely well. Computation became completely dependent on it. GATE, our extension of GAT, made heavy use of the disk (Perks, Van Zoeren, and Evans 1959). Programs were getting larger, and a form of segmentation was needed. The assembly of machine-language programs and already compiled GATE programs into new ones was becoming a normal mode of use. GATE provided the vehicle for accomplishing these tasks. The construction of GATE was done by Van Zoeren and Smith. Not all programs originated in GATE; some were done in machine language. SOAP, always our model of a basic machine assembly language, had matured into SOAP 11 but had not developed into an adult assembler for a 650 with disks. IBM was about to stunt that species, so we designed and built TASS (Tech Assembly System). Smith and Arthur Evans wrote the code; Smith left Carnegie, and Evans completed TASS. A few months later he extended it to produce TASS I! and followed it with SUPERTASS. TASS and its successors were superb assemblers and critical to our programming research (Perks, Smith, and Evans 1959). Essentially, any TASS routine could be assembled and appended to the GATE subroutine library. These routines were relocatable. GATE programs were fashioned from independently compiled segments connected by link commands whose executions loaded new segments from disk. Unfortunately, we never implemented local variables in GATE, although their value was appreciated and an implementation was sketched. The TASS family represented our thoughts on the combinational issues of programming. In the TASS manual is the following list of desiderata for an assembler: 1. Programs should be constructed from the combination of units (called P routines in TASS) so that relationships between them are only those specified by the programmer. 2. A programmer should be able to combine freely P routines written elsewhere with his own. 3. Any program, once written, may become a P routine in the library. 4. When a P routine is used from the library, no detailed knowledge of its internal structure is required. 5. All of the features found in SOAP I! should be available in P routines. TASS supported an elaborate, but not rococo, mechanism for controlling circumstances when two symbols were (1) identical but required different addresses and (2) different but required identical addresses. Communication between P routines was possible both at assembly and at run time. Language extension through macrodefinitions was supported. SUPERTASS permitted nesting of macrocalls and P routine definition. Furthermore, SUPERTASS permitted interruptions of assembly by program execution and interruption of execution for the purpose of assembly. Many of the modern ideas on modularization and structured programming were anticipated in TASS more as logical extensions to programming than as good practice. As so often happens in life cycles, both TASS and GATE attained stable maturity about the time the decision to replace the 650 by the Bendix G-20 was made. Three other efforts to smooth the programming process developed as a result of the programming language work. IBM developed the FORTRANSIT system (see Hemmes in this issue) for translating FORTRAN programs into IT, thus providing a gradient for programs that would anticipate the one for computer acquisition. Van Zoeren (1959) developed a program GIF, under support of Gulf Oil Research, that went the other way so that programs written by their engineering department for their 650 could run on an available 704. Both programs were written in SOAP II. GATE translated programs in one pass, statement by statement. Van Zoeren quickly developed a processor called CORREGATE that enabled editing of compiled GATE programs by processing, compiling, and assembling into already compiled GATE programs only new statements. GATE was anticipating BASIC, although the interactive, time-sharing mode was far from our thoughts in those days. As so often happened, when a new computer arrived, sufficient software didn't. The 650 was replaced in the spring of 1961 by a superior computer, the Bendix G20, whose software was inferior to that in use on our 650. For a variety of reasons, it had been decided to port GATE to the new machine -- but no adequate assembly language existed in which to code GATE. TASS had become as complex as GATE and appeared to be an inappropriate vehicle to port to the new machine, particularly because of the enormous differences in instruction architecture between the two machines. Consequently, a new assembler, THAT (To Help Assemble Translators) was designed (Jensen 1961). It was a minimal assembler and never attained the sophistication of TASS -- another example of the nonmonotonicity of software and hardware development over time. We found an important lesson in this first transition. In the design and construction of software systems, you learn more from a study of the consequences of success than from analysis of failure. The former uses evolution to expose necessary revolution; the latter too often invokes the minimal backtrack. But who gave serious attention to the issues of portability in those days? The 650 was a small computer, and its software, while dense in function, was similarly small in code size. The porting of GATE to the G-20 was accomplished in less than one man-year by three superb programmers, Evans, Van Zoeren, and Jorn Jensen, a visitor from the Danish Regnecentralen. They shared an office, each being the vertex of a triangle, and cooperated in the coding venture: Jensen was defining and writing THAT, Evans was writing the lexical analyzer and parser, and Van Zoeren was doing the code generator. The three activities were intricately meshed much as co-routines with backtracking: new pseudooperations for THAT would be suggested, approved, and code restructured, requiring reorganization in some of the code already written. This procedure converged quite quickly but would not be recommended for doing an Ada compiler. in Annals of the History of Computing, 08(1) January 1986 (IBM 650 Issue) 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 Resources
|