MACSYMA(ID:431/mac025)Symbolic math systemProject MAC's SYmbolic MAnipulator. Joel Moses The first comprehensive symbolic math system, written in LISP. Participating in the original design work for MACSYMA (beginning in July, 1968) were W. A. Martin, C. Engelman, and J. Moses. Programming began in July, 1969. The expression evaluator and input-output (i.e. string editor, parser, 2-D display, language) were programmed by W. A. Martin, P. Loewe, and T. Williams. Of the other major modules in MACSYMA, W. A. Martin designed and programmed the polynomial arithmetic package; R. Fateman designed and programmed the rational function package and its extensions (including the radical simplifier); J. Moses designed and programed the simplifier (a major overhaul of the Korsvold program), many of the commands (e.g. differentiation, substitution), and the integration facility. E. Tsiang and W.A. Martin designed and programmed the power series expansion routines. P. Wang designed and implemented the limit programs, and the secondary storage control. R. Fateman designed and implemented the semantic pattern matching system. The improved LISP compiler is the work of J. Golden. Others who have contributed to the programming include D. Hill and S. Saunders. In debugging these programs and in interfacing the different modules, it often became necessary for one programmer to add to or considerably modify another's work. In this sense, many of the modules are joint efforts. Used parser written by Vaughan Pratt Versions: Symbolics Macsyma, DOE Maxima (ANL), Vaxima. People: Related languages
References: MACSYMA is a system for symbolic manipulation of algebraic expressions which is being developed at Project MAC, M.I.T. This paper discusses its philosophy, goals, and current achievements. Drawing on the past work of Martin [6], Moses [9], and Engelman [I], it extends the capabilities of automated algebraic manipulation systems in several areas, including a) limit calculations b) symbolic integration c) solution of equations d) canonical simplification e) user-level pattern matching f) user'specified expression manipulation g) programming and bookkeeping assistance MACSYMA makes extensive use of the power of its rational function subsystem. The facilities derived from this are discussed in considerable detail. An appendix briefly notes some highlights of the overall system. Extract: Introduction and Goals Introduction and Goals Computers have an important role to play in applied mathematics. Their ability to accurately carry out large numbers of computational steps has revolutionized the field of numerical analysis. Many classical methods for hand calculation of approximate solutions (such as higher-order quadrature formulas) have been abandoned. It may turn out, however, that some years from now this will be only a minor part of the computers' contributions to applied mathematics. By extrapolating from the successful applications of symbolic computer methods already reported, and from the current research in problem-solving by computer, one can imagine a computer system which serves the mathematician as a tireless, capable, knowledgeable servant, co-worker, and occasionally, mentor. The system would know and be able to apply all of the straightforward techniques of mathematical analysis. In addition, it would be a storehouse of the knowledge accumulated about many specific problem areas, such as treatments of differential equations or series. In some areas, such as symbolic integration, it would apply complex and tedious algorithms to produce results considered to be in the domain of unstructured problem-solvlng only a few years ago. If such a system can be constructed, its impact on applied mathematics would be substantial. Books would still be used, but only for tutorial exposition. It would be possible for the casual mathematician at a time-shared computer terminal to bring to bear on his problem a wider and more current range of methods and information. It seems reasonable to expect that a mathematician's thinking and productivity would be stimulated when he could quickly work out the consequences of his ideas. The way would be opened for the discovery of new problem-solving techniques. These goals are not new, nor are they unique to mathematics. There are clear parallels in systems design, medical diagnosis, and interactive problem solving in many fields. We mention them here because we plan to extend the MACSYMA system until it becomes clear whether or not such goals can be attained. We feel that we will be able to do this. Our rough hypothesis is that a mathematician knows perhaps 10,000 mathematical facts. For example, if a student learned four facts an hour, four hours a day, five days a week, nine months a year for four years, he would learn some 12,000 facts. The average mathematician may not be able to sustain this pace with complete retention, but he has been learning for a longer time period. At present, the MACSYMA system contains perhaps 500 mathematical facts. For the system to be generally acceptable as a mathematical co-worker, we might estimate that it is necessary to expand the knowledge content of the current system by a factor of 20. The current knowledge is embodied in a program of about 30,000 computer words, embedded in a 60,000 word system. The expanded program might then be around b00,000-1,000,000 words, assuming that the growth will be roughly linear with the number of facts added. This roughly linear estimate for expansion is based on system programming considerations which arise in the construction of large systems of this type. If the interaction of every fact with every other fact had to be explicitly represented, then the size of the program would tend to grow as the square of the number of facts. Our experience to date indicates that this will not occur. The MACSYMA system currently consists of about 20 principal modules. The interactions are of two types, inter-module and intra-module. As a module is asked to communicate with an increasing number of other modules, its internal complexity does increase, but the increase does not continue indefinitely as more modules are added. There is a limit to the number of really distinct and valuable facets which we have been able to find for a module to present to the world. It may be argued that a system consisting of many independent modules will lack global understanding; that the facts will be in the system, but the mathematician will not know how to obtain them. This is certainly the case in the large programs which have been developed for time-sharlng and operating systems. These might be characterized as being ineffectively hierarchical, with many duplicate functional units. The FORTRAN and PL/I subroutine libraries may be similar, but incompatible; also, there are many possible (perhaps superfluous) communication links between modules. These systems are, however, very useful. We picture the MACSYMA system as more hierarchical and more closely knit than current time-sharing or operating systems. Just how useful a personality it can be made to present to the world is one of the objects of our research. We have grave doubts about the usefulness of large systems constructed through the haphazard contributions of unsophisticated users. Every new bit of the system must be carefully integrated with the old. In addition, we rely heavily on the work of our colleagues in the field for the analysis and development of new symbolic algorithms, it is their work which makes us feel that our goal of amassing the fastest and most powerful techniques can be realized. While systems like MACSYMA must be carefully integrated, they must not be restricted to an inflexible language, a single data representation, or a minimal set of transformations. A powerful algebraic manipulation system must respond to a variety of demands and constraints, both from internal modules, and external users. We attempt to do this by providing a small number of carefully chosen alternative approaches, rather than one very general one. The more specifically a data representation and algorithm is tailored to a given application, the greater power the program has for that application. On the other hand, such programs require a great deal of effort to write and are less generally applicable. Our opinion is that the greatest gain in power comes from applying, in each case, an algorithm which fully exploits the mathematical properties of the problem to be solved. A smaller gain, which tends to be independent of problem size, comes from optimum selection of the data representation. We are employing a three part approach: (a) We provide a general language and data representation so that a user may code any algorithm he wishes, although the execution may be inefficient; (b) We try to provide all of the necessary basic algorithms, along with special data representations, if they are appropriate to make the algorithms efficient; and (c) We are initiating research in automated algorithm and data-representation improvement. To expand on point (a), our approach to user language is also based on a combination of, rather than a compromise between, ease of use and efficiency. We want to make it possible for the user to use notation natural to his problem, although we must restrict him somewhat to the framework of notations we have chosen for our user-computer interface. On the other hand, we are willing to make substantial transformations on the input in computing the internal form of an expression. It is clear that the system we are trying to create is a very ambitious one. Nevertheless, we think it is appropriate because it focuses our thinking and efforts on the important computer science questions of the day. One of these is the creation of intelligent systems and the modeling of thinking and problem solving. Several years ago it was optimistically predicted that computers would by now be proving important new theorems. This has not come to pass for several reasons. The general techniques available for improving search strategies have not turned out to be very powerful, and it is not as easy to invent methods for programs to learn new information as had been hoped. Nevertheless, the performance of programs which have had information added "by hand" has been impressive. For example, there are programs which converse in English, and answer questions concerned with a suitable nontrivial data-base. The question of what could be done by a program possessing the same knowledge of a subject as the best human problem solvers has been raised. In the past few years the techniques and languages for writing such programs have been greatly improved. The related question of computer aided instruction involves bringing people into a controlled environment which "understands" what they are thinking about. To do this, the environment must know something of value which the person wishes to learn, so that it can interact with him in depth. The MACSYMA system already contains features, and has solved problems, which have proved of interest to applied mathematicians (a group of skilled problem solvers) and has experienced continually increased demand as more features have been added. The MACSYMA system offers a concrete example for study of man-machine interactive problem solving. Another problem area is the management of large programs and the automation of the programming process. Experience in the design of systems of the hierarchical nature of algebraic manipulation programs has lead to several conclusions discussed earlier. Problems of intelligent information retrieval and management of large complex data bases also arise in this area. Finally, the careful analysis of mathematical algorithms, which has been an important input to our design effort, constitutes new data for those interested in building a useful theory of computation. Extract: An Overview of the Current MACSYMA System An Overview of the Current MACSYMA System The principal modules of the current MACSYMA system are shown in Figure 1. Modules are shown linked to those other modules on which they depend heavily. Those modules still under development are shown as squares. The initial development goal of MACSYMA was to combine the results of the doctoral research of Martin [6] and Moses [9] with the ideas in Engelman's MATHLAB [1]. This suggested an interactive system written in LISP which emphasized step-by-step problem solving. We also wanted to add new algorithms for handling arbitrary precision arithmetic, polynomials, rational functions, and integration. Except for the integration algorithm, which does not include all the capabilities we know how to implement, this initial goal has largely been met, and the system has reached new levels of performance in the following areas: a) Obtaining limits and some cases of infinite integrals b) Solving equations c) Canonical simplification d) User-level pattern matching capabilities e) user'specification of transformations on expressions f) Programming and bookkeeping assistance. The ideas used for simplification [8], integration [7], display [5], limits [11] and pattern matching [2] have been presented in detail in Separate papers. In this paper we will give an overview of MACSYMA by demonstrating the facilities for user'specification of transformations, algorithms, and simplifications. We will then describe in some detail the routines for handling rational functions and the solution of equations. We expect that one use of MACSYMA will be the symbolic recasting of a problem as a prelude to numerical solution. Appendix II gives a specific example. It outlines the steps required to transform some differential equations describing a boundary layer so that they are expressed in terms of a more interesting set of independent and dependent variables. The recasting involves a knowledge of the magnitudes of certain quantities and how fast they may vary. We use this information to apply truncated series expansions (or neglect small terms altogether). We also apply various side relations. Thwaites [10] suggests that the basic concern of applied mathematics is the approximate solution of canonical equations such as the ones we will be dealing with. The approximations can be motivated by either mathematical or physical considerations. If a machine is to automatically apply approximations based on physical considerations, it must know the relevant physics as well as the mathematics. It seems unlikely that such problems will be solved in the near future without the step-by-step guidance of someone familiar with the relevant physical interpretations. In order to work with the computer, the mathematician must be explicit and precise. The challenge to systems designers is to reduce the burden which the system places on its users. 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 Proceedings of the SIGPLAN symposium on Two-dimensional man-machine communication 1972 , Los Alamos, New Mexico, United States 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 in SIGSAM Bulletin 8(3) August 1974 view details in Rosenfeld, Jack L. (Ed.): Information Processing 74, Proceedings of IFIP Congress 74, Stockholm, Sweden, August 5-10, 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: MACSYMA MACSYMA In many ways a descendant of MATHLAB, this leviathan of the field possesses enough sheer code to approach an order of magnitude dominance over many other systems. It can do just about anything any other system can do, with the obvious exception of certain very specialized capabilities, such as the REDUCE high energy physics machinery. Furthermore. considerable attention has been devoted recently to insure that it concedes little in efficiency to less general systems. Extract: MACSYMA and SCHATCHEN It is impossible to summarize here its facilities, ranging as they do from extremely flexible user control over the form in which rational functions are presented to a semantic pattern-matching facility that, at least, if taken together with SCHATCHEN serves to define the state of the art. Features such as programs for the manipulation at polynomials over the Gaussian integers or the best extant program for the computation of symbolic limits are almost lost in the enormity of this first system to approach the goal al an algebraic manipulation facility. 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 in Proceedings of the 5th International Joint Conference on Artificial Intelligence IJCAI-77, MIT, Cambridge, Mass., August, 1977 view details in SIGPLAN Notices 13(11) Nov 1978 view details in E.W. Ng (ed) "Symbolic & Algebraic Computation Proceedings of EUROSAM 79" Springer-Verlag, Berlin, 1979 view details in E.W. Ng (ed) "Symbolic & Algebraic Computation Proceedings of EUROSAM 79" Springer-Verlag, Berlin, 1979 view details current developments in LISP and specialized LISP hardware happening in Europe, America and Japan. This research will have major implications for computer algebra and algebra system environments. Although LISP, by its extensible nature, has always been an evolving language, unconstrained by standards, the past few years have been amongst the most active. In the field of language work there have been SCHEME-84, Common LISP, Standard LISP 85 and 3-LISP, whilst in hardware there are the continuing development of Symbolics, the arrival of Texas Instruments, several experimental machines in Japan, such as FLATS, Alpha and TAO, and the start of similar projects in Europe. How all these factors will affect future developments and implementations of REDUCE, MACSYMA and SCRATCHPAD will also be discussed. in European Conference on Computer Algebra EUROCAL 85 LNCS 204 view details assist engineers, scientists, and mathemaricians in solving mathematical problems. A user supplies symbolic inputs and MACSYMA yields symbolic (or numeric) results. The MACSYMA system has been under continual development at MIT from 1969 to 1982 and at Symbolics from 1982 to the present. More than 100 man-years of effort has resulted in over 300,000 lines of MACSYMA code. Over 1000 man-years of extensive use, coupled with consistent and diligent debugging, has made MACSYMA uniquely reliable for a system of its size and complexity. There are currently thousands of users at more than 400 sites worldwide. MACSYMA has the most extensive range of capabilities of all computer algebra systems. The capabilities include (in addition to the basic arithmetic operations) facilities for computing arialyric answers for: Limits Derivarives Indefinite Integrals Definite Integrals Taylor Series (several variables) Poisson Series Laplace Transformations Indefinite Summations Ordinary Differential Equations Matrix Manipulation Systems of Equations (Nonlinear)Vector Manipulation Simplification of Expressions Tensor Manipulation Factorization of Expressions FORTRAN Generation MACSYMA aclamlly provides a large percentage of the basic mathematical techniques used in engineering and the sciences. I will present a basic introduction to MACSYMA and its capabilities. In addition, I will show many examples of applications of MACSYMA to real problems in engineering and the sciences. These examples illustrate the scientific, economic, and creative benefits derived from using MACSYMA. Reference: PaveUe, Rothstein, and Fitch, "Computer Algebra", Scientific American, Vol. 245, December 1981. in European Conference on Computer Algebra EUROCAL 85 LNCS 204 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 in [ACM] CACM 28(04) (April 1985) view details Macsyma. At present, there are two very similar programs going by the name Macsyma. One is called DOE Macsyma and is available through the National Energy Software Center (NESC) in Argonne, Ill. The second simply goes by Macsyma and is sold through Symbolics Inc. (Burlington, Mass.). If this isn't confusing enough, there's soon to be a third program based on the same code, if not bearing the same name. The progenitor of all these versions of Macsyma was a government-funded research project begun on a DEC PDP-10 at MIT's Artificial Intelligence laboratory in 1968. The name is derived from project Mac's symbolic manipulation system. By 1982, the code was sufficiently developed for MIT to begin licensing it; Symbolics bought the first license in that year. For a variety of reasons, most of them related to lawsuits, the two programs currently bearing the name Macsyma are built around a "frozen" 1982 version of the MIT code. It allows users to differentiate, integrate take limits, solve systems of equations, factor polynomials, expand functions in Laurent or Taylor series, solve differential equations, compute Poisson series, plot curves, and manipulate matrices and tensors. Most of it was written in common Lisp. The DOE version of Macsyma is little more than that frozen code, save for fixes of some of the bugs that users have discovered. "We're a nonprofit organization," explained Larry Reed, a computer scientist at the NESC, which maintains a library of over 15,000 codes. "We don't offer support here. The people who are using the code, and in some cases people we contract with, supply the fixes." Reed admitted that Symbolics has refined and added to the code more than the NESC has. But the NESC gives users the source code, and Symbolics "provides only a run-time version of the software," said Reed. While DOE Macsyma is installed at 250 sites, Symbolics' Macsyma has racked up 10 times that number of installations, according to development manager Randy Zeitvogel. DOE Macsyma runs under Vax/VMS and Unix as well as Alliant's Concentrix and Data General's AOS/VS. Symbolics' Macsyma runs on the Vax/VMS, Unix, and Ultrix as well as on IBM PCs with 80386 processors, and on Apollo, Sun, and Symbolic workstations. Both versions of Macsyma are licensed to their respective users. DOE Macsyma license fees range from $1500 to $2400. In addition to the one-time license fee, Symbolics requires its users to choose an extra-cost service contract. The price of Symbolics' PC license is $1950; basic service is $390 and full service (which includes telephone technical support) is $990. "Macsyma is huge and cluttered, but it's a gold mine," said Kahan. "It represents the accumulation of some decades of work, but it's grown in an undisciplined way. No one really knows everything that's in it." Get ready for another program built around the same code frozen in 1982. It is currently in development at Paradigm Inc. (Cambridge, Mass.), a company that supported the Vax/VMS version of DOE Macsyma until relatively recently. Maple. in [ACM] CACM 28(04) (April 1985) view details Long before the advent of microcomputers and even longer before the widespread use of computer graphics, work began on software whose problem-solving abilities would go considerably beyond those of Fortran. The first symbolic solver originated at MIT's famed Artificial Intelligence Laboratory in the late 1960s as part of Project MAC. (The acronym has nothing to do with the Macintosh, which didn't appear until 1984. MAC stands for multiple-access computing.) A program that ran on a Digital Equipment PDP-10 was a direct antecedent of today's PC Macsyma. The "Mac" in Macsyma relates to the program's Project MAC heritage. PC Macsyma is just one of the versions of the program now marketed by Symbolics Inc. The other versions run on workstations and minicomputers. Symbolics has given the PC version a Macintosh-like interface with pull-down menus. But PC Macsyma's origins are evident in the hardware it requires. It needs an 80386-based PC with a minimum of 4M bytes of RAM and at least 17M bytes of free space on a hard disk. If your computer has 10M bytes or more of RAM or a numeric processor, operation speeds up noticeably. For $1995, the single-copy price without educational discounts, PC Macsyma gives you a lot. The algorithms it uses, including artificial-intelligence techniques for parsing equations, have been honed and refined for 20 years. Though the PC version is new, Macsyma is a robust, proven product with great capabilities and extensive on-line help. But Symbolics admits that there are less expensive programs, designed from the outset to run on personal computers, that solve some problems faster and provide more attractive graphic outputs. in [ACM] CACM 28(04) (April 1985) view details 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 Resources
|