SPECIALIZATION OF LAZY FUNCTIONAL LOGIC PROGRAMS

Partial evaluation is a method for program specialization based on fol d/unfold transformations [8, 25]. Partial evaluation of pure functiona l programs uses mainly static values of given data to specialize the p rogram [15, 44]. In logic programming, the so-called static/dynamic di stinction is hardly present, whereas considerations of determinacy and choice points are far more important for control [12]. We discuss the se issues in the context of a (lazy) functional logic language. We for malize a two-phase specialization method for a non-strict, first order , integrated language which makes use of lazy narrowing to specialize the program w.r.t. a goal. The basic algorithm (first phase) is formal ized as an instance of the framework for the partial evaluation of fun ctional logic programs of [2, 3], using lazy narrowing. However, the r esults inherited by [2, 3] mainly regard the termination of the PE met hod, while the (strong) soundness and completeness results must be res tated for the lazy strategy. A post-processing renaming scheme (second phase) is necessary which we describe and illustrate on the well-know n matching example. This phase is essential also for other non-lazy na rrowing strategies, like innermost narrowing, and our method can be ea sily extended to these strategies. We show that our method preserves t he lazy narrowing semantics and that the inclusion of simplification s teps in narrowing derivations can improve control during specializatio n.