Online partial evaluators are hardly ever self-applicable, because the
complexity of deciding whether to residualize terms causes a combinatorial
explosion when self-application is attempted. T. Mogensen (1995) has found a
way to write a self-applicable online partial evaluator for the
-calculus. His method is to regard every -term as having
both static and dynamic aspects; then, applications can always be done
statically (using the static aspect of the operator). However, the absence of
decision-making about residualization has a down-side: his partial evaluator
knows only how to fully reduce partially evaluated terms. The result is
considerable code explosion. We show how this problem can be overcome, in part,
by changing the type of the partial evaluator, and giving a new version of the
Futamura projections to correspond to that new type. Specifically, we have the
partial evaluator take a third argument, called a strategy, which “advises” the
partial evaluator whether to residualize. Strategies allow the programmer to
control the tradeoff between the size of a specialized term and the cost of
subsequently applying it. We present a number of strategies and examples of
each.
