CONTROLLING PARITAL EVALUATORS USING FUNCTIONAL PARAMETERS BY

Partial evaluation is a source to source program transformation that makes use of symbolic interpre-tation to perform aggresive constant propagation. Most partial evaluators are written as monolithic programs that operate on their terms directly by recursing over the structure of the expressions. Several partial evaluators and code generators have been published that do not process their terms directly; instead, the partial evaluator is inlined into the program to be specialized via a source to source translation. This technique has resulted in some evaluators with interesting properties, such as a very small size and the ability to self-apply in the online case. A weakness of these partial evaluators is that they lack a mechanism to control the specialization process, and as a result explode on inputs that more standard oine partial evaluators are able to handle. We propose the addition of a control mechanism called a strategy, a function that advises the partial evaluator about whether to perform a reduction. Like traditional methods such as binding time analysis, strategies can prevent combinatorial explosion by instructing the partial evaluator to residulaize at appropriate times. They also allow us to make tradeo®s, such as partial evaluation speed versus the size of the result. Strategies are a way of abstracting control, an