PACT I(ID:103/pac005)
Translator for SHARE IBMs
for Project for the Advancement of Coding Technique (but it was also a pact)
Co-operative endeavour for a translating compiler between Douglas Aircraft, IBM, North American Aviation, Ramo-Wooldridge, and The RAND Corporation, hence first ever language designed by a Committee
Released (June 1955) by the time the computer became obsolete, so replaced by PACT Ia (which had a new theoretical basis as well)
from Fred Gruenberger "History of Computing in the Southern California Area" Annals of the History of Computing:
"Late in 1954 an event occurred that was to have national significance. A group of 701 users in the Southern California area decided, at the suggestion of Frank Wagner and Jack Strong, based on the success of the DCA, that (1) a better coding system for the 701 was needed, and (2) no single installation could produce it alone. The group formed into an informal organization called PACT (Project for the Advancement of Coding Techniques) and proceeded to produce PACT I, a compiler. PACT-IA for the 704 followed later. A complete account of the PACT efforts can be found in the October 1956 Journal of the Association for Computing Machincy. The point about PACT was the cooperative effort; a direct result of this effort was the formation of SHARE, the first of the user groups. From SHARE, we have proceeded to GUIDE, DUO, USE, and so on. "
Places
People: Hardware:
- IBM 701 IBM
Related languages
| A-2 | => | PACT I | Moderate Influence | |
| Comprehensive | => | PACT I | Dissatisfaction Moderate Influence | |
| FORTRAN | => | PACT I | Moderate Influence | |
| MIDAC Input Translation Program | => | PACT I | Dissatisfaction Moderate Influence | |
| PACT I | => | PACT IA | Evolution of | |
| PACT I | => | SAP | Influence |
References:
in [ACM] JACM 3(4) (Oct 1956) view details
Conclusion
The choice of this particular system for allocating data storage was greatly influenced by the scope of the PACT I project and the structure of the PACT working committee. In order to distribute the-work involved in producing the compiler among numerous installations, the compiler was broken down into several sections, one of which was data storage allocation. This partitioning made it desirable to make the data storage allocation as independent as possible from the allocation of the program storage. However, in order to make an optimum automatic allocation of storage, it would have been necessary to closely coordinate the data storage allocation section with the sections that expand the program code, which would have meant that the scope of PACT I would have had to be enlarged.
In order to fix the idea, let us consider some of the additional things the compiler would be required to do in order to impose automatically the SYN, SUC. and IMS constraints, make secondary storage allocation, and to do this in some optimum fashion. The compiler would, of course, only make an optimum allocation based upon the rules built into the system. Now, if we were to neglect the efficiency factor, the task accorded to the compiler would be relatively easy. The transmission of data between the high-speed storage and the auxiliary storages could be accomplished according to some relatively simple scheme. But in order to do this efficiently, the compiler would need to make additional judgments concerning the frequencies with which groups of operations are performed, input-output to computing ratios, etc. Essentially, the compiler would be required to follow the logic of the entire program.
In order to construct a system which will automatically and efficiently make auxiliary storage assignments and provide for the overlapping of high-speed storage for both the program and the data, much more effort will have to be expended than was for PACT I. The increase in difficulty is analogous to that involved in the application of Boolean algebra to the design of electrical systems involving "sequential" (feedback) circuits compared with the design involving only "combinatorial" (static) circuits. The accomplishment of such a system should be one of the principal objectives of the next PACF venture into the field of automatic programming.
Extract: Introduction
Introduction
One of the principal objectives of the PACT I compiler has been to eliminate as much as was immediately feasible of the bookkeeping and rudimentary thinking which is involved in the preparation of a computational problem for a large-scale, high-speed digital computer. To this end, a set of PACT pseudo-operations was developed. These operations are more closely related to the computational problem than the machine operations. In addition a pseudo-language was devised for addressing operands. The function of PACT is to compile a machine-language code from a given PACT pseudo-language code. In this sense PACT shortens the gap between the computational model and the final machine code by performing much of the intervening work. In this paper we shall be primarily concerned with the system which was designed to allocate machine storage locations for the operands which are involved in PACT pseudo-operations. The system was made to automatically allocate storage locutions up to the total capacity of the high-speed memory and to allow the user'some convenient means for constraining this allocation when necessary. No provision was made for automatic secondary storage allocation. Extract: General Discussion of Storage Assignment
General Discussion of Storage Assignment
Several general types of storage can be classified in order to facilitate the following discussion. Under this enumeration we single out temporary storage, number storage, variable storage, and instruction storage.
By temporary (working) storage, we mean the storage which is used primarily to retain the intermediate arithmetic results of PACT instruction steps which are referred to in other PAC] I instructions by their step numbers, in Figure 1 the result of step 2 will be placed in temporary storage for use in step 5. Any such results which need to be retained within a region arc automatically assigned to temporary storage by the compiler.
The numbers are the data which are Written explicitly as operands in relevant PACT instruction steps. The number 123 in Figure 1 will be automatically assigned to number storage. Optimal use of storage space is effected here by assigning equal numbers to the same memory locations.
The variables are the data which are addressable by unique symbolic names and these names are independent of the current values of the data. This invariant arises from the fact that each variable is assigned permanent storage locations, and only the contents of these locations can be altered, In Figure 1, A, B, and C are variables.
The three types of storage already described represent examples of data storage. In contrast there is that storage used to retain the resulting machine language code; it is called instruction storage. PACT I automatically assigns instruction storage locations independently of the data storage.
It might be pointed out here that, each type of storage is located in an independent block or region of high-speed memory. Since the compiler, at the time these assignments are made, does not know how much storage to set aside for each block, the assignments of these storages are made relative to the beginning of the block. Then just before the final compiled program is ready to be executed, these blocks are assigned to actual memory locations which are usually non-overlapping. As was stated above, the number, temporary, and instruction storage assignments are made automatically by PACT I. Variable storage assignment, however, is made automatically only under certain limitations, and this type of assignment needs further discussion.
First, variable storage is allocated for vectors and matrices, as well as for scalars, and the dimensions of these arrays may be dependent on some parameters of the problem. In either event, the compiler must be told the maximum extent of each array in order to assign them the correct amount of storage. Secondly, variable storage--especially when arrays are to be operated on-- usually constitutes a very significant portion of storage. By allowing two or more variables to occupy the same storage locations, an extensive optimization of high-speed memory usage can be effected.
There is another problem associated with variable storage. When several sections of a program are to be compiled separately, it is sometimes necessary that the results of one section be accessible to another. The compiler can be signaled to assign the same locations to these common variables.
We are now ready to state the task that was set for the PACT data allocation system. Ordinarily, all storage assignments are to be made automatically.
Variable storage assignments, though, will require that there be provided a convenient means for specifying the maximum ranges of arrays and constraints on the assignment where the user deems necessary. The remainder of this paper will be concerned with the allocation of variable storage.
Extract: Description of Variable Storage Allocation
Description of Variable Storage Allocation
Before describing how to specify the maximum range for each dimension of an array, we shall first indicate what PACT I considers to be an array. An array is any set of data which can occupy more than one storage location and is referred to by only one symbolic name. By specifying the range for either dimension of a variable to exceed one, we are defining that variable as an array. The definitions are made by recording the proper information on the variable definition sheet illustrated in Figure 2. On line one of Figure 2, the variable A is defined to be at most a 5 by 10 matrix. The variable B is defined as a vector with a maximum of 10 elements. Information on this sheet is punched into variable definition cards (one card to a line) and is read by the compiler shortly after the last PACT instruction card has been read.
On the code sheet, elements within an array are indicated by inductive subscripts. There is another type of subscript we call definitive. A definitive subscript can be considered as an extension beyond the factor field of the name by which we specify the variable. In step 5 of the coding sheet HA is a definitive subscript since ALP has not been defined as an array. In step 4, J is an inductive subscript since B has been defined as a vector.
Extract: Constraints on Variable Assignment
Constraints on Variable Assignment
In this section we shall describe the methods by which the coder may strain the allocation of variable storage. One such constraint allows the direct specification of the relative address to be assigned to a variable. On line one of Figure 4, the ten by twenty matrix E is constrained to have its first element located at variable storage location 1000. This constraint could have been used because E had been assigned location 1000 during a previous compilation another part of the problem. On lines 2 and 3 we have caused F and G to occur the same part of memory. In case a problem overflows the high-speed memory the overlapping of variable storage becomes necessary.
The REL constraint allows complete flexibility for specifying assigmnents However, if the coder uses the REL constraint for the sole purpose of constraining variable storage to overlap, then he must know or compute the amount ell storage for each variable. It was felt that this bookkeeping burden should be assumed by the compiler. Therefore, other more convenient eo~straints off variable assignment have been devised.
If the user desires to permit a vaciable to occupy the same storage locations as some other variable (called the constraining variable), he can accomplish this by using a SYN (synonym) constraint. On line 2 of Figure 5 the matrix B' is constrained to start at the same storage locations as the constraining vector A, (A has been defined as a vector on line 1.) Since A and B are allowed to overlap, they must be used in different phases of the problem. As a result of the SYN constraint B is automatically assigned in a phase one greater than that of the constraining variable A. Below the variable definition sheet in Figure 5 is a line diagram of the assignments rrtade as a result of the constraints specified. The lines represent consecutive relative locations. Here, both B and C have been specified to overlap A. Since A is a smaUer array than both B and C, and B has: been read by the compiler before C, only B will be assigned the same first location as A. The SYN constraint only permits the possibility of overlapping.
In Figure 6 we have the same example except that here C is constrained to overlap B instead of A. If the coder desires to have the storage locations allow eared to a variable follow--that is, be larger numerically than the locations allocated to another variable regardless of the order of the variable definition cards- -he can effect this by using a SUC (Succeeds) constraint. This constraint insures that the variables will be in the same phase and can be used for this purpose alone where the ordering is not important. Figure 7 illustrates the assignments made with a succeeds constraint. D has not been overlapped here. If this is desired, an IMS (Immediately Succeeds) constraint can be specified. This constraint insures that the storage assigned to the variable will always follow immediately after the storage assigned to the constraining variable.
Extract: details
These four constraints, REL, SYN, SUC, and IMS--together with the order ii of the variable definition cards constitute all the means by which the coder may control variable storage assignments. The execution of these constraints by the compiler greatly complicates the previously described procedure for assigning variable storage. The modified procedure will now be discussed. To facilitate the following description we shall first define the term chain. All variables whose assignments depend (dependence is a transitive relation) oll the assignment of a generating variable (thai is, by means of constraints) will constitute a chain of that variable. For example, in Figures 7 and 8 the variables A, B, and D form chains of the variable A. A is said to generate the chains.
On the first level the allocation of storage is made by chains. Each variable belongs to a unique chain which might consist of just the variable itself. The order in which the chains are allocated storage essentially depends first upon the order in which the variable definition cards are read and secondly, upon the order in which the PACT instruction steps are investigated when searching for variables defined by EQ instructions. The normal procedure is to assign the first chain starting at relative location zero and assign each succeeding chain starting immediately after the preceding one.
However, the allocation of storage for chains of variables generated by REL ¢onstrMned variables will always take precedence over the storage allocation for chains generated by non-constrained variables. In addition the chains dependent on non-constrMned variables are not allowed to overlap the chains dependent on REL constrained variables. In Figure 5, for example, A, B, and C form a chain of the REL constrained variable A. D is a non-const, rained variable and therefore is not allowed to overlap the foregoing chain.
On the second level we call consider how the allocation is made within individual chains. The variable which generates the chain is assigned first and the phase number is one. After any given variable has been assigned, the following process takes place: 1. Searoh among all of t he SYN constrained variables which have not yet been assigned for the first one which has the constraint variable exactly the same as the given variable.
a. If such a variable exists, increase the phase number by one and assign the variable so as not to overlap any variable in the chain which has been assigned in a higher phase. Repeat Step 1.
b. If no such variable exists, proceed to Step 2.
2. Search among all of the SUC and IMS constrained variables which have not yet beeli assigned for the first one which has the constraint variable exactly the same as the given variable.
a. If such a SUC constrained variable exists, assign the variable so as not to overlap any variable in the chain which has been assigned in a higher phase. If such an IMS constrained variable exists, assign the variable immediately after the given variable. Repeat Step 1.
b. If no such variable exists, proceed to Step 3.
3. a. If the phase number is one, proceed to the next chain.
b. If the phase number exceeds one, decrease t.he phase number by one. Repeat Step 1.
in [ACM] JACM 3(4) (Oct 1956) view details
in [ACM] JACM 3(4) (Oct 1956) view details
in [ACM] JACM 3(4) (Oct 1956) view details
in [ACM] JACM 3(4) (Oct 1956) view details
in [ACM] JACM 3(4) (Oct 1956) view details
in [ACM] JACM 3(4) (Oct 1956) view details
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
in "Proceedings of the Fourth Annual Computer Applications Symposium" , Armour Research Foundation, Illinois Institute of Technology, Chicago, Illinois 1957 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
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
in [ACM] CACM 6(03) (Mar 1963) view details
The PACT system on the 701 set a precedent as the first programming system designed by a committee of computer users. It also set a precedent for a situation which unfortunately has been quite common in the computer field. The computer for which the programming system was developed was already obsolete before the programming system itself was completed. PACT ideas had a great deal of influence on the later developments that took place under the auspices of the SHARE organization.
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