Tag-free combinators for binding-time polymorphic program generation

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.