Show simple item record

dc.contributor.authorAmin, Nadaen
dc.contributor.authorRompf, Tiarken
dc.date.accessioned2018-04-19T16:45:27Z
dc.date.available2018-04-19T16:45:27Z
dc.date.issued2018-01en
dc.identifier.issn2475-1421
dc.identifier.urihttps://www.repository.cam.ac.uk/handle/1810/275056
dc.description.abstractGiven 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 modi cations. We discuss several examples: compiling regular expressions through an interpreter to base code, building program transformers from modified interpreters, and others. We develop these ideas further to include re 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.
dc.description.sponsorshipParts of this research were supported by ERC grant 321217, NSF awards 1553471 and 1564207, and DOE award DE-SC0018050.
dc.languageenen
dc.publisherAssociation of Computing Machinery
dc.titleCollapsing towers of interpretersen
dc.typeConference Object
prism.endingPage33
prism.issueIdentifierPOPLen
prism.publicationDate2018en
prism.publicationNameProceedings of the ACM on Programming Languagesen
prism.startingPage1
prism.volume2en
dc.identifier.doi10.17863/CAM.21256
dcterms.dateAccepted2017-11-06en
rioxxterms.versionofrecord10.1145/3158140en
rioxxterms.versionAM*
rioxxterms.licenseref.urihttp://www.rioxx.net/licenses/all-rights-reserveden
rioxxterms.licenseref.startdate2018-01en
dc.identifier.eissn2475-1421
rioxxterms.typeConference Paper/Proceeding/Abstracten


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record