The TAMPR Program Transformation System: Simplifying the Development of Numerical Software
by J. M. Boyle, T. J. Harmer and V. L. Winter
In E. Arge, A.M. Bruaset and H.P. Langtangen (eds.)
Modern Software Tools in Scientific Computing pp 353-372, Birkhäuser, 1997
Summary
TAMPR stands for
Transformation Assisted Multiple Program Realisation System. The
TAMPR system, which has been in use since the seventies, is designed for the derivation of efficient
implementations from a specification through transformations,
in particular in the domain of numerical programming.
A
TAMPR specification consists of a series of rewrite
rules. The
TAMPR rewrite engine applies rewrite rules
exhaustively to reach a canonical form. The problem of
non-termination caused by rules that are each others inverses is solved in
TAMPR by organizing a large transformation into a sequence of
consecutive canonicalizations under different sets of rewrite
rules. Typically such a sequence starts with several
preparatory steps that bring the program in the right form,
followed by the pivotal step which achieves the actual
transformation, followed by some post-processing.
In the paper this is illustrated with the transformation
from a polynomial in
y:
(x^2 + 2x + 1)y^2 + (x^2 - 9)y - (20x^2 + 18x - 18)
to the equivalent polynomial in
x
(y^2 + y - 20)x^2 + (2y^2 - 18)x + (y^2 - 9y + 18)
This is achieved by means of the following pipeline of
canonicalizations:
sum-of-monomonials;
x-commuted-to-right;
like-powers-collected;
x-factored-out
(Note that the paper uses a different notation for this.)
The
sum-of-monomonials transforms the polynomial into
x^2y^2 + 2xy^2 + y^2 + x^2y -9y -20x^2 - 18x + 18
By commuting the multiplications, the
x-commuted-to-right
canonical form is achieved:
y^2x^2 + 2y^2x + y^2 + yx^2 -9y -20x^2 - 18x + 18
The
like-powers-collected canonical form commutes
the additions to bring monomonials with the same power of $x$
together:
y^2x^2 + yx^2 - 20x^2 + 2y^2x - 18x + y^2 -9y + 18
Finally, by factoring out the powers of
x, the desired form is
reached.
EelcoVisser - 07 May 2001
CategoryReview,
CategoryTransformation | Contributions by
EelcoVisser