Multi-stage programming in the large with staged classes

Multi-stage programming (MSP) holds great promise, allowing the reliable generation of specialized, partially-evaluated code with static type- and scope-safety guarantees. Yet, we argue that MSP has not reached its full potential yet, as it has been traditionally limited to generating expressions, and has lacked principled facilities for generating modular programs and data structures. In that sense, we argue that MSP has been reserved for programming “in the small,” focused on generating efficient kernels of computation on the scale of single function bodies. We present a novel technique called staged classes, which extends MSP with the ability to manipulate class definitions as first-class constructs. This lets programmers use MSP “in the large,” on the level of applications, rather than mere functions. This way, applications can be designed in an abstract and modular way without runtime cost, as staged classes guarantee the removal of all staging-time abstractions, resulting in the generation of efficient specialized modules and data structures. We describe the design of a prototype relational database system in Scala, which uses several stages of runtime compilation to maximize the efficiency of query execution and data storage. We also show that staged classes can be used for defining type- and scope-safe implementations of type providers.