A Generic Reification Technique for Object-Oriented Reflective Languages.
Computational reflection is gaining interest in practical applications as witnessed by the use of reflection in the Java programming environment and recent work on reflective middleware. Reflective systems offer many different reflection programming interfaces, the so-called Meta-Object Protocols (MOPs). Their design is subject to a number of constraints relating to, among others, expressive power, efficiency and security properties. Since these constraints are different from one application to another, it would be desirable to easily provide specially-tailored MOPs.In this paper, we present a generic reification technique based on program transformation. It enables the selective reification of arbitrary parts of object-oriented meta-circular interpreters. The reification process is of fine granularity: individual objects of the run-time system can be reified independently. Furthermore, the program transformation can be applied to different interpreter definitions. Each resulting reflective implementation provides a different MOP directly derived from the original interpreter definition.
Introduction
Computational reflection, that is, the possibility of a software system to inspect and modify itself
at runtime, is gaining interest in practical applications: modern software frequently requires strong
adaptability conditions to be met in order to fit a heterogenous and evolving computing environment.
Reflection allows, for instance, host services to be determined dynamically and enables the modification
of interaction protocols at runtime. Concretely, the JAVA programming environment [java] relies
heavily on the use of reflection for the implementation of the JAVABEANS component model and its
remote method invocation mechanism. Furthermore, adaptability is a prime requirement of middle-ware
systems and several groups are therefore doing research on reflective middleware [coi99][bc00].
Reflective systems offer many different reflection programming interfaces, the so-called Meta-Object
Protocols (MOPs) 1 . The design of such a MOP is subject to a number of constraints relating
to, among others, expressive power, efficiency and security properties. For instance, using reflection
Extended version. c
2001 Kluwer Academic Publishers. "Higher-Order and Symbolic Computation", 14(1),
2001, to appear.
We use the term "MOP" in the sense of Kiczales et al. [kic91] (page 1): "Metaobject protocols are interfaces to the
language that give users the ability to incrementally modify the language's behavior and implementation, as well as the
ability to write programs within the language."
for debugging purposes may require the MOP to provide access to the execution stack. However,
because of security concerns stack access must frequently be restricted: in JAVA, for example, it is not
allowed to modify the (untyped) stack because security properties essentially rely on type information.
Since these constraints are different from one application to another, we should be able to provide
a specially-tailored MOP for a particular set of constraints. Moreover, the constraints may change during
the overall software life cycle. Hence, the development of such specially-tailored MOPs should
be a lightweight process. Traditional approaches to the development of MOPs do not meet this goal
instead each of them only provides a specific MOP which can hardly be modified (see the discussion
of related work in Section 9). Consider, for instance, a single-processor application which is to be
distributed. In this case, distinct tasks have to be performed on the message sending side and the
receiving side: for example, on the sender side local calls are replaced by remote ones (instead of
relying on proxies) and on the receiver side incoming messages can be synchronized. Many existing
MOPs do not allow the behavior of message senders to be modified. Hence, such a distribution strategy
cannot be implemented using reflection in these systems. Some systems (see, for instance CODA
[aff95]) provide access to senders right from the start. Therefore, they can introduce an overhead for
local applications.
In this paper, we present a reification mechanism for object-oriented interpreters based on program
transformation techniques. We use a generic transformation which can be applied at compile time to
any class of a non-reflective interpreter definition. This mechanism can be used to transform different
subsets of a metacircular interpreter in order to generate increasingly reflective interpreters. It can
also be applied to different interpreter definitions in order to automatically get different reflective
interpreters. Each resulting reflective implementation provides a different MOP directly derived from
the original interpreter definition.
The paper is structured as follows: in Section 2, we briefly introduce Smith's seminal reflective
towers upon which our work is based and we sketch the architecture of our transformational system.
Section 3 provides an overview of a metacircular interpreter for JAVA. Our generic reification technique
is formally defined and its application to the non-reflective interpreter is exemplified in Section
4. Section 5 is devoted to reflective programming: it details our reification technique at work by
presenting several applications. Section 6 complements Section 4 by presenting a few technicalities
postponed for the sake of readability. Section 7 discusses the correctness of the transformation and
sketches a formal correctness proof. Section 8 illustrates how a refined definition of the non-reflective
interpreter produces a more expressive reflective interpreter. Section 9 discusses related work. Fi-
nally, Section 10 concludes and discusses future work. Code occuring in the paper refers to a freely
available prototype implementation, called METAJ [metaj], which enables execution of the reflective
programming examples we present and provides a platform for experimentation with our technique.
2 Overview of the reification process
In our opinion, Smith' definition of reflection [smi84] remains a key reference because of its clean
semantic foundation and generality. This paper proposes one method to transpose his technique into
the domain of object-oriented languages. In this section, we first introduce Smith-like reflection before
presenting the architecture of our reification method.
Level 0
Level 1
Level 2
Level 3
Interpreter
Program Program
Interpreter
Interpreter Interpreter
Program
Interpreter
Program

Figure

1: Smith-like reflective towers
2.1 Smith-like Reflection
Smith's seminal work on reflective 3-Lisp defines reflection with the notion of reflective towers. In

Figure

