|
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,
I-43100 Parma
- Title
-
Measuring the Effectiveness of Narrowing-Driven 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 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.]
|