Rewriting systems on FP expressions to reduce the number of sequences yielded (Q1819572)

We are concerned in transforming FP programs so as to minimize the number of intermediate sequences appearing in FP expressions that express iterative programs. Because FP expressions are often required to run on a Von Neumann machine, it would be useful to eliminate unnecessary intermediate sequences. We propose transformation rules based on the algebra of functional programs. In contrast with many others systems of rules for program transformation, the sets of rules presented here are convergent (i.e. finitely terminating and confluent). These rewriting systems are produced by the Knuth-Bendix procedure applied to an initial set of equations and correspond to equations that are valid in the algebra of functional programs. Essentially, the paper relates our experience in using REVE to process a large set of equations and show the actual limitations. Finally an outline of future research is proposed.