Consider the following example:
When examining this example it is clear that the entries are of two different kinds: some are numbers and one is a parameter. The value of this expression is:
and this can be obtained easily by hand. When computing the rank of the matrix, the question a=1 appears. Obviously, if one does not know whether a is equal to 1, both results are possible, and if one computes using both possibilities, one gets the right answer.
This, however, is not what one gets using a computer algebra system; there, the usual answer is simply ``2''. Computer algebra systems will normally provide only one result, possibly querying the user or selecting the ``more general'' branch during the course of the computation. This can lead to problems when the conditions under which the branch is valid are not recorded. For example, related questions can arise during the course of a computation, and there is no guarantee that the results of querying the user or automatically selecting branches will be consistent. Even when the choices are consistent, the conditions for validity are not presented as part of the answer in available algebra systems.
A proposal has existed for some time in the Maple community to return this list of conditions via a variable, the ``proviso'' [CJ], and an experimental version of Maple's "solve" command has been created to test these ideas [La].
The second difficulty is to obtain a complete solution covering all cases of a general mathematical problem. There do exist packages for particular algorithms which return results covering different cases (as for example [Si]). The next step is to understand how to use such packages together, composing the results of sub-problems. This is not straight-forward, since the course of an algorithm will likely vary depending on the conditions placed on the different cases. One does not wish to obscure the intent of every function in an algebra system with back-tracking logic. Even if one were willing to accept this, it would be necessary to modify all of the code in the entire system.
Dynamic evaluation addresses this problem and gives a method of proceeding when there are many possibilities for the answer [DR]. It has been implemented on the computer algebra system Axiom Version 1 [JS] and has been applied first in computations involving algebraic numbers [DDD, DD, Du], which are considered as a special kind of parameter. Dynamic evaluation is intrinsically parallel, but in earlier implementations the parallelism is only simulated, and some parts of the computation are performed many times. This redundant computation was unavoidable in the Axiom system, as it provides no mechanism for restarting a computation at a point in the middle of a program.
A possible way of avoiding redundant computation is to use
continuations [R4R]. Continuations provide a mechanism for
marking a point in a computation (in the middle of an equality in our
example) and to return to this point as many times as desired. This
allows the back-tracking primitive that dynamic evaluation needs. The
question now is how to use continuations from within a computer
algebra system. This has been made possible by the new Axiom compiler,
called A 
.
In this paper we describe dynamic evaluation and its utilisation in
some computations involving parameters.
We describe how continuations may be used to avoid redundant
computation in the dynamic evaluation of a program, and how
continuations may be used from within the Axiom Version 2
system. Section 2 describes the form of the domains over which dynamic
evaluation can be made. This section then goes on to describe the
splitting trees which can be used to represent a particular
computation over these domains. This section then gives a more
extended example of such a tree. Section 3 describes the
implementations of dynamic evaluation, and describes the interface to
A .