Specialization of Lazy 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 pure functional programs
uses mainly 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. We discuss these issues in the context of a
(lazy) functional logic language. We formalize a two-phase specialization
method for a non-strict integrated language which makes use of 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.
This phase is essential also for other non-lazy narrowing strategies,
like innermost narrowing, and our method can be easily extended to these
strategies. We show that our method preserves the lazy narrowing semantics
and that the inclusion of simplification steps in narrowing derivations can
improve control during specialization.
Keywords
Integration of functional and logic programming, term rewriting systems,
lazy narrowing, partial evaluation, post-processing transformation.