Partial Evaluation of Multi-Paradigm Declarative Languages: Foundations,
Control, Algorithms and Efficiency
Partial evaluation is an automatic technique for program optimization which
preserves program semantics. Optimization is achieved by specializing programs
w.r.t. parts of their input (hence also called program specialization).
This technique has been investigated in the context of a wide variety of
declarative programming languages, specially in both the functional and
logic programming paradigms.
Recently, a unified framework for the partial evaluation of languages
which integrate features from functional and logic programming has been
introduced. This framework is based on the use of narrowing (the
standard operational mechanism of functional logic languages) to drive
the specialization process. However, the narrowing-driven method
is not still suitable for designing an effective partial evaluator for
a realistic multi-paradigm language like Curry,
or Toy, as there are many language
features which are not considered in this framework. In this thesis, we
develop some methods and techniques which make feasible the definition
of effective partial evaluators for these languages. In short, the main
contributions of the thesis are:
Parts of this work have been previously presented in SAS'1998,
The definition of a partial evaluation framework for residuating
functional logic programs, which generalize logic programs based on concurrent
computation models with dynamic scheduling to functional logic programs.
The formulation of effective control issues to handle primitive
function symbols (e.g., the sequential conjunction and disjunction, the
strict equality, if-then-else constructs, etc.) in functional logic languages.
The use of an abstract representation for programs (into which higher-level
programs can be automatically translated). This allows us to define a simple
and concise method for program specialization that covers all the features
of modern multi-paradigm declarative languages.
The development of a partial evaluator for Curry programs written in Curry
itself, which is the first purely declarative partial evaluator for a real
The effectiveness of our partial evaluation method is also crucial for
promoting the wide use of our technology. Therefore, we have also defined
a formal framework which helps us to assess the gain in efficiency due
to the partial evaluation process.