## Measuring the Effectiveness of Partial Evaluation in Functional
Logic Languages

**Elvira Albert, Sergio Antoy and Germán Vidal**
© Springer-Verlag

*Proc. of the 10th Int'l Workshop on Logic-based Program
Synthesis and Transformation (LOPSTR'2000).*
Springer LNCS 2042,
pp. 103-124, 2001

We introduce a framework for assessing the effectiveness of
partial evaluators in functional logic languages.
Our framework is based on properties
of the rewrite system that models a functional logic program.
Consequently, our assessment is independent of any specific
language implementation or computing environment.
We define several criteria for measuring the cost of a computation:
number of steps, number of function applications, and pattern
matching effort.
Most importantly, we express the cost of each criterion
by means of recurrence equations over algebraic data types,
which can be automatically
inferred from the partial evaluation process itself.
In some cases, the equations can be solved by transforming their
arguments from arbitrary data types to natural numbers.
In other cases, it is possible to estimate the improvement
of a partial evaluation by analyzing the associated cost
recurrence equations.

Available:
DVI
PS
BibTeX-Entry

Germán Vidal