compiler are that
From a computer algebra perspective, the most interesting aspects
of the compiler are that
We put these developments in context to show why we have taken the present approach.
The first computer algebra software took the form of libraries, intended for use from Fortran or Lisp [5][10][11]. Shortly thereafter, special-purpose systems were introduced to allow computational input to be given in a more natural form. Some of these were programming languages backed by libraries [4][6], while others also provided an interactive programming environment [12][13]. These algebra systems were closed, in the sense that it was not readily possible to call code written in them from another programming language environment, such as Fortran, or vice versa.
The use of closed systems has predominated over the course of three decades, and the computer algebra software in use today is of this form [7][9][13][14][17][20][23][28]. It remains the case that it is not possible to call programs written in one of these systems from programs written in another. Nor is it possible to use general Fortran or C libraries without resorting to some relatively expensive communication scheme.
One consequence of this is that a great deal of effort is expended in reproducing the same programs in different computer algebra systems, or reproducing the function of other libraries within these systems. While there will always be cases where similar packages are developed independently to establish legal ownership for commercial development, it is regrettable that researchers must reproduce their programs in several different systems to make them available to their colleagues.
There have been a number of proposals to improve on this situation with structured data communication between processes [16][29][30]. This is only a partial solution, however, since IPC-based methods incur a significant communication overhead which can easily dominate the cost of O(n) problems.
Another partial solution has been to build special-purpose interfaces to particular libraries. While this is useful for the particular cases handled, it does not accomodate new or third party libraries as they become available.
The compiler presents an alternative approach to the problem:
sharing code.
libraries participate on an equal footing with other libraries
in the host environment.
Functions in libraries may call and be called by functions
in other libraries in the normal way and it is possible to
share data in forms required by other programs.
This makes it possible, for example, to use libraries for
numeric problem solving or scientific visualization.
This approach is standard practice in the larger world,
but has been abandoned for decades in mainstream computer algebra software.
This discrepancy is perhaps the result of at least two pressures:
users have come to appreciate the value of interactive
environments for computer algebra, and
the languages incorporated in computer algebra systems
have allowed programs to be written more conveniently than the alternatives.
With , however, a user may prototype an application within
an interactive environment, such as the Axiom system, or
with the Foam interpreter, and later generate code to be linked
with other applications.
Furthermore, it is not unreasonable to anticipate running the same
code in ``closed'' systems by taking the approach used
with Lisp: from Foam generating source code to load into Maple,
for example.
A second problem with closed systems is that certain computations will be much slower than they need to be. This arises because these systems are typically structured as a kernel, written in another programming language, and a library providing an assortment of additional functions. The operations coded directly in the kernel can be two or three orders of magnitude more efficient than the same operations written at the library level. It is not possible to know in advance what the efficiency-critical primitives will be for the complete spectrum of mathematics so key primitives for new application areas will likely be missing from the system kernel. These will have to be written at the library level, with the associated slow-down. A case in point is GAP [20], a system very similar to Maple, but with a focus on group theoretic computation. GAP was initially written because the necessary kernel-level efficiency for primitives in group computations could not be achieved by writing Maple library code.
The compiler addresses this issue by giving
the programmer the ability to develop optimized code for
whatever primitives are required.
In practice, these problems are not as severe in Lisp-based systems [13][14][23]. Users of Lisp-based algebra systems may make their own kernel extensions by writing and compiling Lisp code. If the underlying Lisp system supports it, an implementation-specific foreign function interface can provide a mechanism to access C or Fortran libraries.
This direction, however, has drawbacks: In practice, to use a foreign library from Lisp it is necessary to cover the foreign functions with wrappers to convert between the Lisp and the foreign data representations. This may involve copying on each call and return and introduces semantic difficulties when considering sharing of substructure and pointer equality. Next, the Lisp foreign function interface will have a fixed vocabulary of understood data transformations and will not usefully pass function values, file pointers, or other interesting composite objects. Finally, it is necessary to ensure that the values passed to foreign functions do not relocate (e.g. by garbage collection) during the course of execution, and any pointers captured by the foreign functions migth be invalid in subsequent calls. This makes it very difficult to write code to embed in non-Lisp applications, since the controlling side will retain state between call-backs. Because of these difficulties, Lisp foreign function interfaces do not promise a great improvement over IPC methods as a means of accessing libraries.
At this point, one might ask why not move to stand-alone programs based on a mathematical library for C++ [22] or some other programming language. Our response is two-fold: First, we felt that existing object systems were not capable of modelling the intricate relations among algebraic structures sufficiently naturally. Second, it is valuable to maintain a path of access to the existing computer algebra software base.