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.
Suppose we change the meta-interpreter so that it increments
a counter each time a variable named
n is accessed. Re-defining fibonacci
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
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
will still update the counter.
sbt testruns the test suite.
sbt consoleopens a Scala REPL with the system already imported. Then, use
evto evaluate Black terms, like in the tests, e.g.
ev("(+ 1 1)").
eval.scaladefines the stage-polymorphic base interpreter functions and wires the tower.
stage.scaladefines the LMS-specific instantiation of the stage-polymorphic type class.
- The test directory contains many examples.
instr.scaladefines a special form to count calls to several meta-level functions.
taba.scaladefines a special form taba to monitor the stack.
delta.scaladefines the "classic" delta reifer to go up the tower with a reified structure for the current computation from below, and also
call/ccin terms of
undo.scaladefines a scheme to undo at the meta-level.
cont.scaladefines alternative semantics for continuations.
re.scaladefines a string matcher, showing that LMS-Black can also collapse ad-hoc user-level towers.