Partial Evaluation of Multi-Paradigm Declarative Languages: Foundations, Control, Algorithms and Efficiency

Abstract

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, Escher 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:

• 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 multi-paradigm language.
• 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.