Civit: Hybrid Partial Evaluation

Amin Shali
William R. Cook

Hybrid partial evaluation (HPE) is a pragmatic approach to partial evaluation that borrows ideas from both online and offline partial evaluation. HPE performs offline-style specialization using an online approach without static binding time analysis. The goal of HPE is to provide a practical and predictable level of optimization for programmers, with an implementation strategy that fits well within existing compilers or interpreters. HPE requires the programmer to specify where partial evaluation should be applied. It provides no termination guarantee and reports errors in situations that violate simple binding time rules, or have incorrect use of side effects in compile-time code. We formalize HPE for a small imperative object-oriented language and describe Civet, a straightforward implementation of HPE as a relatively simple extension of a Java compiler. Code optimized by Civet performs as well as and in some cases better than the output of a state-of-the-art offline partial evaluator.

Hybrid Partial Evaluation
Amin Shali and William R. Cook
To appear, OOPSLA 2011

Also available background material:

Source of the formal semantics

Java file for Civet java compiler