ALPAK(ID:175/alp002)Extension to ALTRAN to manipulate polynomials and rational functionsSubroutine package used by ALTRAN to manipulate polynomials and rational functions Places People: Related languages
Samples: References: in Bell System Technical Journal 43(2) March 1964 view details in Bell System Technical Journal 43(3) 2 July 1964 view details in Bell System Technical Journal 43(3) 2 July 1964 view details in Proc. IBM Scientific Computing Symp. on Computer-Aided Experimentation, Oct. 1965 view details in Proc. IBM Scientific Computing Symp. on Computer-Aided Experimentation, Oct. 1965 view details An important step in artificial language development centered around the idea that i t is desirable to be able to exchange computer programs between different computer labs or at least between programmers on a universal level. In 1958, after much work, a committee representing an active European computer organization, GAMM, and a United States computer organization, ACNI, published a report (updated two years later) on an algebraic language called ALGOL. The language was designed to be a vehicle for expressing the processes of scientific and engineering calculations of numerical analysis. Equal stress was placed on man-to-man and man-to-machine communication. It attempts to specify a language which included those features of algebraic languages on which it was reasonable to expect a wide range of agreement, and to obtain a language that is technically sound. In this respect, ALGOL Set an important precedent in language definition by presenting a rigorous definition of its syntax. ALGOL compilers have also been written for many different computers. It is very popular among university and mathematically oriented computer people especially in Western Europe. For some time in the United States, it will remain second to FORTRAN, with FORTRAN becoming more and more like ALGOL. The largest user of data-processing equipment is the United States Government. Prodded in Part by a recognition of the tremendous programming investment and in part by the suggestion that a common language would result only if an active Sponsor supported it, the Defense Department brought together representatives of the major manufacturers and Users of data-processing equipment to discuss the problems associated with the lack of standard programming languages in the data processing area. This was the start of the conference on Data Systems Languages that went on to produce COBOL, the common business- oriented language. COBOL is a subset of normal English suitable for expressing the solution to business data processing problems. The language is now implemented in various forms on every commercial computer. In addition to popular languages like FORTRAN and ALGOL, we have some languages used perhaps by only one computing group such as FLOCO, IVY, MADCAP and COLASL; languages intended for student problems, a sophisticated one like MAD, others like BALGOL, CORC, PUFFT and various versions of university implemented ALGOL compilers; business languages in addition to COBOL like FACT, COMTRAN and UNICODE; assembly (machine) languages for every computer such as FAP, TAC, USE, COMPASS; languages to simplify problem solving in "artificial intelligence," such as the so-called list processing languages IPL V, LISP 1.5, SLIP and a more recent one NU SPEAK; string manipulation languages to simplify the manipulation of symbols rather than numeric data like COMIT, SHADOW and SNOBOL; languages for command and control problems like JOVIAL and NELIAC; languages to simplify doing symbolic algebra by computer such as ALPAK and FORMAC; a proposed new programming language tentatively titled NPL; and many, many, more. A veritable tower of BABEL! in Proc. IBM Scientific Computing Symp. on Computer-Aided Experimentation, Oct. 1965 view details OEDIPUS Now let us discuss briefly some of the programming problems which were encountered in the implementation of ALPAK. In the first place polynomials and rational functions must be put somewhere inside the computer, and this is clearly the sort of problem that the ALPAK user'should not have to think about. The amount of space required for a particular expression cannot usually be predicted in advance, and space must also be found for intermediate expressions whose existence the user may not even be aware of. This problem is solved by writing a dynamic storage allocator which finds and frees blocks of space on request. The storage allocator must also be able to handle lists and trees, since our data structures--e.g., products of polynomials--are often fairly complicated. A second problem is that many algebraic procedures are recursive. For example, to divide two polynomials in n variables, it is necessary to call a procedure for dividing polynomials in n-1 variables. If n > l, the second procedure is the same as the first, which therefore must be able to call itself. A third problem is that the introduction of complex data structures, dynamic storage allocation, and recurslon has necessitated a new approach to the problem of post mortem analysis. When a run is terminated because of insufficient space or time or because of a programming error, how can we get the computer to tell us in a problem oriented way what it thinks it was trying to do, where it was, and how it got there? Finally there is the ever present problem of book- keeping for subroutines. The facilities for dynamic storage allocation, recurslon, and post mortem analysis impose so many requirements on the writer of a subroutine that he needs the help of a computer to survive. These problems are all more general than ALPAK, and they led us to develop an operating environment called OEDIPUS (Operating E__nvironment with D_ynamlc Storage Allocation, I_nput-Output, Public Pushdown List, U_nhurried Diagnostics, and Symbolic Snaps). This serves as a foundation for ALPAKB, a new version of ALPAK, and can also be used to implement other systems having similar requirements. in [ACM] CACM 9(08) August 1966 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 in Kuo, F. F. and J. F. Kaiser (eds.), System Analysis by Digital Computer John Wiley, New York, 1966 view details in [ACM] CACM 9(08) August 1966 view details A reasonable extension of polynomial manipulation which can still be handled by essentially numerical processes is the manipulation of rational functions, as done in ALPAK. In this case, one usually needs some type of routine to find the greatest common divisor of two polynomials, and a good method of doing this exists in ALPAK. It is possible to consider including polynomials as a special case within a more general system, but this has not yet been tried. Presumably it should be possible to gain considerable added efficiency, but there are obviously severe implementation problems unless the concept of handling both polynomials and genera! expressions is designed in from the start. in Advances in Computers, Vol. 8 FL Alt and M Rubinoff (Eds.), Academic Press, New York, 1967 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 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: ALPAK A more general program, but one still written on the assembly level, and hence very efficient in machine time and space is ALPAK (Brown, Hyde, and Tague 1963), which is concerned in particular with polynomial manipulation. The program can handle about 8000 polynomial terms at a time with one man-hour = 1 sec on an IBM 7090. Knowledge of FAP, an assembly language for the 7090 or 7094, is presupposed. As an example, the format of the polynomial 3x2-\-2xyz2= 5yz2 may be represented as 3 2,0,0 2 1,1,1 -5 0,1,2 0 or in other ways that preserve the array notation and permit compression of many terms on a punched card. This fixed representation of terms in a polynomial is similar in concept to Herget and Musen's and is common to other systems, except that in ALPAK an exact representation of integer or rational function coefficients is used, rather than floating point representation. Irrational numbers may be represented by symbols. Integer coefficients, however, are limited to 35 bits, or about 10 decimal digits. However, it is possible for the user to redefine the macros to suit himself, in particular to do rational arithmetic. As can be seen from the internal representation of a polynomial, a canonical array notation is used, no symbol manipulation is necessary and hence great savings in time and space are possible. A few of the basic operations in ALPAK are Basic operations Meaning POL ADD R, P, Q R=P+Q POLSUB R, P, Q R=P-Q POLMPY R, P, Q R=P*Q POLDIV R, P, Q, NODIV R = P/Q (divide, if possible) POLDIF Q, P, x Q = ap/ax […] ALPAK has been used only to a limited extent despite its power. 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 ACM Computing Reviews 8(01) January-February 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 [ACM] CACM 14(08) August 1971 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 Computers & Automation 21(6B), 30 Aug 1972 view details The exact number of all the programming languages still in use, and those which are no longer used, is unknown. Zemanek calls the abundance of programming languages and their many dialects a "language Babel". When a new programming language is developed, only its name is known at first and it takes a while before publications about it appear. For some languages, the only relevant literature stays inside the individual companies; some are reported on in papers and magazines; and only a few, such as ALGOL, BASIC, COBOL, FORTRAN, and PL/1, become known to a wider public through various text- and handbooks. The situation surrounding the application of these languages in many computer centers is a similar one. There are differing opinions on the concept "programming languages". What is called a programming language by some may be termed a program, a processor, or a generator by others. Since there are no sharp borderlines in the field of programming languages, works were considered here which deal with machine languages, assemblers, autocoders, syntax and compilers, processors and generators, as well as with general higher programming languages. The bibliography contains some 2,700 titles of books, magazines and essays for around 300 programming languages. However, as shown by the "Overview of Existing Programming Languages", there are more than 300 such languages. The "Overview" lists a total of 676 programming languages, but this is certainly incomplete. One author ' has already announced the "next 700 programming languages"; it is to be hoped the many users may be spared such a great variety for reasons of compatibility. The graphic representations (illustrations 1 & 2) show the development and proportion of the most widely-used programming languages, as measured by the number of publications listed here and by the number of computer manufacturers and software firms who have implemented the language in question. The illustrations show FORTRAN to be in the lead at the present time. PL/1 is advancing rapidly, although PL/1 compilers are not yet seen very often outside of IBM. Some experts believe PL/1 will replace even the widely-used languages such as FORTRAN, COBOL, and ALGOL.4) If this does occur, it will surely take some time - as shown by the chronological diagram (illustration 2) . It would be desirable from the user's point of view to reduce this language confusion down to the most advantageous languages. Those languages still maintained should incorporate the special facets and advantages of the otherwise superfluous languages. Obviously such demands are not in the interests of computer production firms, especially when one considers that a FORTRAN program can be executed on nearly all third-generation computers. The titles in this bibliography are organized alphabetically according to programming language, and within a language chronologically and again alphabetically within a given year. Preceding the first programming language in the alphabet, literature is listed on several languages, as are general papers on programming languages and on the theory of formal languages (AAA). As far as possible, the most of titles are based on autopsy. However, the bibliographical description of sone titles will not satisfy bibliography-documentation demands, since they are based on inaccurate information in various sources. Translation titles whose original titles could not be found through bibliographical research were not included. ' In view of the fact that nany libraries do not have the quoted papers, all magazine essays should have been listed with the volume, the year, issue number and the complete number of pages (e.g. pp. 721-783), so that interlibrary loans could take place with fast reader service. Unfortunately, these data were not always found. It is hoped that this bibliography will help the electronic data processing expert, and those who wish to select the appropriate programming language from the many available, to find a way through the language Babel. We wish to offer special thanks to Mr. Klaus G. Saur and the staff of Verlag Dokumentation for their publishing work. Graz / Austria, May, 1973 in Computers & Automation 21(6B), 30 Aug 1972 view details 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 Computers & Automation 21(6B), 30 Aug 1972 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 Computers & Automation 21(6B), 30 Aug 1972 view details |