Call-by-Name Specialization of Functional Logic Programs


María Alpuente, Moreno Falaschi, Pascual Julián and Germán Vidal


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.


Integration of functional and logic programming, term rewriting systems, lazy narrowing, partial evaluation.