A Cost-Augmented Partial Evaluator
for the Multi-Paradigm Declarative Language Curry

(Version v1.3 of 01/06/2004)

This is an extension of the
partial evaluator
for the multi-paradigm language
Curry.
It has been implemented in Curry itself.
The original narrowing-driven
partial evaluator has been enhanced with the computation of
symbolic costs. They are "symbolic" in the
sense that they measure the number of *basic* operations
performed during a computation rather than actual execution
times. We also incorporate a simple speedup analysis
which allows us to determine the global improvement achieved by
the specialization process.

The enhanced specializer is able to deal with programs containing local declarations, higher-order functions, and several built-in functions. The system considers programs written in Curry and translates them to an intermediate language, FlatCurry, in order to specialize them. This is essential to express the above language features at an appropriate level of abstraction. In this way, the resulting tool can be used to specialize "real" Curry programs.

Let us consider a simple example to illustrate the behavior of the developed tool. Consider the well-known benchmark "all_ones" (a typical example for deforestation techniques):

allones x = case x of { Z -> [] ; (S y) -> 1 : allones y } length x = case x of { [] -> Z ; (y:ys) -> S (length ys) }The partial evaluation of this program w.r.t. the initial call

allones (length x)returns the following residual program:

allones_pe x = case x of { [] -> [] ; (y:ys) -> 1 : allones_pe ys }which is clearly more efficient than the original one. Here, "

Original: Alt (Cost 2 2 1 0 1) (Cost 2 2 8 0 1) Residual: Alt (Cost 1 1 1 0 1) (Cost 1 1 6 0 1)where the "

Thus, for each recursive call of the residual function
"`allones_pe`" we perform: one function unfolding, one case
evaluation, 6 applications, and one non-deterministic branching, while
the equivalent computation in the original program requires: two
function unfoldings, two case evaluations, 8 applications, and one
non-deterministic branching.

Apart from its ability to perform deforestation, a powerful optimization achieved by the partial evaluator is the transformation of higher-order functions into first-order functions. This reduces the execution time and space requirements w.r.t. existing implementations. Let us consider, for instance, the following (higher-order) program:

map f xs = case xs of { [] -> [] ; (y:ys) -> apply f y : map f ys } foldr f z xs = case xs of { [] -> z ; (y:ys) -> apply (apply f y) (foldr f z ys) }implementing the usual higher-order functions "

foldr_pe xs = case xs of { [] -> 0 ; (y:ys) -> (y + 1) + foldr_pe ys }with associated costs:

Original: Alt (Cost 2 2 1 0 1) (Cost 3 2 11 3 1) Residual: Alt (Cost 1 1 1 0 1) (Cost 1 1 8 0 1)where "

A complete description of cost-augmented narrowing-driven specialization can be found in [Vid04].

The source files of the enhanced partial evaluator are in
pevalcost.tar.gz.
It contains `pevalcost.curry`, a modified file from the PAKCS
library, `Flat.curry`, which should be in the same directory as
`pevalcost.curry`, a reduced version of the Curry prelude,
`xprelude.curry`, and a number of (annotated) examples.
PAKCS version 1.6.0 is required.
As in the original partial evaluator, expressions to be partially evaluated
must be marked in the source program by `(PEVAL ...)`, where
"`PEVAL`" is the identity function (defined in the standard prelude).
For instance, you can load in the enhanced partial evaluator as follows:

prelude> :l pevalcostThen, to partially evaluate the above example "

pevalcost> main "allones"where

pevalcost> Cost-Augmented Partial Evaluator for Curry (v1.3 - 01/06/2004) (TU Valencia) Annotated expressions to be partially evaluated: allones (length x) Starting pevalcost for program "allones"... Independent Renaming: allones (length x) -> allones_pe0 x Case (length x) of (Z -> [] (S y) -> 1 : allones_allones y -> case_pe1 x Specialized Program: allones_pe0 x = case_pe1 x Original: (Cost 1 0 0 0 0) Residual: (Cost 1 0 0 0 0) case_pe1 x = Case x of [] -> [] (y:ys) -> 1 : allones_pe0 ys Original: (Alt (Cost 1 2 1 0 1) (Cost 1 2 8 0 1) ) Residual: (Alt (Cost 1 1 1 0 1) (Cost 1 1 6 0 1) ) After Post-unfolding: allones_pe0 x = Case x of [] -> [] (y:ys) -> 1: allones_pe0 ys Original: (Alt (Cost 2 2 1 0 1) (Cost 2 2 8 0 1) ) Residual: (Alt (Cost 1 1 1 0 1) (Cost 1 1 6 0 1) ) Speedup Analysis: Loop1(orig): (Cost 2 2 8 0 1) (spec): (Cost 1 1 6 0 1) Writing specialized program into "allones_pe.flc"...

Please report any bug or comment to gvidal@dsic.upv.es.

MIST | ELP | GPLIS | DSIC | UPV |

Last update June 2004 # gvidal (at) dsic (dot) upv (dot) es