## Measuring the Effectiveness of Partial Evaluation

**Elvira Albert, Sergio Antoy and Germán Vidal**
*Proc. of the 10th Int'l Workshop on Logic-based Program
Synthesis and Transformation (LOPSTR'2000).*
Technical Report UMCS-00-6-1,
University of Manchester, pp. 72-79, 2000

We introduce a framework for assessing the effectiveness of
partial evaluators for functional logic programs.
Our framework is based on properties
of the rewrite system that models a functional logic program
and, 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 effort for pattern
matching.
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 recurrence equations.

Available:
PS
BibTeX-Entry

Germán Vidal