Given a tower of interpreters, i.e., a sequence of multiple interpreters interpreting one another as input programs, we aim to collapse this tower into a compiler that removes all interpretive overhead and runs 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 programs, e.g., for analysis and verification. In this paper, we lay the foundations in an idealized but realistic setting.
by Nada Amin and Tiark Rompf
- the paper https://www.cs.purdue.edu/homes/rompf/papers/amin-popl18.pdf
- the source https://github.com/TiarkRompf/collapsing-towers/tree/master/popl18
- the source in pink https://github.com/namin/pink
- discussion on hn https://news.ycombinator.com/item?id=15626816
- ACM link https://dl.acm.org/citation.cfm?id=3158140&picked=formats
Videos
- Programming Should Eat Itself
- Nada Amin - Collapsing Towers of Interpreters slides
- Tiark Rompf - Collapsing Towers of Interpreters
Related
- Collapsing a Reflective Tower http://lampwww.epfl.ch/~amin/doc/lms-black.pdf
Would add this classic, with a dad joke title to boot: A Lisp through the Looking Glass
This counts as one of the most beautiful ideas I’ve ever encountered, but I feel somewhat stuck in actually applying it. I probably need to sit with it for awhile longer.
An easier starting point might be meta circular evaluators, https://lobste.rs/s/dydfkh/william_byrd_on_most_beautiful_program
The enable one to build a thing-b that is almost like thing-a by delegating to thing-a. Amazingly powerful.
And then Abstract Interpretation