Call-by-Name Specialization of Functional Logic Programs
Author
María Alpuente, Moreno Falaschi, Pascual Julián and
Germán Vidal
Abstract
Partial evaluation is a method for program specialization based
on fold/unfold transformations. Partial evaluation of functional programs
uses only static values of given data to specialize the program.
In logic programming, the so-called static/dynamic
distinction is hardly present, whereas considerations of determinacy
and choice points are far more important for control.
In this paper, we formalize a two-phase specialization method
for a non-strict functional logic language which makes
use of (normalizing) lazy narrowing to specialize the program w.r.t. a
goal. The basic algorithm (first phase) is formalized as an instance of the
framework for the partial evaluation of functional logic programs of
[AFV96-ESOP'96], using lazy narrowing. However, the results inherited by
[AFV96-ESOP'96] mainly regard the termination of the PE method, while the
(strong) soundness and completeness results must be restated for the lazy
strategy. A post-processing renaming scheme (second phase) for
obtaining independence is then described and illustrated on the well-known
matching example. We show that our method preserves the lazy narrowing
semantics and that the inclusion of simplification steps in
narrowing derivations can greatly improve control during specialization.
Keywords
Integration of functional and logic programming, term rewriting systems,
lazy narrowing, partial evaluation.