poly-controlled partial evaluation in practice
Poly-Controlled Partial Evaluation (PCPE) is a powerful approach to partial evaluation, which has recently been proposed. PCPE takes into account sets of control strategies instead of a single one. Thus, different control strategies can be assigned to different call patterns, possibly obtaining results that cannot be obtained using a single control strategy. PCPE can be implemented as a search-based algorithm, producing sets of candidate optimized programs. The quality of each of these programs is assessed through the use of a fitness function, which can be resource aware , in the sense that it can take multiple factors into account, such as run-time and code size. Unfortunately, PCPE suffers from an inherent blowup of its search space when implemented as an all-solutions, search-based algorithm. Thus, in order to use it in practice we must be able to prune its search space without losing the (most) interesting solutions. In this work we explore several techniques for pruning the search space of PCPE. Some of these techniques are based on heuristics, while others are based on branch and bound and are guaranteed to obtain an optimal solution. Our experimental results show that, when combined with the proposed pruning techniques, PCPE can cope with realistic programs. Also, that the solutions obtained by PCPE outperform the solutions found by PE under similar conditions.
partial evaluation resource-aware specialization logic programming