Tag-free Combinators for Binding-Time Polymorphic Program Generation

Peter Thiemann and I have written a paper on (off-line) partial evaluation for polymorphic languages using GHC's advanced typing features.

The source code of the combinators is available here.

Here's the abstract:

Binding-time polymorphism enables a highly flexible binding-time analysis for offline partial evaluation. This work provides the tools to translate this flexibility into efficient program specialization in the context of a polymorphic language.

Following the cogen-combinator approach, a set of combinators is defined in Haskell that enables the straightforward transcription of a binding-time polymorphic annotated program into the corresponding program generator. The typing of the combinators mimics the constraints of the binding-time analysis. The resulting program generator is safe, tag-free, and it has no interpretive overhead.