FORMAC(ID:158/for019)
FORmula MAnipulation Compiler
An extension of FORTRAN which does many types of algebraic manipulation on general mathematical expressions. (Sammett 1966)
FORmula MAnipulation Compiler. J. Sammet & Tobey, IBM Boston APD, 1962.
Extension of FORTRAN for symbolic math.
People:
Related languages
| FORTRAN II | => | FORMAC | Extension of | |
| FORMAC | => | ALBERT | Extension of | |
| FORMAC | => | Clemens and Matzner | Extension of | |
| FORMAC | => | Desktop Calculator Formac | Subset | |
| FORMAC | => | IAM | Strong, Influence | |
| FORMAC | => | PL/I-FORMAC | Variant | |
| FORMAC | => | REDUCE 2 | Incorporated some features of | |
| FORMAC | => | Scope FORMAC | Extension of | |
| FORMAC | => | SYMFORM | Conversational system for |
Samples:
References:
in Proceedings of the 19th ACM national conference January 1964 view details
in IEEE Transactions on Electronic Computers Vol EC-13 August 1964 (Special Issue on Programming Languages) view details
in IEEE Transactions on Electronic Computers Vol EC-13 August 1964 (Special Issue on Programming Languages) view details
An important step in artificial language development centered around the
idea that i t is desirable to be able to exchange computer programs between
different computer labs or at least between programmers on a universal level.
In 1958, after much work, a committee representing an active European computer
organization, GAMM, and a United States computer organization, ACNI,
published a report (updated two years later) on an algebraic language called
ALGOL. The language was designed to be a vehicle for expressing the processes
of scientific and engineering calculations of numerical analysis. Equal stress was
placed on man-to-man and man-to-machine communication. It attempts to
specify a language which included those features of algebraic languages on
which it was reasonable to expect a wide range of agreement, and to obtain a
language that is technically sound. In this respect, ALGOL Set an important
precedent in language definition by presenting a rigorous definition of its syntax.
ALGOL compilers have also been written for many different computers.
It is very popular among university and mathematically oriented computer
people especially in Western Europe. For some time in the United States, it will
remain second to FORTRAN, with FORTRAN becoming more and more like
ALGOL.
The largest user of data-processing equipment is the United States Government.
Prodded in Part by a recognition of the tremendous programming investment
and in part by the suggestion that a common language would result only
if an active Sponsor supported it, the Defense Department brought together
representatives of the major manufacturers and Users of data-processing equipment
to discuss the problems associated with the lack of standard programming
languages in the data processing area. This was the start of the conference on
Data Systems Languages that went on to produce COBOL, the common business-
oriented language. COBOL is a subset of normal English suitable for expressing
the solution to business data processing problems. The language is
now implemented in various forms on every commercial computer.
In addition to popular languages like FORTRAN and ALGOL, we have
some languages used perhaps by only one computing group such as FLOCO,
IVY, MADCAP and COLASL; languages intended for student problems, a
sophisticated one like MAD, others like BALGOL, CORC, PUFFT and various
versions of university implemented ALGOL compilers; business languages in addition
to COBOL like FACT, COMTRAN and UNICODE; assembly (machine)
languages for every computer such as FAP, TAC, USE, COMPASS; languages to simplify problem solving in "artificial intelligence," such as the so-called list
processing languages IPL V, LISP 1.5, SLIP and a more recent one NU SPEAK;
string manipulation languages to simplify the manipulation of symbols rather
than numeric data like COMIT, SHADOW and SNOBOL; languages for
command and control problems like JOVIAL and NELIAC; languages to simplify
doing symbolic algebra by computer such as ALPAK and FORMAC;
a proposed new programming language tentatively titled NPL; and many,
many, more. A veritable tower of BABEL!
in IEEE Transactions on Electronic Computers Vol EC-13 August 1964 (Special Issue on Programming Languages) view details
in FORMAC User's Symposium, June, 1965 view details
in FORMAC User's Symposium, June, 1965 view details
THE digital computer has by now become a commonplace tool of the astronomer. Most applications have involved the ability of the computer to perform prodigious volumes of arithmetic computation. Less familiar to most scientists are the nonnumerical uses of digital Computers. An example is the development of computer programs to carry out the formal manipulation of algebraic expressions. The present paper illustrates the use of a recently developed programming System, FORMAC, to derive closed-form expressions for the coefficients of a familiar series expansion in celestial mechanics.
It is well known that the Taylor series expansion of the coordinates of a body in Keplerian motion about an attracting mass can be written in the form
where u represents X, y, or z; uo and uo are the initial position and velocity at time t=to; and f and g are functions of ~=t?t0. These two functions may be expressed as power series in T:
Equation (1) was first used by Lagrange (1869), who gave explicit expressions for the coefficients f, and g, up to n= 5. Lagrange made use of the auxiliary variable s, defined as
which satisfies the differential equation
where
It is easily shown that all the coefficients f, and g, can be expressed as polynomials in the variables (l/r3), s, and i, where
A number of investigators since the time of Lagrange have used Eq. (1) in the problem of orbit determination, and have given explicit expressions for f, and g, up to the sixth or seventh order. A particularly elegant procedure for finding the coefficients uses the pair of recursive formulas
with the initial terms f0=l and g0=O, which were discovered originally by Cipolletti (1872). Using these recursions, Stumpff (1959) deduced expressions up to the seventh order in terms of a related Set of parameters:
This particular Set of local invariants has the advantage that a and E are small quantities for orbits of low eccentricity (vanishing identically for circular orbits). Maki's use of the relations
we deduce easily the first few coefficients:
The expressions of higher order are also polynomials in p, a, and E, the complexity of which grows rapidly with increasing order. The reader who wishes to convince himself that a considerable amount of algebraic labor is required to derive Stumpff's expressions will probably have no desire to continue to higher orders.
The formidable manipulative labor may explain, in part, why no attempt has been made since the time of Lagrange to tabulate explicit expressions for f, and g, for n greater than 7. Another reason may be the fact that the principal application of Eq. (1) has been in orbit determination problems where the time interval t is small. It is usually assumed in such problems that only the first few terms of the expansions (2) are really needed, because the factor ~"/n! will be negligible for large n. A more careful decision on where to truncate the series must depend on the radius of convergence for these expansions, which has been evaluated by Moulton (1903) for a representative class of orbits (orbits of minor planets) and by Sconzo (1964) for orbits typical of artificial earth satellites and lunar ~robes. To estimate the number of terms to be retained when T is close to the radius of convergence, we require expressions for f, and g, for large n.
This problem was recognized as a suitable test case for an experimental digital computer programming systern which can carry out the tedious algebra involved in the evaluation of the recursive formulas (7). The FORMAC Programming Language (Bond, et al. 1964; Sammet and Bond 1964), currently under development by IBM, combines the numerical and control capabilities of FORTRAN IV with the ability to generate and manipulate symbolic mathematical expressions. A short program in the FORMAC language, implementing formulas (7), generated f, and g, on the IBRI 7094 Computer, up to n=27, in a total of 18.67 min. The resulting expressions were printed out in standard FORTRAN notation. Terms up to the 12th order, transcribed into ordinary algebraic notation, are reproduced in Table I. The integer coefficients in these expressions are exact; beyond the 12th order, however, the coefficients were obtained in floatingpoint form, correct to eight significant figures. It may be of interest to note that computation and output of the expressions given in Table I required only 58 sec of computer time.
A slight modification of the program resulted in expressions for the coefficients in terms of r, T, and V, where
Specimen expressions for f8 and g8 are given in Table 11, in order to demonstrate the flexibility of FORMAC. At the option of the programmer, f8 has been ordered with respect to increasing powers of r; g8 has, on the other hand, been ordered with respect to decreasing powers of V.
Approximately three hours of a professional programmer's time were required for the formulation, coding, and checkout of the programs used to generate f and g.
The authors will undertake to make available. to interested readers, copies of the full Computer output (f and g, up to the 27th order, in FORTRAN notation),
in FORMAC User's Symposium, June, 1965 view details
in [AFIPS JCC 28] Proceedings of the 1965 Fall Joint Computer Conference FJCC 1965 view details
in [AFIPS JCC 28] Proceedings of the 1965 Fall Joint Computer Conference FJCC 1965 view details
in IBM Systems Journal 5 (1966) view details
Extract: Introduction
Introduction
Among the many and interesting achievements in the scientific use of electronic computers one cannot help but notice the advances made in the area of symbolic algebraic manipulation. One such advance is the advent of the experimental FORMAC system.
The purpose of this paper is to highlight and summarize pertinent facts concerning project goals and overall system capability, design, and usefulness. The paper also reports on the results of an interesting experiment to develop a time-shared, algebraic, desk-calculator program. Note that this paper is a summary, and does not attempt to provide details, motivation, or justification of the design. Throughout this paper various documents are referenced which explore particular aspects of the system in greater detail. Readers interested in more detailed information are encouraged to review the appropriate reports listed in the bibliography.
The FORMAC manual states the purpose of the FORMAC system as follows:
"FORMAC is an experimental programming system to as sist in the symbolic manipulations of mathematical expressions. It is an extension of the FORTRAN IV language and operates under the IBM 7090/94 IBSYS (Version 13) Operating System. It provides such capabilities as symbolic differentiation, expansion, substitution, comparison and evaluation of expressions (to name just a few) in addition to the full arithmetic, testing and loop control, and input/output capabilities of the FORTRAN system. The system can be used to obtain analytic solutions in problem areas for which only numeric techniques have proved of value in the past. "
Stated in another way, FORMAC and other similar systems attempt to give scientists a tool for solving analytic problems analytically.
The advantages of using computers for solving numerical problems are unchallenged today. An obvious question is: Can computers be equally successful in removing the tedium, errors, and wasted time associated with algebraic manipulations? Successful experimentation is proving that the advantages of using a digital computer for numerical computation apply in almost equal measure to the use of a digital computer for nonnumeric or symbolic work. With the refinement of list processing techniques, growth in memory size, and speed of modern computers, it has become evident that many of the analytic processes can be handled by machine. Simple analytic differentiation, for example, has become almost a classroom exercise in list processing.
It appears reasonable, then, for one to be able to write a set of routines that perform tedious, but routine, algebra and analysis. It was felt, however, that routines to perform the algebra were not, in themselves, enough. An adequate system should have a high-level language tO invoke the routines. Also, and equally important, is the facility to freely mix the algebraic capability with the numerical, looping, control, testing, and input/output capability such as is available in many well-known, high-level languages. The FORMAC project was formed with these ideas in mind.
Extract: History of FORMAC Project
History of FORMAC Project
In August 196Z, the FORMAC project began. A decision was made that the feasibility of the idea would best be proven by developing an experimental system rather than by paper design alone. We recognized, then, that in the long run, the capability to manipulate mathematical expressions would be most useful in a remoteterminal time-sharing environment. At that time, however, time-sharing was not developed to the extent that it is today, and it was believed to be unwise to try to solve, simultaneously, the problems of time-sharing, and developing a practical algebraic manipulating system. We also considered it important to have the system operate on standard hardware as a part of standard operating systems.
By mid 1963, the system goals were well enough defined to begin coding. In April 1964, the system became operational. During the summer and early fall of 164 the operational system was a vehicle for experimentation. Experimentation with the system disclosed some interesting facts concerning running time (which was not as bad as initially feared), core requirements (which turned out to be greater than anticipatecl), where the system was spending its time (such as checking for how well an expression was formed), and, in general, how certain decisions in design had affected overall performance (such as carrying explicit subscript of variables in an expression instead of reserving blocks for arrays of elements.)
A desire for wider audience reaction to and experience with the system led to the decision to release FORMAC on an experimental basis. In November 1964, after making some improvements the system was released. Since then many tapes have been distributed, and many interesting, and useful problems have been solved.
The cost of the initial system (approximately ten man-years) was divided among three major components:
(1) Capability and Language
(2) Compiler
(3) Object-Time System
The balance of this paper summarizes the salient features of these areas, comments on the problems that havebeen solved with the aid of FORMAC, and summarizes the features of a FORMAC algebraic desk-calculator program, which operates under the MIT Compatible Time-Sharing System.
Extract: Capability
Capability
It is important that the reader clearly understand the basic concept being discussed. This might be accomplished by comparing FORMAC with the numerical capabilities of FORTRAN.
In FORTRAN, arithmetic expressions are evaluated to yield a single numerical value. For example, D = B+C*5 results in a meaningful numerical value only if B and C have been assigned numerical values. Thus, the sequence of statements:
m = 3.
C = 4,
D = B+C*5.
will result in D being assigned the numerical value 23.
The algebraic capabilities of FORMAC differ from the numerical capabilities of FORTRAN in the following way. Although, at the source level, the user writes mathematical expressions in the same way as when numerical results are desired, the result of the evaluation is a mathematical expression. Thus, if B and C represent themselves or other expressions, then the value of D would be an expression.
For example, assume X and Y represent themselves (i.e., they are atomic)
Thus, computation yields an expression which exists as an entity at execution time, rather than a single numerical value. When this capability for declaring variables as having nonnumeric values is provided within the context of already existing scientific high-level languages, one has the facility for defining mathematical expressions which remain symbolic entities at execution time.
I mentioned earlier that FORMAC was added to FORTRAN IV. Thus, it is not surprising that expressions in FORMAC are written in the same way as in FORTRAN, and can be made up from all the operators in FORTRAN IV plus operators such as differentiation, combinatorial, and factorial. Also, there are a set of operators in FORMAC corresponding to the trigonometric and logarithmic functions in FORTRAN (see Figure 1). Operands of FORMAC operators may be FORMAC variables, or FORTRAN variables and constants.
In addition to building expressions and differentiating, we considered it desirable to provide direct high-level algebraic functions (commands) to manipulate the expressions. A dilemma existed in determining where to draw the line between providing primitive tools from which individual users can build their own higher level specialized functions, and providing what might be considered generalized, but basic, high-level tools. The FORMAC system concentrated on developing capabilities in the direct high-level end of the scale, with only a weak attempt made at developing the primitives.
In determining the capabilities, which would be made available in the FORMAC system, careful thought was given to the types of operations required in solving mathematical problems.
Among the most obvious features desired is the ability to symbolically differentiate expressions. The FORMAC operator, FMCDIF.provides this capability.
FMCDIF [Z, (X, Z), (Y, 15 ] is equivalent to
If Z is a function of X then the -~- will be carried as a symbolic entity, otherwise its value is zero. FORMAC permits implicit dependence relationships to be declared among atomic elements via the DEPEND statement.
The capability to multiply-out expressions by applying the distributive law and/ or multinomial theorem is also considered necessary. This advantage is easily seen in the following example (particularly if the reader imagines each variable to be a complicated expression).
R = [(A+B) ** Z + (A-D) * C] * FMCDIF(A**Z,A, 1)
results in
A question that you may ask at this point is: Does the system provide the counterparts to these two capabilities ? Although recognized as desirable features, the FORMAC system does not provide either an integration or a general factoring capability. Unlike the differentiation case, there is no simple comprehensive algorithm to integrate general expressions. To a lesser extent the same is true for general factoring. The FORMAC system, however, does provide enough basic capability to permit the user to write routines to do limited integration and factoring.
To assist in factoring, the FORMAC system offers the ability to find coefficients of variables, and limited expressions. The COEFF command also indicates whether an 7 numerically higher and/or lower powers of the specified variable exists in the expression. This is helpful when working with polynomial expressions.
A useful system must include the requirements for substituting into and numerically evaluating expressions. Substitution permits variables to be replaced by other variables, constants, or expressions. Evaluation of expressions (although not conceptually necessary if a substitution capability is provided) is available to direct the system to convert a number, from its expression representation to its numerical representation, so that it can be used as a numerical value in its host language statements (i. e. , in FORTRAN statements).
Note, that in addition to the mathematically meaningful commands, the user also requires aides that simulate actions he would do visually, or with pencil and paper. Seeking, partitioning, and examining elements of an expression; determining identity, and equivalence of expressions; editing, and input/output of expressions are all desirable (if not necessary) requirements of a practical system. See Figure 2 for a complete list of FORMAC commands and declarative statements.
A question that may have occurred to the reader is: What happens to terms, factors, and values that have been generated as a result of a manipulation, but that can be combined or eliminated to simplify the expression? An essential ingredient of every FORMAC command is a process called automatic simplification. In general, automatic simplification collects like terms in sums; collects like factors in products; deletes extraneous terms (e. g., a zero term or unit factor); and performs such obvious transformations as replacing A0 by 1, FMCCOS(0) by 1, 0B by 0. For a complete description of the automatic simplification function see (TOBER650).
Now that the reader has an understanding of the concept and basic capabilities, it is meaningful to discuss the specific environment and language for the capability.
The FORMAC capability was added to the FORTRAN language in a way which required separate FORMAC statements. This was done primarily to minimize the compiler effort. The method of implementation of the compiler, and restrictions in the FORTRAN language itself prevented a complete and natural embedding of the algebraic capability within the FORTRAN language.
However, even though separate statements were designed, care was taken to make the FORMAC language appear as syntactically close to FORTRAN as was reasonable. Not only is the same coding form used, but, variables, subroutines, and functions are named in the same manner. FORMAC and FORTRAN expressions are constructed at the source level in the same way, and the same rules for subscripting apply. FORMAC, however, permits mixed mode expressions. A key word, LET, which is the first word of all but three of the FORMAC executable statements, distinguishes FORMAC from FORTRAN arithmetic statements.
In addition to the entire FORTRAN IV language, FORMAC provides 15 executable statements and four declarative statements. See Figure 2. Complete details are given in (BONDE640) and (FORMI650). It should be emphasized that even though separate statements for FORMAC are required, FORMAC and FORTRAN statements can be freely mixed ix, one program or routine.
in [ACM] Proceedings of the ACM symposium on Symbolic and algebraic manipulation, 1966 view details
in [ACM] Proceedings of the ACM symposium on Symbolic and algebraic manipulation, 1966 view details
in [ACM] Proceedings of the ACM symposium on Symbolic and algebraic manipulation, 1966 view details
Another language in this same field, CALTRAN, tackles this same problem of "intermediate swell" in forming a product by using Pacioli multiplication (which stores no intermediate products) and positional representation of monomials [ for example, 7 3 stored in A (4,5,G) means that expression A contains the monomial 73.345 ] Extract: FORMAC
In this article, one of the architects of FORMAC presents
an interesting discussion of the problems encountered in obtaining the product of two polynomials, differentiating polynomial, and organizing the resulting expressions. The FORMAC operations used are EXPAND, AUTSIM, LEXICO, FMCDIF, FMCSEX, and SHRINK.
If
raised to the sixth power, hundreds of intermediate products are involved, although the final expression contains only 31 terms. In FORMAC, which is designed to handle and express each monomial in full, this expanding and condensing requires much storage; so much thought has been given to finding algorithms which permit economy. This is a formidable problem in the important and growing field of what is coming to be called "big math."[...]
It seems to this reviewer that FORMAC output expressions are awkward to read; how about a code for writing them on a plotter?
in ACM Computing Reviews 7(06) November-December 1966 view details
The paper is divided into four sections: Background; the Role of Simplification in the FORMAC system; Simplification Transformations; and the FORMAC Simplification Algorithm. A summary of FORMAC language extensions to FORTRAN IV are summarized. The simplification transformations that apply the distributive, associative, permutative laws and properties of additive and multiplicative identity elements in conjunction with a P-canonical form are nicely presented. Flow diagrams specifying the basic principles of the FORMAC automatic simplification routine and the organization of the sort routine are given.
The paper is well done, as where most papers presented at the AFIPS Fall Joint Computer Conference. After several years in the research stage, non-numeric programming seems now to be coming into its own.
in ACM Computing Reviews 7(03) May-June 1966 view details
in [ACM] CACM 9(08) August 1966 view details
Concrete examples are provided by the FORMAC EXPAND and differentiation algorithms, a basic FORMAC utility routine, and an experiment in the extraction of the skeletal structure of an expression. One recurrent theme is the need to avoid excessive intermediate expression swell in order to minimize core storage requirements. Although many details from the FORMAC implementation are presented, an attempt is made to stress principles and ideas of general relevance in the design of algorithms for manipulating mathematical expressions.
in [ACM] CACM 9(08) August 1966 view details
Extract: Introduction
Introduction
Scientists and engineers spend a sizeable portion of their time performing mathematical analysis. A large part of this analysis is tedious; i.e., it is conceptually straightforward and only requires mechanical skill from the human protagonist. Some of this analysis can be performed with numeric techniques; indeed, the high speed computer has made it possible and practical to utilize many numeric techniques for this kind of problem solving. But what about symbolic mathematics? If computers are so adept at performing well-structured, carefully defined tasks, why not use them to do tedious - but symbolic - mathematical analysis? Over the past thirteen years many efforts have been made in this direction. A more recent accomplishment has been the development of FORMAC. FORMAC is an experimental programming system, which runs under IBSYS on the IBM 7090 and 7094 computers, and has been available since November 1964. More recently it has been available on the direct couple system (it runs in direct couple mode).
This paper presents a selected sample of FORMAC applications to scientific and engineering problems. As early as 1953, Kahrimanian and Nolan, working independently, developed programs for performing analytic differentiation. During the ensuing years, a great deal of work directed toward performing tedious algebra and repetitive analysis has been performed. But until recently this work consisted of special coding efforts to accomplish a single symbolic computation or of efforts to produce general symbol manipulating systems such as LISP or IPL V.
Recent developments include ALPAK, Formula ALGOL and FORMAC. Each of these is a programming system designed to provide some type of mathematical expression manipulation capability. Of these, only Formula ALGOL and FORMAC provide the capability to manipulate general expressions; ALPAK is a polynomial and rational function system. Applications of these three programming systems to practical problems have been documented only for ALPAK and FORMAC.
Originally, the ALPAK language was FAP; one coded using the ALPAK macros (which contained calls to the ALPAK subroutines) to manipulate ratios of polynomials. A higher level language, ALTRAN, is currently under development for the ALPAK system.
FORMULA ALGOL is an extension of ALGOL that provides tools for formula manipulation, list processing and limited string manipulation. It includes the numeric and control capability of ALGOL and is a more general programming language than either ALPAK or FORMAC, due to the inclusion of list and string processing capabilities. Formula ALGOL does not include specific expression manipulating commands; however, a general capability is provided by which the user may write his own expression-manipulating procedures. For example, the user must write his own expansion and automatic simplification routines. The first Formula ALGOL was an experiment in extending the ALGOL language. The language of the revised Formula ALGOL is sketched in [...]. This system was demonstrated at the SICSAM Symposium in March, 1966.
The FORMAC language is an extension of FORTRAN IV; hence it contains FORTRAN IV as a proper subset. All the numerical capability of FORTRAN as well as the I/O and loop control capability are available in FORMAC. In fact, knowledgeable FORTRAN programmers experience little difficulty in learning the fundamentals of FORMAC; this can be accomplished by browsing through the FORMAC Manual in a morning. FORMIC provides specific expression-manipulating commands such as EXPAND and automatic expression simplification (AUTSIM) as a central part of the system.
The main purpose of this paper is twofold: (a) to discuss technical areas in which useful application has been made of the FORMAC system, and (b) to display and discuss the FORMAC expression manipulation capabilities which were essential in implementing these applications. The following have proved to be valuable attributes of the FORMAC system:
(1) Access to the capability is via a high level programming language that is easy to learn and use.
(2) The system manipulates general mathematical expressions including elementary transcendental functions of arbitrary complexity and depth of function nesting.
(3) Automatic simplification of expressions [13] and a versatile differentiation operator are provided as an integral part of the system.
(4) Expressions with either rational or floating-point coefficients may be manipulated.
(5) An interface is provided between the FORMAC symbolic capability and the FORMAC numeric capability so that symbolic analysis and numerical evaluation may be performed in the same program.
(6) The FORMAC programming system is embedded in IBSYS so that the full power and versatility of a general purpose monitor system is available to the FORMAC user.
Problems which occur in doing symbolic mathematics by computer are also discussed. The basic limitations on expression manipulation by computer which arise due to expression size, due to the time required to manipulate expressions, due to the size of integer coefficients and due to roundoff in floating-point coefficients are touched upon.
The applications are discussed in alphabetical order according to the application area and include aerolasticity, Bessel functions for large arguments, celestial mechanics, combinatorial analysis, curve fitting, differential equations, error-bound calculations, incomplete beta function, nonlinear maximum likelihood estimation and tensor calculus. They cover an entire spectrum from one-shot applications that have produced new mathematical results, through converted FORTRAN production programs, which can accept arbitrary functions as input and perform at object time the "preliminary analysis" that used to be done by hand prior to coding in the source language. Many other applications of the FORMAC system have been made. Applications not discussed here include: plasma physics, generation of Jacobi polynomials, stability analysis, symbolic integration of rational functions, crystal field theory, Thiele continued fraction expansions, game theory, symmetric polynomials, circuit design, generation of Frame's convergents, Fourier waveform analysis and a study of vehicle re-entry.
in [ACM] CACM 9(10) October 1966 view details
in [ACM] CACM 9(10) October 1966 view details
From the Author's Summary
This article is a review of applications of FORMAC to various problems. The application areas discussed are "aeroelasticity, Bessel functions for large arguments ,celestial mechanics, combinatorial analysis, curve fitting, differential equations, errorbound calculations, incomplete functions, nonlinear maximum likelihood estimation and tensor calculus."
In each case, a brief description of the problem is given, too brief for real understanding of the underlying physics or mathematics but enough for the reader to get a feel for the versatility and usefulness of FORMAC.
in ACM Computing Reviews 8(01) January-February 1967 view details
in Advances in Computers, Vol. 8 FL Alt and M Rubinoff (Eds.), Academic Press, New York, 1967 view details
in Computers & Automation 16(6) June 1967 view details
in Computers & Automation 16(6) June 1967 view details
in Computers & Automation 16(6) June 1967 view details
in Computers & Automation 16(6) June 1967 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: FORMAC
The first of the high-level nonnumeric compilers was written by a small group at IBM in Cambridge, Massachusetts, for IBM 700 and 7000 series computers and is called FORMAC for Formula Manipulation Compiler (Sammet 1965). It is a superset to FORTRAN and one of its prime virtues is simplicity for the user. Following is a partial list of declarations and commands in FORMAC
Declarations
ATOMIC A variable that stands for itself
DEPEND Expresses dependence of variables
SYMARG Beginning of a FORMAC program; also declaration for subroutine arguments
PARAM List of parameters used in EVAL or SUBST statements
Commands
LET Form an expression
SUBST Substitute an expression for a variable
EXPAND Remove parentheses
COEFF Obtain coefficient to a given power
PART Partition terms in an expression
ORDER Sequence variables
EVAL Evaluate expressions numerically
MATCH Compare two expressions for equivalence or identity
FIND Determine dependence relation
CENSUS Count words or terms or factors
As an application of FORMAC consider Sconzo's calculation of the f and g series to f27 and g27 (Sconzo 1965). The coordinates of a body in elliptic motion may be expanded in a Taylor series in the form
where
Recursion formulas of the following form exist:
where fi= 1 and gl= 0. Let
Part of the program which accomplishes this is given in Table IV.
FORMAC has a number of drawbacks. The greatest complaint is the lack of space for programs in execution. Because intermediate expressions are almost invariably long, FORMAC has a spill feature that enables generated expressions to be spilled onto magnetic tape. There exists an ERASE instruction that will liberate space occupied by expressions that are no longer needed. Unfortunately, ERASE does not presently operate on spilled information. Another disadvantage in FORMAC is that a few basic simplifications do not occur automatically, which may contract expressions considerably. Thus FORMAC does not recognize that cos(? 0) = cos6' or eWx=ecX.
There have been, and will continue to be controversies on the question of simplification in languages of this type. One extreme position is that simplification should be left entirely in the hands of the user, who knows the manner of simplification he desires. The opposite extreme is that the compiler should fully take care of this. FORMAC takes a middle-of-the-road position allowing the user to override automatic simplification by use of the command AUTOSIM. While no official commitment has been made by IBM, it appears very likely that an improved FORMAC
in Computers & Automation 16(6) June 1967 view details
applications include the derivation of power-series solutions to the equations of motion, the generation and application of high-order time derivatives of arbitrary powers of the radius vector, and the extension of Cayley's tables. Extract: Symbolic Manipulation by Computer
Symbolic Manipulation by Computer
AFTER more than a decade of development, digital computer systems for the formal manipulation of symbolic expressions are now available to scientists and engineers faced with problems involving long and tedious application of the operations of algebra and the calculus in strictly literal form. Some of the history of this development has been traced elsewhere (Davis 1968) along with a review of several currently available systems.
The present authors limit themselves to a brief description of IBM's FORMAC system, and then present three specific applications to problems in celestial mechanics.
FORMAC (the acronym represents FORmula MAnipu-lation compiler) was designed as a practical tool for scientists to use in solving problems requiring extensive literal manipulation of formulas and expressions. To make this tool available to as many users as possible, IBM has implemented the FORMAC system as an extension of Fortran. Hence, programmers familiar with Fortran, algol, or related languages can usually learn to use the FORMAC system in a few days.
FORMAC presently operates on the IBM 7090 and 7094 computers, and will be available for certain models of the System 360. It permits the user to define symbolic expressions in a notation that is identical to Fortran. Expressions may be built up from symbolic variables, and from other expressions, by using the basic operations of addition, subtraction, multiplication, division, exponentiation, and analytic differentation (total or partial). Functions automatically available include trigonometric, exponential, logarithmic, and hyperbolic. New expressions may also be generated from existing expressions by substitution, simplification, and expansion (i.e., removal of parentheses). A symbolic expression may also be evaluated, by substituting numerical values for some or all of the symbolic variables. The result is a simplified symbolic expression or, ultimately, a single numerical quantity.
These capabilities have been particularly convenient to apply in problems involving the manipulation of power series, e.g., generation of power-series solutions to ordinary differential equations; addition, multiplication, etc. of power series; substitution of one series into another; series inversion, and reversion (extension of the results of Van Orstrand to higher orders). FORMAC has proved to be especially effective, also, in literal developments based on recursion formulas? like those for the Legendre, Bernoulli, and Chebyshev polynomials; Bessel functions; and more complex recursions. It has been applied by scientists and engineers in a wide variety of research projects, involving such diversified areas as symbolic integration of rational functions; quadrature formulas of Radau, Lobatto, and Peano type; Fourier wave-form analysis; Thiele continued fraction expansions; nonlinear maximum likelihood estimation; Ricci's tensor calculus and Christoffel symbols; combinatorial analysis; and theory of numbers (generation of Bernoulli, Euler, and Genocchi numbers). A critical review of a number of published applications of the FORMAC system (Tobey 1966), and a comprehensive survey (Sammet 1966a) and annotated bibliography (Sammet 1966b) on the subject of the applications of symbolic formula manipulation, have appeared recently.
in Computers & Automation 16(6) June 1967 view details
in Bobrow, D. G. (ed) "Symbol Manipulation Languages and Techniques", Proceedings of the IFIP Working Conference on Symbol Manipulation Languages. North-Holland Publishing Co., Amsterdam, 1968 view details
in Bobrow, D. G. (ed) "Symbol Manipulation Languages and Techniques", Proceedings of the IFIP Working Conference on Symbol Manipulation Languages. North-Holland Publishing Co., Amsterdam, 1968 view details
in Tobey, R. G. (ed) Proceedings of the 1968 Summer Institute on Symbolic Mathematical Computation, IBM Federal Systems Center, Gaithersburg, Maryland, July-August 1968, IBM Programming Laboratory Report No. FSC-69-0312 (proceedings published June 1969). view details
in Tobey, R. G. (ed) Proceedings of the 1968 Summer Institute on Symbolic Mathematical Computation, IBM Federal Systems Center, Gaithersburg, Maryland, July-August 1968, IBM Programming Laboratory Report No. FSC-69-0312 (proceedings published June 1969). view details
in Tobey, R. G. (ed) Proceedings of the 1968 Summer Institute on Symbolic Mathematical Computation, IBM Federal Systems Center, Gaithersburg, Maryland, July-August 1968, IBM Programming Laboratory Report No. FSC-69-0312 (proceedings published June 1969). view details
in Tobey, R. G. (ed) Proceedings of the 1968 Summer Institute on Symbolic Mathematical Computation, IBM Federal Systems Center, Gaithersburg, Maryland, July-August 1968, IBM Programming Laboratory Report No. FSC-69-0312 (proceedings published June 1969). view details
in [ACM] CACM 14(08) August 1971 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] CACM 14(08) August 1971 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
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
FORMAC (FORmula MAnipulation Compilers)s a high-level language that manipulates algebraic expressions. It was developed, but not supported, by IBM, and is now considered a dead language.
in The Computer Journal 15(4) 1972 view details
in Computers & Automation 21(6B), 30 Aug 1972 view details
in ACM Computing Reviews 15(04) April 1974 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 ACM Computing Reviews 15(04) April 1974 view details
Introduction: The simple past.
The first version of FORMAC was written for the IBM 7090/94 as an extension of FORTRAN IV running under the IBM IBSYS-IBJOB monitor. It was an experimental programming system to assist in the symbolic manipulation of mathematical expressions and provided such capabilities as symbolic differentiation, expansion, substitution, comparison and evaluation of expressions. The project originated in August 1962 and the system was released in November 1964. References are given in [27].
Comments of users initialized the design and implementation of PL/I-FORMAC, a more flexible system based on the same principles. The first version was released in 1967, the second in September 1969, [27]. The PL/I-FORMAC interpreter, an extension of the OS/360 PL/I(F) compiler, was originally designed to run on an IBM S360 H-level model 40 and above. It consists of two modules of assembled routines whi6h are added to a system's library: the preprocessor and the objecttime library. In March 1970 the SHARE SMC project (now LASM project) composed a list of known errors and proposed extensions of the IBM preprocessor, [21]. In April 1970 a new preprocessor became available. It was developed at KFA-Julich, Germany-West, by R. Schwerdt, [19]. The errors were corrected and most of the proposed extensions were implemented.
To make the FORMAC-system again available to FORTRAN-users, a new FORTRAN-FORMAC, comparable with PL/I-FORMAC, has been written for and tested with FORTRAN IV(H) under 0S/360 in 1970 at DRZ-Darmstadt, Germany-West, by Knut A. Bahr, [1].
At 1.1.1971 IBM stopped the FORMAC project. Information about SHARE's FORMAC maintenance and distribution is given in SIGSAM Bulletin No. 26, page 2. The address of the FORMAC library of SEAS is: ZAM/KFA-Juelich, Postfach 365, D517 Juelich I, Germany-West.
Extract: SCOPE FORMAC
Another early system was the Scope FORMAC
Language, [28]. When the system was operational
it ran in a 256 K partition of an IBM 360/50 with
an IBM 2250 graphic display unit as I/0 device.
The system was last operational in January 1969,
at which time IBM decided to support it no
longer, [29]. Extract: FINSTER
A prototype of FINSTER ran on the
IBM 360/75 of KFA-Juelich in 1970, in a 160 K
partition under OS/MFT and serving four 2260
terminals. Extract: FORDECAL
FORDECAL is running in a number of institutions
on an IBM 360/67 under CP67-CMS and serving 2741
terminals. The system may be used on an IBM 370
under VM, although the testing of this FORDECAL
version is not yet finished, [15]. A TSO-version
will be announced in the near future, [15].
FORDECAL is an interactive system similar to a
desk calculator. The statements are executed as
soon as they have been typed on the key-board of
the terminal. Although this system does not
allow to execute a program with the whole range
the PL/I-FORMAC language itself offers, some
statements may be executed repeatedly with either
a DO or BEGIN command (compound DO-loops, DOgroups
and blocks respectively). The system allows
to c~ll user typed (function) procedures, which
can be recursive. The FORDECAL statements
resemble the PL/I-FORMAC statements, but are
written in a syntax as nearly similar as the
usual mathematical syntax. FORDECAL uses only
the FORMAC-components of PL/I-FORMAC and can be
used without any knowledge of PL/I and with only
a vague impression of FORMAC. [ii] and [12] survey
the system, [13] contains a description of some
of the practised implementation techniques and
[14], written in French, offers an accurate and
detailed description of FORDECAL and its
implementation, Extract: TUTOR
TUTOR, [16], was originally implemented on an IBM
360/65 at Calspan Corporation, Buffalo, N.Y.,
under OS/MFT using the FORTRAN GSP package for
the graphics facility (an IBM 2250 as I/O device)
and an interface program to make it compatable
with PL/I. When MVT and the PL/I GSP package
became available the program was modified for
these facilities. A normal run at Calspan
allowed 250 K. Due to changes in Calspan's
computer configuration TUTOR's future is
uncertain, [17].
TUTOR is a simple conversational system without
advanced control commands as provided in FORDECAL.
An essential difference between TUTOR and the
other interactive systems is its capability of
accepting two-sides equations, that is mathematical
expressions on either or both sides of the
equal sign. Special commands to manipulate
equations are implemented. Extract: SYMBAS
An experimental version of SYMBAS, a FORMAC
orientated version of BASIC, is running under TSS
since summer 1972 at KFA-J~lich serving 2741
terminals. A TSO-version of SYMBAS, running
under VS2, is in consideration, [9]. To have a
system available which is well suited for symbolic
as well as numerical applications the
interactive, line-orientated BASIC system was
chosen and its semantics were extended in the
case of symbolic applications. This technique
enabled the implementation of an interpreter
which evaluates expressions numerically when ~
ever possible. In this extension BASIC
variables do not need to have assigned numerical
values; they may be interpreted as atoms or
symbolic expressions may be assigned to them. So
assigning numerical values to all variables of a
SYMBAS program does the program run as if it
would have been a proper BASIC program.
The matrix statements of BASIC are also included
and are extended to facilitate fraction free
elimination algorithms for symbolic matrices.
The run-time routines of FORMAC are used to do
symbolic computations.
A special editor is available to create and
change programs. A debugging system enables the
user to stop his program at any point, to display
and to reassign variables, and to change statements
and program flow.
in ACM Computing Reviews 15(04) April 1974 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: 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 SIGPLAN Notices 13(11) Nov 1978 view details
in IBM Journal of Research and Development, 25(5), September 1981 25th anniversary issue view details
in IBM Journal of Research and Development, 25(5), September 1981 25th anniversary issue view details
in IBM Journal of Research and Development, 25(5), September 1981 25th anniversary issue view details
The author is eminently qualified to have written this paper. She is a long-time employee of IBM, and has written many papers and a definitive book on the development of programming languages. Her account of the contributions of IBM to the development of programming languages is itself a contribution to the subject.
in IBM Journal of Research and Development, 25(5), September 1981 25th anniversary issue view details
in Annals of the History of Computing 4(1) January 1982 IEEE view details
A BRIEF HISTORICAL SKETCH
-------------------------
The development of systems for symbolic mathematical computation first became
an active area of research and implementation during the decade 1961-1971.
. . .
. . .
To put the decade 1961-1971 into perspective, let us recall that FORTRAN
appeared about 1958 and ALGOL in 1960. These two languages were designed
primarily for numerical mathematical computation.
Then in 1960/1961 came the development of LISP, a language for list
processing. LISP was a major advancement on the road to languages for
symbolic computation. An operation such as symbolic differentiation which
is foreign to FORTRAN and ALGOL is relatively easy in LISP. (Indeed this
is one of the standard programming assignments for students first learning
LISP.) As will be noted later, several computer algebra systems were
written in LISP.
1961-1966
---------
In 1961, James Slagle at M.I.T. wrote a LISP program called SAINT
for Symbolic Automatic INTegration.
This was one of the earliest applications of LISP to symbolic computation
and it was the first comprehensive attempt to program a computer to behave
like a freshman calculus student.
The program was based on a number of heuristics for indefinite integration
and it performed about as well as a good calculus student.
One of the first systems for symbolic computation was FORMAC, developed
by Jean Sammet, Robert Tobey, and others at IBM during the period 1962-1964.
It was a FORTRAN preprocessor (a PL/I version appeared later) and it was
designed for the manipulation of elementary functions including, of course,
polynomials and rational functions.
Another early system was ALPAK, a collection of FORTRAN-callable subroutines
written in assembly language for the manipulation of polynomials and rational
functions. It was designed by William S. Brown and others at Bell Laboratories
and was generally available about 1964.
A language now referred to as Early ALTRAN was designed at Bell Laboratories
during the period 1964-1966. It used ALPAK as its package of computational
procedures.
There were two other significant systems for symbolic computation developed
during this period. George Collins at IBM and the University of Wisconsin
(Madison) developed PM, a system for polynomial manipulation, an early
version of which was operational in 1961 with improvements added to the
system through 1966. The year 1965 marked the first appearance of MATHLAB,
a LISP-based system for the manipulation of polynomials and rational
functions, developed by Carl Engelman at M.I.T. It was the first interactive
system designed to be used as a symbolic calculator. Included among its
many firsts was the use of two-dimensional output to represent its
mathematical output.
The work of this period culminated in the first ACM Symposium on Symbolic
and Algebraic Manipulation held in March 1966 in Washington, D.C.
That conference was summarized in the August 1966 issue of the Communications
of the ACM.
1966-1971
---------
In 1966/1967, Joel Moses at M.I.T. wrote a LISP program called SIN
(for Symbolic Integrator). Unlike the earlier SAINT program, SIN was
algorithmic in approach and it was also much more efficient.
In 1968, Tony Hearn at Stanford University developed REDUCE, an
interactive LISP-based system for physics calculations. One of its
principal design goals was portability over a wide range of platforms,
and as such only a limited subset of LISP was actually used.
The year 1968 also marked the appearance of Engelman's MATHLAB-68,
an improved version of the earlier MATHLAB interactive system, and of
the system known as Symbolic Mathematical Laboratory developed by
William Martin at M.I.T. in 1967.
The latter was a linking of several computers to do symbolic manipulation
and to give good graphically formatted output on a CRT terminal.
The latter part of the decade saw the development of several important
general purpose systems for symbolic computation.
ALTRAN evolved from the earlier ALPAK and Early ALTRAN as a language and
system for the efficient manipulation of polynomials and rational functions.
George Collins developed SAC-1 (for Symbolic and Algebraic Calculations)
as the successor of PM for the manipulation of polynomials and rational
functions. CAMAL (CAMbridge Algebra system) was developed by David Barton,
Steve Bourne, and John Fitch at the University of Cambridge. It was
implemented in the BCPL language, and was particularly geared to
computations in celestial mechanics and general relativity.
REDUCE was redesigned by 1970 into REDUCE 2, a general purpose system
with special facilities for use in high-energy physics calculations.
It was written in an ALGOL-like dialect called RLISP, avoiding the
cumbersome parenthesized notation of LISP, while at the same time retaining
its original design goal of being easily portable.
SCRATCHPAD was developed by J. Griesmer and Richard Jenks at IBM Research
as an interactive LISP-based system which incorporated significant portions
of a number of previous systems and programs into its library, such as
MATHLAB-68, REDUCE 2, Symbolic Mathematical Library, and SIN.
Finally, the MACSYMA system first appeared about 1971.
Designed by Joel Moses, William Martin, and others at M.I.T., MACSYMA was
the most ambitious system of the decade.
Besides the standard capabilities for algebraic manipulation, it included
facilities to aid in such computations as limit calculations, symbolic
integration, and the solution of equations.
The decade from 1961 to 1971 concluded with the Second Symposium on
Symbolic and Algebraic Manipulation held in March 1971 in Los Angeles.
The proceedings of that conference constitute a remarkably comprehensive
account of the state of the art of symbolic mathematical computation in 1971.
1971-1981
---------
While all of the languages and systems of the sixties and seventies began
as experiments, some of them were eventually put into "production use''
by scientists, engineers, and applied mathematicians outside of the
original group of developers. REDUCE, because of its early emphasis on
portability, became one of the most widely available systems of this decade.
As a result it was instrumental in bringing computer algebra to the attention
of many new users. MACSYMA continued its strong development, especially
with regard to algorithm development. Indeed, many of the standard
techniques (e.g. integration of elementary functions, Hensel lifting,
sparse modular algorithms) in use today either came from, or were strongly
influenced by, the research group at M.I.T. It was by far the most powerful
of the existing computer algebra systems.
SAC/ALDES by G. Collins and R. Loos was the follow-up to Collins' SAC-1.
It was a non-interactive system consisting of modules written in the ALDES
(Algebraic DEScription) language, with a translator converting the results
to ANSI FORTRAN. One of its most notable distinctions was in being the only
major system to completely and carefully document its algorithms.
A fourth general purpose system which made a significant mark in the late
1970's was muMATH. Developed by David Stoutemyer and Albert Rich at the
University of Hawaii, it was written in a small subset of LISP and came
with its own programming language, muSIMP.
It was the first comprehensive computer algebra system which could actually
run on the IBM family of PC computers.
By being available on such small and widely accessible personal computers,
muMATH opened up the possibility of widespread use of computer algebra
systems for both research and teaching.
In addition to the systems mentioned above, a number of special purpose
systems also generated some interest during the 1970's. Examples of these
include: SHEEP, a system for tensor component manipulation designed by
Inge Frick and others at the University of Stockholm;
TRIGMAN, specially designed for computation of Poisson series and written
in FORTRAN by W. H. Jeffreys at University of Texas (Austin);
and SCHOONSCHIP by M. Veltman of the Netherlands for computations in
high-energy physics.
Although the systems already mentioned have all been developed in
North America and Europe, there were also a number of symbolic manipulation
programs written in the U.S.S.R. One of these is ANALITIK, a system
implemented in hardware by V. M. Glushkov and others at the Institute of
Cybernetics, Kiev.
1981-1991
---------
Due to the significant computer resource requirements of the major
computer algebra systems, their widespread use remained (with the exception
of muMATH) limited to researchers having access to considerable
computing resources. With the introduction of microprocessor-based
workstations, the possibility of relatively powerful desk-top computers
became a reality. The introduction of a large number of different computing
environments, coupled with the often nomadic life of researchers (at least
in terms of workplace locations) caused a renewed emphasis on portability
for the computer algebra systems of the 1980's.
More efficiency (particularly memory space efficiency) was needed in order
to run on the workstations that were becoming available at this time,
or equivalently, to service significant numbers of users on the
time-sharing environments of the day.
This resulted in a movement towards the development of computer algebra
systems based on newer "systems implementation'' languages such as C,
which allowed developers more flexibility to control the use of
computer resources. The decade also marked a growth in the commercialization
of computer algebra systems. This had both positive and negative effects
on the field in general. On the negative side, users not only had to
pay for these systems but also they were subjected to unrealistic claims
as to what constituted the state of the art of these systems. However,
on the positive side, commercialization brought about a marked increase in
the usability of computer algebra systems, from major advances in user
interfaces to improvements to their range of functionality in such areas
as graphics and document preparation.
The beginning of the decade marked the origin of MAPLE.
Initiated by Gaston Gonnet and Keith Geddes at the University of Waterloo,
its primary motivation was to provide user accessibility to computer algebra.
MAPLE was designed with a modular structure: a small compiled kernel of
modest power, implemented completely in the systems implementation
language C (originally B, another language in the "BCPL family'')
and a large mathematical library of routines written in the user-level
MAPLE language to be interpreted by the kernel. Besides the command
interpreter, the kernel also contained facilities such as integer and
rational arithmetic, simple polynomial manipulation, and an efficient
memory management system. The small size of the kernel allowed it to be
implemented on a number of smaller platforms and allowed multiple users
to access it on time-sharing systems.
Its large mathematical library, on the other hand, allowed it to
be powerful enough to meet the mathematical requirements of researchers.
Another system written in C was SMP (Symbolic Manipulation Program) by
Stephen Wolfram at Caltech. It was portable over a wide range of machines
and differed from existing systems by using a language interface that was
rule-based. It took the point of view that the rule-based approach was the
most natural language for humans to interface with a computer algebra
program. This allowed it to present the user with a consistent,
pattern-directed language for program development.
The newest of the computer algebra systems during this decade were
MATHEMATICA and DERIVE.
MATHEMATICA is a second system written by Stephen Wolfram (and others). It
is best known as the first system to popularize an integrated environment
supporting symbolics, numerics, and graphics. Indeed when MATHEMATICA
first appeared in 1988, its graphical capabilities (2-D and 3-D plotting,
including animation) far surpassed any of the graphics available on
existing systems. MATHEMATICA was also one of the first systems to
successfully illustrate the advantages of combining a computer algebra
system with the easy-to-use editing features on machines designed to use
graphical user-interfaces (i.e. window environments). Based on C,
MATHEMATICA also comes with its own programming language which closely
follows the rule-based approach of its predecessor, SMP.
DERIVE, written by David Stoutemyer and Albert Rich, is the follow-up to
the successful muMATH system for personal computers. While lacking the
wide range of symbolic capabilities of some other systems, DERIVE has an
impressive range of applications considering the limitations of the 16-bit
PC machines for which it was designed.
It has a friendly user interface, with such added features as two-dimensional
input editing of mathematical expressions and 3-D plotting facilities.
It was designed to be used as an interactive system and not as a programming
environment.
Along with the development of newer systems, there were also a number of
changes to existing computer algebra systems. REDUCE 3 appeared in 1983,
this time with a number of new packages added by outside developers.
MACSYMA bifurcated into two versions, DOE-MACSYMA and one distributed by
SYMBOLICS, a private company best known for its LISP machines.
Both versions continued to develop, albeit in different directions,
during this decade. AXIOM, (known originally as SCRATCHPAD II)
was developed during this decade by Richard Jenks, Barry Trager,
Stephen Watt and others at the IBM Thomas J. Watson Research Center.
A successor to the first SCRATCHPAD language, it is the only
"strongly typed'' computer algebra system. Whereas other computer algebra
systems develop algorithms for a specific collection of algebraic domains
(such as, say, the field of rational numbers or the domain of polynomials
over the integers), AXIOM allows users to write algorithms over general
fields or domains.
As was the case in the previous decade, the eighties also found a number
of specialized systems becoming available for general use.
Probably the largest and most notable of these is the system CAYLEY,
developed by John Cannon and others at the University of Sydney, Australia.
CAYLEY can be thought of as a "MACSYMA for group theorists.''
It runs in large computing environments and provides a wide range
of powerful commands for problems in computational group theory.
An important feature of CAYLEY is a design geared to answering questions not
only about individual elements of an algebraic structure, but more
importantly, questions about the structure as a whole. Thus, while one
could use a system such as MACSYMA or MAPLE to decide if an element in a
given domain (such as a polynomial domain) has a given property (such as
irreducibility), CAYLEY can be used to determine if a group structure is
finite or infinite, or to list all the elements in the center of the
structure (i.e. all elements which commute with all the elements of the
structure).
Another system developed in this decade and designed to solve problems
in computational group theory is GAP (Group Algorithms and Programming)
developed by J. Neubueser and others at the University of Aachen, Germany.
If CAYLEY can be considered to be the "MACSYMA of group theory,'' then GAP
can be viewed as the "MAPLE of group theory.'' GAP follows the general
design of MAPLE in implementing a small compiled kernel (in C) and a large
group theory mathematical library written in its own programming language.
Examples of some other special purpose systems which appeared during this
decade include FORM by J. Vermaseren, for high energy physics calculations,
LiE, by A.M. Cohen for Lie Algebra calculations,
MACAULAY, by Michael Stillman, a system specially built for computations
in Algebraic Geometry and Commutative Algebra,
and PARI by H. Cohen in France, a system oriented mainly for number theory
calculations. As with most of the new systems of the eighties, these last
two are also written in C for portability and efficiency.
Research Information about Computer Algebra
-------------------------------------------
Research in computer algebra is a relatively young discipline, and the
research literature is scattered throughout various journals devoted to
mathematical computation. However, its state has advanced to the point where
there are two research journals primarily devoted to this subject area: the
"Journal of Symbolic Computation" published by Academic Press
and "Applicable Algebra in Engineering, Communication and Computing"
published by Springer-Verlag.
Other than these two journals, the primary source of recent research
advances and trends is a number of conference proceedings.
Until recently, there was a sequence of North American conferences and
a sequence of European conferences.
The North American conferences, primarily organized by ACM SIGSAM
(the ACM Special Interest Group on Symbolic and Algebraic Manipulation),
include SYMSAM '66 (Washington, D.C.), SYMSAM '71 (Los Angeles),
SYMSAC '76 (Yorktown Heights), SYMSAC '81 (Snowbird),
and SYMSAC '86 (Waterloo).
The European conferences, organized by SAME (Symbolic and Algebraic
Manipulation in Europe) and ACM SIGSAM, include the following whose
proceedings have appeared in the Springer-Verlag series
"Lecture Notes in Computer Science":
EUROSAM '79 (Marseilles), EUROCAM '82 (Marseilles),
EUROCAL '83 (London), EUROSAM '84 (Cambridge),
EUROCAL '85 (Linz), and EUROCAL '87 (Leipzig).
Starting in 1988, the two streams of conferences have been merged
and they are now organized under the name ISSAC (International Symposium
on Symbolic and Algebraic Computation),
including ISSAC '88 (Rome), ISSAC '89 (Portland, Oregon),
ISSAC '90 (Tokyo), ISSAC '91 (Bonn) and ISSAC '92 (Berkeley).
-----------------------------------------------
Professor Keith Geddes
Symbolic Computation Group
Department of Computer Science
University of Waterloo
Waterloo ON N2L 3G1
CANADA
in Annals of the History of Computing 4(1) January 1982 IEEE view details
in [ACM SIGPLAN] SIGPLAN Notices 28(03) March 1993 The second ACM SIGPLAN conference on History of programming languages (HOPL II) view details
in [ACM SIGPLAN] SIGPLAN Notices 28(03) March 1993 The second ACM SIGPLAN conference on History of programming languages (HOPL II) view details