
CS Seminar: Elvira Albert, February 27, 2002
 Speaker

Prof. Elvira Albert,
DSIC,
Technical University of Valencia
 Date and Time

Wednesday, February 27, 2002 at 15:00
 Place

Aula 1,
Dipartimento di Matematica,
Università di Parma,
Via D'Azeglio 85/A,
I43100 Parma
 Title

Measuring the Effectiveness of NarrowingDriven Specialization
 Abstract

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 machineindependent 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.]
