Guido Chari, Diego Garbervetsky, Stefan Marr, and Stephane Ducasse. 2019. “Fully reflective execution environments: virtual machines for more flexible software.” IEEE Transactions on Software Engineering, 45, 9, Pp. 858-876. Publisher's Version
Nada Amin and Tiark Rompf. 2017. “Collapsing towers of interpreters.” Proceedings of the ACM on Programming Languages, 2, POPL, Pp. 1-33. Publisher's VersionAbstract
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. We present a multi-level lambda calculus that features staging constructs and stage polymorphism: based on runtime parameters, an evaluator either executes source code (thereby acting as an interpreter) or generates code (thereby acting as 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 evaluator 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 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 realizes a conceptually infinite tower, where every aspect of the semantics can change dynamically. Addressing an open challenge, we show how user programs can be compiled and recompiled under user-modified semantics.
Jesper Andersson, Rogerio de Lemos, Sam Malek, and Danny Weyns. 2009. “Reflecting on self-adaptive software systems.” In 2009 ICSE Workshop on Software Engineering for Adaptive and Self-Managing Systems, Pp. 38-47. IEEE. Publisher's Version
Kenichi Asai, Satoshi Matsuoka, and Akinori Yonezawa. 1996. “Duplication and partial evaluation.” Lisp and Symbolic Computation, 9, 2-3, Pp. 203-241. Publisher's Version
David S. Warren. 1992. “Memoing for logic programs.” Communications of the ACM, 35, 3, Pp. 93-111. Publisher's Version
Gregor Kiczales, Jim des Rivieres, and Daniel G. Bobrow. 1991. The Art of the Metaobject Protocol. MIT Press.
B. Foote and R. E. Johnson. 1989. “Reflective facilities in Smalltalk-80.” In Conference proceedings on Object-oriented programming systems, languages and applications - OOPSLA '89, Pp. 327-335. New York, New York, USA: ACM Press. Publisher's VersionAbstract
Computational reflection makes it easy to solve problems that are otherwise difficult to address in Smalltalk-80, such as the construction of monitors, distributed objects, and futures, and can allow experimentation with new inheritance, delegation, and protection schemes. Full reflection is expensive to implement. However, the ability to override method lookup can bring much of the power of reflection to languages like Smalltalk-80 at no cost in efficiency.
Olivier Danvy and Karoline Malmkjaer. 1988. “Intensions and extensions in a reflective tower.” In Proceedings of the 1988 ACM conference on LISP and functional programming - LFP '88, Pp. 327-341. New York, New York, USA: ACM Press. Publisher's Version
Mitchell Wand and Daniel P. Friedman. 1986. “The mystery of the tower revealed: A non-reflective description of the reflective tower.” In Proceedings of the 1986 ACM conference on LISP and functional programming - LFP '86, Pp. 298-307. New York, New York, USA: ACM Press. Publisher's Version
Brian Cantwell Smith. 1984. “Reflection and semantics in LISP.” In Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages - POPL '84, Pp. 23-35. New York, New York, USA: ACM Press. Publisher's Version