Proc. of JICSLP'96 Post-Conference Workshop on Multi-Paradigm Logic Programming (MPLP'96), TU Berlin, 1996
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.
Available: PDF BibTeX-Entry