ALAM(ID:487/ala004)Atlas LISP Algebraic Manipulationfor Atlas LISP Algebraic Manipulation Symbolic maths system developed by Ray d'Inverno at King's College, London, UK, especially for General Relativity. Places
Related languages
References: Extract: Motivation and background Motivation and background In the past decade a large number of computing systems for carrying out algebraic manipulation have been constructed. The general trend has been towards increasing the capability of the systems, thus allowing a whole spectrum of algebraic problems to be processed. On the other hand, it is clear that with respect to one computer and one language, the more general the capability the less efficient the system is likely to be. The interest of the author is the application of these systems in General Relativity where a large number of algorithmic algebraic problems exist. The systems encountered have a very definite limit on the complexity of the calculation they can handle in terms of what is economically viable. ALAM was constructed to allow more complicated problems to be processed, by restricting the capability of the system to what happens in normal calculations only, thus increasing its efficiency. ALAM possesses some peculiar features, their final justification being that the system appears to work more efficiently, in performing the same task, than other systems encountered, and that ALAM can proceed with problems where other systems cannot. For the above reasons attention was turned to the largest, fastest available computer, namely Atlas 1. The most convenient (although not necessarily the most efficient) way of representing algebraic structures is in tree-structures or lists. LISP 1.5 is a language which processes lists and has the advantages of being a very powerful language allowing recursive functions to be defined and possessing an automatic garbage collector. Many algebraic systems have been written in LISP; they seem in practice to be more efficient than systems written in other languages. Thus it was decided that a version of LISP under development for the Atlas 1 would be incorporated as a subset of ALAM. This version of LISP did not possess the function COMPILE which translates LISP functions into machine-code, allowing programs to run very much faster,:: and use less store. For this reason, ALAM was written in LAP, LISP's two-pass assembler (i.e. essentially in machinecode). Although ALAM can and has been written in LISP proper, such machine-code subroutines are probably more efficient than similar LISP functions compiled. In this paper, the structure and distinctive features of ALAM are introduced, and in Section 5 ALAM is compared with representative systems of the two languages most used in this field (LISP 1.5 and $ claims of up to a factor of 100 have been made. FORMAC). Section 6 contains definitions of some of the terms used in this paper. Extract: Distinctive features of ALAM Distinctive features of ALAM Some of the main differences between ALAM and other existing systems are: (i) Input-Output. Input is a relatively rare procedure; a well-defined Polish notation has been found to be unambiguous, while difficulties in this respect can arise with FORTRAN-type expressions. Output on the other hand is more frequent, and an attempt has been made to output in a 'mathematical notation', with standard indices, trigonometric and exponential forms. [...] This requires no transformation to a readable format for the mathematician without computer training. On the other hand large FORTRAN-type expressions are not easily readable, and translation by hand into a different notation is not only laborious but can introduce errors. (ii) Recursion avoided. When writing functions in LISP it is natural to write recursive functions. In fact in all functions where it was possible recursion has been dropped in favour of cycling (this of course is not always possible, as for example in the definition of COPY). This has proved to increase the overall efficiency considerably; for example the transfer of information to and from the push-down stack is bypassed; this could otherwise quickly build up in a large problem. This feature is related to the fact that in LISP proper PROG generally allows one to define functions more efficiently than COND does. (iii) SimpliJication in three steps. Again it might be more natural to write a main simplifying function with branches covering all possible simplifications, but functions can be made more efficient if their arguments are of a very particular form, since less tests of the arguments need to be made. The strategy of eradication of zeros, and expansion into a general form allows one to write functions with fewer branches in them. (iv) Modijication of list structure. All the main functions act by modifying existing list structure rather than by making modifications while copying existing list structure (consing). This is considerably faster when one realises that the majority of computing time is spent in either modifying or copying list structures. On Atlas, each modification takes only 1 or 2 machine instructions whereas 'consing' takes 15 or 16, and also makes more use of the push-down stack. The disadvantage of this approach, which only shows itself in very large computations, is that each expression must be stored uniquely (without common use of sublists). Both (ii) and (iv) considerably reduce the frequency of garbage collections, a redundant and time-consuming, though necessary, process. (v) Restricted capability. To save run-time some primitive simplifications have been adequate in many problems. For example no simplification of (SINAI) is attempted because nowhere in ALAM does the system construct such a quantity which could be simplified, as for example (SIN 0) could. Of course the programmer could- construct such a quantity as (SIN O), but if he did he would need to modify ALAM to simplify it fully. Although, for efficiency in most probems, the capability is restricted, it may be extended either by the device mentioned in (vi) or by changing functions or defining new ones. Apart from the substitution device, other alterations suffer from the disadvantage of requiring the user to have a somwhat detailed knowledge of the system. On the other hand it has been found that extensions are usually straightforward. For example suppose one wished to express a result involving (SIN A) and (COS A) in terms of SIN, COS and powers of SIN only. One could use the substitution device to replace powers of COS by their corresponding SIN expressions. Alternatively one could quite easily write a function which when simplifying ** would check for powers of COS and make the appropriate simplifications. (vi) Common factors. In most algebraic manipulation programs, a large amount of time is spent in trying to obtain common factors. The problem of common factors is not well-defined, and in most applications it has been found that either the answer is not the one desired, or that the added complexity arising from the attempt precludes any answer at all. The simple expedient of substituting an arbitrary function for common factor expressions and resubstituting only when printing out, has so far proved adequate in applications. This same device can be used to abbreviate constantly recurring long expressions in answers, and in substituting one expression for another. (vii) Numbers. Except for zero, all numbers in ALAM are rational, or algebraic numbers defined in terms of rationals. This ensures exact treatment and unambiguous output, unlike some systems which translate all numbers into floating-point form. In problems so far encountered, floating-point numbers have not been required. All arithmetic in ALAM is executed by special functions which take advantage of knowing the specific form of their arguments and which also avoid the need for numeric atoms in intermediary results. This avoids a lot of the redundancy in LISP arithmetic. (viii) Use of magnetic tape. Atlas LISP possesses the function SYSTEM which defines the present system in the computer as a new compiler by outputting it onto magnetic tape. This allows one both to modify ALAM permanently when one wishes and to keep a large number of expressions for future use. ALAM also possesses functions which can output and input individual expressions to and from magnetic tape when required. (ix) Overall economy of machine instructions. Savings which may seem small in a function can achieve significance when the function is entered over and over again during the course of simplification. in The Computer Journal 12(2) 1969 view details in The Computer Journal 12(2) 1969 view details in [ACM] CACM 14(08) August 1971 view details in The Computer Journal 17(3) August 1974 view details in The Computer Journal 17(3) August 1974 view details |