 Home Page

Web

Wiki

# The TAMPRProgram Transformation System

Program-Transformation.Org: The Program Transformation Wiki
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