PSYCO(ID:3185/psy002)Princeton SYntax COmpilerPrinceton SYntax COmpiler Related languages
References: Introduction Although FORTRAN (in various versions) is one of the most widely used algorithmic languages, with translators existing for upwards of sixteen machines, the language itself has never been given a complete and explicit definition except informally, through the various reference manuals. Part of the reason for this is that FORTRAN'S position as a "common" language did not occur through official acceptance, but through use, with translators being written to process what people thought was the language. Furthermore, the specifications of the language, being to a large extent machine dependent, or at least largely influenced by the structure of the machine for which the first FORTRAN was written (the IBM 704), were altered for convenience whenever the language could not easily be accommodated by a particular machine. The result, of course, is that each translator implements something closely resembling the same language, but with differences. For example, 650 FORTRAN allows identifiers to be five characters long, while 1604 FORTRAN allows them to be seven characters long, both restrictions being due to convenience in writing the compilers. In line with the present fad for syntacticizing everything in sight, the present effort was undertaken. The immediate impetus for the work was the existence of PsYco [1], a compiler for ALGOL 60 on the CDC 1604, which requires a complete "syntax table" of the source language in order to do the translation. If such a table could be constructed for FORTRAN, then the same compiler could be used for both languages, with merely a change of tables. Work is presently being done to use PsYco to translate from FORTRAN to 1604 code [2]. To make our frame of reference explicit, the language with which this paper is concerned is that defined in the IBM publication "Reference Manual, 709/7090 FORTRAN Programming System" [3], the system presently used on the IBM 7090. We do not include any features of the language which have to do with the monitor system used with FORTRAN, nor do we include the syntax of Complex and Double Precision modifications (Column 1 mode indicators "I" and "D", respectively). The semantics of the language is of course a function of the processor, and is not considered here, although it has a tendency to creep into the syntactic specifications. References to quotations from the manual in this paper will be made in the form [Mn], where n is the page number in the manual. in [ACM] CACM 5(06) June 1962 view details in Goodman, Richard (ed) "Annual Review in Automatic Programming" (3) 1963 Pergamon Press, Oxford view details in ACM Computing Reviews 5(04) July-August 1964 view details in ACM Computing Reviews 5(04) July-August 1964 view details in ACM Computing Reviews 5(04) July-August 1964 view details in ACM Computing Reviews 5(04) July-August 1964 view details This paper is highly recommended to those seeking an introduction to syntax-directed techniques of analysis. It should also interest those who may already be familiar with the basic ideas but would like to learn who has done what, without reading all the original papers. in ACM Computing Reviews 8(03) May-June 1967 view details in ACM Computing Reviews 8(03) May-June 1967 view details We should like to thank Dr. J. H. Matthewman for the use of the Psyco compiler with which we have constructed our own compiler. Further, we thank him for his invaluable assistance in teaching us to use Psyco and assisting with the development of the compiler. Extract: A compiler for the system A compiler for the system A load and go compiler has been written for the language using Psyco (Matthewman, 1966) and at compile-time this occupies 16K of core store. At runtime the store required depends upon the size of the calculation involved. For the above program 8K is required when N = 2, while 12K is necessary for the case N = 4. (The Titan is a prototype Atlas 2 with 128K of 48-bit words.) The time required to compile and run the case N = 2 is 35 seconds, and for N = 4 is 90 seconds. The system we have described is particularly well suited to the calculation that we have used as an example, and it is in daily use performing the calculations for which it was designed. Indeed the existence of this system has made it possible to undertake many calculations that would otherwise be impracticable in a reasonable time. It is clear that this system is restricted in its scope, and it is through the manipulative routines that most of the system's restrictions arise. It should be mentioned that the compiler is quite independent of these routines. However, there is evidence that the modifications indicated earlier in this paper will improve the run-time system to such an extent that it will be of real value to users other than those in celestial mechanics. Extract: Introduction The system that we wish to describe here may be conveniently divided into two sections. The first section is concerned with the language in which the manipulative problem is to be programmed. This language will be described by an example. We shall not be concerned with the compiling techniques since these have been fully described elsewhere (Matthewman, 1966). The second section contains the run-time system and is composed of a set of closed subroutines that actually carry out the manipulation under the direction of the compiled object code. This latter system of programs has been described in Barton (1967) but a brief specification of the facilities available is desirable here in order to draw attention to the limitations of the system and to indicate possible means of extension. It is important to remark that while the syntax of the language that we shall describe is almost identical to Titan Autocode (-, 1967) the data elements with which we compute are not numbers but algebraic expressions. Extract: The programming language The programming language The language in which programs are written allows the four types of variable listed below: 1. Indices These are fixed point signed integers in the range In1 < lo6 and are called by the names I, J, . . ., S, T. It is also possible to use arrays of indices indexed by a single modifier. These are called as I[n], . . ., T[n]. 2. Expressions These are literal functions of the type cr (equation 1). They may be called by any of the names A, B, . . ., H or U, V, . . ., Z. Arrays of such expressions are allowed and these are called A[n], . . ., H[n], U[n], . . ., Z[n]. 3. Polynomial variables These are the atomic variables a, b, . . ., I that occur as arguments in the polynomials that make up an expression defined in equation (1). 4. Periodic variables These are the atomic variables u, v, . . ., z that occur as arguments of cosine or sine in an expression a. Extract: SUBSTITUTE The arithmetic operations carried out on expressions are denoted by + and -, while multiplication is denoted by juxtaposition. However, we have used . to represent exponentiation, * for differentiation and $ for integration of expressions. The differential coefficient of an expression whose name is A with respect to atomic variable a is therefore written A*a, while the integral is written $Aa. Thus the sequence of instructions A = a. 2; A = A + A*a; A = $(Ab)b results in the setting of A to the expression +a2b2 + ab2. Since there is no explicit multiplication operator we have used quotes to allow the input of complex expressions including cosine and sine. Hence A = 'SIN(U)' sets A to sin(u). The symbol 1 (vertical bar) has been used to introduce comment in programs and everything following on the same line as I is ignored, including 1. Two substitution routines are provided by the system and these will be illustrated by example. The program A = a + b; B = c.2; B = SUBSTITUTE (B, A, c) will result in the setting of variable B to the expression a2 + 2ab + b2, where we have substituted the initial value of A into the initial value of B for the polynomial variable c. The second type of substitution that is provided will perform as follows : B = a; C = SUBSTITUTE (A, v + B, u, 4) will result in C being set to the expression a2 a4 a a3 COS(V) (I - + -) - sin ( v ~ ( ~ - g). . 4! Here one should note that the literal expression cos(u) is enclosed in quotes. The substitution program has then substituted into the initial value of A for the periodic variable u the expression v + B. The expression B is assumed to be a small quantity and the result is the appropriate Taylor series in the initial value of B truncated to include only the terms up to order 4, the last parameter in the call of substitute. In the above example the algebraic operations that have been performed by the call of SUBSTITUTE are (a) u is replaced by v + B in the expression cos(u). (b) The expansion cos(v + B) = cos v cos B - sin v sin B is performed. (c) The expression B is replaced by its value a, to obtain the result. Our work in celestial mechanics frequently requires the expansion of functions as Taylor series in small parameters and the truncation of such series to include terms less than some prescribed order. The run-time system therefore provides a facility to check the result of any calculation for the presence of unwanted terms. These checks are imposed by the run-time system whenever it carries out a multiplication and may be used in several modes. Mode zero is preset and in this mode all multiplication is carried out exactly. Mode one will select terms whose total order is less than some prescribed quantity, while mode two will select only those terms whose order in a particular variable is less than a given quantity. Several other modes are available. The particular mode is selected by the directive MULTIPLY that takes effect at run-time. The directive defines what is meant by multiplication and takes two parameters. The first is simply an integer indicating which particular mode of multiplication is to be employed, and the second parameter references an index vector containing the parameters associated with each mode of multiplication. For example, A = ab; B = a + b.2; MULTIPLY( 1, I); I[O] = 3; A = AB will set the variable A to the expression a2b since multiplication in mode one selects only those terms whose total order is less than or equal to the first parameter of the index array, namely I[O]. Extract: Conclusion Conclusion We have indicated above that this compiler is independent of the run-time system as far as the manipulative routines are concerned. It would seem that a useful purpose would be served by the development of a simple language, the syntax of whch was defined, while the semantics were left undefined, at least in so far as arithmetic operations are concerned. It would then be possible for independent users to construct their own systems for algebraic manipulation or indeed other projects. These systems could be specially tailored to meet the requirements of particular problems and would, in general, be more economic in time and store than the comprehensive giant systems that will otherwise be developed. Further, it is remarkable that in no problem that we have encountered has it been necessary to factorise polynomials or general expressions or even to simplify expressions in anything other than the trivial sense. We are of course aware that simplification and factorisation are of great importance in certain problems of mathematics that it is desirable to solve on a computer, but nevertheless it is unnecessary to hold up possible developments on other subjects while these very difficult problems are overcome. It is true that languages have been previously developed with a syntactic/semantic distinction similar to that indicated above but these do not appear to be generally available to the machine user outside the computing laboratory. in The Computer Journal 11(3) March 1968 view details Introduction During recent years a number of systems have been written to manipulate algebraic expressions on computers. These systems may be classified according to their motivation; in one class there are systems such as ALAM that have been designed to solve a particular problem in Applied Mathematics. In the other class may be found systems like FORMAC and REDUCE whose aim is to provide general algebraic manipulation facilities. From the outset, the CAMAL system has been designed as an aid to the solution of large scale problems. These are taken from such fields as the Lunar Theory and General Relativity so that CAMAL may be placed in the former class of system. Two types of problem arise in the development of algebra systems. The first is concerned with the nature of the algebra being performed and includes such problems as integration and simplification. The second type arises from the fact that algebraic expressions may occupy large quantities of storage, and operations such as the multiplication of two expressions may take an inordinately long time. These problems are related since the successful application of simplification techniques will, in many cases, reduce the size of expressions and hence the total resource requirements. One source of inefficiency in an algebra system occurs as a result of the over representation of expressions. For example, in a calculation using only floating point numbers it would be inefficient to represent these as degenerate polynomials. As a consequence of this redundancy the time taken to manipulate these data structures may be significantly increased. Also the system required to handle more general structures will in itself occupy more store, thus decreasing the free space available to the user. For some problems these overheads are unacceptable. In general, economic data structures depend on the nature of the objects being manipulated; these may well differ substantially for different classes of mathematical entity. For this reason it is important that the choice of language in which the system is written should depend on the data structures involved, while the availability of a particular language should of secondary importance. In order to obtain sufficient flexibility of storage allocation and data manipulation a special language was devised for writing the CAMAL system. This language is similar in many respects to the user language and gives the system writers control over the operation of all parts of the CAMAL system. To achieve the aims outlined above, the CAMAL system employs a number of techniques that include modularity, selection and the reduction of expressions to canonical form. As well as assisting the development of a system for a given requirement, the modular concept ensures that, within limits, a system of minimum generality, and hence minimum overheads may be used for particular calculations. Selection facilities enable the user to impose conditions dynamically upon calculations in order to reduce the size of generated expressions. Indeed, some calculations are not possible unless such techniques are employed. Finally, all modules impose a canonical form upon the expressions they control. This technique has also been used in SYMBAL 11 and is a vital step in the implementation of effective general simplification procedures; further, such reductions as and x*O->O y* 1->y 2xy + 5xy -> 7xy become trivial operations. In this way explicit and redundant occurrences of zero are readily removed. Extract: PSYCO The syntax directed compiler, PSYCO, is used to generate compilers for both the user and systems languages just described. The syntax of the language with associated semantics are presented to PSYCO as a table of constructions in a notation similar to Backus Normal Form and to change the language it is only necessary to update this table. When a language is being developed, this is very convenient although the cost in terms of machine overheads is higher than for a hand written compiler. in [ACM] Proceedings of the Second Symposium on Symbolic and Algebraic Manipulation, March 23-25, 1971 Los Angeles (SYMSAM 71) 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 [ACM] Proceedings of the Second Symposium on Symbolic and Algebraic Manipulation, March 23-25, 1971 Los Angeles (SYMSAM 71) 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 |