Collapsing Towers of Interpreters

In a reflective programming language such as Black, user programs are interpreted by an infinite tower of meta-circular interpreters. Each level of the tower can be accessed and modified, so the semantics of the language changes dynamically during execution.

In this talk, we show that it is possible to compile a user program under modified, possibly also compiled, semantics.

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.

Joint work with Tiark Rompf.

Talk objectives

Share ideas on reflective towers of interpreters and their compilation.

Talk audience

Programmers interested in reflection and compilation.