1, the left hand side tower shows a user-written (i.e. level 0) Program in a double-square box
and its Interpreter, which defines its operational semantics. A simple classic example of reflective programming
deals with the introduction of debugging traces. Trace generation requires the interpreter
to be modified, that is, two steps have to be performed at runtime: provide an accessible representation
of the current interpreter and change this representation. Such a computation creates an extra
interpretation layer by means of a reification operator "reify," so that the level 1 Interpreter becomes
now part of the program: in the illustration, it is included in the double square box. We get a second
tower with three levels. The Program can now modify the standard semantics of the language defined
by the level 1 Interpreter to get Interpreter' which generates traces during execution (see the third
tower). Finally, when a non-standard semantics Interpreter" of Interpreter' is required, a further extra
interpretation level can be introduced as illustrated by the fourth tower. The fourth tower would be
required, for example, to trace Interpreter'.
On a more abstract level, Smith's reflection model - as well as our reification technique - has
two essential properties: there is a potentially infinite tower of reflective interpreters and the interpreter
at level n interprets the actual code of the interpreter at level n 1.
2.2 Making object-oriented interpreters reflective
In order to get a first intuition of our reification technique, consider the following simple example of
how we intend reflection to be used: color information (represented by the class Color) should be
added to pairs at runtime. Using reflection, we could dynamically modify the inheritance graph such
that Pair inherits from Color. This can be achieved by
// Pair extends Object
// Pair extends Color
where 4 is a reification operator. The application of the reification operator to an expression yields
an accessible representation of the value denoted by the expression. In this example, the expression
Pair denotes the corresponding Class object, say c, in the interpreter's memory (see Figure 7).
4Pair returns an instance (say i), i.e. an object of type Instance, in the interpreter's memory
which represents c and which can be inspected and modified. The default superclass of Pair is
replaced by Color by assigning the field extendsLink. From now on, newly instantiated pairs
contain color information.
It is crucial to our approach that the reified representation i is based on the definition of c. This
Parser
Java.jjt
Runtime System
ExpAssign.java
Reflective Interpreter
Reflective_Prog.java
Java2ExpVisitor.java
Parser
Java.jjt
Runtime System
ExpAssign.java
Non-Reflective Interpreter
Prog.java
Java2ExpVisitor.java
Instance.java
BaseClass.java
Instance.java
generation of reflective interpreter
program
transformation

Figure

