Cost-Augmented Partial Evaluation of Functional Logic Programs

Germán Vidal

© Kluwer Academic Press
Higher-Order and Symbolic Computation (formerly Lisp and Symbolic Computation), Volume 17(1-2), pp. 7-46, 2004.

We enhance the narrowing-driven partial evaluation scheme for lazy functional logic programs with the computation of symbolic costs. The enhanced scheme allows us to estimate the effects of the program transformer in a precise framework and, moreover, to quantify these effects. The considered costs are "symbolic" in the sense that they measure the number of basic operations performed during a computation rather than actual execution times. Our scheme may serve as a basis to develop speedup analyses and cost-guided transformers. A cost-augmented partial evaluator, which demonstrates the usefulness of our approach, has been implemented in the multi-paradigm language Curry.

Available: Pre-press version Accepted version (online article) BibTeX-Entry


Germán Vidal