The point of behavioral reflection is to modify the syntax, the semantics and the implementation of the language. Compiler extensions and automatic compiler generation appear as tools of choice to directly achieve such modifications. A modification to the syntax is achieved by modifying the lexer and the parser. Modifications to the semantics are implemented by modifications to the code generator. The run-time system can also be modified to match the needs of an application. Interestingly, in reflection the semantics of the language is incrementally modified, a process which suggests incremental compiler generation.
Compiler extensions are exemplified by the open compiler approach, which provides exactly the kind of incremental generation needed for reflection. Compared to automatic compiler generation, it appears as a proven approach, but forces the reflective programmers to construct modifications in terms of a complex compiling process. Automatic compiler generators start from a specification of the language that may appear more appropriate. Unfortunately, they produce less efficient compilers, and the specification they use may be as difficult to modify as the compiler itself. An interesting question is whether or not the fact that reflection incrementally modifies specifications for which there is already an existing compiler can help to construct automatic incremental compiler generators that would produce better compilers. In this context, it is interesting to assess the relative merits of the different formalisms of specifications in a reflection perspective.
We propose the following criteria of a good formalism for reflective purposes, which seem to catch the core issues:
Besides compile time MOPs, which are rather new, the need to represent the formalism in the language as well as the need to easily provide causal connection have advocated the use of interpreters as formalism to specify the languages. Interpreters seem easy to represent, to understand and to modify. From a compilation point of view, interpreters can be transformed into compilers by partial evaluation as we have seen before. Unfortunately, this is actually difficult to achieve.
Part of the problem comes from the relative youth of the technique. Our own experiments [Dem94] have shown that currently available partial evaluators are often a little too fragile for production use. We have noticed that it takes great care to write interpreters and programs that perform well under partial evaluation. A deep knowledge of partial evaluation and of the particular partial evaluator under use is needed to achieve the goal of compiling away the levels of meta-interpretation. Other recent experiments, such as the one by Masuhara et al. [MMAY95], do not invalidate these remarks.
Part of the problem also comes from immoderate expectations put in partial evaluation. Partial evaluation performs a kind of compilation but Ruf [Ruf93] has pointed out that programs resulting from partial evaluation essentially stick to the implementation choices made by the interpreter. For example, if the interpreter uses a-lists to implement environments, partially evaluating it with respect to a program will yield a ``compiled'' program that still uses a-lists for its environments. Hence, unless a very precise model of the underlying machine leaks out to the interpreter, the ``compiled'' program will not achieve good performance. These remarks are corroborated by the study of Lee [Lee89] on automatic compiler generation from formal semantics. Unfortunately, if the interpreter deals with so many details, it may force reflective programmers to express their modifications to the semantics and implementation of the language in such a low-level model that most of them would probably be put off by this perspective.
Compiler generators have also been developed around formal semantics like denotational (see [Lee89]), action [Mos92,BMW92] and monadic semantics [LH95]. Denotational semantics is universally acknowledged as too monolithic to be extended easily. Action semantics has been developed in reaction to the monolithism of denotational semantics, but Liang and Hudak [LH95] argue that the theory of reasoning about programs in the action formalism is still weak and this may hamper program transformations, and therefore optimizations. Monads have attracted a lot of attention since the beginning of the nineties because of their powerful structuring capabilities, which have been used to develop modular interpreters where language features are represented as monads extending a vanilla monadic interpreter. Interestingly, the possibility for combining already existing monads to obtain an interpreter with mixed capabilities is also rapidly evolving [JD93,Ste94,LHJ95]. Finally, the most recent work in this domain tries to use monadic semantics to implement efficient compiler generators. Although still depending on partial evaluation, this approach seems to enable the development of specific program transformations [LHJ95,LH95], which, as we have argued, appear mandatory for the time being to obtain efficient compilers.
In our view, modular interpreters and monads, in conjunction with the idea of incremental compiler generation, are currently the most promising avenues to provide extensibility to reflective languages at an affordable cost in terms of performance.