August 1966 - Vol. 9 No. 8

A medium-scale programming system is written in MAD and FAP on the IBM 7094 to manipulate some of the objects of modern algebra: finite groups, maps and sets of maps, subsets and sets of subsets, constant integers and truth-values. Designed to operate in a time-sharing environment, the system can serve as a teacher's aid to the undergraduate student of modern algebra, as well as for the working scientist or engineer wishing to familiarize himself with the subject.

A programming language is described which is applicable to problems conveniently described by transformation rules. By this is meant that patterns may be prescribed, each being associated with a skeleton, so that a series of such pairs may be searched until a pattern is found which matches an expression to be transformed. The conditions for a match are governed by a code which also allows subexpressions to be identified and eventually substituted into the corresponding skeleton. The primitive patterns and primitive skeletons are described, as well as the principles which allow their elaboration into more complicated patterns and skeletons. The advantages of the language are that it allows one to apply transformation rules to lists and arrays as easily as strings, that both patterns and skeletons may be defined recursively, and that as a consequence programs may be stated quite concisely.

Bell Telephone Laboratories' Low-Level Linked List Language L6 (pronounced “L-six”) is a new programming language for list structure manipulations. It contains many of the facilities which underlie such list processors as IPL, LISP, COMIT and SNOBOL, but permits the user to get much closer to machine code in order to write faster-running programs, to use storage more efficiently and to build a wider variety of linked data structures.

A procedure for numerically solving systems of ordinary differential equations is shown to also generate symbolic solutions. The procedure is based on a finite Taylor series expansion that includes an estimate of the error in the final result. A computer program is described that reads in a system of such equations and then generates the expansions for all of the dependent variables. The expansions are determined symbolically, hence any non-numeric parameters in the original equations are carried automatically into the final expansions. Thus the exact influence of any parameters on the problem solution can be easily displayed.

The elimination procedure as described by Williams has been coded in LISP and FORMAC and used in solving systems of polynomial equations. It is found that the method is very effective in the case of small systems, where it yields all solutions without the need for initial estimates. The method, by itself, appears inappropriate, however, in the solution of large systems of equations due to the explosive growth in the intermediate equations and the hazards which arise when the coefficients are truncated. A comparison is made with difficulties found in other problems in non-numerical mathematics such as symbolic integration and simplification.

An algorithm for finding the symbolic factors of a multivariate polynomial with integer coefficients is presented. The algorithm is an extension of a technique used by Kronecker in a proof that the prime factoring of any polynomial may be found in a finite number of steps. The algorithm consists of factoring single-variable instances of the given polynomial by Kronecker's method and introducing the remaining variables by interpolation. Techniques for implementing the algorithm and several examples are discussed. The algorithm promises sufficient power to be used efficiently in an online system for symbolic mathematics.