ASHMEDAI(ID:1835/ash001)Symbolic maths packagePresumably for the King of the Devils in Jewish lore - Solomon wants to build the temple without tools, to avoid noise, and some demons he captures tells him to consult Ashmodai Levine CMU; Symbolic maths package. Had an influence on SMP and FORM. Versions for Univac 1108 and VAX/VMS. Related languages
References: INTRODUCTION In this paper, we wish to discuss the algebraic system ASHMEDAI which has been used to great advantage in large scale analytic calculations in theoretical physics. To put the discussion in perspective, we begin with a very brief historical account. ASHMEDAI is written by one of us (MJL). It arose initially as a set of limited purpose algorithms to do many of the tedious straightforward operations arising in Weak Interaction and Quantum Electrodynamic (QED) calculations. Levine then realized that these algorithms could naturally be extended to become a more general algebraic language. Through the course of several implementa- tions, the package was a fairly austere machine language, Fortran-callable polynomial manipulation scheme together with special features to handle the specialized structures (Dirac matrices and Lorentz 4-vectors) arising in QED. Shortly before the collaboration with Roskies on computing the magnetic dipole moment of the electron, Levine instituted many changes in the program. Fortran was adopted as the source language to facilitate writing, debugging, modifying and disseminating the code. A very simple but very much improved user interface was developed to facilitate usage of the system. Numerous capabilities of the machine language versions were discarded because they did not seem necessary. Similarly, some algorithms were degraded to facilitate coding even at the expense of execution time efficiency if that seemed likely to speed up the work as a whole. However, as a result of difficulties encountered in the magnetic moment problem, many changes have been made which greatly increased the efficiency of the program and expanded its capabilities. Sometimes this involved reinstating older, more efficient procedures, and sometimes entirely new procedures were developed. We feel very strongly that being 'led by the problem' is one important technique to be used in the development of algebraic systems. This presentation is made not so much to explain the system as to point out to you who spend more of your time on such things those types of capabilities which we have found to be vital for some serious calculations. Since so many of the program capabilities were inspired by the difficulties of the magnetic moment calculation, we begin by briefly discussing this problem, showing what kinds of execution features it requires. Then we discuss the program itself, how it looks to the user, its basic structure, its operating philosophy, some aspects of its storage management, some of its special features, and ways in which it can be improved. We then devote a section to checking techniques. This aspect of algebraic programming is rarely discussed, but is very important and involves a great deal of effort. We end with conclusions. Extract: The Computing System THE COMPUTING SYSTEM All of these manipulations were performed using ASHMEDAI, a simple general purpose algebraic manipulation program. ASHMEDAI is written entirely in Fortran V. As we run it on a Univac 1108 it is a single overlay of about 24K words of program and uses another 28K words for general storage of data. This storage is allocated dynamically as the calculation develops. Although our machine affords us no permanent on-line storage, we do use about half a.million words of drum storage at execution time for sorting and saving very large data structures. Some program features are simply due to the environment in which we use the system. We run in a single user, batch mode without data files. Thus the program response to detected errors is minimal. Without file storage and swapping facilities program size must be kept down and overlaying frees core only at the expense of drum space. ASHMEDAI also runs on many PDP-10 and IBM 360-370 machines. There it can he used interactively. Conversion is no worse than for any large Fortran program such as those used in high energy physics data processing. It is being used for a variety of field theory and perturbation theory applications. Most of these applications are in high energy physics. ASHMEDAI implements interpretively a modest algebraic processing language. From the user's viewpoint, ASHMEDAI differs from most programming languages. The program is comfortable and easy to use for problems which flow in one direction -- problems which start with some input expression, require substitutions and collection of terms, more substitutions, a new collection of terms and so on. To the uninitiate it is remarkable how many problems can be handled this way. Conditional branching, looping structures, and the presence of several expressions simultaneously are all possible, but require more user intervention than in some other programming languages. The user also has more decisions to make, such as where to invoke certain substitutions and where to collect terms. The advantage is greater efficiency, and small storage requirements. With the drum utilization technique to be described later, we are able to run a powerful program interactively on a PDP-10 in a 24K partition. The input character stream contains commands which cause certain operations to be performed or which modify the way in which they are performed. That character stream also contains input data structures and comments. The basic input data structure is the 'term' or product of constants and indeterminates. These terms are combined to form 'expressions' and 'identities' according, largely, to the usual rules for Fortran 'arithmetic expressions'. The entire input character stream is scanned from left to right, one character at a time. This stream is derived principally from data cards. Commands can cause characters to be taken from other devices or from data files. Elaborate 'textual functions' which are similar to the macros used in assembly languages, and conditional commands can be used to augment the input character stream. Output from the program contains a variety of information much of which can be suppressed by appropriate commands. There is a running commentary containing images of cards read, characters derived from textual functions, names of commands recognized, names oF symbols created, the elapsed time, the amount of core available and counts of the number of terms which have been processed. Intermediate results and temporary data structures can be printed, directed to card, tape or data files for reuse by other ASHMEDAI runs. Results can be printed for reading or punched for later use in Fortran programs. Explicit commands are used to cause operations to be performed; operations are usually not triggered simply by the appearance of their related data structures. For example, the appearance of a new substitution need not cause that substitution to be implemented. Expressions and identities can be input and left in core, inert and unused. A few commands cause operations to be performed on expression in its entirety; most commands refer to a 'one term at a time' processing mode which can be tailored to make the best use of storage at little expense in time. Those commands in ASHMEDAI which operate on an expression in its entirety are used to change the structure of the expression. Such changes are intended to facilitate either Fortran numerical evaluation of the expression or subsequent symbolic work. For example a polynomial in 2 variables (x,y) each occurring with up to the 99th power might contain l0 T terms. Complicated operations involving only one of the variables(e.g, x) need only be performed I00 different ways. Operating on the whole expression would require i00 times the work. By restructuring the expressions into a polynomial in x with coefficients which are polynomials in y and operating only upon the polynomial in x, such extravagant wastes of time can be avoided. Because of its utility in large calculations we will now describe the 'one term at a time' processing scheme and the 'control stack' of commands and pushdown list of intermediate, partial results used in its implementation. After that, we will describe a use of auxiliary storage which allows collecting terms and then reprocessing them in this 'one at a time' fashion even though the expressions will not fit in core. Operations involving only single terms of larger polynomials arise naturally in these problems. Replacements wherein the sought expression is not a single term require very time-consuming multiple scans of expressions. We do without these. Differentiation is also performed on single terms. Integration can often be performed term by term. An exception occurs when recognition of a polynomial 'integrating factor' can greatly facilitate an integration. Aside from the simple distributive rule, all commonly used Dirac matrix and Lorentz 4-vector operations are also performed only on products of simple factors. The utility of the 'one term at a time' approach rests both upon a recurring feature of these calculations and upon a disparity between the numbers of terms which time allows us to process and which space allows us to store. (In less than 1 minute we can process more terms than will fit in memory.) Consider an initial polynomial PF the operation @12 which takes it into polynomial P2 and the operation @23 which takes that into polynomial P3" Often, P1 readily fits in the machine, P2 exceeds its capacity yet P5 once again fits. Especially if P$ is subject to little simplification by collecting like terms, we profit by never having all of P2 exist at any one time. Situations of this kind occur over and over again in these calculations. This storage problem for P2 may be completely avoided. We simply take one term of Pl, perform 012 upon it to get ~2' a part of P2' and immedlately perform 023 on that to produce part of P3" Before taking the-fiext term from Pl, we destroy the part of P2 which we have created but no longer need. In this way P2 becomes virtual: it never exists in its entirety at one time. We carry this scheme to its extreme by making even v2 virtual if it contains more than a single term. Thus at a given instant, the immediate input to a routine is kept to a single term. Its output is kept to a single term and whatever information it needs to resume work at a later time. The list of operations to be performed is the 'control stack' There is also the list containing the current input terms and the 'impure data' needed for resuming processing. These two structures are cross linked and the latter changes, dynamically, as the processing continues. The operations in a control stack are not executed as they are extracted from the input character stream. Recognition of one of the commands which can initiate a control stack causes ASHMEDAI to start queuing commands for this stack. Such a command must produce one term at a time from some data structure. Subsequent requests for substitutions or other 'one term at a time' operations are included in the growing control stack. Recognition of a command to collect like terms or somehow dispose of terms causes ASHMEDAI to terminate the control stack. Then the stack is 'executed'. Terms start flowing from the initial to the final real expressions through the worker routines in 'one at a time' fashion. This continues until the final real expression is complete. The temporary storage possibly including the input expression, some identities and the control stack is relinquished and commands are again taken from the input character stream. Most calculations require many different control stacks for their completion. Although this mode of operation places a load upon the user, we know of no reasonable alternative. Some intermediate expressions are too large for storage and must remain virtual. Some collapse very little when like terms are collected. For these, even though they may fit in storage, the time spent collecting like terms would be wasted. They, too, should remain virtual. However, when an intermediate expression is not prohibitively large and when it will collapse appreciably, one should collect like terms and create a real expression. Unfortunately, it is usually not clear ahead of time when to use each approach. As a result ASHMEDAI leaves it up to the user. He must then decide by understanding the structure of the problem or by trial and error. Since we often find it necessary to collect terms on expressions which would vastly exceed our core memory, ASHMEDAI does this operation using the combination of a very efficient comparing algorithm and about half a million words of drum storage. The job of the comparing algorithm is to take each term as it is produced in the 'one at a time' fashion and to compare it with the terms it has already collected in core. If the new term is like one already in the collection, their coefficients are added. If the new term has no counterpart in the collection, it is appended to the collection. If there is no room in memory for this new term, the collection is declared closed and the new term is written out on drum. Once the collection in core is declared closed, no new terms are appended to it even though more core may later become available. If another incoming new term is like one already in core, the coefficients are added. If not, the new term is written out on drum, but no comparison with other terms on the drum is made. In that way we are sure that the terms in core and those on the drum form mutually exclusive sets. The collection is maintained as a set of balanced binary trees. Each node of the trees contains a term of the expression and may contain left and right links to subtrees. All terms are in a canonical form and they are ordered within the trees. Scanning the collection to find a given term is then done using a binary search. Because we are interested in cases where the number of different terms is much less than the total number of searches, we need not worry about the time required to build and balance the trees. Once all terms to be produced by the current control stack of commands have either been added to the collection or saved on drum, the collection in core is linearized and written to another part of the drum. Then a new control stack is created which takes the uncollected terms on drum and tries once more to collect them. This pass begins with an empty collection in core. Once more, if the collection is finally closed, overflow terms are written back on the drum. This process continues until there is no more overflow and the final collection has been written on the drum. At this time the overflow area is empty and a new control stack can be created in response to user commands. This control stack will take terms from the collections on the drum. Since we only want one term at a time and we do not care about their order, the linear storage of the drum is quite satisfactory. You do have to pay the price of multiple attempts to collect some terms. Still greater speed could probably be attained by using a hash-search and by double buffering the drum I/O. However, we are now able to do the collection of like terms on expressions with many hundreds of thousands of terms before collecting and many tens of thousands of terms after collection. By simply setting some operating modes, a user can substitute tapes for the drum areas. This effectively removes any storage limitation on the size of expressions. One of the noteworthy special features which we developed for our problem is the integration package. 4 It expects input, in the form of transcendentals times rationals, in fully partialfractioned form. It must be given a list of possible linear or quadratic factors which may appear in denominators and a list of transcendentals, their derivatives and a few terms of their expansions around the end points of the integration region {if the rational factors can become singular there). The main technique is integration by parts. If the rational factor is not a single denominator factor, it integrates by parts and for our class of functions this reduces the degree of the transcendentals by I. If this introduces new denominators the result is first partial fractioned and then sent to the integrator again. Integrands with single denominator factors are done by explicit substitution. These generally increase the degree of the transcendental. This simple technique is very powerful. In our case, our final integral consists of trilogarithms, dilogarithms, logarithms, polynomials and rational factors of the form i/x, i/(l-x), i/(l+x), i/(l-x+x 2) to be integrated from 0 to i. Our program evaluates integrals consisting of 1000 such terms in about 2 minutes. Besides the virtue of speed, this program is easily extended to include more transcendentals or rational functions, and the new additions are easily checked numerically. In the realm of conjecture parallel processing is a very promising approach for algebraic work organized in this way. In particular the multi-mini processor configuration with many small, simple processors sharing a core area should greatly speed up execution. Because very little use is made of non-indexing arithmetic operations, the lack of fast floating point and double precision arithmetic operations is not important. The 'one at a time' processing scheme allows many processors to share a common control stack, but each one could completely process a different term of the input expression, including threading its separate way down shared trees in collecting terms. The amounts of 'impure storage' generated while processing terms is generally negligible, so that multiplying this by the number of processors puts no strain on the system. When finished, the processor could return to pick up another term of the input expression. We feel that no other existing algebraic program meets the requirements for our calculation. Others may be too inefficient in time or storage management, or they may be too inaccessible or too inflexible. We hope to have convinced you that ASHMEDAI is a very useful program. Extract: Improvements But it can be improved. The program has been developed and used by physicists. For us physicists, the problems which the system can attack are more important than the system itself. We have often added new features to get us through a particular bottleneck. After that problem is solved, instead of going back to polish the new feature, we press on to another calculation. As fast as the program may be, no effort has been put into general timing checks or into algorithm optimization. We have used whatever seemed to be a good idea unless forced by the problem to do better. So the program might benefit from some face-lifting. For example, since the program was designed primarily for batch, there is no recovery from syntax errors in the interactive mode although this is easy to implement. The user interface can be markedly improved. The user's guide needs to be more systematic. Certain commonly used constructions ought to have simple mnemonics to call them. Some awkward user commands should be streamlined. This is like a traditional packaging problem in marketing. The contents are worthwhile, but what meets the consumer's eye is very important. We do not have the time or the training for this job. Perhaps one of you will take up the challenge. The result would be a powerful system which was also more attractive and easy to use. in Proceedings of the Third ACM symposium on Symbolic and algebraic computation, August 10-12, 1976, Yorktown Heights, New York, United States view details in [ACM] CACM 28(04) (April 1985) view details |