WG211/M9Westbrook

Towards a Generalization of Specialization

Edwin Westbrook

Code specialization is a powerful technique for optimizing programs in general-purpose languages. Unfortunately, specialization faces many challenges when applied to domain-specific languages (DSLs). Automatic specialization (AS) techniques, such as partial evaluation and supercompilation, require monolithic implementations that are difficult to understand and modify, making it hard for domain experts - who often are not AS experts - to use them effectively and to add support for domain-specific optimizations. Existing techniques in manual specialization, that is, techniques that apply multi-stage programming (MSP), are often ad-hoc, making them difficult to apply to new domain-specific optimizations and difficult to prove correct.

In this talk, we describe ongoing work on a generalized theory of code specialization, called staging functors, which we believe can overcome these difficulties. A staging functor gives a disciplined way to transform dynamic code fragments into partially static data that captures semantic information about the code. Further, any valid staging functor is guaranteed to be correct. Staging functors can be given with a small set of rules that can then be applied automatically, thus yielding user-customizable AS. Staging functors can also be applied manually, giving a new, disciplined, provably correct approach technique for MSP. Finally, we believe staging functors can be used for many useful domain-specific optimizations. As an example, we show how load elimination, an optimization for pointer programs, can be implemented as a staging functor.