CS Seminar: Elvira Albert, February 27, 2002

Prof. Elvira Albert,
DSIC, Technical University of Valencia

Date and Time
Wednesday, February 27, 2002 at 15:00
Aula 1,
Dipartimento di Matematica, Università di Parma, Via D'Azeglio 85/A, I-43100 Parma

Measuring the Effectiveness of Narrowing-Driven Specialization

A common motivation of all partial evaluation techniques is to improve the efficiency of a program while preserving its meaning. Rather surprisingly, relatively little attention has been paid to the development of formal methods for reasoning about the effectiveness of this program transformation; usually, only experimental tests on particular languages and compilers are undertaken. Clearly, a machine-independent way of measuring the effectiveness of partial evaluation would be useful to both users and developers of partial evaluators.

In this talk, we present 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. Therefore, 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.

The cost associated to each criterion is expressed 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.

Contact Person
Roberto Bagnara

[Page last updated on February 26, 2002, 17:54:13.]

Page maintained by
Enea Zaffanella

Home | People | Projects | Publications | Seminars | Software | Links