# Safe Folding/Unfolding with Conditional Narrowing

### Author

María Alpuente, Moreno Falaschi, Ginés Moreno, and Germán
Vidal
### Abstract

Functional logic languages with a complete operational semantics are based on
narrowing, a generalization of term rewriting where unification
replaces matching. In this paper, we study the semantic properties of a general
transformation technique called *unfolding* in the context of functional
logic languages. Unfolding a program is defined as the application of narrowing
steps to the calls in the program rules in some appropriate form. We show that,
unlike the case of pure logic or pure functional programs, where unfolding is
correct w.r.t. practically all available semantics, unrestricted unfolding using
narrowing does not preserve program meaning, even when we consider the weakest
notion of semantics the program can be given. We single out the conditions which
guarantee that an equivalent program w.r.t. the semantics of computed answers
is produced. Then, we study the combination of this technique with a
*folding* transformation rule in the case of innermost conditional
narrowing, and prove that the resulting transformation still preserves the
computed answer semantics of the initial program, under the usual conditions for
the completeness of innermost conditional narrowing. We also discuss a
relationship between unfold/fold transformations and partial evaluation of
functional logic programs.
### Keywords

integration of functional and logic programming, narrowing,
partial evaluation, term rewriting systems, program transformation.