@inproceedings{AlberAntoyVidal01LOPSTR,
  author = "Elvira Albert and Sergio Antoy and Germ\'an Vidal",
  title = "Measuring the Effectiveness of Partial Evaluation
          in Functional Logic Languages",
  booktitle = "Proc.\ of 10th Int'l Workshop on Logic-based Program
              Synthesis and Transformation (LOPSTR'2000)",
  publisher = "Springer LNCS 2042",
  pages = "103-124",
  year = 2001,
  abstract = {
    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.}
}