WG211/M17Amin

Nada Amin

Collapsing Towers of Interpreters

Abstract: Given a tower of interpreters, i.e. a sequence of interpreters interpreting each other, we aim to collapse this tower into a one-pass compiler that removes all interpretive overhead. We present a multi-level lambda calculus that features staging constructs and stage polymorphism: based on runtime parameters, the interpreter can either act as a normal interpreter or generate code, which turns it into a compiler, according to the Futamura projections. We identify stage polymorphism as the key mechanism to make such interpreters compose in a collapsible way.

We present a meta-circular Lisp interpreter on top of this calculus and demonstrate that we can collapse arbitrarily many levels of self-interpretation, including levels with semantic modifications. We discuss several examples: compiling regular expressions through a Lisp interpreter to base code, building program transformers from modified interpreters, and others. We develop these ideas further into an implementation of the reflective language Black, which implements a conceptually infinite tower, where every aspect of the semantics can change dynamically, and as a novel feature, we demonstrate how user programs can be compiled and recompiled under user-modified semantics.