## An Automatic Composition Algorithm for Functional Logic Programs

**María Alpuente, Moreno Falaschi, Ginés Moreno
and Germán Vidal**
© Springer-Verlag

*Proc. of the 27th Annual Conference on Current Trends in Theory
and Practice of Informatics (SOFSEM'2000).*
Springer LNCS 1963,
pp. 289-297, 2000

Functional logic languages with a complete operational semantics
are based on narrowing, which combines the instantiation of
variables with the reduction of expressions.
In this paper, we investigate the relationship between
partial evaluation and more general transformations
based on folding/unfolding.
First, we show that the transformations obtained by partial
evaluators can be also achieved
by folding/unfolding using a particular kind of eurekas
which can be mechanically attained. Then, we propose an
algorithm (based on folding/unfolding) which starts with the
automatic eureka generation and is able to perform program composition, i.e.,
it is able to produce a single function definition
for some nested functions of the original program.
This avoids
the construction of intermediate data structures that are produced
by the inner function and consumed as inputs
by the outer function.
As opposed to both partial evaluation and (general) fold/unfold
transformations,
strong correctness of the transformed programs holds
w.r.t. goals which contain calls to
the "old" function symbols (i.e., from the original program)
as well as to the "new" ones (i.e., introduced during the
transformation).

Available:
PS
BibTeX-Entry

Germán Vidal