Simplification-Driven Automated Partial Evaluation
J.M. Boyle · University of North Texas Digital Library (University of North Texas) · 1992
I describe an automated approach to partial evaluation based on simplification and implemented by program transformations. The approach emphasizes program algebra and relies on canonical forms and distributive laws to expose instances to which simplifications can be applied. I discuss some of the considerations that led to the design of this approach. This design discussion should be useful both in understanding the structure of the partial evaluation transformations, and as an example of how to approach the design of automated program transformations in general. This approach to partial evaluation has been applied to a number of practical examples of moderate complexity, including: the running example used in this paper, proving an identity for lists, and eliminating a virtual data structure from a specification of practical interest. The chief practical barrier to its wider application is the growth of the intermediate program text during partial evaluation. Despite this limitation, this approach has the virtues of being implemented, automated, and able to partially evaluate specifications containing implicit data, including some specifications of practical interest.