Static Performance Guarantees Through Storage Modes and Multi-Stage Programming

This thesis explores two approaches to bridge the gap between expressiveness and performance in programming languages. It presents two complementary directions that reconcile performance and expressiveness: retrofitting static performance guarantees into an expressive general-purpose language like Scala, and transparently extending a restricted language like Datalog with features like polymorphism and user-defined functions while generating specialized and efficient code.

We first introduce storage modes, lightweight type qualifiers that enable statically tracking the lifetime of values in Scala programs. This enables stack allocating them and reduce memory pressure on the garbage collector. A key novelty is delaying the popping of the stack frames when returning dynamically-sized stack-allocated values, overcoming limitations of previous approaches.

Second, we present Flan, a Datalog compiler and embedding in Scala implemented as a multi-stage interpreter. Through staging, Flan can generate highly specialized code for different execution strategies and indexing structures, achieving performance on par with state-of-the-art domain-specific compilers like Soufflé. Moreover, by leveraging the host language, Flan enables seamless extension of Datalog with powerful features like user-defined functions, lattices and polymorphism, retaining the expressiveness of languages like Flix.

Overall, this work advances the design space for expressive and efficient programming languages, through lightweight annotations in an expressive host language, and transparent compiler specialization of an embedded domain-specific language. The techniques intoduced bridghe the gap between low-level performance and high-level programming abstractions.