Neutral mention · rule
Nada is the best! Don't forget the mind bending https://dl.acm.org/doi/10.1145/3158140 (not quite on topic, but in the multi-stage rabbit hole)
Back to the collection
Collapsing towers of interpreters
Nada Amin, Tiark Rompf
2017 · Proceedings of the ACM on Programming Languages
- HN score
- 0
- Mentions
- 3
- Readers
- 3
- Months
- 3
From the abstract
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.
Metadata: Crossref. Abstracts retain their original authors’ rights.
In the conversation
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
3 selected excerpts · 3 total mentions
Neutral mention · rule
Fascinating! I've seen references to Dan Friedman's work on this in the '80s. It looks very powerful, but he's said it made his head hurt. I bet there will be fruitful research layering interpreters like this with AI code generation. Also, Nada Amin and Tiark Rompf had something to say about this: https://dl.acm.org/doi/10.1145/3158140 "12 CONCLUSIONS We have shown how to collapse towers of interpreters using a stage-polymorphic multi-level λ-calculus λ↑↓. We have also shown that we can re-create a similar effect using LMS and polytypic programming via type classes. We have discussed several examples including novel reflective programs in Purple / Black. Looking beyond…
Read the full comment
this paper, we believe that collapsing towers, in particular eterogeneous towers, has practical value. Here are some examples: (1) It is often desirable to run other languages on closed platforms, e.g., in a web browser. For this purpose, Emscripten [Zakai 2011] translates LLVM code to JavaScript. Similarly, Java VMs [Vilk and Berger 2014] and even entire x86 processor emulators [Hemmer 2017] that are able to boot Linux [Bellard 2017] have been written in JavaScript. It would be great if we could run all such artifacts at full speed, e.g., a Python application executed by an x86 runtime, emulated in a JavaScript VM. Naturally, this requires not only collapsing of static calls, but also adapting to a dynamically changing environment." (2) It can be desirable to execute code under modified semantics. Key use cases here are: (a) instrumentation/tracing for debugging, potentially with time-travel and replay facilities, (b) sand-boxing for security, (c) virtualization of lower-level resources as in environments like Docker, and (d) transactional execution with atomicity, isolation, and potential rollback. (3) Non-standard interpretations, e.g., program analysis, verification, synthesis. We would like to reuse those artifacts if they are implemented for the base language. For example, a Racket interpreter in miniKanren [Byrd et al. 2017] has been shown to enable logic programming for a large class of Racket programs without translating them to a relational representation. Other examples are the Abstracting Abstract Machines (AAM) framework [Horn and Might 2011], which has recently been extended to abstract definitional interpreters [Darais et al . 2017]. For these indirect approaches to be effective, it is important to remove intermediate interpretive abstractions which would otherwise confuse the analysis. For these use cases, our approach hints at a solution where we only need to manually lift the meta interpreter of the user level while the rest of the tower acts in a kind of pass-through mode, handing down staging commands to the lowest level, which needs to support stage polymorphism. Last but not least, it is important to note that the present work is based on interpreters derived from variations of the λ-calculus, and thus leaves a gap towards collapsing heterogeneous towers of truly independent languages. This gap is especially prominent in a setting where a language level does not follow the usual functional or imperative paradigm, e.g., if a logic programming language or a probabilistic programming language is part of the tower. Thus, we hope that our work spurs further activity in implementing stage polymorphic virtual machines and collapsing towers of interpreters in the wild." https://www.codemesh.io/codemesh2017/nada-amin Nada Amin - Collapsing Towers of Interpreters - Code Mesh 2017 https://www.youtube.com/watch?v=Ywy_eSzCLi8 Tiark Rompf - [POPL'18] Collapsing Towers of Interpreters https://www.youtube.com/watch?v=QLyBxXqml5Y
Neutral mention · rule
These two papers from the author should be linked as background reading for those interested: https://dl.acm.org/doi/pdf/10.1145/3158140 https://lampwww.epfl.ch/~amin/doc/lms-black.pdf As a side note, I'm missing some more frequent submissions related to programming language theory, like in the old days.
Keep following the thread.
More in Programming languagesMore from the same topics.
1994arXiv
On proof and progress in mathematics
William P. Thurston
In response to Jaffe and Quinn [math.HO/9307227], the author discusses forms of progress in mathematics that are not captured by formal proofs of theorems, especially in his own work in the theory of foliations and geometrization of 3-manifolds and dynamical systems.
29 mentions21 months
9HN score
2023arXiv
Sparks of Artificial General Intelligence: Early experiments with GPT-4
Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan +11
Artificial intelligence (AI) researchers have been developing and refining large language models (LLMs) that exhibit remarkable capabilities across a variety of domains and tasks, challenging our understanding of learning and cognition.
60 mentions14 months
3.5HN score
2015arXiv
A Critique of the CAP Theorem
Martin Kleppmann
The CAP Theorem is a frequently cited impossibility result in distributed systems, especially among NoSQL distributed databases.
6 mentions6 months
3.5HN score
2020arXiv
Language Models are Few-Shot Learners
Tom B. Brown, Benjamin Mann, Nick Ryder +28
Recent work has demonstrated substantial gains on many NLP tasks and benchmarks by pre-training on a large corpus of text followed by fine-tuning on a specific task.
83 mentions35 months
3HN score