Specialization of Functional Logic Programs Based on Needed Narrowing
María Alpuente, Michael Hanus, Salvador Lucas, Germán Vidal
Functional logic languages 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. Needed narrowing is an optimal narrowing strategy
and the basis of several recent functional logic languages. In
this paper, we define a partial evaluator for functional logic
programs based on needed narrowing. We prove strong correctness
of this partial evaluator and show that the nice properties
of needed narrowing carry over to the specialization process
and the specialized programs. In particular, the structure
of the specialized programs provides for the application of
optimal evaluation strategies. This is in contrast to other
partial evaluation methods for functional logic programs which
can change the original program structure in a negative way.
Finally, we present some experiments which highlight the
practical advantages of our approach.