Parameterized partial evaluation principle and practice
Siau‐Cheng Khoo · 1993
Partial evaluation aims at specializing a program with respect to part of the input that is known. This process yields a new program which is a specialized version of the original program. This specialized program is expected to be more efficient than the original one. In practice, there are two apparently independent strategies of partial evaluation: on-line and off-line. An on-line partial evaluator processes a program in one single phase, whereas an off-line partial evaluator performs some analyses before specializing the program. Regardless of strategies used, most existing partial evaluators have the limitation that they only specialize program with respect to actual values. Specializing programs with respect to static properties about the input (such as signs, ranges, and types) is a natural extension of current partial evaluation and significantly contributes towards adapting partial evaluation to a larger variety of applications. Although work has been done in this direction, there has not been a formal treatment of this idea, and the systems developed thus far do not provide users with the capability of introducing static properties into the partial-evaluation process. This thesis introduces the notion of parameterized partial evaluation-- a generic form of partial evaluation parameterized with respect to user-defined static properties. This generality is accomplished by introducing an algebraic framework that enables modular definition of static properties and systematic incorporation of these properties into the partial-evaluation process. Consequently, new kinds of partial-evaluation applications become possible through the introduction of various static properties. Not only does the framework guarantee the safety of the partial-evaluation process with respect to the static properties introduced, but it also defines a formal relationship between on-line and off-line partial evaluation. Moreover, it enables us to prove the correctness of partial evaluation with polyvariant specialization (in which any function in a program can have more than one specialized version), which has not been done before. Finally, the effectiveness of parameterized partial evaluation is demonstrated through an implementation for a first-order strict functional language with data structures. Some applications are experimented to show the qualitative improvement of the residual programs produced using the parameterized partial evaluator.