Polyvariant Expansion and Compiler Generators

Polyvariant expansion is a binding-time-improving transformation for offline partial evaluation. We show how to achieve it automatically for a higher-order functional language using the interpretive approach. We have designed and implemented an interpreter that statically propagates binding times. When specialized with respect to a source program, it performs polyvariant expansion. Extending the interpreter to an online specializer allows us to generate a binding-time-polyvariant compiler generator. Maintaining the binding times affords an abstract interpretation equivalent to a constraint-based binding-time analysis