Algebraic Evaluation

The evaluation of expressions is the heart of REDUCE. Because of its great complexity, it is only briefly touched on here. One central problem in automatic formula manipulation is the detection of identity between objects, e.g. the confirmation a + b = b + a under the assumption of commutative addition.

It is well known that this problem is equivalent to the problem of recognizing that an expression is zero, in other words to the existence of an algorithm for the transformation of a formula into an equivalent canonical normal form. Unfortunately there is no universal canonical form; only for subcases, for example polynomials, rationals, and ideals, are canonical forms known. Therefore REDUCE evaluation is based on a canonical form for rational functions (i.e., quotients of multivariate polynomials), where symbols or function expressions play the role of variables (REDUCE: kernels). REDUCE attempts to tranform as many functions as possible into the canonical form by applying additional heuristic rules.

A coarse sketch of evaluation is as follows:

• a symbol with an assigned value is replaced by the value,
• a call for a known procedure is replaced by the value produced by the procedure invocation,
• matching rules are applied,
• polynomials are expanded recursively using a lexicographic order of variables (kernels): a multivariate polynomial is a polynomial in its highest variable with decreasing exponents, where the coefficients are polynomials in the remaining variables,
• a rational function is converted into a form with common denominator (i.e., a quotient of two polynomials).

This is, of course, a highly recursive process, which is applied until no more transformations are possible.