Unfolding-Definition-Folding, in this order, for Avoiding Unnecessary Variables in Logic Programs

We present an approach to the automatic improvement of performances of logic programs by using the unfold/fold transformation technique. A cause of program inefficiency is often the presence of variables which are unnecessary, in the sense that they force computations of redundant values or multiple visits of data structures. We propose a strategy which automatically transforms initial program versions into new and more efficient versions by avoiding unnecessary variables. Our strategy is an extension of the one which was introduced in an earlier paper by Proietti-Pettorossi (1990). It is based on the syntactical characterization of the unnecessary variables and it uses a composite transformation rule made out of unfolding-definition-folding steps, in this order. The strategy consists in the repeated application of that composite rule to each clause with unnecessary variables. It avoids the search for eureka definitions which is often required by other techniques proposed in the literature. We define a class of programs for which our transformation strategy is successful and we propose a variant of that strategy which uses the so-called generalization rule. This variant is always terminating, but, in general, not all unnecessary variables are eliminated. We finally present an enhancement of the proposed transformation techniques which exploits the functionality of some predicates.