Combinators for Impure yet Hygienic Code Generation

Code generation is the leading approach to making high-perfor-mance software reusable. Effects are indispensable in code gener-ators, whether to report failures or to insert let-statements and if-guards. Extensive painful experience shows that unrestricted effects interact with generated binders in undesirable ways to produce un-expectedly unbound variables, or worse, unexpectedly bound ones. These subtleties hinder domain experts in using and extending the generator. A pressing problem is thus to express the desired effects while regulating them so that the generated code is correct, or at least correctly scoped, by construction. We present a code-combinator framework that lets us express ar-bitrary monadic effects, including mutable references and delimited control, that move open code across generated binders. The static types of our generator expressions not only ensure that a well-typed generator produces well-typed and well-scoped code. They also ex-press the lexical scopes of generated binders and prevent mixing up variables with different scopes. For the first time ever we demon-strate statically safe and well-scoped loop exchange and constant factoring from arbitrarily nested loops. Our framework is implemented as a Haskell library that embeds an extensible typed higher-order domain-specific language. It may be regarded as ‘staged Haskell. ’ To become practical, the library relies on higher-order abstract syntax and polymorphism over gen-erated type environments, and is written in the mature language