LMS Black aka Purple

In a reflective programming language such as Black, user programs are interpreted by an infinite tower of meta-circular interpreters. Each level of the tower can be accessed and modified, so the semantics of the language changes dynamically during execution.

In this project, we show that it is possible to compile a user program under modified, possibly also compiled, semantics -- a question raised by Kenichi Asai in his GPCE 2014 paper, Compiling a Reflective Language using MetaOCaml.

How? All functions are polymorphic as to whether they generate code or run. Generated code, when compiled, is also polymorphic in this way so that there's no difference between built-in and compiled functions.

An example. Suppose we change the meta-interpreter so that it increments a counter each time a variable named n is accessed. Re-defining fibonacci with parameter n as a compiled lambda will generate code that includes code for a counter increment each time n is mentioned in the body (compare test-generated code without vs with the meta-change). Running this compiled fib function has the same behavior as an uncompiled fib function evaluated by the modified interpreter. Still, once we undo the modifications to the interpreter, the previously compiled fib function will still update the counter.

Running

• sbt test runs the test suite.
• sbt console opens a Scala REPL with the system already imported. Then, use ev to evaluate Black terms, like in the tests, e.g. ev("(+ 1 1)").

Code

• eval.scala defines the stage-polymorphic base interpreter functions and wires the tower.
• stage.scala defines the LMS-specific instantiation of the stage-polymorphic type class.
• The test directory contains many examples.
  • instr.scala defines a special form to count calls to several meta-level functions.
  • taba.scala defines a special form taba to monitor the stack.
  • delta.scala defines the "classic" delta reifer to go up the tower with a reified structure for the current computation from below, and also call/cc in terms of delta.
  • undo.scala defines a scheme to undo at the meta-level.
  • cont.scala defines alternative semantics for continuations.
  • re.scala defines a string matcher, showing that LMS-Black can also collapse ad-hoc user-level towers.

Further Reading

• Our POPL 2018 paper, Collapsing Towers of Interpreters (PDF).
• Some older LMS-Black Design Document (PDF) to be read in conjunction with this code.