ADES II(ID:2807/ade003)
Automatic Digital Encoding System v II
for Automatic Digital Encoding System
second implementation, translatable and featuring recursion
Possibly the first language to feature the universal quantifier
Places
People: Hardware:
- IBM 650 IBM
Related languages
| ADES | => | ADES II | Evolution of | |
| ADES II | => | SEMANOL | Evolution of |
References:
Abstract: The ADES approach to automatic programming is believed to be entirely
new. Mathematically, it is based on the theory of recursive functions, as propounded in references [1], [2] and [3] say, and on the closely related mathematical logic. These two dAscipllnes provide a natural framework for constructing an automatic coding system of sufficient generality to cope with most of the mathematical problems submitted to a digital computer. It is believed that ADES possesses such generality. Furthermore, ADES is not designed for any specific computing machine. With suitable modification, the system can be adapted to any electronic digital computer. Extract: Nature of system
In this brief talk, the main features of the system will be presented in su~mmry fashion. A detailed account is given in Naval Ordnance Report 4209, "Automatic Digital Encoding System, II".
ADES consists of three primary components : a formulation language, an electronic digital computer, and an "Encoder" (i.e. a machine which automatically translates from the for~11ation language to the computer program language.) The formnlatlon language and the logical design of the Encoder are independent of the computer, which accordingly plays a minor role. It is assumed that the computer is a stored-program machine capable of modifying its instructions, but otherwise, no special characteristics are necessary. However, certain desirable features of the computer are suggested in Report 4209. Of particular interest to designers is a new method of address--modification for single-address machines.
In ADES II, attention is focused on those problems which can be entirely contained in the computer's internal storage, that is no provision is made for references to auxiliary storage other than the initial input of data and instructions, and the final output of results. The logistics for using external storage during computation in those problems which require storage in excess of the internal storage capacity will be built into ADES III.
The critical component of an automatic coding system is the formulation language. The ADES language is simple, concise, and closely resembles ordinary mathematical notation. Its alphabet is constructed from the nine generic symbols, q,r,a,b,c,e,f,p,~ and the integers. The letters of the alphabet consist of the generic symbols with two-digit subscripts attached; e.g. qll' a12' bol' f03" The usage of the letters is indicated by their names. The q's and r's are indices, the a's are independent variables, the b's are dependent variables, the f's are operators, (or functions) the p's are punctuation marks, the e's are equ~l signs, the d's are output symbols , and the c's are free variables. To state a problem in ADES language, the mathematician begins as usual by first writing the equations in some conventional mathematical notation involving continuous variables. He proceeds to apply the techniques of numerical analysis to reduce the "continuous" equations to explicit equations involving discrete variables as required in digital computation. At this point, instead of programming, he rewrites the "discrete" formulas in ADES notation. For non-recursive formulas this involves only a simple transliteration to the ADES alphabet and a recasting into the prefixed-operator form.
For example, suppose x I and x 2 are independent variables in the mathematical statement of the problem, and Yl is a dependent variable defined by the equation, Yl = Xl + x2" The corresponding ADES formmlation could be written as, b I = +ala2, where al,a2, and b I are identified with Xl,X2, and YI' respectively. If x I and x 2 are to take on a sequence of values, Xl(O), Xl(1), ..., xl(a3) and ~(0), x2(1), ..., x2(a3) , respectively, and we wish to compute Yl(i) = xl(i ) + x2(i) for 0 _~ i <_ as, then we introduce the index ql for i, and write,
V Oqla 3 b I : + al%a2%,
where the inverted A, "V", denotes the universal quantifier; i.e. "~Oqla3" means "for all integral values of ql from 0 to a 3 inclusive." By writing such quantifications, the formulator can prescribe iterative loops in the flow chart of the computation in all possible combinations. The structure of the flow chart is further determined by "branch equations", in which a variable is defined by either of two alternative formulas depending on whether a branch condition is or is not satisfied; if we wish to define b I = a 3 + a 4 whenal< a 2 and b I = a 3- a 4 when al>_ a2, then we write, b I = :al< a 2, + a3a 4, -- a3a4J.
Quantifications are used also to specify the bounds of indices used in recursive definitions. Several standard formats are provided for the definition of dependent variables by recursion equations. The choice of these formats was dictated in part by the theory of recursive functions, in part by practical requirements of machine computation, and for the rest, by the desideratum of conformity with conventional usage. Formats are available for the following kinds of recursions :
(i) Simple scalar recursion; i.e. a recursion on one index, i, in which the scalar quantity, bl(i + i), is defined in terms of its preceding values bl(i), ..., bl(O ).
(2) Simple vector recursion; i.e. a recursion on one index, i, in which the components of a vector, bl(i + i), b2(i + i), ..., bn(i + i), are defined by a system of silm/itaneous equations in terms of the preceding values bl(i), b2(i), ..., bn(i), ..., bl(O) , ..., b (0).
(3) Double recursion; i.e. a recursion on two indices, i and J, in which one or more quantities bl(i + l, J + I), ..., bn(i + i, J + 1), are defined in terms of "preceding" values.
(4) Triple recursion; i.e. arecursion on three indices, bn(i'~ and k, in whAch one or more quantities, bl(i + i, J + i, k + i), ..., + I, J + I, k + 1), are defined in terms of "preceding" values. For the precise meaning of "preceding", see Report 4209.
As an elementary example of a simple scalar recursion, consider the Newton algorithm for the square root of al, as given by the equations,
y(o) -- 3,
In ADES language, letting b I = y, and ql = i, we write,
V 0%9 b I =n/+ bl%lalbl%2 ' fl 3 '
where fl is the identity function; i.e. fl(3) = 3.
For more complicated examples involving double and triple recursions, such as the solution of algebraic linear equations, differential corrections, and the solution of differential equations, see Report 4209.
Special equation formats are provided for increasing the efficiency of the computer program and to specify the flow chart. For the most part, however, the flow chart is determined by the quantifiers and branch equations in a natural way.
When all the formulas defining the quantities to be computed have been written, it remains only to specify input and output requirements. Here, the system~st take some cognizance of the fact that the computer has an internal storage unit. Conventions have been adopted for loading data into the computer storage. With these conventions, the formulator need specify only the total number of data to be supplied for each independent variable, and, in the case of a matrix of data, the mathematical structure of the matrix; e.g. rectangular, triangular, etc. The mathematical structure is defined by a formula which Is essentially a mapping of the two-dimenslonal matrix grid onto a linear grid. Similar mathematical formulas are used to specify"store" instructions for computed results. Note that this type of input-output instruction is easy to write and requires no knowledge of the computer, hence is compatible with all computers. Finally; output symbols must be written to indicate which results are to be printed, punched, etc., and the kind of format desired.
The complete formulation Is punched on cards, or tape, and loaded into the Encoder. The Encoder consists of a digital computer with certain routines, called "schemata", loaded into its storage. These schemata will translate the mathematical formulation into a complete program of computer instructions, assigning addresses, operation codes, input-output instructions, and compiling the necessary subroutines. The logical design of the schemata is independent of the computer. 0nly the last stage of translation, the selection of the computer operation codes, is dependent on the particular computer used. When the translation is completed, the Encoder will punch out the computer program. This program is then loaded into the computer and the computation can begin. Assuming that the data Is arranged according to convention on tape or cards, the program will cause the data to be read in, will proceed to calculate and the results will be punched out, stored on tape, or printed as specified.
An Encoder Is now being constructed for use with the 650 Magnetic Drum Calculator.
in Proceedings of the 1956 11th ACM national meeting view details
in Proceedings of the 1956 11th ACM national meeting view details
in Proceedings of the 1956 11th ACM national meeting 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
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 15(06) (June 1972) view details
in Belzer, J. ; A. G. Holzman, A. Kent, (eds) Encyclopedia of Computer Science and Technology, Marcel Dekker, Inc., New York. 1979 view details