|
Partial Evaluation (PE) is an automatic transformation technique for program optimization. The idea is to specialize the original program w.r.t. parts of its input data.
Since declarative languages present clear semantical foundations, they offer advantages for the design of correct transformers. Functional logic languages allow us to integrate the best features of classical declarative languages. Recently, María Alpuente et. al. introduced a generic framework for the PE of functional logic languages. This method is based on the use of narrowing, an inference rule which combines the reduction principle of functional languages and the resolution principle of logic languages. In this thesis, we investigate the techniques and requisites to improve the narrowing driven PE method. Following this aim we introduce:
1) Improvements of the PE interpreter strategy. We define a PE algorithm based on lazy narrowing (an expressive and efficient evaluation strategy) and we prove its correctness. We identify the class of uniform programs as the one where it is possible to introduce a refinement of lazy narrowing strategy, namely uniform lazy narrowing, which remains complete over the class of uniform programs and it is computationally equivalent to needed narrowing (in the sense that they both compute the same results and answers). Finally, we prove that the instance of our PE framework based on uniform lazy narrowing is strongly correct. Also we show that the new instance of the partial evaluator has better performance that the original one (instantiated by the lazy narrowing strategy).
2) Advanced techniques of specialization. We improve the control mechanism of our generic algorithm of narrowing driven PE by introducing: (i) a well-balanced dynamic unfolding rule and (ii) a new abstraction operator using partitioning techniques. This novelties allow us to specialize programs w.r.t. complex expressions (i.e., expressions containing primitive function symbols) without any ad hoc artifice and preserving the termination of the PE process.
We obtain a PE method applicable to modern functional logic languages with a lazy narrowing operational semantics such as Babel, Curry and Toy, thus giving a specialization method which subsumes both lazy functional and conventional logic program specialization.