The TAMPRProgram Transformation System

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