Partial Evaluation using Rewrite Rules -- A Specification Of Partial . . .

Partial evaluation, or program specialization, is used when a variable is known to often hold one particular value. In that case, it is possible to specialize a program for that value, so the program performs better when the variable indeed has that value, as computations depending only on that variable(s) are already done. Rewrite rules provide a good mechanism for expressing program transformations. As partial evaluation is an example of a program transformation, rewrite rules should provide a good mechanism for partial evaluation. Similix is a self-applicable partial evaluator for a large higher order subset of the strict functional language Scheme, a lisp-like language. Stratego is a programming language that provides us with rewrite rules which can be combined using rewriting strategies. An approach to an implementation of the process of partial evaluation as it is done by Similix 5.0, using the rewrite rules provided by Stratego is given. The rewrite rules and strategies provided by Stratego prove to be a nice way to express partial evaluation. All phases a program has to pass to attain a partial evaluated version of the program can be split up in simple rewriting steps, which are combined in a neatly arranged manner by the rewriting strategies. The Stratego program stays clearly structured, as no complicated rules have to be used to do partial evaluation, and the strategies used to combine the rules can be set up in a logical way