Invited Talk

Given a tower of interpreters, i.e., a sequence of interpreters interpreting each other, we aim to collapse this tower into a compiler that removes all interpretive overhead in a single pass. In the real world, a use case might be Python code executed by an x86 runtime, on a CPU emulated in a JavaScript VM, running on an ARM CPU. Collapsing such a tower can not only exponentially improve runtime performance, but also enable the use of base-language tools for interpreted languages, e.g., for analysis and verification. Here we lay the foundations in an idealized but realistic model environment.

We present a multi-level lambda calculus that features staging constructs and stage polymorphism: based on runtime parameters, an interpreter can either act as a normal interpreter or generate code, which turns it into a compiler. We identify stage polymorphism, a programming model from the domain of high-performance program generators, as the key mechanism to make such interpreters compose in a collapsible way.

We present Pink, a meta-circular Lisp-like interpreter on top of this calculus, and demonstrate that we can collapse arbitrarily many levels of self-interpretation, including levels with semantic modi cations. We discuss several examples: compiling regular expressions through an interpreter to base code, building program transformers from modi ed interpreters, and others. We develop these ideas further to include reflection and reification, culminating in Purple, a reflective language inspired by Brown, Blond, and Black, which implements a conceptually in nite tower, where every aspect of the semantics can change dynamically. Addressing an open challenge, we demonstrate how user programs can be compiled and recompiled under user-modified semantics.

Joint work with Tiark Rompf.