Automatic Trasformation by Rewriting Techniques
Françoise Bellegarde · 1994
The paper shows how term rewriting techniques can be used to automatically transforms first-order functional programs by both deforestation (eliminating useless intermediate data structures) and tupling (eliminating parallel traversals of identical data structures). Its novelty is that it includes these strategies for program improvement in a transformation system which uses completion procedures to automatically control a unfold/fold methodology. This means that eureka for these strategies are automatically discovered and that they are processed by a completion procedure. The completion procedure is automatically constrained for orienting pairs into rules and for producing critical pairs. An interesting result is that the process preserves termination of the original set of rules, which is not guaranteed in general by a unfold/fold method.