ESP(ID:546/esp002)Symbolic maths systemEarly symbolic maths system for investigating Delaunay calculation of the moon's orbit André Deprit, Jaques Henrard and Arnold Rom, Boeing Scientific Research Laboratories Seattle, Washington 1970 Related languages
References: in [ACM] CACM 4(09) (September 1961) view details In March 1958 a Celestial Mechanics Conference was held at Columbia University and the Watson Scientific Computing Laboratory in New York (Davis 1958). One of the topics discussed was the possibility of constructing general-purpose compilers capable of carrying out literal theories in celestial mechanics. Such a compiler, according to Grosch, should be capable of performing the manipulations of complicated algebra as well as differentiation and integration of a limited class of functions. He estimated that 200 man-years of effort would be needed to program a completely literal theory, such as Delaunay's. That the programming language may be of crucial importance in endeavors of this kind is emphasized by the fact that Barton (1966) carried out the literal development of the lunar disturbing function to the sixth order in 2 min, to the eighth order in 7 min, and to the tenth order (two orders of magnitude beyond Delaunay) in 50 min. Barton noted that it took less than 6 h of programming effort to write this program. To complete and extend the work of Delaunay additional programming has to be done for the manipulations of the transformation theory. More about Barton's work later. Three problems were recognized almost ten years ago relative to the development of analytical theories on computers: (1) The generally slow speed of computers (2) Their small storage capacities (3) The nonexistence of algebraic compilers for literal calculations Today the large computers are some 15 times faster than the large computers of 1958 and fast core memories have increased in size by a factor of about 4. Algebraic compilers have come into existence as well as other languages suited to symbol manipulation. While all of these languages have some shortcomings, many are useful enough for celestial mechanicians to adopt as regular "tools of the trade." Actually, the number of languages on various levels of sophistication which may be used for a variety of nonnumerical applications is quite imposing. Table I gives a list of current symbolic manipulation languages (Sammet 1966). These languages may be categorized as follows: (1) List Processing. In this method of programming, information in the computer memory is stored associa-tively, i.e., elements of a data set are not stored consecutively but rather each element contains pointers to its succeeding (also sometimes preceding) element. These pointers are part of the data, and are wholly transparent to the user. This technique is especially useful in building up and manipulating lists of information. Such methods are often needed in building compilers to algebraically manipulate formal expressions. Examples: LISP, IPL V and SLIP. (2) String Manipulation. String manipulation involves operations on a concatenation of characters, including matching, insertion, deletion and replacement of characters. Example: SNOBOL. (3) Symbol Manipulation. Generally the same as (2) above. (4) Formula Manipulation. Generally means operations on algebraic expressions. In addition to the general languages shown here, there are many special-purpose programs designed to do a special job. These may be written in a high-level language, such as FORTRAN or ALGOL or may be in a low-level language. Broadly speaking, high-level languages allow less flexibility to the user but are easier to learn and apply, while low-level languages permit more flexibility but may require a considerable investment of time to acquire knowledge of the assembly language, basic machine instructions and special programming techniques. Extract: CAMAL, ESP, Davis In celestial mechanics general-purpose compilers like FORMAC have been used successfully in a small number of problems. However, special-purpose programs designed for specific tasks have produced a number of significant results. Deprit will describe some of his work during this colloquium. The development of special-purpose programs requires a set of specifications of the functions desired. Here are three sets of
Barton's work referred to earlier (Barton 1966) is a tour de force, and demonstrates some of the exciting possibilities of nonnumeric uses of computers. Written for the Titan computer at Cambridge University, Barton's program carried out the development of the lunar disturbing function and the contact transformations of Delaunay's theory, the latter work yet to be published. The method used for the developments of the disturbing function are shockingly simple in application and are executed in a special-purpose language written by Barton in less than 6 h. The transformation theory, however, is more complex. All of Delaunay's calculations to the eighth order were duplicated by Barton using his program in 7 min. The problem was repeated to the tenth order requiring only 50 min of machine time. Barton estimates the ratio of machine to human speed as at least 10 000:l. It should be pointed out that Barton was trained in Computer Science at Cambridge?an advantage that young astronomers should contemplate. in [ACM] CACM 4(09) (September 1961) view details The range of validity of these series is quite large: in the system sun-Jupiter, it includes the retrograde orbits for inferior planets as far as 90% of the astronomical unit, and the retrograde orbit of the eighth satellite of Jupiter. in [ACM] CACM 4(09) (September 1961) view details in [ACM] CACM 4(09) (September 1961) view details in [ACM] Proceedings of the Second Symposium on Symbolic and Algebraic Manipulation, March 23-25, 1971 Los Angeles (SYMSAM 71) view details in [ACM] Proceedings of the Second Symposium on Symbolic and Algebraic Manipulation, March 23-25, 1971 Los Angeles (SYMSAM 71) view details Introduction Use of computers for performing algebraic manipulations has gained widespread acceptance in recent years. While many efforts in implementing Systems for mechanized algebra are still experimental in nature, it is fair to say that in the field of celestial mechanics and non-linear dynamics, mechanized algebra has surpassed the experimental stage. We feel that the reason for success in this area stems from the fact that specific algebraic entities are defined before setting up the software. The form of the expressions to be manipulated is determined by the nature of the problems to be solved with the package. Once the algebraic structure is rigorously defined, software development is geared toward efficient implementation. The prime design criterion then becomes the ability of the package to handle large expressions with an acceptable amount of machine time. For a number of years the Poisson series has proved to be a useful tool for certain classes of problems in celestial mechanics and non-linear dynamics. Historically, computerized manipulation of Poisson series dates back to the days of the IBM 650 (Herget). In 1965 the author, in collaboration with J. M. A. Danby and A. Deprit, implemented a package for the IBM 7094. Since then the author has implemented several different versions of the package. The basic concepts of these packages were adopted and implemented by other workers in the field (Broucke, Jefferys). A recent publication in Celestial Mechanics describes the latest version of the system for manipulating Poisson series [I]. By definition Poisson series do not contain literal divisors, although any or all of the monomial letters can have negative exponents. These restrictions present no difficulties in problems where the frequencies can be treated as numerical constants. On the other hand, for problems like the Lunar Theory, the ability to handle divisors symbolically becomes necessary. Such divisors increase the complexity of the algebraic entity to be manipulated. Considering the relationship between divisors and the trigonometric factors, it seems natural to arrange the various factors of a series in a tree structure consisting of three echelons. The top echelon contains all the trigonometric factors, and the second echelon contains the divisors, while the bottom echelon contains the monomials (see Figure 1). In Figure 1, the T's stand for trigonometric factor, the D's represent divisors, and the P's represent monomials. [...] An Echeloned Series Processor (ESP) was implemented on an IBM 360144. The package is coded in assembly language but is used from FORTRAN. From the user's point of view ESP is similar to MAO [I], except that ESP places greater emphasis on enabling the user to code basic routines in FORTRAN. The storage schemes in ESP differ significantly from those used in MAO in that we employ a list structure whenever we build the terms of a series. ESP is operational and is currently being used to develop a general Lunar Theory [2]. The package was also used to compute the characteristic exponents at L, in the Elliptic Restricted Problem [3]. Extract: The ESP Language The ESP Language The ESP language is quite similar to the language of MAO. To use ESP one must know FORTRAN. A series of subroutines are provided for the basic operations. Table I provides a brief Summary of all the important routines. The bulk of these routines are identical to the routines in MAO. In the paper on MAO we gave detailed descriptions on how the routines are used from FORTRAN. Here we emphasize significant innovations and deviations. We assume that the reader is already familiar with MAO. Since all integers signifying exponents or multiples are packed in bytes, as is described in MAO, their values range from - 64 to + 63. There are two exceptions: the leading trigonometric argument is always positive and the exponent of the factors in the divisor are always positive. ESP handles up to six trigonometric arguments, up to twelve monomial letters, and up to three letters in the divisor. There is no limit to the number of factors which make up a particular divisor. Each factor can have an exponent ranging from + 1 to + 63. The routines in Table I fall, roughly, into three categories: (1) Routines for multiplication, addition and partial differentiation comprise the basic algebraic operations. (2) Input/Output routines which partially overcome the limitations of core size belong to the second category. Some I/O routines are also needed for storing computed results permanently. Punched cards or magnetic tape are economically best suited for the latter requirement while disk or drum satisfy the first requirement. (3) Besides the operations in category (1) there are a number of specialized operations which cannot be included here since they depend on particular problems. The last category consists of routines which allow one to manipulate the individual elements of a series. These routines are used to construct specialized operations in FORTRAN. From a user's point of view routines in the third category represent the most significant deviations from MAO. These will be described in detail later. First we review the routines already familiar from MAO. Note that there is no ORDER routine in ESP; terms are kept ordered as they are stored. 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 manipulation. The 6rst part of the paper is tutorial and several typical problems are introduced which can be solved using algebraic manipulative systems. Sample programs for the solution of these problems using several algebra systems are then presented. Next, two more difficult examples are used to introduce the reader to the true capabilities of an algebra program and these are proposed as a means of comparison between rival algebra systems. A brief review of the technical problems of algebraic manipulation is given in the final section. in The Computer Journal 15(4) 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 The Computer Journal 15(4) 1972 view details The best known, purely symbolic systems are, of course, Formac and its current version PL/IFORMAC (Petrick, 1971; pp. 105-114). Formac was the first widely available general-purpose algebraic manipulation system and served for a period to define the field. Certainly, there was a time when one could have safely made the statement that the majority of all mechanical symbolic mathematical computations had been done within Formac. The practical success of these systems, in spite of their rigidity with respect to user modifications and their lack of any seminumerical facilities for rational function computations, is probably due to the overall intelligence of the facilities that were provided. Above all, they were certainly sufficient to support the dominant application area of truncated power series expansion. Current support is minimal. Extract: ESP We will omit discussion of, as probably outside the interests of our general reader, a number of very special purpose systems that fall within this category. We feel compelled, however, to mention the system of Deprit, Henrard, and Rom, which is constructed basically for a single computation -- the reproduction and extension of the DeLaunay lunar theory expansion. This splendid achievement probably represents a mechanical computation on an order of magnitude greater in size than any achieved by earlier researchers. Extract: Symbolic systems SYMBOLIC SYSTEMS. We should mention first a sequence of three early programs for the simplification of general symbolic mathematical expressions represented as prefix-notation tree structures. The first, at M.I.T., was due to Hart, and the other two were due to Wooldridge and Korsvold at Stanford. The latter has survived in current usage as a result of its incorporation, subject to modification, into the MATHLAB, MACSYMA, and SCRATCHPAD systems. In the mid-1960s there appeared two systems, Formula Algol and FAMOUS, which, while dedicated to the symbolic manipulation of mathematical expressions, presented the user with almost no built-in automatic simplification facilities. This was due, at least in the case of FAMOUS, to a conscious decision that, since the "simplicity" of an expression is surely context- dependent, it should be reasonable to present the user with complete control over the simplification process. That is, the user'should be compelled to define all transformations, rather than, as with most systems, be permitted simply to switch on and off the transformations supplied by the system architects. No system of this species has ever solved the inherent efficiency problems to the extent that it could serve more than didactic purposes. Probably neither Formula Algol nor FAMOUS could be revived today. Another lost symbolic system of importance is the Symbolic Mathematical Laboratory of W. A. Martin. This system provided high-quality 2-D graphics on a DEC-340 display and was also the first to employ a light pen for subexpression selection. In some ways, it represented a degree of interaction that has not been duplicated by any subsequent system. Nor were its innovative internal programming techniques restricted to its graphics facilities. Of particular interest is the use of hash coding for subexpression matching (Petrick, 1971; pp. 305-310). in Encyclopedia of Computer Science, Ralston, Anthony, and Meek, Chester L. (eds) New York, NY Petrocelli/Charter 1976 view details in Encyclopedia of Computer Science, Ralston, Anthony, and Meek, Chester L. (eds) New York, NY Petrocelli/Charter 1976 view details |