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.