Extending the Power of Automatic Constraint-based Partial Evaluators

In the control of automatic program specialisers, there has always been a tradeoff between precision and termination. What is necessary to extend the power of automatic partial evaluation? We compare two frameworks for partial evaluation: constraint-based partial evaluation, and generalized partial computation. Both techniques incorporate advanced information propagation. Using theorem proving, generalized partial computation achieves greater specialisation than constraint-based partial evaluation, but the constraint-based approach has a dened procedure for control of the algorithm. We examine the differences between the two techniques, in light of a particularly difcult specialisation problem, McCarthy's 91-function, and identify features which may lead to the eventual development of a powerful, automatic partial evaluator. Categories and Subject Descriptors: I.2.2 [Articial Intelligence]: Program Transformation.