2: System architecture
is achieved by the system architecture shown in Figure 2. Our non-reflective JAVA interpreter (repre-
sented by the box at the top) takes a non-reflective program Prog.java as input. This program is
parsed into a syntax tree and evaluated. According to the required reflective capabilities, the language
designer 2 transforms a subset of the classes of the non-reflective interpreter. Basically, this transformation
generates two classes for each original class. In our example, the file Class.java, which
represents classes in the non-reflective interpreter, becomes BaseClass.java and a different version
of Class.java in the reflective one.
The reflective interpreter relies on the non-reflective interpreter in order to build levels of the
reflective tower. This is the core issue of our approach: the tower levels shown in Figure 1 are
effectively built at runtime on the basis of the (verbatim) definition of the non-reflective interpreter as
in Smith's model. This is why the original definition of Class.java is an input of the reflective
interpreter in Figure 2. So, the behavior of the reflective interpreter is derived from the non-reflective
one. Furthermore, our approach is selective and complete because the transformation is applicable to
any class of the non-reflective interpreter definition.
implements one version of this system architecture. Its parser has been implemented
by means of JAVACC and JJTREE (versions 0.8pre2 and 0.3pre6, respectively). METAJ itself is
operational with the JDK versions 1.1.6 and 1.2.
3 A simple non-reflective interpreter
We have implemented a non-reflective metacircular interpreter for a subset of JAVA, which provides
support for all essential object-oriented and imperative features, such as classes, objects, fields, meth-
ods, local variables and assignment statements. (We did not implement features such as some primitive
2 Note that building a reflective interpreter by transformation and writing reflective programs are two different tasks: the
former is performed by language designers and the latter by application programmers.
class ExpId extends Exp {
private String id;
ExpId(String id) {
Data eval(Environment localE) {
return localE.lookup(this.id);

Figure

3: Class ExpId
class ExpAssign extends Exp {
private Exp lhs;
private Exp rhs;
ExpAssign(Exp lhs, Exp rhs) {
Data eval(Environment localE) {
Data
Data
return d2;

Figure

4: Class ExpAssign
types or loop constructs; all of these could be integrated and reified similarly.)
JAVA programs are represented as abstract syntax trees the nodes of which denote JAVA's syntactic
constructs and are implemented by corresponding classes. For example, variables, assignment
statement, method call, and class instantiation expressions are respectively encoded by the classes
ExpId, ExpAssign, ExpMethod and ExpNew. All of these classes define an evaluation method
Data eval(Environment localE) that takes the values of local variables in localE and
returns the value of the expression (wrapped in a Data object).
In particular, ExpId (see Figure 3) holds the name of a variable and its evaluation method yields
the value currently associated to the variable in the local environment. An ExpAssign node (see

Figure

stores the two subexpressions of an assignment. Its evaluation method evaluates the location
of the right-hand side expression, followed by the value represented by the left-hand side expression
and finally performs the assignment. ExpMethod (see Figure 5) represents a method call with a receiver
expression (exp), a method name (methodId) and its argument expressions (args). Method
call evaluation proceeds by evaluating the receiver, constructing an environment from the argument
values, looking up the method definition and applying it. ExpNew (see Figure 6) encodes the class
name (classId) and constructor argument expressions. Its evaluation fetches the class definition
from the global environment, instantiates it and possibly calls the constructor.
As suggested before, the interpreter defines a few other classes to provide a runtime system and
implement an operational semantics. For example, the class Class (see Figure 7) represents classes
by a reference to a superclass (extendsLink), a list of fields (dataList) and a list of methods
(methodList). It provides methods for instantiating the class (instantiate()), accessing the
list of methods including those in super classes (methodList()), etc. Methods are represented by
class ExpMethod extends Exp {
private Exp exp; // receiver
private String methodId; // method name
private ExpList args; // arguments
ExpMethod(Exp exp, String methodId, ExpList args) {
Data eval(Environment localE) {
// evaluate the lhs (receiver)
Instance
// evaluate the arguments to get a new local environment
Environment
// lookup and apply method
return m.apply(argsE, i);

Figure

5: Class ExpMethod
class ExpNew extends Exp {
private String classId; // class name
private ExpList args; // constructor arguments
ExpNew(String classId, ExpList args) {
Data eval(Environment localE) {
// get the Class and create an Instance
Instance
// call non default constructor if it exists
if (i.getInstanceLink().methodList().member(this.classId).booleanValue()) {
Environment
// lookup and apply method
return new

Figure

class Class {
Class extendsLink; // superclass
DataList dataList; // field list
MethodList methodList;
Class(Class eL, DataList dL, MethodList mL) {
Class getExtendsLink() { return this.extendsLink; }
// implementation of Java's 'new' operator
Instance instantiate() { . }
// compute complete method list (incl. superclasses)
MethodList methodList() { . }

Figure

7: Class Class
class Method {
private StringList args; // parameter names
private Exp body; // method body
Method(StringList args, Exp body) {
Data apply(Environment argsE, Instance i) {
// name each argument
argsE.add("this", new
// eval the body definition of the method
return this.body.eval(argsE);

Figure

8: Class Method
the class Method (see Figure 8) by means of a list of argument names (args) and a body expression
(body). Its method apply() binds argument names to values including this and evaluates the
body. Other classes include Instance (contains a reference instanceLink to its class and a
list of field values; provides field lookup and method lookup), MethodList, Data (implements
mutable memory cells such as fields), DataList, Environment (maps identifiers to values), etc.
The architecture of the interpreter follows the standard design for object-oriented interpreters as
presented in Gamma et al. [ghjv95] by the Interpreter design pattern. Instantiating this design pattern,
the following correspondences hold: their 'Client' is our interpreter's main() method, their methods
'Interpret(Context)' is our eval(Environment). The reification technique described in this
paper is applicable to other interpreters having such an architecture. Note that these interpreters may
implement many different runtime systems.
4 Generic reification by code transformation
In this section, we give an overview of our generic reification scheme for the class Class and formally
define the underlying program transformation. (For the sake of readability, we postpone the
discussion of a few technicalities to Section 6.) Then, we apply it in detail to the class Instance.
4.1 Overview of the generic reification scheme
Reification of an object should not change the semantics of that object but change its representation
and provide access to the changed representation. For example, it is not possible to modify the superclass
of a class at runtime in our non-reflective interpreter (although a reference representing the
inheritance relation exists in the memory of the underlying implementation). The reified representation
of a class provides access to this reference. Once the internal representation has been exposed,
access to this structure allows the semantics of the program to be changed (e.g. by means of dynamic
class changes). Note that this form of structural reification of the interpreter memory subsumes the
traditional notions of structural and behavioral reflection.
For illustration purposes, consider a class Pair with two fields fst and snd which is implemented
in the interpreter memory by a Class (from here on, C denotes an instance of the class C).
In order to reify Pair, we choose Class to be reifiable. Basically, a reifiable entity can have two
different representations as exemplified in Figure 9: either a base representation or a reified represen-
tation. Since reification of any object does not change its behavior, the object should provide the same
method interface in both representations. This common interface is implemented using a dispatch
object 3 : the Class denoted by Pair.
The dispatch object points to the currently active representation: either the base representation
(BaseClass in Figure 9a) or the reified representation (Instance denoted by 4Pair in Figure
9b). The dispatch object provides a method reify() (triggered by 4) to switch from the base
representation to the reified one: a call to reify() creates a new tower level. The dispatch object
executes incoming method calls according to the active representation: when the base representation
is active, the dispatch simply delegates incoming method calls to it. When the reified representation
is active, the dispatch object interprets the method call.
Whether an object is accessed through its dispatch object or through its reified representation is
irrelevant, that is, modification of the object through the access path Pair is visible through the other
access path 4Pair. (This property is commonly referred to as the causal connection between levels.)
3 The dispatch technique is close to the bridge and state patterns introduced in Gamma et al. [ghjv95].
denotes
methodList
dispatch object
Class
Instance
dataList
methodList, extendLink
active representation
instance of
a) before D b) after D
Pair Pair
Pair Pair Pair
different
representations

Figure

9: Before and after reification of the class Pair
Obviously, the two paths provide different interfaces. Consider, for example, the problem of keeping
track of the number of Pair instances using a static field countInstances: this field could be accessed
either by Pair.countInstances or by (4(4Pair).staticDataList).lookup
4 . In the last expression, the outermost reification operation is necessary in
order to call lookup() on a data list object (cf. the fourth item below).
In order to conclude this overview, we briefly mention other important properties of our reification
scheme:
Since reflection provides objects representing internal structure for use in user-level programs,
every reification operation returns an Instance (e.g. the one in Figure 9b). This implies that
reification of reified entities requires that Instances are reifiable.
4Exp yields an accessible representation of the value denoted by Exp (i.e. an object in the
interpreter's memory, such as Class, Instance, Method) 5 .
References from dispatch objects to their active representations cannot be accessed by user
programs. Only a call to the reification operator may modify these references. This ensures that
the tower structure cannot be messed up by user programs.
The scope of the reification process is limited to individual objects in the interpreter's memory.
For example, the reification of a class does not reify its list of methods methodList nor its
superclass. So, three categories of objects coexist at runtime: reified objects, non-reified (but
4 METAJ does not allow static fields but could be extended easily to deal with such examples.
5 4 is a strict operator. A syntax extension would be necessary to reify the expression (e.g. the AST representing 1+4)
rather than the value denoted by the expression (e.g. the integer 5).
class Name {
Type f1 field f1 ;
Type fn field fn ;
Name(Type f1 arg f1 , ., Type fn arg fn ) { body }
Type m1 method m1 (Type m11 arg m11 , ., Type m 1k arg m 1k ) { body m1 }

Figure

10: Original class definition
reifiable) ones and non-reifiable ones. If a program accesses an object o through a reified one,
the use of restricted exactly as in the non-reflective case. 4Pair.extendsLink, for
example, references a Class representing the superclass of Pair. Therefore, the only valid
operations on this reference are new (4Pair.extendsLink)() 6 as well as accesses to
static fields and members of this class. If the structure or behavior of the superclass is to be
changed, it must be reified first. This implies that accesses to non-reifiable objects through
reified ones are safe.
4.2 Formal definition of the generic reification scheme
Based on the implementation technique outlined above, our generic reification scheme is an automatic
program transformation which can be applied to an arbitrary class, called Name in the following
definition, of the original interpreter. As shown in Figure 10, such classes consist of a number of fields
and methods and must have a constructor with arguments for all of their fields. The transformation of
a set of classes has time and space complexity linear in the number of classes.
The transformation consists of two main steps:
1. Introduce the class BaseName (see Figure 11) which defines the base representation of the
original class Name. This class is very similar to the original class Name.
2. Redefine the class Name (see Figure 12) such that it implements the corresponding dispatch
object. This class provides the same method interface as the original class Name and implements
a method reify() which creates the reified representation and switches from the base
representation to the reified one.

Figure

11 shows the generated base class. (In the figures of this section, we use different style
conventions for verbatim text, schema variables and [text substitutions].) Ba-
sically, the original class is renamed and a field referent is added. Remember that a reifiable entity
is implemented by a dispatch object that points to the current representation. The referent field,
which is initialized in the constructor and points back from the representation to the dispatch object,
is mandatory to distinguish the dispatch object and the representation: if this is not used to access
6 The current parser of METAJ does not allow such an expression: new requires a class identifier. However, the parser
could be easily extended to deal with such expressions and we allow this notation in this paper.
class BaseName {
Type f1 field f1 ;
Type fn field fn ;
Name referent;
BaseName(Type f1 arg f1 , ., Type fn arg fn , Name referent) {
body
Type m1 method m1 (Type m11 arg m11 , ., Type m 1k arg m 1k ) {

Figure

Generated base class
fields or methods in the base class it should denote the dispatch object 7 . In the transformation, this
is implemented by substituting this(~.) (matching the keyword this followed by anything but a
dot) by this.referent.
The generated dispatch class, shown in Figure 12, has two fields: representation that points
to either the base representation or the reified representation, and a boolean field isReified that
discriminates the active representation. Its constructor creates a base representation for the object.
The methods method m i have the same signature as their original version. When the base representation
is active (i.e. isReified is false), the method call is delegated to the base representation.
When the reified representation is active (i.e. isReified is true), the method call is interpreted:
the corresponding call expression is parsed (Parser.java2Exp()), a local environment is built
(argsE.add()) from the method arguments and the field representation of the dispatch object
and the method call is evaluated (eval()). Note that for the sake of clarity, this code is intentionally
naive. The actual implemented version could be optimized: for example, the call to the parser
could be replaced by the corresponding syntax tree.
The method reify() builds a reified representation of the base representation by evaluating a
new-expression. The corresponding class is cloned in order to build a new tower level. So, every
reified object has its own copy of a Class. This way, the behavior of each reified object can be specialized
independently. If sharing is required the application programmer can achieve it by explicitly
manipulating references. Finally, the reified representation is installed as the current representation
and a reference to it is returned. A series of experiments led us to this sharing strategy. A previous
version of the transformation did not clone the class. This sharing led to cycling dependency relationships
and reflective overlap after reification: in particular, reification of the class Class introduced
7 This is a typical problem of wrapper-based techniques that introduce two different identities for an object.
class Name {
Object representation;
boolean isReified;
Name(Type f1 arg f1 , ., Type fn arg fn ) {
new BaseName(arg f1 , ., arg fn , this);
Type m1 method m1 (Type m11 arg m11 , ., Type m 1k arg m 1k ) {
if (this.isReified) {
"reifiedRep.method m1 (arg m11 ,.,arg m 1k )");
Environment
argsE.add("reifiedRep", this.representation);
argsE.add("arg m11 ", arg m11 );
Data
return result.read();
else
return (BaseName)
this.representation.method m1 (arg m11 , . , arg m 1k );
Instance reify() {
if (!this.isReified) {
baseRep_field fn ,
Environment
argsE.add("baseRep_field f1 ", this.representation.field f1 );
argsE.add("baseRep_field fn ", this.representation.field fn );
argsE.add("aClass", aClass);
return (Instance)this.representation;

Figure

12: Generated dispatch class
non-termination. Alternatively, we experimented with one copy of each class per level but in this case
the reification (without modification) of an object could already change its behavior.
This generic reification technique is based on only two assumptions:
1. Each syntactic construct is represented by an appropriate expression during interpreter execu-
tion. We assume that all of these expressions can be evaluated using the method eval(argsE)
where argsE contains the current environment, i.e. the values of the free variables in the current
expression.
2. We assume that the textual definitions of all reifiable classes have been parsed at interpreter creation
time and that they are stored as Class objects in the global environment Main.globalE.
These objects have to be cloneable.
This way, reify() creates an extra interpreter layer based on the actual interpreter definition.
Note that these simple assumptions and the formal definition enable the transformation to be performed
automatically.
In Java, the operator new returns an object (i.e. an Instance). Therefore, in order to let the user
build other runtime entities than Instances, such as Classes and Methods, we provide a family
of deification 8 operators, one for each of these entities. These operators are the inverse of the generic
reification operator. For example, in the reflective program (where r Class denotes the deification
operator for classes):
the right-hand side expression returns a Class dispatch object in front of the Instance created by
new. Note that the deification operators - while functionally inverting the reification operation -
do not change the representation of an object "back" to its unreified structure (e.g. to a BaseClass
in the case of classes).
The dispatch objects engender the structure of the reflective tower; their implementation is not
accessible to the user. In particular, the reification operator and the deification operators encapsulate
the fields representation and isReified of dispatch objects as well as the field referent
from the base class. So, user programs cannot arbitrarily change the tower structure. However, the
user or a type system to be developed should avoid the creation of meaningless structures, such as
r Class (new Method(.
4.3 Example: making the class Instance reifiable
To illustrate the definition of the transformation, we apply it to the class Instance (see Figure 14),
which is used in the examples of reflective programming in the next section. This class implements
objects in the interpreter. For example, a pair object with two fields fst and snd is implemented
by an Instance the field dataList of which contains two memory cells labelled fst and snd.
Its field instanceLink points to a Class containing the methods of the class Pair. The method
lookupData() is called whenever a field of pair is accessed. (For the sake of conciseness, we
did not show the other methods of Instance, such as lookupMethod().)
The application of the transformation defined above to Instance yields the two classes Ba-
seInstance (see Figure 15) and the dispatch class Instance (see Figure 16). Now, pair is
implemented by a dispatching Instance as shown in Figure 13. Its default unreified representation
is a BaseInstance (say b 1
whose dataList field contains the fields labelled fst and snd (see
8 We prefer the term 'deification' [iyl95] to the equivalent terms `reflection' [wf88] and 'absorption' [meu98].
dispatch object
Instance
dispatch object
Instance
denotes
active representation
instance of
a) before b) after
BaseInstance
dataList
instanceLink
Instance
different
representations
dispatch object
Instance

Figure

13: Before and after reification of the object pair
class Instance {
public Class instanceLink; // ref. to Class
public DataList dataList; // field list
Instance(Class instanceLink, DataList dataList) {
// field access
Data lookupData(String name) {
return this.dataList.lookup(name);

Figure

14: Original class Instance
class BaseInstance {
Class instanceLink;
DataList dataList;
Instance referent;
BaseInstance (Class instanceLink, DataList dataList,
Instance referent) {
Data lookupData(String name) {
return this.dataList.lookup(name);

Figure

15: Class BaseInstance

Figure

13a). Once pair has been reified (see Figure 13b), it is represented by an Instance which
points to a BaseInstance (say b 2
). Note that in contrast to the reification of classes shown in Figure
9, the reified representation of an instance is reifiable (because it is an instance itself; hence, the
second dispatching Instance in Figure 13b). Since the reification is based on the actual definition of
the original Instance, the dataList of b 2
contains the three fields instanceLink,dataList
(itself containing fst and snd) and referent. The definition of the method lookupData() in
the dispatch object calls the method lookupData()of b 1
as long as pair is not reified. Once it is
reified, the definition of lookupData() of Instance is interpreted.
In order to prove the feasibility of our approach, we applied this reification technique to different
classes defining object-oriented features of our JAVA interpreter resulting in the prototype METAJ. The
imperative features of the non-reflective interpreter can be tackled analogously. This way we could,
for example, redefine the sequentialization operator ';' in order to count the number of execution steps
in a given method (say m). One way to achieve this is by reification of occurrences of ExpS in reified
m and dynamically changing their classes by a class performing profiling within the eval() method.
Another solution would be to replace ExpS nodes in reified m by nodes including profiling.
Reflective Programming
In this section, we express several classic examples of reflective programming in our framework.
These detailed examples of our reflective interpreter at work should help the reader's understanding
of the system's working.
The examples highlight an important feature of our design: since our reification scheme relies on
the original interpreter definition, the meta-object protocol of the corresponding reflective interpreter
(i.e. the interface of a reflective system) is quite easy to apprehend. It consists of a few classes which
are reifiable in METAJ, the reification operator 4 and the deification operators r .
In

Figure

17 the class Pair is defined, and in main() a new instance pair is created. In the
interpreter, the object pair is represented by an Instance (see Figure 13a). Our generic reification
method provides access to a representation of this Instance which we name metaPair (denoted
by 4pair in Figure 13b). The most basic use of reflection in object-oriented languages consists in
class Instance {
Object representation;
boolean isReified;
Instance(Class instanceLink, DataList dataList) {
new BaseInstance(instanceLink, dataList, this);
Data lookupData(String name) {
if (this.isReified) {
// interpret lookup method call
// pass already evaluated values
Environment
argsE.add("name", name);
argsE.add("reifiedRep", this.representation);
Data
// unpack result
return (Data)result.read();
else
return ((BaseInstance)this.representation).lookupData(name);
Data reify() {
if (!this.isReified) {
// copy the base class BaseInstance
// create and initialize new representation
Environment
argsE.add("baseRep_instanceLink", this.representation.instanceLink);
argsE.add("baseRep_dataList", this.representation.dataList);
argsE.add("aClass", aClass);
return new

Figure

Dispatch class Instance
class Pair {
String fst;
String snd;
Pair(String fst, String snd) {
class PrintablePair extends Pair {
String toString() {
return "(" this.fst
class InstanceWithTrace extends Instance {
Method lookupMethod(String name) {
// trace method-called
System.out.println("method
return this.instanceLink.methodList().lookup(name);
class Main {
void main() {
Pair new Pair("1", "2");
invariance under reification
Instance
test existence of a super class
if (metaClass.getExtendsLink() == null)
System.out.println("Class Pair has no superclass");
class change
method-call semantics
Instance
metaMetaPair.setInstanceLink(InstanceWithTrace);
instance and class deification
System.out.println((r InstancemetaPair).fst);

Figure

17: Examples of Reflective Programming
reifying an object: changing the internal representation without modifying its behavior (see Example
1). Another simple use is introspection. Let us consider the problem of testing the existence of a super
class of a given class. In Example 2, the class Pair (represented by a Class in the interpreter) is
reified which enables its method getExtendsLink() to be called.
In METAJ, reflective programming is not limited to introspection, but the internal state of the
interpreter can also be modified (aka intercession). The third example in main() shows how the
behavior of an instance can be modified by changing its class dynamically. Imagine that we would
like to print pairs using a method called toString(). We define a class PrintablePair which
extends the original class Pair and implements a method toString(). A pair can then be made
printable by dynamically changing its class from Pair to PrintablePair (remember that the
field instanceLink of Instance holds the class of the represented instance, see Figure 15).
Afterwards the object pair understands the method toString().
The fourth example deals with method call tracing for debugging purposes. The class Instance
of the interpreter defines the method Method lookupMethod(String name) that returns the
effective method to be called within the inheritance hierarchy. In our interpreter each lookup-
is followed by an apply(). Thus, method call tracing can be introduced by defining
a class InstanceWithTrace which specializes the class Instance of the interpreter such that
its method lookupMethod() prints the name of its parameter. In order to install the tracing of
method calls of the instance pair, its standard behavior defined in the interpreter by the class Instance
(note that this class can be accessed because the interpreter definition is an integral part of
the reflective system built on top of the reflective interpreter) is replaced by InstanceWithTrace.
Reification of pair provides access to an Instance whose field instanceLink denotes the class
Pair. A sequence of two reification operations on pair provides access to an Instance whose
instanceLink denotes the class Instance. This link can then be set to the class Instance-
WithTrace. A method call of the object pair then prints the name of the method. Therefore,
"toString" is printed by our third example. Finally, note that our tower-based reflection scheme
makes it easy to trace the tracing code if required because any number of levels may be created by a
sequence of calls to 4.
The fifth (rather artificial) example illustrates deification by deifying metaPair and meta-Class
in order to create an instance and a class at the base level. After deification of the reified
representation metaPair we show that base-level operations can be performed on the resulting ob-
ject. In the case of class deification, we restore the original class of pair.
More advanced examples that illustrate our approach rely on the capacity to reify arbitrary parts
of the underlying interpreter. As discussed in Section 4.3, the reification of ExpS allows the behavior
of the sequence operator ';' to be changed. This way, we could, for instance, stop program execution
at every statement for debugging purposes or handle numeric overflow exceptions by re-executing
the current statement block with higher-precision data representations. Furthermore, reification of the
control stack would allow Java's try/catch-mecanism for exception handling to be extended by a retry
variant.
6 The nuts and bolts of generic reification
Section 4 presents the essential parts of the generic reification mechanism. However, the actual implementation
of a full-fledged reflective system requires several intricacies to be handled. In the current
section, we motivate the problems which must be handled and sketch the solution we developed. For
an in-depth understanding of these technicalities we refer the reader to the METAJ source code.
class ExpId extends Exp {
// same fields and constructor as in
Data eval_original(Environment localE) {
// same definition as eval in
Data eval(Environment localE) {
if (!localE.member("#meta_level").booleanValue())
return this.eval_original(localE);
else {
if (this.id.equals("this"))
return new Data(((Instance) localE.lookup("this").read()).referent);
else return eval_original(localE);

Figure

class ExpMethod extends Exp {
Data eval(Environment localE) {
Instance
if (!localE.member("#meta_level").booleanValue())
return this.eval_original(localE);
else {
// evaluate the lhs (object part)
Object
if (o instanceof Reifiable && ((Reifiable) o).getIsReified()) {
// evaluate the receiver
// evaluate the arguments to get a new local environment
Environment new Environment(null, null, null);
argsE.add("#meta_level", new
// lookup the method and apply it
return m.apply(argsE, i);
} else {
if ((o instanceof DataList) && this.methodId.equals(lookup)) {
Environment
return new Data(((DataList) o)
} else . // other delegation cases

Figure

19: Class ExpMethod
First, in the reflective interpreter a reified object is represented by a dispatch object and a reified
representation. So, basically a reified object has two different identities. With our technique, this is
bound to the representation rather than the dispatch object by parsing the expression "reifiedRep.
method m1 (arg m11 ,\dots,arg m 1k )" in the dispatch object (see Figure 12). However, if a statement
return this is to be interpreted, this should denote the dispatch object. Otherwise, user-level
programs could expose the reified representations. The interpreter class ExpId is in charge
of identifier evaluation (including this) and has therefore to be modified to account for this be-
havior. In Figure 18 the method eval() distinguishes two cases by means of the environment-tag
#meta_level. 9 First, interpretation has been initiated by the interpreter's entry point and non-reflective
evaluation is necessary. Second, interpretation has been initiated by a dispatch object and
reflective interpretation is required. In the first case eval_original() is called: this method has
the same definition as eval() in the non-reflective interpreter. In the second case if the identifier is
this, the dispatch object of the current representation is returned. Remember that the field referent
points back from the base representation to the dispatch object, the same mechanism is used to
link the reified representation to the dispatch object. This field must be set by the methods reify(),
so the class Instance has to provide such a field 10 .
Second, remember that the scope of reification is limited to a single object in the interpreter
memory. This means interpretation involves reified and non-reified objects. For example, the reification
of an Instance does not reify neither its field list dataList nor its class denoted by in-
stanceLink. In particular, once an Instance has been reified, the interpretation of its method
lookupData (repeated from Figure 14):
Data lookupData(String name){return this.dataList.lookup(name);}
requires this.dataList to be interpreted and the call lookup(name) to be delegated because
this.dataList denotes a non-reifiable object. In abstract terms, a dispatch object introduces an
interpretation layer (a call to eval()) and this layer has to be eliminated when the scope of the
current (reified) object is left. This scheme is implemented in ExpMethod.eval() (see Figure
19).
Because of these two problems, the methods ExpData.eval() and ExpNew.eval() have
to be modified similarly. This means that our reification scheme cannot be applied to the four classes
ExpId, ExpMethod, ExpData, ExpNew 11 . However, our method provides much expressive
power: these restrictions fix the relationship between certain syntactic constructs and the runtime
system, but the runtime mechanisms themselves can still be modified as exemplified in Section 5. In
order to weaken this restriction, we designed and implemented a variant 12 of our reification scheme
that does not require ExpId and ExpData to be modified. Unfortunately, this advantage comes at a
price: the field referent can be exposed and modified by reification in this case.
7 Discussion of the correctness of the transformation
A complete treatment of the correctness of our technique is beyond the scope of this paper. However,
in this section we discuss very briefly work related to semantics of reflective systems and sketch a few
essential properties constituting a skeleton for a formal correctness proof of our technique.
9 The dispatch objects insert this tag into the local environment.
10 For the sake of simplicity, the code shown in Figures 12 and 16 does not mention the field referent.
11 The restriction that all parts of a reflective system cannot be reified seem to be inherent to reflection [wf88].
This variant is also bundled in the METAJ distribution.
Semantics of reflective programming systems is a complex research domain. Almost all of the
existing body of research work in this domain is about reflection in functional programming languages
[wf88][dm88][mul92][mf93]. Even in this context, foundational problems still exist. For example, it
seems impossible to give a clean semantics which avoids introducing non-reifiable components [wf88]
and logics of programming languages must be considerably weakened in order to obtain a consistent
theory of reification [mul92]. One of the very few formal studies of reflection in a non-functional
setting has been done by Malenfant et al. [mdc96]. This work deals with reflection in prototype-based
languages and focuses on the lookup() ; apply() MOP formalized by means of rewriting
systems. This approach is thus too restricted to serve as a basis for our correctness concerns. In
general, semantic accounts of imperative languages are more difficult to define than in the functional
case. In particular, the transposition of the results obtained in the functional case to our approach
requires further work. We anticipate that this should be simpler in a transformational setting such as
ours than for arbitrary reflective imperative systems.
In order to prove the correctness of our scheme, the basic property to satisfy would be equivalence
between a non-reflective interpreter I nr and a reflective interpreter generated by applying our
transformation to I nr , i.e.
Since the transformation Tr is operating on individual classes, this property can be tackled by
establishing an equivalence between an arbitrary class (say c) of the non-reflective interpreter and its
transformed counterpart. Essentially, the transformation introduces an extra interpretation layer into
the evaluation of the methods of c. Programs and their interpretations introduced by transformation
satisfy the property
This property can be proven by induction on the structure of the AST representation of p. (Note
that the formulation of this property is intentionally simplistic and should be parameterized with
contextual information, such as a global environment and a store.) It can be applied to the dispatch
classes (see Figure 12) to fold interpreting code into delegating code. When the then-branches of
dispatching methods are rewritten using the property from left to right, the then-branches equal the
corresponding else-branches. Henceforth, the conditionals become useless and the dispatch objects
become simple indirections that can be suppressed. In the case of the method reify(), the rewriting
leads to the expression new Name(.) that creates a copy of the non-reified representation.
Finally, we strongly believe our transformation is type-safe (although we did not formally prove
every well-typed interpreter is transformed into a well-typed reflective interpreter. Obviously,
wrongly-typed user programs may crash the non-reflective interpreter. In the same way, some reflective
programs may crash the reflective interpreter, for instance by confusing reflective levels or trying
to access a field which has been previously suppressed using intercession. Specialized type systems
and static analysis methods for safe reflective programming should be developed.
Generating alternative metaobject protocols
We have already mentioned that each set of reified classes along with their definitions determines a
MOP of its own. We think that this is a key property of our approach because it provides a basis for the
systematic development of specially-tailored MOPs. In this section, we modify the message-sending
part of the non-reflective interpreter in order to provide a finer-grained MOP which distinguishes the
sender and the receiver of a message.
class Instance {
// add two new methods
Data send(Msg msg) {
return msg.to.receive(msg);
Data receive(Msg msg) {
return msg.to.lookupMethod(msg.methodId)
class ExpMethod extends Exp {
Data eval(Environment localE) {
// as before evaluate receiver and arguments: o, argsE
// new code: determine sender, build and send message
Instance
new Msg(self, o, this.methodId, argsE);
return self.send(msg);

Figure

20: Alternative original interpreter
class InstanceWithSenderTrace extends Instance {
Data send(Msg msg) {
System.out.println("method called
return

Figure

21: (User-defined) extension of Instance
In the original interpreter, ExpMethod.eval() evaluates a method call by implementing the
composition lookupMethod();apply(). So, the behavior of the receiver of a method call can
be modified easily by changing the definition of lookupMethod() (as illustrated by trace insertion
in the Section 5). However, a modification concerning the sender of the method call (see CODA
[aff95] for a motivation of making the sender explicit in the context of distributed programming) is
much more difficult to implement. Such a change would require the modification of all instances of
ExpMethod in the abstract syntax tree, i.e. all occurrences of the operator '. Indeed, we have to
check whether the object this in such contexts has a non-standard behavior.
A solution to this problem is to modify the non-reflective interpreter, such that its reflective version
provides a MOP enabling explicit access to the sender in a method call. Intuitively, we split message
sending in two parts: the sender side and the receiver side. First, we introduce a new class Msg which
is a four-tuple. For each method call, it contains the sender from, the receiver to, the method name
methodId and the corresponding argument values argsE. Then, two methods dealing with messages
are added to the definition of Instance in the original interpreter: send() and receive()
(see

Figure

20). Finally, ExpMethod.eval() is redefined such that it creates and sends a message
to the receiver.
This new version of the non-reflective interpreter is made reflective by applying our program
transformation. Then, the user can, for example, introduce tracing for message senders (see Figure
21), the same way traces have been introduced in the previous section.
This example highlights three advantages of our approach: MOPs are precisely defined, application
programmers are provided with the minimal MOPs tailored to their needs and language designers
can extend MOPs at compile time without anticipation of these changes.
9 Related work
A comparison between reflective systems is inherently difficult because of the wide variety and the
conceptual complexity of reflective models and implementations. For example, the detailed definition
of the CLOS MOP requires a book [kic91] and a thorough comparison between CLOS and
already fills a book chapter [coi93].
Consequently, we restrict our comparison to the three basic properties our reflection model obeys
(the first and second characterizing Smith-like approaches, the third being fundamental to our goal of
the construction of specially-tailored MOPs):
1. (tower) There is a potentially infinite tower of reflective interpreters.
2. (interpreter) The interpreter at level n interprets the code of the interpreter at level n 1.
3. (selectivity & completeness) Any part of the runtime system and almost all of the syntax tree
(see Section 6) of an interpreter at level n can be reified and has an accessible representation at
level
First, most reflective systems are based on some notion of reflective towers and provide a potentially
infinite number of levels. A notable exception to this are OPEN-C++ [chi95] and IGUANA [gc96]
whose MOPs only provide one metalevel.
Second, our approach is semantics-based following Smith's seminal work on reflective 3-LISP
[smi84] for functional languages. This is also the case for the prototype-based languages 3-KRS
[mae87] and AGORA [meu98]. The other object-oriented approaches to reflection (including OBJ-
VLISP [coi87], SMALLTALK [bri89] [riv96], CLASSTALK [bri89], CLOS [kic91], MetaXa [gol97])
are not semantics-based (in the sense of the second property cited above) because they do not feed
higher-level interpreters with the code of lower-level interpreters. Instead, different levels are represented
by appropriate pointer structures. This proceeding allows more efficient implementations but
has no semantic foundation. Moreover, these reflective languages are monolithic entities while our
modular approach consists of three simple parts: a non-reflective interpreter, the operator 4 and the
operators r .
Third, our approach enables language designers to precisely select which mechanisms of the language
are reflective. With the exception of IGUANA and OPEN-C++, all the reflective systems cited
above do not have this characteristic. Finally, note that our approach shares a general notion of completeness
with 3-LISP, 3-KRS and AGORA: the programming model is defined by the interpreter
and almost all of its features can be made reifiable ("up" and "down" are primitives in 3-LISP and
cannot be reified, for instance). Asai et al. [amy96] also starts from such a complete model but this
interesting approach to reflection in functional languages restricts reifiable entities in order to allow
optimization by partial evaluation. In contrast, the remaining reflective systems described above do
not base reflection on features of an underlying interpreter but implement an ad hoc MOP. The notion
of completeness therefore does not make sense for them.
Conclusion and future work
In this paper we have presented a program transformation technique to generate reflective object
oriented interpreters from non-reflective ones. This technique allows specially-tailored MOPs to be
produced quickly. New MOPs can be developed from scratch or by refinement from existing ones
as exemplified in Section 8. Compared to general MOPs, specially-tailored ones could be tuned, for
instance, towards better efficiency and security properties.
To the best of our knowledge, the resulting framework for reflective object-oriented languages is
the first one satisfying the three basic properties mentioned in Section 9. Consequently, our approach
cleanly distinguishes between reifiable and non-reifiable entities, thus helping the understanding of
reflective programs.
A prototype implementation, called METAJ [metaj], is available.
Future work. We presented a generic reification technique for object-oriented reflective languages,
which provides a basis for the exploration of the metaprogramming design space, optimization techniques
and the formalization of reflective systems.
First, at the system level the design space of MOPs should be explored by defining and refining
different non-reflective interpreters as exemplified in Section 8, yielding a taxonomy of reflective
mechanisms. At the user level, the proliferation of reflective dialects requires appropriate design and
programming tools, including libraries of user-friendly reflective operators, program analyses and
type systems.
Second, reflection is deeply related to interpretation. Each dispatch object introduces a new interpretation
layer by calling the method eval(). So, specialization techniques like partial evaluation
[bn00] are prime candidates for efficiency improvements. Furthermore, user-written reflective programs
may not use all reflective capabilities provided by a reflective interpreter (e.g. only make use
of a bound number of reflective levels). In this case, optimization techniques such as that presented
by Asai et al. [amy96] could be used to merge interpretation levels.
Third, since reflective programming is a rather complex task, it should be based on a formal
semantics, e.g. to define and ensure security properties. We believe that our transformation could be
used to generate specially-tailored reflective semantics from a non-reflective one.
Finally, we firmly believe that our reification technique can also be applied to (parts of) applications
instead of an interpreter in order to make them reflective (preliminary results can be found in a
related paper by the authors [ds00]).

Acknowledgements

. We thank the anonymous referees for their numerous constructive comments
and the editor Olivier Danvy. The work reported here has also benefited from remarks by Kris de
Volder, Shigeru Chiba and Jan Vitek. It has been improved through many discussions with our colleagues
Noury Bouraqadi, Mathias Braux and Thomas Ledoux.



--R


Duplication and Partial Evaluation - For a Better Understanding of Reflective Languages


Programming with Explicit Metaclasses in SMALLTALK.
A Metaobject Protocol for C
are First Class Objects: the OBJVLISP Model.
"Object-Oriented Programming: The CLOS perspectives?"

Intensions and Extensions in a Reflective Tower.
On the lightweight and selective introduction of reflective capabilities in applications.
Design Patterns.
Design and Implementation of a Meta Architecture for Java.

Using Meta-Objects to Support Optimisation in the Apertos Operating System
Sun Microsystems
The Art of the Metaobject Protocol.
Concepts and Experiments in Computational Reflection.
A Semantics of Introspection in a Reflective Prototype-Based Language
Towards a Theory of Reflective Programming Languages.
http://www.
"Prototype-based Programming"
M-LISP: A Representation-Independant Dialect of LISP with Reduction Seman- tics
SMALLTALK: a Reflective Language.
Reflection and Semantics in LISP.
The Mystery of the Tower Revealed: A Non-Reflective Description of the Reflective Tower
--TR

--CTR
Gregory T. Sullivan, Aspect-oriented programming using reflection and metaobject protocols, Communications of the ACM, v.44 n.10, p.95-97, Oct. 2001
Manuel Clavel , Jos Meseguer , Miguel Palomino,  Reflection in membership equational logic, many-sorted equational logic, Horn logic with equality, and rewriting logic, Theoretical Computer Science, v.373 n.1-2, p.70-91, March, 2007
reflection;language implementation;OO languages;program transformation