International Conference on Logic Programming (ICLP'95), MIT Press, pp. 665-679, 1995
Extra variables in a clause are variables which occur in the body but not in the head. It has been argued that extra variables are necessary and contribute to the expressive power of logic languages. In the first part of this paper, we show that this is not true in general. For this purpose, we provide a simple syntactic transformation of each logic program into a logic program without extra variables, and we show a strong correspondence between the original and the transformed program. In the second and main part of this paper, we use a similar technique to provide new completeness results for equational logic programs with extra variables. In equational logic programming it is well known that extra variables cause problems since narrowing, the standard operational semantics for equational logic programming, may become incomplete in the presence of extra variables. Using a simple syntactic transformation, we derive a number of new completeness results for narrowing. In particular, we show the completeness of narrowing strategies in the presence of nonterminating functions and extra variables in right-hand sides of rewrite rules. Using these results, current functional logic languages can be extended in a practically useful way.
Preprint (PDF) BibTeX-Entry