Refined Definitional Trees and Prolog Implementations of Narrowing

Abstract. This paper describes how high level implementations of (needed) narrowing into Prolog can be improved by introducing a refined representation of definitional trees that handles properly the knowledge about the inductive positions of a pattern. We define some generic algorithms that allow us to transform a functional logic program into a set of Prolog clauses which incorporates some refinements that are obtained by ad hoc artifices in other similar implementations of functional logic languages. We also present and discuss the advantages of our proposal by means of some simple examples