ALTRAN(ID:312/alt003)
A FORTRAN extension for rational algebra
W.S. Brown, Bell Labs
A FORTRAN extension for rational algebra.
An extension of FORTRAN which incorporates some of the ALPAK capability.
Places
People:
Related languages
| ALPAK | => | ALTRAN | Incorporated into | |
| Early ALTRAN | => | ALTRAN | Evolution of | |
| ALTRAN | => | Pfortran | Written using |
Samples:
References:
in [ACM] CACM 4(01) (Jan 1961) view details
ALTRAN
We have discussed several classes of expressions, and the operations that can be applied to them. ALPAK is a package of subroutines for performing these operations. ALTRAN is a new programming language for ALPAK users. Roughly speaking, ALTRAN is obtained by adding rational numbers, polynomials, rational functions, and in the future other classes of expressions to the data types of FORTRAN.
Both ALTRAN and FORTRAN are algebraic in the sense that they include statements which may contain algebraic expressions in several variables. ALTRAN is also algebraic in the sense that it includes variables whose values may be algebraic expressions in several variables. Since both the language and the data contain expressions, variables, and constants, we shall refer to language expressions, language variables, and language constants on the one hand, and data expressions, data variables, and data constants on the other. Thus the value of a language variable is, in general, a data expression in several data variables.
It is natural to expect that a language which included variables with nonnumerlcal values should also include nonnumerlcal constants, and this is indeed the case for ALTRAN. When a data variable (that is, one of the symbols from which data expressions are composed) appears explicitly in an ALTRAN program, it represents only itself; so it is in fact a language constant. Such language constants are sometimes called symbolic constants (see Section 3). If X is a data variable, the statement X = 2 would be illegal for the same reason that the statement 2 = 0 would be illegal; namely one cannot assign a value to a constant.
Every ALTRAN language variable must be declared explicitly. For example
POLYNOMIAL P, Q, R
declares that P, Q, and R are language variables of the type polynomial. That is, the values of P, Q, and R will always be polynomials.
An array of variables may be introduced whenever convenient. For example
INTEGER A,B(3,5),C(4)
declares that A is an integer variable, B is a two-dimensional array of integer variables with maximum subscripts 3 and 5 respectively, and C is a one-dimensional array of integer variables with maximum subscript 4.
Language expressions are constructed as in FORTRAN except that ALTRAN includes a notation for substitution. For example, suppose F, P, and Q are language variables of algebraic type, and X and Y are data variables. Then
F (X=P, Y=Q)
represents the result of simultaneousl [ replacing the data variables X and Y by the data expressions represented by P and Q respectively in the data expression represented by F. As a special case
F (X=Y, Y=X)
represents the result of interchanging the data variables X and Y in the data expression represented by F. As another special case
F(X=2, Y=3)
represents the result of evaluating the data expression represented by F at the point (2,3) in the XY plane. If the only data variables in the layout of F are X and Y in that order, then the above expressions can also be written as
F(P,Q), F(Y,X), and F(2,3) respectively.
in Kuo, F. F. and J. F. Kaiser (eds.), System Analysis by Digital Computer John Wiley, New York, 1966 view details
BROWN, W. S. A language and system for symbolic algebra.
[ in System analysis by digital computer, 349-373. See main entry CR Rev. 11,062. ]
This is a short, straightforward, and well written article describing the fundamental concepts inherent in ALPAK and ALTRA~-, which are respectively a set of polynomial handling subroutines to be used with FAP, and a language extension of FORTRAN to include the facilities of ALPAK. The paper includes an indication of how the polynomials are represented internally, what subroutines are available, how and why rational functions are handled, as well as comments about truncated power series, matrices and side relations. The description of A~TRAN is too short to be useful to anyone who does not already know about the concepts being described. A discussion of some of the implementation problems is short but indicative of the problems which exist in developing systems of this kind.
About half the paper is devoted to a discussion of applications, with several lists of applications given, and one worked out in considerable detail.
Perhaps the only fault one might find with the paper is its complete lack of mention of, or any reference to, any other related work done in this field. However, since the author was presumably allotted very little space, perhaps he was justified in such omissions.
J. E. Sammet, Cambridge, Mass.
in ACM Computing Reviews 8(01) January-February 1967 view details
An extension to FORTRAN on the 7090/94 to do formal rational-function manipulation. Uses ALPAK subroutines.
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: ALTRAN
The Bell Telephone people have made it simpler to program by writing a related compiler called ALTRAN (McIlroy and Brown 1966). The commands in ALTRAN are written as a dialect of FORTRAN. The following are self-evident statements in ALTRAN where P, Q, R, A, B are language variables of algebraic type, X, Y are data variables and K is an integer:
R=p+Q P=Q**K (exponentiation)
R=P-Q R=P(X=A7 Y=B) (substitution)
R=P*Q Q=DIFF(P7X) (Q=aP/aX)
R=P/Q R=GCD(P,Q) (greatest common divisor)
Expressions can be evaluated numerically by using the substitution statement above with A, B having numerical values.
[...]
ALTRAN has rational number arithmetic, rational functions, dynamic storage allocation and allows recursive procedures.
Extract: Time taken in developing ALPAK, ALTRAN, ALPAKA, ALPAKB
ALTRAN has rational number arithmetic, rational functions, dynamic storage allocation and allows recursive procedures. It is of interest to see how much work is involved in building compilers of this type.
ALPAK A 6.5 man-years
ALPAK B 2.5
ALTRAN 0.5
_________ 9.5 man-years
ALPAK B contains many improvements and extensions of version A, such as internal procedures to simplify the simplification process and multiple precision coefficients. The Bell Telephone Laboratories have subcontracted the development of ALPAK C which will be written in PL/I. BTL itself is writing ALTRAN C in PL/I and will consist of a series of calls to ALPAK C. Variables in ALTRAN C will be of five basic function data types: (1) number, (2) array, (3) entry, (4) polynomial, and (5) rational, allowing for a wide range of function domains.
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 Proceedings of the twenty-fourth ACM national conference August 1969 view details
SYMCIR was developed at Bell Telephone Laboratories to assist in designing complex linear circuits. Three programs (written in SNOBOL, ALPAK-A, and ALTRAN- A) apply indefinite admittance matrix analysis techniques using symbolic (not numerical) methods. This involves considerable manipulation of matrices of rational functions (ratios of polynomials), and yields results in the form of analytic expressions. This paper is directed to programmers and is concerned with implementation of SYMCIR on digital computers. It illustrates the kind of difficulties encountered in symbolic manipulation and the methods used to overcome these obstacles.
Contained in this short paper are a brief introduction to indefinite admittance matrices, several examples, and many insights into symbolic algebra via computers. Areas requiring further investigation are noted. Significant differences between symbolic and numerical operations are highlighted. This paper should be of interest to those working in, or preparing to work in, the field of symbolic algebra via computers.
in ACM Computing Reviews 11(01) January 1970 view details
Extract: Introduction
Introduction
ALTRAN is a programming language for the formal manipulation of rational functions in several variables with integer coefficients. As in most scientific programming languages, the elementary arithmetic operations (+, -, * /, **) are provided. In addition• ALTRAN also provides a notation for substitution. More complicated operations such as differentiation and greatest common divisor are available through procedure calls to library routines.
The ALTRAN system, composed of a translator, interpreter and run-tlme library, has been written almost entirely in FORTRAN IV. Considerable effort has been spent to achieve a portable system without undue sacrifice of efficiency.
In this paper, a brief description of the language, run-time data structures, and implementation is presented. A short history of the project is included, while a complete history and bibliography can be found in [2]. Extract: Brief History
Brief History
An early version of ALTRAN was designed by M. D. Mcllroy and W. S. Brown. The current ALTRAN language and system were designed by W. S. Brown with contributions from S. I. Feldman, W. M. Gentleman, A. D. Hall, S. C. Johnson and D. Mo Ritchie. The translator was implemented by D. M. Ritchle, the interpreter by A. D. Hall, the run-tlme rational function and polynomial routines by S. I. Feldman and S. C. Johnson, and the I/0 routines by S. C. Johnson. L. K. Russell wrote a SNOBOL IV program to check all subroutine and function calls with their definitions. G. Sande gave the portability scheme its first test by installing the system on an IBM 360/65. Extract: Data Organization and Manipulation
Data Organization and Manipulation
At run-time, space for all data is allocated dynamically in a large array called the workspace. The basic unit of allocation is called a block and always contains data of uniform type; either pointers to other blocks, integers, short floating point or long floating point. Several pointers to a block may exist and a reference count is kept to determine when a block is no longer needed. When required, garbage is collected by simply compacting the blocks that are not being used.
The value of each ALTRAN variable is represented by some structure in the workspace A SHORT INTEGER is stored as an integer. A LONG INTEGER is stored as an array of integers each representing a digit of the LONG INTEGER in base I0 n notation. RATIONAL numbers are stored as a pair of relatively prime SHORT or LONG integers. SHORT and LONG REAL numbers are represented by single or double precision floating point numbers, respectively.
ALGEBRAIC's are represented by a pointer to a formal product which is a block containing pointers to each of the factors and one pointer to another block containing the powers of the corresponding factors, as illustrated in Fig. 1.
In general, the factors of an ALGEBRAIC can be pointers to other ALGEBRAIC's or polynomials. If all the factors are polynomials, the ALGEBRAIC is said to be flat, otherwise non-flat.
A polynomial itself is represented by a block which contains three pointers. The first points to a layout which contains a description of the packing of exponents into machine words. The second pointer points to an array of coefficients and the third points to an array of exponent sets. The terms of the polynomial are ordered lexicographically by the exponents of each term. A typical polynomial is illustrated in Fig. 2.
An important feature of the ALTRAN data representation is that it permits large scale sharing of data. A polynomial may become a factor in several formal products and a block of coefficients or exponent sets may become a part of several polynomials. When large polynomials are present, this sharing can sometimes result in significant economies of storage.
ALTRAN maintains all ALGEBRAIC's in formal product representation and always reduces the result of a formal product operation to a flat ALGEBRAIC in one of several canonical forms. The canonical form used is changeable at runtime and represents the desired amount of factoring and GCD activity. A user may elect to have the numerator and denominator of an ALGEBRAIC maintained in factored or expanded form. Independently, he may or may not elect to have the numerators and denominators kept relatively prime. The arithmetic operations, multiplication, division, and exponentiation of ALGEBRAIC's are performed by making a non-flat ALGEBRAIC and then calling a routine to flatten the result and restore it to the required canonical form.
Addition and subtraction are performed by first removing the common factors of the operands, adding or subtracting the results, multiplying in the factors originally removed and restoring to canonical form. Polynomial operations are used extensively in the processes of flattening, addition and subtraction of ALGEBRAIC's. Addition and subtraction are carried out in a manner similar to that used in ALPAK [4]. Multiplication and division are performed using new versions of the classical algorithms [5], and the greatest common divisor of two polynomials is found using the modular algorithm described in [6].
ALTRAN makes no attempt to factor polynomials directly, but whenever the factored mode is elected and a factoring is discovered (usually through a GCD calculation or divisibility test) the polynomial is always replaced by a formal product representing the factors. All ALGEBRAIC's which shared that polynomial will then get the benefit of the factoring.
in [ACM] CACM 14(07) (July 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
[321 programming languages with indication of the computer manufacturers, on whose machinery the appropriate languages are used to know. Register of the 74 computer companies; Sequence of the programming languages after the number of manufacturing firms, on whose plants the language is implemented; Sequence of the manufacturing firms after the number of used programming languages.]
in [ACM] Proceedings of the Second Symposium on Symbolic and Algebraic Manipulation, March 23-25, 1971 Los Angeles (SYMSAM 71) view details
in [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
in The Computer Journal 15(4) 1972 view details
in [ACM] CACM 15(06) (June 1972) view details
External link: Online copy
in [ACM] CACM 15(06) (June 1972) view details
in ACM Computing Reviews 15(04) April 1974 view details
Extract: Introduction
In designing the language we strove for simplicity and conventionality; yet several new challenges were thrust upon us, and several older topics were brought into sharper focus.
Since old fashioned debugging techniques would be hopelessly inadequate in the complicated and unpredictable environment of symbolic computation, we developed a sophisticated error-handling strategy, and implemented it as an integral part of the language and the system. Essentially the same strategy has since been implemented in the Bell Laboratories Honeywell FORTRAN environment, and has dramatically improved the quality of life for literally hundreds of programmers.
In searching for a way to make ALTRAN widely available to others, and relatively immune to hardware improvements in our own computation center, we developed a broad general strategy for software portability, and a set of software aids for implementing it. This approach to portability has now been thoroughly tested in practice, and can readily be copied by others.
In seeking to develop a practical tool for applied mathematicians, we acquired a new perspective on a considerable body of old mathematics, and we encountered a host of exciting new mathematical questions. Even the seemingly simple problem of computing with rational expressions has been full of surprising challenges - inspiring contributions to an emerging theory of simplification, and to the fundamental understanding of other topics including Euclid's algorithm for polynomials and the theory of formal power series.
After exploring each of these areas in greater detail, I shall conclude with a brief discussion of some recent applications of ALTRAN.
in Proceedings of the 1975 ACM annual conference view details
ALTRAN Developed at Bell Labs out of its predecessor ALPAK system, ALTRAN is perhaps the most typical of seminumerical systems. It provides precisely for the arithmetic (through greatest common divisors, but not factorization) of multivariate rational functions over the integers and truncated power series. It is written in Fortran, but a few primitives must be hand coded. Its authors see this as a method of achieving portability while making no untoward sacrifice of efficiency. Extract: FORMAC
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 Encyclopedia of Computer Science, Ralston, Anthony, and Meek, Chester L. (eds) New York, NY Petrocelli/Charter 1976 view details
Both ALTRAN and PORT are written in PFORT, a large and mechanically verifiable subset of ANS FORTRAN. To make PFORT programs easier to write and easier to read, we now use an extension called RATFOR and a preprocessor that translates it into PFORT. A more ambitious extension called EFL is under development.
From a theoretical viewpoint the key to all our work on software portability is a model of the computing environments in which our programs will be expected to operate. We assume a hardware-software environment that fully supports the PFORT language and is characterized by parameters (machine constants) in four basic areas: 1) logical unit numbers, 2) word size, 3) integer arithmetic, and 4) floating-point arithmetic. To demonstrate the use of this model, we discuss an algorithm by J. L. Blue for computing the Euclidean norm of a real vector. The algorithm is portable, accurate, and efficient, avoids overflow and underflow, and will be included in the next edition of PORT.
in Portability of numerical software (Workshop, Oak Brook, 111., 1976), Lecture notes in computer science, Vol. 57, Springer-Verlag, New York, 1977 view details
This method requires quite a bit of algebraic calculation that is handled quite nicely by ALTRAN using its truncated power-series package. Flow diagrams are given for the ALTRAN program along with some sample input and output.
The authors do not discuss the limitations of their implementation. For example, they say only that the right-hand side of the differential equation is a nonlinear function in X. Obviously their program cannot handle every nonlinear function, but they do not indicate how the class of possible functions is delimited. Also, it would be nice to know if their implementation has been used to solve any significant problem. There are many mathematical methods that can be more or less straightforwardly implemented in existing algebraic systems. It is not particularly interesting to know that such a method has been implemented. It is interesting to know that the implementation exists and has been used to solve some significant problems.
A few minor remarks: The authors indicate that they chose ALTRAN over REDUCE because ALTRAN is machine-independent. Although ALTRAN is more machine-independent than REDUCE, REDUCE is also largely machine-independent. Furthermore, this does not explain why they did not use SAC-1, for example, which is just as machine-independent as ALTRAN. ALTRAN was a good choice for this problem, but for reasons other than machine-independence. In stating the execution times for their program the authors neglected to say which machine was used.
in ACM Computing Reviews 19(01) January 1978 view details
A FORTRAN-like language to do formal rational-function manipulation
in SIGPLAN Notices 13(11) Nov 1978 view details
ALTRAN, by design inherited from FORTRAN,
lead to fixed length integers.
Two examples will be discussed, illustrating
that, due to this integer representation,
a straightforward use of
ALTRAN easily can lead to discouraging
problems concerning core size limitations
and numeric overflow.
The first example is taken from fluid
mechanics; the rotating disk problem.
It covers both effects.
The use of polynomial resultants, the
second example, rapidly can lead to
numeric overflow.
Finally we discuss some preliminary
idea's to overcome these problems:
"Can a polynomial or truncated power
series representation for integers be
helpfull?"
References:
R.P. Hettich and J.A. van Hulzen,
"Approximation with a class of rational
functions", THT/TW Memorandum No.
165 (1977).
J.A. van Hulzen, Production of exact
Taylor coefficients for the rotating
disk problem using an algebra system",
THT/TW Memorandum No. 183 (1977).
in SIGPLAN Notices 13(11) Nov 1978 view details
Because of their universality, computers are perfectly capable of deriving symbolic mathematical expressions as well as numbers. Since symbolic results are free of round-off error and may provide more insight as well, Brown, Tague, and John P. Hyde of Bell Labs developed the ALPAK package of subroutines for symbolic algebra in the early 1960s. Then, in the middle 1960s, Brown, McIlroy, Gerald S. Stoller, and Leagus developed the ALTRAN language to facilitate ALPAK programming. 86 Shortly after the completion of the ALTRAN translator, the IBM 7094 computers, on which ALPAK and ALTRAN were totally dependent, began to be replaced by newer machines. This seemingly unfortunate situation led to a more advanced ALTRAN language and system developed by Brown, Hall, Johnson, Dennis M. Ritchie, and Stuart I. Feldman, which is highly portable and has proven useful in a wide variety of scientific applications, both at Bell Labs and elsewhere. Later, Feldman and Julia Ho added a rational expression evaluation package that generates accurate and efficient FORTRAN subroutines for the numerical evaluation of symbolic expressions produced by ALTRAN.
in SIGPLAN Notices 13(11) Nov 1978 view details
in [ACM] CACM 28(04) (April 1985) view details
Extract: Introduction
Introduction
Simplification of algebraic expression has been an important theme of computer algebrists since computer began to perform algebraic computation, as surveyed in [Moses71]. We have now two types of simplifiers for algebraic expressions. The simplifier of the first type transforms a given expression to a uniquely defined canonical forms (canonical simplifier). The simplifier of the second type applies term rewriting rules successively (term rewriting simplifier). The simplification algorithms described in [Brown69], [Cavin70], [Buchb65], [Lauer76], etc. are classified into the first type, while the RULE command in MACSYMA [MACSY77], LET command in REDUCE [ REDUC831, Rep command in SMP [SMP81]. etc. are implementations of term rewriting simplifiers.
Both types of simplifiers have fortes and faults. The canonical simplifier is very effective for specialized kinds of expressions, such as radical expressions, but it is unpractical to apply to large expressions. On the other hand, the term rewriting simplifier is applicable even to very large expressions, but it lacks the mathematical rigor. Simplifiers of term rewriting type were implemented in many algebra systems because they are simple. yet they have been used quite often in applications because they are applicable to almost any algebraic expressions.
So far, term rewriting simplifiers .perform mstly application of monomial rewriting rules. However, the importance of the multiterm rewriting simplifier has been recognized by many authors, see [Hearn84] for example. This is because that, as the user began to calculate larger and larger expressions, the inferiority of the conventional simplifiers to the human turned out clear and the power of current algebra system is strongly limited by the expression swell. For this point. see [ Stout773 and [Brenn84] for example.
As far as the author knows, there are two techniques for performing multiterm rewriting. One is the code optimization technique, as described by [ vanHu83], etc. The other is the so-called ?sum substitution? by Hornfeldt [Hornf83]. Both techniques seem to be quite powerful, and we should develop both because they are used mostly for different purposes.
In this paper, we describe a multiterm rewriting simplifier which is similar to that by Hornfeldt and a naive simulation of human?s method, We have implemented the simplifier as a command of computer algebra system GAL which is being constructed in Japan. An example of the command is
RULE sinf@X)**2 + cos(@X)**Z -> 1.
Hence, we can use the command just the same as we use the mathematical formula sin2(x) + ccls2(x) = 1. The rewriting rules may be either conventional mathematical formulas or defined by the user.
in [ACM] CACM 28(04) (April 1985) 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 [ACM] CACM 28(04) (April 1985) view details