Eric: Created page with "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 i..."

2017-06-17T23:00:04Z

Created page with "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 i..."

New page

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.

WG211/M17Amin - Revision history

Eric: Created page with "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 i..."