Collapsing Towers of Interpreters
summary
Claims that an interpretive tower can be reduced to a one-pass compiler are demonstrated by a staged, stage-polymorphic calculus plus two prototypes: a dynamic Pink system and a static Purple built on LMS in Scala. A meta-circular Lisp interpreter and an implementation of Black show the system collapsing arbitrarily many levels (including a conceptually infinite reflective tower), compiling and recompiling programs under user-modified semantics, and exposing concrete examples (compiled Fibonacci, traced runs that increment a meta counter to 102).
AI-written summary · about
chapters (20)
- 0:00Start
- 7:04Example in Purple/Black
- 7:56Reflection in Purple/Black
- 9:43Compilation in Purple
- 12:00Solving the Challenge
- 12:14The 1st Futamura Projection
- 12:45Practical Realization
- 13:49Staging
- 17:42Pink & Purple Towers of Interpreters
- 21:00Lift
- 25:37Double & Triple Pink Interpretation
- 25:50Pink Compilation
- 26:51Pink Transformers
- 28:23Recall: Collapse in Purple
- 28:46"Classic" vs Rigid Structures for Reflective Towers
- 29:40Purple: Modified Semantics
- 29:56Purple: User-Level "Interpreter"
- 30:37Summary
- 32:10Potential Applications
- 34:23Thank you!
related talks
27mParsing, Compiling, and Static Metaprogramming
26mMake Your Own Programming Language!
22mImplement an Esoteric Programming Language for Fun
14mA Relational Interpreter For Synthesizing JavaScript
28mHow to Build a Compiler
31mA brief history of programming languages
18mHow to Build an Interpreter in 25 Minutes or Less
20mPartial Evaluation, Whole-Program Compilation