Advanced multi-stage programming with computational effects

Developer productivity and software performance are two key properties of software development that are hard to achieve simultaneously. The former requires rich layers of abstraction and highly reusable, contextindependent code. In contrast, the latter aims at code without generic overhead or indirections that is highly specialized. General-purpose optimized compilation can automatically improve the performance of high-level programs, but is still far from optimal. Much more promising are code generation techniques that can be employed in "active libraries" to offer high-level programming interfaces, and exploit knowledge of the problem domain and of the code structure to generated highly tuned code. Standard code-generation techniques (e.g., templates in C++) can be quite error-prone and hard to debug. Multi-stage programming promises to considerably lower the threshold by providing strong static guarantees with respect to well-scopedness and well-typedness at the level of the generators. This project aims to advance the state-of-the-art of multi-stage programming. In particular, we aim to develop the interaction between staging and computational effects. While most existing effort has targeted effect-free code, side-effects are essential for functionality and/or performance in most applications. We take a foundational approach, developing a formal calculus for multi-staging with support for algebraic effects and handlers, complemented by practical case studies.