Narrowing-driven Partial Evaluation of Functional Logic Programs
María Alpuente, Moreno Falaschi and Germán Vidal
Languages that integrate functional and logic programming
with a complete operational semantics
are based on narrowing, a
unification-based goal-solving mechanism which subsumes the reduction principle
of functional languages and the resolution principle of logic languages. Formal
methods of transformation of functional logic programs can be based on this
well-established operational semantics. In this paper, we present a partial
scheme for functional logic languages based on an automatic unfolding algorithm
which builds narrowing trees. We study the semantic properties of the
transformation and the conditions under which the technique
terminates, is sound and complete, and is also
generally applicable to a wide class of programs.
We illustrate our method with several examples and discuss the relation
with Supercompilation and Partial Evaluation.
To the best of our knowledge this is the first formal approach to
partial evaluation of functional logic programs.
integration of functional and logic programming, narrowing,
partial evaluation, term rewriting systems, equational unification.