SOAP(ID:121/soa001)
Symbolic Optimal Assembly Program
for Symbolic Optimal Assembly Program
Stan Foley and Grace Mitchell IBM 1955-6
IBM 650 assembly language. "Optimal" refers to rearranging instructions on slowly rotating drum memory. This optimisation was not always as good as careful hand-assembly, which led to a long-dead intellectual feud as to whether machine-generated code was "real" coding.
This is in effect what is beng parodied in the RINSO spoof
Hardware:
- IBM 650 IBM
Related languages
| ASSEMBLER | => | SOAP | Influence | |
| SAP | => | SOAP | Evolution of | |
| SOAP | => | BABEL | Influence | |
| SOAP | => | IT 2 | Intermediate language for | |
| SOAP | => | RINSO | Parody of | |
| SOAP | => | SIR | Targetting | |
| SOAP | => | SOAP I | Production version | |
| SOAP | => | SODA | Influence |
References:
Let me elaborate these points with examples. UNICODE is expected to require about fifteen man-years. Most modern assembly systems must take from six to ten man-years. SCAT expects to absorb twelve people for most of a year. The initial writing of the 704 FORTRAN required about twenty-five man-years. Split among many different machines, IBM's Applied Programming Department has over a hundred and twenty programmers. Sperry Rand probably has more than this, and for utility and automatic coding systems only! Add to these the number of customer programmers also engaged in writing similar systems, and you will see that the total is overwhelming.
Perhaps five to six man-years are being expended to write the Alodel 2 FORTRAN for the 704, trimming bugs and getting better documentation for incorporation into the even larger supervisory systems of various installations. If available, more could undoubtedly be expended to bring the original system up to the limit of what we can now conceive. Maintenance is a very sizable portion of the entire effort going into a system.
Certainly, all of us have a few skeletons in the closet when it comes to adapting old systems to new machines. Hardly anything more than the flow charts is reusable in writing 709 FORTRAN; changes in the characteristics of instructions, and tricky coding, have done for the rest. This is true of every effort I am familiar with, not just IBM's.
What am I leading up to? Simply that the day of diverse development of automatic coding systems is either out or, if not, should be. The list of systems collected here illustrates a vast amount of duplication and incomplete conception. A computer manufacturer should produce both the product and the means to use the product, but this should be done with the full co-operation of responsible users. There is a gratifying trend toward such unification in such organizations as SHARE, USE, GUIDE, DUO, etc. The PACT group was a shining example in its day. Many other coding systems, such as FLAIR, PRINT, FORTRAN, and USE, have been done as the result of partial co-operation. FORTRAN for the 705 seems to me to be an ideally balanced project, the burden being carried equally by IBM and its customers.
Finally, let me make a recommendation to all computer installations. There seems to be a reasonably sharp distinction between people who program and use computers as a tool and those who are programmers and live to make things easy for the other people. If you have the latter at your installation, do not waste them on production and do not waste them on a private effort in automatic coding in a day when that type of project is so complex. Offer them in a cooperative venture with your manufacturer (they still remain your employees) and give him the benefit of the practical experience in your problems. You will get your investment back many times over in ease of programming and the guarantee that your problems have been considered.
Extract: IT, FORTRANSIT, SAP, SOAP, SOHIO
The IT language is also showing up in future plans for many different computers. Case Institute, having just completed an intermediate symbolic assembly to accept IT output, is starting to write an IT processor for UNIVAC. This is expected to be working by late summer of 1958. One of the original programmers at Carnegie Tech spent the last summer at Ramo-Wooldridge to write IT for the 1103A. This project is complete except for input-output and may be expected to be operational by December, 1957. IT is also being done for the IBM 705-1, 2 by Standard Oil of Ohio, with no expected completion date known yet. It is interesting to note that Sohio is also participating in the 705 FORTRAN effort and will undoubtedly serve as the basic source of FORTRAN-to- IT-to-FORTRAN translational information. A graduate student at the University of Michigan is producing SAP output for IT (rather than SOAP) so that IT will run on the 704; this, however, is only for experience; it would be much more profitable to write a pre-processor from IT to FORTRAN (the reverse of FOR TRANSIT) and utilize the power of FORTRAN for free.
in "Proceedings of the Fourth Annual Computer Applications Symposium" , Armour Research Foundation, Illinois Institute of Technology, Chicago, Illinois 1957 view details
Appendix H Graphical Circuit Analysis Employing The IBM 650 Digital Computer
A program to perform the graphical analysis discussed in Section 1 has been prepared for the IBM 650 computer. The program has been run and the results obtained are shown in Fig. H-1. The program consists of two major parts. The first reduces the type 437A plate characteristics to digitized form and then interpolates several intermediate curves. The second performs the numerical computations as indicated in Section 1. Approximation of the characteristic curves was done by representing each curve by a number of straight line segments. The points thus obtained were converted to slope-intercept straight line equations. Each curve was represented by 4 segments. The method of interpolation used was to bisect the angle between a given segment and the respective segment on the next higher grid curve. This was repeated until 17 curves had been obtained from the original 5. Figure H-2 illustrates the original curves obtained experimentally. Figure H-3 shows the approximation used for representing these curves and Fig. H-4 shows the method of interpolation used. The equations solved by the program are listed after Fig. H-4. The results obtained agree closely with what would be expected with the values of circuit constants used. It is felt that the program would be useful for evaluating various combinations of input values. The program has been written so that any parameter of the circuit may be varied at will as well as the input pulse conditions. Since the original tube curves are not exact, it is felt that more exact curve fitting methods or interpolation methods would not be justified. The program was written in the "IT" language which is an interpretive translator from a mathematical language format to "SOAP" language. The deck of cards to the 650 program is available if desired.
in "Proceedings of the Fourth Annual Computer Applications Symposium" , Armour Research Foundation, Illinois Institute of Technology, Chicago, Illinois 1957 view details
An automatic programming routine called S.I.R., Symbolic Interpretive Routine, was used to program the problem. It is similar to S.O.A.P., with the addition of floating point arithmetic (automatic scaling) and several additional operations such as SINE, EXP, LOG, etc. The program can handle up to approximately 300 points on the experimental curve at one time. Extract: SOAP
The program was first written in symbolic notation in which no definite drum locations or "addresses" were used. This was then assembled and optimized by means of a program known as S.O.A.P., Symbolic Optimal Assembly Program. By means of this program addresses are assigned for the instructions in such a way that a minimum of time is required to perform the program. All data are punched on cards in eight groups or "words" each containing ten digits. The first word on each data card contains the address of the first piece of data on the card along with the total number of pieces of data on the card. This is the usual seven word format used when data are to be read in by means of the seven word loading routine. The Kurie analysis program is essentially a data handling program. Seven tables are stored in the computer. The experimental data are modified and correlated by means of extensive "table lookups," interpolation within the tables, and simple arithmetic calculatians.
Extract: MITILIAC
The least-squares program was coded in MITILAC, an interpretive routine which simplifies coding for small problems. The data are punched in the standard MITILAC data card format. The program was designed to be able to analyze ane y number of curves without having to read in the MITILAC deck and the instructions each time.
in "Proceedings of the Fourth Annual Computer Applications Symposium" , Armour Research Foundation, Illinois Institute of Technology, Chicago, Illinois 1957 view details
R.I.N.S.O.
(Real Ingenious New Symbolic Optimizer)
Edttor's Note: The following parody on the S.O.A.P. System is reprinted from the September 1958 issue of the Journal of Machine Accounting, Systems and Management, through the kind permission of the editor, Mr. Charles Johnson.
RINSO represents the ultimate sophisticated optimizing routine for use with the recently announced 699 Electronuclear Computing Machine. The routine allows any- untrained person with an I.Q. of 40 or more to program any problem capable of definition by the human brain. Logic is taken care of by RINSO.
With RINSO, it is not necessary for the programmer to know arithmetic or any advanced mathematics.
Nor must he confine himself to the use of English in his choice of symbols. The routine is capable of interpreting symbols in any of the 98 languages officially recognized by the United Nations, as well as in Uto-Aztecan and Quarani.
The RINSO deck consists of three cards, one of which may be thrown away if the computer is equipped with the floating square root device. The only restriction involving the program is that it be written on a sheet of white paper measuring not more than 4' x 6 '
To prepare the machine, first drop three RINSO cards into the slot marked "THINK" on the console and place the program (s) sheet on the moving conveyor belt. Set the alpha-numeric console switches to "ANALYZE" and push the button marked "GO".
The output of RINSO consists of a printed form from the 499 Accounting Machine Listing 1) the program steps in Basic English, 2) an analysis of the program in the light of present-day computing techniques and 3) a statement of the kind and quantity of raw data necessary to make the 699 System economically feasible.
Copies of the RINSO deck may be obtained by writing to:
Programmer Number 4096,
Ivory Tower, Bellevue Hospital,
New York, N. Y.
in [ACM] CACM 1(10) (Oct 1958) view details
in [ACM] CACM 1(10) (Oct 1958) view details
Bob Bemer states that this table (which appeared sporadically in CACM) was partly used as a space filler. The last version was enshrined in Sammet (1969) and the attribution there is normally misquoted.
in [ACM] CACM 2(05) May 1959 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 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
Introduction to the Problem
DEUCE is a two-plus-one-address computer having twelve 32-word mercury delay lines of rapid-access storage, and an 8,192-word magnetic drum backing store (see Haley, 1956). It has proved to be a powerful tool for both scientific and commercial applications, and its usefulness is greatly increased by a large library of subroutines and programs. The cost of the machine places it in the medium-scale computer class, but the speed of operation is comparable to machines in the large-scale class. Certain aspects of programming DEUCE, however, are clerical in nature, and can be somewhat tedious; such programming work might well be left to the machine itself.
The object of the work leading to this paper has been the development of a programming scheme which makes the writing down of a program much simpler and more straightforward than normal DEUCE programming. This is because the SODA language is closer to that of a mathematical language, and includes strong mnemonic aids. Any sort of intermediate routine which eases the programmer's work is especially of value in an academic environment. Universities tend to have a great number of problems which necessitate the use of a computer, but do not have the necessary programming staff to write the programs. A system such as SODA enables people who are familiar with a problem, and who are not familiar with computers, to write their own programs with relatively little external assistance.
The basic difficulties in preparing a program for any machine can be minimized by the use of either interpretive or translation routines. Almost all computers in use today have routines of this nature available simply for the ease, efficiency, and convenience of the user. Even though these "intermediate" routines generally require more machine time, the aid they give the programmer (particularly a novice) makes them highly desirable from an economic point of view.
Extract: Interpretive and Translation Routines
Interpretive and Translation Routines
Any intermediate automatic coding program for a computer may be broken down into either a translation or an interpretive routine. There are routines which combine the advantages of both translation and interpretive routines to give optimum results in terms of machine efficiency and programming effort. For example, some routines, in order to minimize programming time, require that a pseudo program be run through a translator, an interpreter, and then an optimizing program (in the case of computers with only a drum or delay-line store), before giving a coded program in machine language, suitable for the actual solution of the problem.
An interpretive routine is a program which, when given an order (which is called a pseudo order) in a simplified language, calls in (i.e. transfers control to) an appropriate subsequence, stored elsewhere in the machine, to carry out that step in the calculation. After completion of the subsequence, control returns to the interpretation of the next pseudo instruction. An interpretive routine most useful for the DEUCE machine is called the General Interpretive Program (GIF). GIF, designed for handling almost any matrix manipulation, also enables the programmer to operate on large blocks of data in a prescribed sequence. Another similar but less elaborate interpretive routine for the DEUCE is the Tabular Interpretive Program (TIP). Still another interpretive program is called Alphacode; this is an alpha-numeric system which transforms the computer into a three-address machine which has indexing facilities and works entirely in floating-point arithmetic. These three routines were described by Robinson (1959).
When using a translation routine, the program is first written down in terms of the pseudo orders of the translator's vocabulary, which is similar to that of an interpretive routine. These pseudo orders, however, are then fed into the translator, which produces an output program in terms of standard machine orders. It is this program, in the standard computer language, which effects the problem solution. The interpretation of the pseudo orders thus occurs only once. Since interpretation usually consumes considerable machine time, a translation scheme is of most advantage with often-used programs. It is believed that SODA is the first translation scheme prepared for DEUCE.
Extract: The SODA Machine and the SODA Language
The SODA Machine and the SODA Language
The selection of a pseudo language rests on many requirements, the most important of which are the ease with which the language can be used, and the efficiency of the final machine program. Other points of consideration include the ease with which the translation program itself can be written, and the more pressing requirements of the computation laboratory sponsoring the development.
The first point argues for a language close to that which the human user employs as his own language. Thus we might desire to write algebraic equations, or merely give sentence statements of what is desired. The former of these is presently receiving some attention by Dr. C. Hamblin of the Humanities Department of the University of New South Wales, Sydney, Australia. He has already written an interpretive program using such a language. A translation program for this type of language is extremely involved, and it was felt that something which would be available quickly would be more desirable.
In addition, it was felt that at a university it would be advantageous to have a language which was more like that of a conventional single-address machine. Once such a language is mastered, the step towards programming any machine, including DEUCE, is a relatively minor one. The choice for a language, therefore, embodies the principles employed in programming a more conventional type computer, with the additional facility that the instruction names and the various addresses can be alphabetical in nature, thereby allowing for mnemonic aids. Indeed, SODA incorporates many of the features employed in SOAP (Symbolic Optimum Assembly Program) for the IBM 650 computer and SAP (Share Assembly Program) for the IBM 704 machine. The basic language of these same two schemes was used as a guide throughout the development.
in The Computer Journal 2(2) July 1959 view details
in E. M. Crabbe, S. Ramo, and D. E. Wooldridge (eds.) "Handbook of Automation, Computation, and Control," John Wiley & Sons, Inc., New York, 1959. view details
Assembly and Compiling Systems both obey the "pre-translation"7 principle. Pseudo instructions are interpreted and a running program is produced before the solution is initiated. Usually this makes possible a single set of references to the library rather than many repeated references.
In an assembly system the pseudo-code is ordinarily modified computer code. Each pseudo instruction refers to one machine instruction or to a relatively short subroutine. Under the control of the master routine, the assembly system sets up all controls for monitoring the flow of input and output data and instructions.
A compiler system operates in the same way as an assembly system, but does much more. In most compilers each pseudo instruction refers to a subroutine consisting of from a few to several hundred machine instructions.8 Thus it is frequently possible to perform all coding in pseudo-code only, without the use of any machine instructions.
From the viewpoint of the user, compilers are the more desirable type of automatic programming because of the comparative ease of coding with them. However, compilers are not available with all existing equipments. In order to develop a compiler, it is usually necessary to have a computer with a large supplementary storage such as a magnetic tape system or a large magnetic drum. This storage facilitates compilation by making possible as large a running program as the problem requires.
Examples of assembly systems are /Symbolic Optimum Assembly Programming (S.O.A.P.) for the IBM 650 and REgional COding (RECO) for the UNIVAC SCIENTIFIC 1103 Computer. The X-l Assembly System for the UNIVAC I and II Computers is not only an assembly system, but is also used as an internal part of at least two compiling systems. Extract: MATHMATIC, FORTRAN and UNICODE
For scientific and mathematical calculations, three compilers which translate formulas from standard symbologies of algebra to computer code are available for use with three different computers. These are the MATH-MATIC (AT-3) System for the UNIVAC I and II Computers, FORTRAN (for FOR-mula TRANslation) as used for the IBM 704 and 709, and the UNICODE Automatic Coding System for the UNIVAC SCIENTIFIC 1103A Computer. Extract: FLOW-MATIC and REPORT GENERATOR
Two advanced compilers have also been developed for use with business data processing. These are the FLOW-MATIC (B-ZERO) Compiler for the UNIVAC I and II Computers and REPORT GENERATOR for the new IBM 709.13 In these compilers, English words and sentences are used as pseudocode.
in E. M. Crabbe, S. Ramo, and D. E. Wooldridge (eds.) "Handbook of Automation, Computation, and Control," John Wiley & Sons, Inc., New York, 1959. view details
in E. M. Crabbe, S. Ramo, and D. E. Wooldridge (eds.) "Handbook of Automation, Computation, and Control," John Wiley & Sons, Inc., New York, 1959. view details
in [ACM] CACM 4(01) (Jan 1961) view details
The 650 permitted optimization of programs by means of proper placement of instructions on the drum. Optimization was a very tedious job for the programmer, but could produce a very considerable improvement in program running time. A program called SOAP, a Symbolic Optimizer and Assembly Programs, combined the features of symbolic assembly and automatic optimization. There is some doubt as to whether a symbolic assembly system would have received very general acceptance on the 650 at the time SOAP was introduced. The optimization feature was obviously valuable. Symbolic assembly by itself on a decimal machine without magnetic tape did not present advantages that were nearly as obvious. Extract: IT compilers
The major competitor to the 650 among the early magnetic drum computers was the Datatron 205, which eventually became a Burroughs product. It featured a 4000 word magnetic drum storage plus a small 80 word fast access memory in high speed loops on the drum. Efficient programs had to make very frequent use of block transfer instructions, moving both data and programs to high speed storage A number of interpretive and assembly system were built to provide programmed floating point instructions and some measure of automatic use of the high speed loops. The eventual introduction of floating point hardware removed one of the principal advantages of most of these systems. The Datatron was the first commercial system to provide an index register and automatic relocation of subroutines, features provided by programming systems on other computers. For these reasons among others the use of machine code programming persisted through most of the productive lifetime of the Datatron 205.
One of the first Datatron computers was installed at Purdue University. One of the first Algebraic compilers was designed for the Datatron by a group at Purdue headed by Dr. Al Perils. This is another example of a compiler effort based on a firm belief that programming should be done in problem-oriented languages, even if the computer immediately available may not lend itself too well to the use of such languages. A big problem in the early Datatron systems was the complete lack of alphanumeric input. The computer would recognize pairs of numbers as representing characters for printing on the Flexowriter, but there was no way to produce the same pair of numbers by a single key stroke on any input preparation device. Until the much later development of new input-output devices, the input to the Purdue compiler was prepared by manually transcribing the source language into pairs of numbers.
When Dr. Perils moved to Carnegie Tech the same compiler was written for the 650, and was named IT. IT made use of the alphanumeric card input of the 650, and translated from a simplified algebraic language into SOAP language as output. IT and languages derived from it became quite popular on the 650, and on other computers, and have had great influence on the later development of programming languages. A language Fortransit provided translation from a subset of Fortran into IT, whence a program would be translated into SOAP, and after two or more passes through SOAP it would finally emerge as a machine language program. The language would probably have been more popular if its translation were not such an involved and time-consuming process. Eventually other, more direct translators were built that avoided many of the intermediate passes.
in [AFIPS JCC 25] Proceedings of the 1964 Spring Joint Computer Conference SJCC 1964 view details
[321 programming languages with indication of the computer manufacturers, on whose machinery the appropriate languages are used to know. Register of the 74 computer companies; Sequence of the programming languages after the number of manufacturing firms, on whose plants the language is implemented; Sequence of the manufacturing firms after the number of used programming languages.]
in [AFIPS JCC 25] Proceedings of the 1964 Spring Joint Computer Conference SJCC 1964 view details
in [ACM] CACM 15(06) (June 1972) view details
in Computers & Automation 21(6B), 30 Aug 1972 view details
in Computers & Automation 21(6B), 30 Aug 1972 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 Computers & Automation 21(6B), 30 Aug 1972 view details
The first generation of computers were programed in machine language, typically by binary digits punched into a paper tape. Activity in higher-level programming was found on both the large-scale machine and on the smaller commercial drum computers.
High-level programming languages have their roots in the mundane. A pressing problem for users of drum computers was placing the program and data on the drum in a way that minimized the waiting time for the computer to fetch them.
It did not take long to realize that the computer could perform the necessary calculations to minimize the so called latency, and out of these routines grew the first rudimentary compilers and interpreters. Indeed, nearly every drum or delay line computer had at least one optimizing compiler. Some of the routines among the serial memory computers include SOAP for the IBM 650, IT for the Datatron, and Magic for the University of Michigan's MIDAC.
Parallel memory machines had less sophisticated and diverse compilers and interpreters. Among the exceptions were SPEEDCODE developed for the IBM 701, JOSS for the Johnniac, and a number of compilers and interpreters for the Whirlwind.
in The Computer Museum Report, Volume 7, Winter/1983/84 view details
Heising noted that plans for the 650 did not include an assembly program. Elmer Kubie and a colleague in Endicott had written some load routines and a small mathematical library, including some floatingpoint subroutines incorporated into a simple interpretive system.98 But for the work at the center, Heising wanted an assembly program. Kubie had developed an algorithm for choosing instruction and data locations that a 650 programmer could apply in trying to reduce execution-time slowdown due to drum storage latency. Heising thought the optimization algorithm could be automated and somehow applied during assembly by the 650 itself.
Heising found the programmers at the center indifferent about the impending 650 arrival; they were looking forward to the 704 scheduled to replace the 701 later in the year. When Applied Science conducted a 650-oriented computation seminar in August, Heising attended with a recent hired member of his staff, Stanley Poley, who described a 650 program he had written before joining IBM. Heising was impressed by the quality of work described in the twenty-four papers by 650 users. Several papers described assemblers; one, by a speaker from John Hancock Mutual Life Insurance Company, which?eight months earlier?had been the first customer to receive a 650, mentioned provisions for automatic optimization.
Heising asked Poley to join with a colleague, Grace E. Mitchell, in writing a 650 assembler that would combine mnemonic operation codes and "free" mnemonic labels, the latter being a relatively new idea that permitted the assembly language programmer to identify conveniently an instruction or operand by a short term chosen to suggest the function of the instruction or data. Examples in an accounting context might be SUBR or TAX. Heising had learned of free labels through an enhancement of Rochester's original symbolic assembler done by 704 planners at Poughkeepsie. The idea was feasible because the 650 at the center wras to be equipped with a newly announced "alphabetic device." Also to be adopted from the Poughkeepsie assembler was a novel form of symbol table wherein table entries could be stored and rapidly retrieved during assembly at locations determined with a "hashing" algorithm (the "open method" of search described in note 61 of chapter 8). Finally, the assembler would assign "optimum" drum locations to assembled instructions and data.
Poley and Mitchell completed their assembler in three months and named it SOAP (Symbolic Optimal Assembly Program). In November 1955, their first mimeographed programmer's guide gave instructions for use and included a wiring diagram for a control panel to be used in printing input and output card decks on the IBM 407 tabulator. Figure 9.5 shows an example of a SOAP output listing for an illustrative problem.
Heising had wanted the program only to enhance programming productivity at the center. SOAP came to be used, however, by almost all 650 installations, after a slow start due to the requirement for the alphabetic device, a reluctance to step away from the machine-language coding procedures familiar from the 650 manual and IBM courses, and the low-key manner of promotion of programs at that time. In September 1956, DeCarlo wrote a letter to Sales and Applied Science representatives stating that SOAP could double programming effectiveness. He attached a detailed description of the alternative coding procedures (one titled "The Programmer as Clerk") for comparison.
While SOAP was being written, Beckman had a number of utility programs under development for the 650 and 704 at the Scientific Computing Center. The 704 work was supervised by John L. Green-stadt, a Brooklyn College graduate who had known Sheldon at Yale University graduate school and whom Sheldon had hired a few months before the 701 was installed. Greenstadt had been impressed by the quality of utility programs brought to the center by 701 customers for use during their preinstallation tests. Therefore, while planning 704 utilities, he made it a point to visit some 701 customers. His trip, in early 1955, followed soon the one made by Backus to gather views on his compiler project.
in C.J. Bashe, L.R. Johnson, J.H. Palmer, and E.W. Pugh "IBM's Early Computers" MIT Press, 1986 (Vol. 3 in the History of Computing series) view details
I suppose it was natural for a person like me to fall in love with his first computer. But there was something special about the IBM 650, something that has provided the inspiration for much of my life's work. Somehow this machine was powerful in spite of its severe limitations. Somehow it was friendly in spite of its primitive man- machine interface.
I had just turned 19 when I was offered a part-time job helping the statisticians at Case Institute of Technology. My first task was to draw graphs; but soon I was given some keypunching duties, and I was taught how to use the wondrous card sorter. Meanwhile a strange new machine had been installed across the hall -- it was what our student newspaper called "an IBM 650 Univac," or a "giant brain." I was fascinated to look through the window and see the lights flashing on its console.
One afternoon George Haynam explained some of the machine's internal code to a bunch of us freshmen who happened to be in the lab. It all sounded mysterious to me, but it seemed to make a bit of sense, so I got hold of a couple of manuals. My first chance to try the machine came a few weeks later, when one of the upperclassmen at the fraternity I was pledging needed to know the five roots of a particular fifth-degree equation. I decided that it would be fun to compute the roots by using the 650. More precisely, I had been reading the manual for the Wolontis-Bell Labs Interpreter, and I decided that polynomial root finding would be a good test case.
A program for the Bell System (as we called it) consisted of 10-digit numbers like 1 271 314 577 which meant "Add the (floating-point) number in location 271 to the (floating-point) number in location 314 and put the result in location 577." I found a book that gave formulas for the roots of a general fourth-degree equation; so it was easy to factor a general real polynomial of degree 5 by first doing a simpleminded search for a real root r, then dividing by x-r and plugging the result into the formulas for quartics.
I realize now how lucky I was to have had such a good first encounter with computers. The polynomial problem was well matched to my mathematical knowledge and interests, and I had a chance for hands-on experience, pushing buttons on the machine and seeing it punch the cards containing the answers. Furthermore, the Bell language was an easy way to learn the notion of a program that a machine could carry out. I've forgotten the name of the fraternity brother who asked me to solve this particular problem, but I bet he's kicking himself now for not having done it himself.
I often wonder whether it might not still be best to teach programming to novices by starting with a numeric language like that of the Bell interpreter, instead of an algebraic language like BASIC or LOGO. I think a small child can understand machinelike language better than an algebraic language. But I know that such ideas are now considered out of date, and I suppose I'm being an old fogy.
I learned a few years ago that the Bell interpreter had been inspired by John Backus's Speedcoding system for the IBM 701 (Backus 1954). During my student days I had never heard of the 701, and this, I think, leads to an important point: The IBM 650 was the first computer to be manufactured in really large quantities. Therefore the number of people in the world who knew about programming increased by an order of magnitude. Most of the world's programmers at that particular time knew only about the 650, and were unaware of the already extensive history of computer developments in other countries and on other machines. We can still see this phenomenon occurring today, as the number of programmers continues to grow rapidly.
When I did finally learn about the existence of the IBM 701, it had been improved to the 709, and it was shortly to become the 7090; but I must confess that I still liked my good old 650 a lot better. The 650 had only 44 operation codes (IBM 1955), while the 709 had more than 200; yet I never enjoyed coding for the 709, because I never seemed to be able to write short and elegant programs for it -- the opcodes didn't blend together especially well. By contrast, it was somehow quite easy and pleasant to do complex things on the 650 with very few instructions. Most of the commands in the 650's repertoire accomplished several things at once, and it was frequently possible to make good use of the side effects. For example, the instruction 60 1234 1009 meant, "Load the contents of location 1234 into the distributor; put it also into the upper accumulator; set the lower accumulator to zero; and then go to location 1009 for the next instruction." All four of these actions were often useful in the subsequent program steps.
In fact, I usually got by with only 34 of the 44 opcodes, because I seldom had a good application for the ten "branch on distributor digit equal to 8" commands. After 25 years I still can remember the numeric codes for most of the remaining 34 ops; and I'll never forget the fact that addresses 8001, 8002, and 8003 referred to the distributor, lower, and upper accumulator registers.
The 650's "one-plus-one address" code, in which each instruction designated the location of its successor (and branch instructions designated both successors), has been rejected by modern machine designers. But it was in fact extremely effective, because it allowed convenient subroutine linkage and because it became easy to execute instructions from registers. A one-plus-one scheme was important, of course, on a machine without efficient access to all words of memory, because instructions could be located in "optimum" places on the magnetic drum.
The incredible thing about the 650 was that we could do so many things with it, although it was three orders of magnitude slower than today's computers, and it had three orders of magnitude less memory. The memory-space limitation was more important than anything else during my first year of programming. I had to learn how to pack data and how to use subroutines in order to save space. For example, my first large program was a tic-sac-toe routine that "learned" to play by remembering the relative desirability or undesirability of each position that it had ever encountered. The hardest part was figuring out how to keep one digit of memory for each possible configuration of the board; board positions that were equivalent under rotation or reflection were considered to be identical.
The first program that I ever wrote in machine language still stands out in my mind. It was June 1957, and my freshman year at Case had just ended. I decided to hang around Cleveland instead of going home, and I was allowed to stay up all night playing with the computer by myself. So I decided to write a program that would find prime factors. The idea was that a person could set up a 10-digit number in the console switches and start my routine, which would punch the corresponding prime factors on a card and stop; then another number could be set up and factored in the same way, etc. I believe my first draft program was about 80 instructions long, but I didn't save it, so I can't be sure. Anyway, I wrote it as a sequence of about 80 decimal numbers, and punched it onto cards -- much as I had done with my previous (Bell system) program for root-finding. Then I sat down at the console of the machine and began to learn how to debug, using the half-cycle switch to step through the instructions slowly, or using the addresss-top switch to discover when the program used particular locations for data or instructions. The 650 console was excellent for on-line debugging, and nobody else was using the machine at that time of night.
Well, my program was riddled with errors, and I removed them one by one during the next two weeks. Besides the "obvious" mistakes, I hadn't realized at first that a 10-digit number can have as many as 33 prime factors. Only eight numbers could be punched on a card, so I would have to punch up to five cards. (My original program had only thought of punching one card.) Then I had to clear the memory between runs so that spurious data from a previous factorization wouldn't appear on the next one, and so on. You know the story; we all make the same mistakes. I was lucky enough to have the opportunity to make lots of mistakes right from the beginning, and to diagnose them all by myself, sitting at the machine. All the facts I needed were available to me, because I was working in machine language, and no operating system or other software was interposing itself between me and what I needed to know. Debugging took a long time at first, but I think I had the machine to myself about six hours every night. Finally I arrived at a program that was satisfactory; I vaguely recall that it took about 11 minutes to determine that the number 9999999967 was prime, although at one point this particular test case had taken 17 minutes.
By this time my program had grown to 140 words long, and I think I had changed each of the instructions at least twice. I had also learned about the SOAP assembly language (Poley and Mitchell 1955), so my final program was expressed in symbolic form; I had been weaned away from numeric machine language during those two weeks. The success of this program gave me the confidence to try another (which converted a given number on the console switches to a specified radix); then I was ready for tic-tac-toe.
The SOAP language allowed symbols to be up to five letters long, and I recall spending a lot of time trying to come up with suitable names. It was a great moment when I hit on the right term for the program step that was to be executed when the computer had won at tic-tac-toe by finding three x's in a row: I called that step BINGO.
I regret to report that I've recently looked again at my prime factors and tic-tac-toe programs, and they are entirely free of any comments or documentation.
Shortly afterward I got hold of the SOAP II manual (Poley 1957), which impressed me greatly and had an enormous influence on my subsequent career. This manual included the entire listing of SOAP II in its own language, and the program was absolutely beautiful. Reading Poley's code was like listening to a symphony; I wanted to be able to compose programs like that. I also learned several new techniques, such as hashing, from this code. My next project was to write a modification of SOAP II that would have worked on a 650 with only 1000 words of memory. (I knew that such machines were sold, but I never actually saw one.) Then I spent the rest of the summer writing SOAP III (Knuth 1958), which went the other way by adding additional features for enhanced 650s that had index registers and/or floating-point hardware.
SOAP III was my introduction to software writing. In particular, I learned about what is now called "creeping featurism," where each of my friends would suggest different things they wanted in an assembler. I probably tried to accommodate them all, since SOAP III had 24 pseudo-operations that were not in SOAP II. I also left 150 memory locations available for user-defined pseudo-operations. I put liberal comments into the code, having learned that lesson at last.
Our lab received an amazing program from Carnegie Tech during the summer of 1957, namely the famous IT compiler by Perlis and Smith (1957). IT took algebraic statements as input, then computed awhile, and punched SOAP programs as output. I had no idea how such a feat would be possible, but I got hold of the program listing at the end of the summer, and I read it while vacationing with my parents at a beach resort on Lake Erie. This program was not beautifully written like Poley's, but it accomplished remarkable things, so I naturally had an urge to rewrite everything in the style of 650 coding that I had just learned. Bill Lynch and I began this project late in 1957, under the direction of Fred Way III and George Haynam. We first called our program Compiler III, but it eventually became known as RUNCIBLE (Knuth 1959b; Case 1959). The language was a superset of Perlis's IT, and we worked very hard to squeeze in as many new features as we could.
Somehow it was possible to cram a complex compiler into the 2000 words of the 650. Yet when we were done, I don't think we could have gotten by with only 1999 words, because we had spent considerable time finding every last bit of space -- by using terrible tricks so that small changes to one part of our code would usually cause some apparently unrelated part to blow up. I guess Parkinson's Law applies to programs as well as to organizations; we kept adding features until the space was filled.
RUNCIBLE had four versions called AX, AY, BX, and BY, where X stood for object code that invoked subroutines for floating-point arithmetic, while Y stood for object code that used the 650's optional floating-point hardware; A stood for SOAP output, while B stood for directly loadable machine-language programs punched five per card (and bypassing the need for assembly). It turned out that the X version became a Y version by replacing exactly 95 instructions by 95 others; similarly, the A version became a B version by replacing exactly 406 instructions by 406 others. If we discovered a way to save one line of code in, say, the A version, we looked closely at the B version until we had saved a line there, too.
We called the A version "two-pass operation," while the B version was called "one-pass." At the end of the summer I hacked together a "zero-pass" version that took one less pass than B, since it loaded machine instructions directly into their memory locations instead of punching anything on cards. For this I had to eliminate the matrix feature of IT; that is, doubly subscripted arrays were not permitted in "RUNCIBLE zero." My main goal was to prove that 2000 words of memory were not too few for a compile-load-and-go system, because somebody (Perlis?) had reportedly said that it would be impossible.
By 1959 our lab had acquired the ultimate in 650 upgrades: we had a full 653 system (IBM 1959) including index registers, floating-point hardware, and 60 whole new words of core memory! It was heavenly. Besides this, we put our printer on-line (so that listings didn't have to be made via cards), and we acquired a RAMAC disk storage, as well as several tape units.
At this point it was desirable to have a new assembly program so that we would make proper use of the new equipment. I therefore wrote SuperSoap (Knuth 1959a), a major improvement over SOAP III. I'm still pretty proud of SuperSoap, because it introduced some good ways of dealing with programs that would be loaded into the drum but executed from core, and because I had the courage to remove some features of SOAP III that didn't work as well as planned. Furthermore, SuperSoap introduced what I think was the best approach to the problem of "optimizing" the drum locations of data and instructions for the 650; it was a combination of machine and hand methods (Knuth 1961).
The name SOAP stood for Symbolic Optimal Assembly Program, and optimal meant that the machine would choose drum locations so that at least one reference to that location would involve no delay. Such optimization was much better than random placement of instructions; I had (for fun) experimented with SHOAP, a "Symbolic Horribly Optimizing Assembly Program" that used the algorithm of SOAP in reverse so that at least one reference to each location would lead to a 49-word-time delay. By adding seven cards to the normal SOAP program deck, you had SHOAP, which produced extremely slow programs. Conversely, it was possible to improve significantly on SOAP'S performance by choosing locations carefully by hand and rewriting the program when necessary, as I discuss in Knuth (1961); the Bell interpretive system had been hand-optimized in a particularly beautiful way, which was quite an inspiration to me. In 1958, I wrote HAND SOAP, which permitted me to hand-optimize the locations without giving up the advantage of symbolic assembly. We used HAND SOAP to prepare the runtime system for RUNCIBLE; SuperSoap was later designed to incorporate similar ideas into a full-fledged assembler.
Somebody in 1958 or so circulated a joke about a program called RINSO, a "Real Ingenious New Symbolic Optimizer"; we were carried away by acronyms in those days. For some reason there has been an intimate relation between cleaning agents and software that I have written through the years, even though my programs haven't always been very clean. For example, John McNeley and I devised a system called SOL in 1963 (Knuth and McNeley 1964), and when I visited Norway a few years later I learned that SOL is the name of a Norwegian laundry detergent. Even more amazing was that my MIXAL assembler language (Knuth 1968) turned out to have the same name as a popular detergent in Yugoslavia -- although I had had no idea that MIXAL would even be a word in any language! More recently, I have learned that TEX is a brand name for toilet paper in Greece … but I am digressing.
My preface to the SuperSoap manual (Knuth 1959a) gives a glimpse into the mood that prevailed at IBM 650 sites during the late 1950s:
Soap 3 was written attempting to get as many features into 2000 memory locations as possible, but SuperSoap was written under a different philosophy; speed was the prime consideration, and storage space was conserved only when speed was not appreciably decreased. A factor of roughly 3:1 in running time over Soap 3 has thus been obtained…. Some of the pseudo-op rules have become more logical thanks to Carnegie Tech's TASS [a competing assembler, written by Art Evans]…. Once again much gratitude must be given to the Case Computing Center for letting me chew up thousands of cards.
On rereading SuperSoap, I find most of it reasonably similar to today's assemblers except in one significant respect: We assumed in 1959 that the computer lab would be an "open-shop" operation in which any student could come in and take personal charge of the machines while running a program. Therefore the error messages in SuperSoap consisted of machine halts, and my manual gave the following advice for error recovery:
SuperSoap believes that the best place to catch errors is during assembly, and so it will stop if it finds something amiss…. The offending card is the fourth-last card out if you clear the read feed…. To restart, correct the bad card, … reinsert it in the deck, and hit Program Start.
There was a keypunch right next to the console, so this was probably the most efficient way to get the job done in those days.
Cards, cards, cards; we used tens of thousands each day. The run-time system of RUNCIBLE had a debugging feature whereby you could turn the console knobs and get a card punched for every statement of your program that was being executed; or you could even trace every machine-language operation, with one card per instruction. The 533 Card Read Punch could produce 100 cards per minute, and it often did.
One of the nice things about the 650 and its peripherals was their robustness. Our computing center staff could safely let random students work all of the IBM machines, changing plugboard control panels, clearing the punch hopper, mounting tapes, fixing card jams, etc., without worrying that the machines would be ruined. (This was emphatically not the case for the Univac equipment in another part of our laboratory; those machines had been designed with the assumption of a trained operator in attendance, and I tended to break them accidentally every time I went nearby. If all computers had been like those, a lot of people like me would never have gotten a good start on the use of computers, because we would never have been allowed to touch them.) During all my experience with the 650 I can remember only two instances where the design could perhaps have been slightly more foolproof: Once I discovered a special case of the divide operation that put our machine into an infinite loop, restartable only by hitting Power Off. (Later I visited Carnegie Tech and tried it on their 650; it blew the fuse! Ah yes, those were the joys of student life.) The other time was when one of the tiny console display lights was broken; the glass was gone and two little wires were sticking out. I changed the display so that this particular light was off, then tried to pull out the broken bulb by grabbing onto what looked like a dead filament. This gave me quite a jolt, and I was sick for a day or so. Perhaps the machine was trying to fill my brain with advice about how to write better software; or perhaps it was trying to kill me.
By 1959 I had developed a pretty good style of 650 coding, and I must confess also being addicted to tricks. One of the competitions among students was to do as much as possible with programs that would fit on a single card -- which had room for only eight instructions. One of the unsolved problems was to take the 10-digit number on the console and to reverse its digits from left to right, then display the answer and stop; nobody could figure out how to do this on a single card. But one day I proudly marched up to the machine and made a demonstration: I read in a card, then dialed the number 0123456789 on the console, and started the machine. Sure enough, it stopped, displaying the number 9876543210. Everybody applauded. I didn't explain until later that my card would display the number 9876543210 regardless of what number appeared on the console switches.
There's more to the story. Our machine had an extra set of console switches, which were called register 8004. (As far as I know, Case's 650 was unique with this particular feature.) It turned out that nine instructions on an extended 650 were sufficient to reverse the digits of a number, and the ninth instruction could be put into one of the sets of console switches. Therefore I was able to solve the problem without cheating (see the appendix following).
The dirtiest trick I ever discovered for the extended 650 was to use the instruction "shift and count by 9004" in a certain context. This one instruction caused four things to happen simultaneously: (1) the upper accumulator was shifted left by four digits; (2) the lower accumulator was set equal to 10; (3) the core memory "timing ring" was set to 9004; and (4) the overflow indicator was turned on. I had an application in which all four of those things were useful.
SuperSoap was the last "system" software I wrote for the 650, although I wrote many application programs during the following year. Then I graduated, and began to tackle other machines. My favorite computer for the next five years became the Burroughs 220, which was another joy to use.
A number of my classmates and co-workers at Case later became leading figures in other computing centers; they include Bill Lynch, Mel Conway, Joe Speroni, Gilbert Steil, Jack Alanen, Mike Harrison, and many others. Our incubation period with the 650 was the foundation of our later work. And the same is true for thousands of other people (such as Bob Floyd) who became intimately familiar with 650s at other computer centers.
What was it about the 650 that made our experiences such a good foundation for our later careers?
Surely I wouldn't recommend that today's software be produced as we did the job then; we would never advance very far past the rudimentary levels achieved in those days, if we remained rooted in that methodology. But growing up with the 650 gave us valuable intuitions about what is easy for a machine to do and what is hard. It was a great machine on which to learn about machines. We had a machine organization that was rudimentary but pleasant to use; and we had program masterpieces like the Bell interpreter and Poley's assembler, as examples of excellent style.
We were forced to think and to develop our abilities to make mental abstractions about control structures; these experiences seem to have made us better able to do complex things later, when the task became easier. I'm reminded that Edsger Dijkstra began his programming experience in a similar way (but on a different computer); he and Zonneveld wrote the first ALGOL 60 compiler in a strictly numeric machine language.
This article about the 650 has turned out to be largely autobiographical. The fact is, it's impossible for me to write about that wonderful machine without writing about myself. We were very close. (One night I missed a date with my wife-to-be, because I was so engrossed in debugging that I had forgotten all about the time. I'll never live that down.) The 650 provided me with solid instruction in the art of computer programming. It was directly related to the topics of the first two technical articles that I ever submitted for publication (Knuth 1959b; 1961). Therefore it's not at all surprising that I decided in 1967 to dedicate my books on computer programming
" ... to the Type 650 computer once installed at Case Institute of Technology, in remembrance of many pleasant evenings."
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
System Software
In the early 1950s, system software was virtually nonexistent. Programming originally was done in absolute, using decimal instructions on the 650 and other decimal machines, and in binary (or octal) on the binary computers. Early assemblers used mnemonics for the operation codes but relative addresses. Selected addresses would be given a symbolic name and then other locations determined by specifying an increment from that symbolic location. This was quickly superseded by one-for-one symbolic assemblers as the amount of main memory available on computers became large enough to permit reasonably large assembly tables.
Because of the nature of the two-address instruction in the 650, particularly if the program was to be optimized, most of the early applications for the 650 were written in absolute. Within two years of the introduction of the 650, automatic optimization programs became available. One of the first of these was SOAP (Symbolic Optimizing Assembly Program) (see Gordon 1956; Poley and Mitchell 1955). It performed optimization on each instruction, but as the program got larger and the instruction and data locations were fixed, later portions of the program could not be optimized effectively. A total reoptimization program that could readjust locations to improve the program performance as a whole was not practical. SOAP was quite effective for small programs, particularly for subroutines called by a main program.
Certain frequently used programs could not be effectively optimized by SOAP, even though they were small. Floating-decimal arithmetic subroutines, complex arithmetic subroutines, square root, trigonometric functions, and other such scientific subroutines needed to be highly optimized. A library of such routines was developed and made available as part of the software support for the 650. They were published in IBM Technical Newsletters (Nos. 7 through 13) and were among the first software support provided by IBM (see the contents of Nos. 8 and 9 in this section and No. 11 at the end of the issue).
in Annals of the History of Computing, 08(1) January 1986 (IBM 650 Issue) view details
System Software
In the early 1950s, system software was virtually nonexistent. Programming originally was done in absolute, using decimal instructions on the 650 and other decimal machines, and in binary (or octal) on the binary computers. Early assemblers used mnemonics for the operation codes but relative addresses. Selected addresses would be given a symbolic name and then other locations determined by specifying an increment from that symbolic location. This was quickly superseded by one-for-one symbolic assemblers as the amount of main memory available on computers became large enough to permit reasonably large assembly tables.
Because of the nature of the two-address instruction in the 650, particularly if the program was to be optimized, most of the early applications for the 650 were written in absolute. Within two years of the introduction of the 650, automatic optimization programs became available. One of the first of these was SOAP (Symbolic Optimizing Assembly Program) (see Gordon 1956; Poley and Mitchell 1955). It performed optimization on each instruction, but as the program got larger and the instruction and data locations were fixed, later portions of the program could not be optimized effectively. A total reoptimization program that could readjust locations to improve the program performance as a whole was not practical. SOAP was quite effective for small programs, particularly for subroutines called by a main program.
Certain frequently used programs could not be effectively optimized by SOAP, even though they were small. Floating-decimal arithmetic subroutines, complex arithmetic subroutines, square root, trigonometric functions, and other such scientific subroutines needed to be highly optimized. A library of such routines was developed and made available as part of the software support for the 650. They were published in IBM Technical Newsletters (Nos. 7 through 13) and were among the first software support provided by IBM (see the contents of Nos. 8 and 9 in this section and No. 11 at the end of the issue).
in Annals of the History of Computing, 08(1) January 1986 (IBM 650 Issue) view details
in Bemer, Bob "Computer History Vignettes" (Web published, retrieved 2000) view details