The Reflective Language Black
Reflective programming languages provide high flexibility and
extensibility by allowing user programs to access and change their
language implementation (or semantics) from within themselves.
Reflective languages are useful not only for extending language
semantics, but also for controlling dynamic behavior of programs.
To change the language semantics in conventional non-reflective
languages, we need to fully understand the low-level implementation
details and carefully alter their implementation
(either an interpreter or a compiler), which is usually written in
lower-level languages.
Reflective languages allow such modifications
within the same language framework using high level abstractions
without understanding low-level implementation.
Because of the high flexibility and extensibility of reflective
languages, however, their implementation has been considered to be
complex.
In this thesis, we clarify the structure of reflective languages,
show a general construction method of reflective interpreters, and
discuss a compilation framework based on partial evaluation.
The thesis is divided into three parts.
In the first part of the thesis, we investigate
a general implementation framework for
reflective languages which satisfy the following favorable
properties:
(1) user programs are allowed to access and change (parts of)
the interpreter defining the language semantics from within the same
language framework in an arbitrary way,
(2) reflective facilities are available at every level (with minor
approximation), hence there
exists conceptually an infinite tower of interpreters, and
(3) the interpreter runs as efficiently as the conventional (directly
implemented) metacircular interpreter when reflection is not used.
Based on this framework, we implement a reflective language called
Black, a reflective extension of the functional language Scheme.
Although the Black interpreter runs efficiently at first, it becomes
considerably inefficient as the modification on the interpreter
becomes substantial.
For more efficient execution, we introduce compilation based on
partial evaluation.
In the second part of the thesis, we concentrate on the construction
of a partial evaluator which is powerful enough to serve as a compiler
for reflective languages.
Specifically, we build a partial evaluator for functional languages
which can correctly handle side-effecting operations and pointer
equality.
These facilities are important in compiling Black programs, since they
play an essential role in the Black interpreter.
We employ a side-effect analysis to identify mutable data structures
and use preactions to avoid code duplication
and code elimination without disturbing the order of execution.
Apart from side-effecting operations, our partial evaluator reduces
more expressions than the previous one thanks to the proper treatment
of pointer equality.
It can now accept almost all the features of Scheme.
In the last part of the thesis, we actually apply the partial
evaluation technique to compile various programs in Black.
This can be also regarded as a non-trivial application of partial
evaluation.
By specializing the current interpreter with respect to a program, it
is compiled under the current language semantics.
Furthermore, a user program is compiled under a modified language
semantics by first compiling the modified interpreter and then
specializing it further with respect to the user program.