Collapsing Towers of Interpreters [pdf]
The paper presents a technique called "collapsing towers of interpreters" that eliminates interpretive overhead in multi-level language implementations by using guaranteed type specialization at each interpreter stage, achieving performance comparable to the base system without intermediate layers.
Background
- Academic paper from POPL 2018 (top programming languages conference) by Nada Amin and Tiark Rompf. Presents a technique to eliminate the performance overhead of "multi-stage interpreters" — interpreters that run on top of other interpreters.
- "Towers of interpreters" refers to layered language implementations (e.g., a DSL interpreted in Python, which is itself interpreted). Each layer adds roughly 10–100x slowdown.
- Key insight: using "staging" (partial evaluation) and the "first Futamura projection," such towers can be automatically collapsed into a single efficient compiled program. Demonstrated using Scala's LMS and Squid frameworks.
- Why it matters: real systems often stack interpreters (JavaScript running a DSL, emulated OS running a VM). Prior approaches required manual rewriting or suffered exponential code blowup. This work showed systematic, efficient collapse.
- Won a POPL 2018 Distinguished Paper Award; foundational for later work on efficient meta-interpretation and language virtualization.