Metalevel Programming and Reflection --- Basic idea: metalevel programming allows you to reprogram your compiler or interpreter, for a variety of purposes. Some purposes include: 1. extending the language. (E.g., adding new control constructs, an object system, or whatever.) 2. changing the implementation of the language to give different performance characteristics. 3. allowing you to adapt the implementation of the language to different underlying systems. 4. allowing systems code to see past normal abstraction layers and operate on lower-level abstractions. For example, a data structure pickler or a parameter marshaler for an RPC system may need to see how objects are implemented so that they can be communicated by serial writing or messaging. --- Metalevel programming is programming about programming. This is closely related to notion of reflection, but some people think reflection is a stronger notion. I'll get to that in a while. In a very general sense of "metalevel programming," a conventional compiler can be viewed as a metalevel program---it takes as input a program in one representation, and spits out a program in another representation. We don't usually call that metalevel programming, however, because we we don't do it from WITHIN the language in question. A compiler for Eiffel or Self might be written in C or C++, rather than in Eiffel or Self itself. A clearer example of metalevel programming is a Scheme (or Self or Smalltalk) compiler that's accessible from within a running system, and which produces code that can then be used from within that running system. Another clear example is an eval function (whether implemented with an interpreter, or by compile-and-run as in RScheme). An eval function lets you take data structures in the language (e.g., S-expressions) and convert them to runnable form, and run them. The key thing to notice here is that you've taken something that's at the "level" of data structures, and converted it into something that's at a higher level---a procedure that is ABOUT data structures. Another example is the use of macros. If you can write macros within the language you're using, and they generate code in the language that you're using, that's metalevel programming: you're using the language to compute results that are expressions in the language itself, which are executable in the language. We might also view the use of first-class and higher-order functions as metalevel programming. MAP is a function that's about other functions (and data structures), for example. Creating a closure of a procedure to specialize it is similarly "meta". We won't usually talk about this as metalevel programming, partly just because it's so commonly accepted. We'll usually reserve the term "metalevel programming" for things that are funkier and "more advanced". (That's partly just politics and accidents of history.) --- Reflection Reflection is a controversial term, sometimes used in a weak sense to include any kind of metalevel programming. There are two other, more stringent criteria that are often used for the term "reflection", however: * the transformation of expressions in the input language must result in something that's in "the same" language. For example, if a Lisp system implements the control structure COND as a Lisp macro that translates to IF expressions, then we may have a reflective Lisp system in that sense---it takes Lisp expressions and translates them into Lisp expressions. Notice, however, that in this case we may translate from a larger dialect of Lisp, which includes the COND, into a smaller one that may not. (Actually, we'd likely translate cond using a recursive macro that generates an IF for the first COND clause, and a nested COND for the remaining COND clauses; each macroexpansion would strip one clause out of the COND, and recursively macroexpand that until a simple IF would handle the last one.) * it must be possible to view the running program and its state as data, modify it, and have those changes affect the future course of the computation. The latter condition is the big one, in many people's minds. We'll call systems like that "seriously reflective". An example of a "seriously reflective" system is an old-fashioned Lisp interpreter that lets you look at and modify the S-expression representation of an existing procedure, modify it, and have that change the meaning of the procedure. (Notice that this is NOT possible in standard Scheme---once you create a procedure, the meaning of that procedure is fixed. But in many old Lisps, you could do it.) Next time you call the modified procedure, it will do whatever the new S-expression says. More generally, this is an example of the notion of REIFICATION, which just means "making real". A reflective language lets you "make real" things that are not normally first class, like the code body of a procedure. Another requirement of serious reflection is that you be able to perform computations over this reified stuff, and then push the resulting representation back down into the implementation (e.g., replace a function definition with a modified definition). These changes must CAUSALLY AFFECT the computation. (e.g., if you later call the procedure, the new definition is the one that's used.) In the case of a simple, old-fashioned Lisp system, this is easy---you can just side-effect the S-expression, and since that's the actual executable (interpretable) code, the effects happen trivially. You can make a reflective compiled system, too, though, with a bit of work. A reflective Scheme system could have a feature that supplies you with the original S-expression used to compile a Scheme procedure, let you compute a new S-expression, and then recompile the procedure using that. (I.e., change the code pointer of the closure to point to the new version.) Then next time you call the closure, it'll execute the new version. A seriously reflective system therefore has two important and related features: 1. Reification, i.e., the ability to create a representation of the program in the language of the program, and 2. Reflection proper, i.e., the ability to take a representation in the language and "push it down" into the implementation of the program. (And this must causally affect the future of the computation.) The first step exposes the implementation of a program to examination, while the second step exposes it to modification. Notice that one of these two steps is called "reflection", but often people won't call a system "reflective" unless it does both. Confusing, huh? --- Reflection and self-modifying code If you're familiar with the concept of "self-modifying code", this probably sounds familiar---and dangerous. It should sound dangerous, because it is, in its full generality. Back in the bad old days, some people used to write a fair amount of self-modifying code in machine language. A program would actually overwrite its own code, to change the way it would behave in the future. One reason was to save space---if you knew that an initialization procedure would only be used once, it might finish the initialization by replacing that code with something that would be used later. Another reason was to avoid conditional branches. A piece of code that could be written with a conditional branch might be replaced with an unconditional piece of code if it was known that future executions would always take the same branch. One thing people learned from bitter experience self-modifying code is that it's usually a BAD IDEA, because it's very difficult to understand. You can't just look at a program and see what it does, because the program will change when it runs. You have to reason very carefully about when and how the program will change. (Recently, some compiler writers have taken to generating self-modifying code for normal source programs. This can generate code that's faster than the usual way compilers generate code, and the compiler writer takes responsibility for ensuring that the compiler gets it right. A smart compiler writer will only use this kind of trick very carefully in a well-thought-out framework.) Self-modifying machine code can be seriously reflective. A program can read its own code, perform computations on it (like parsing the instruction formats to distinguish between different operations and operands), then modify the code in a way that depends on that computation. It can do reification trivially, because the representation it sees is the executable, just like S-expressions in an old-fashioned Lisp system, but closer to the hardware. It can do reflection trivially, too, because overwriting instructions changes the executable program. --- Basic Problems with Reflection One huge problem with self-modifying code (of the machine code or S-expression variety) is that it's TOO LOW-LEVEL TO UNDERSTAND. There is no built-in FRAMEWORK to make it clear to programmers which things it's reasonable to change and which things it's not. This is THE big problem in reflective systems---how do you organize the program so that it's clear what the consequences of a change will be. Another major problem is that it makes it hard for the language implementor to implement the language correctly and efficiently. When you design a language implementation, you design the parts together so that they preserve certain invariants. If procedure calling can only happen in certain ways, for example, the compiler may be able to inline some procedures into others. If self-modifying code is allowed without a proper interface to the compiler, the inlined versions won't get updated when the original changes. Supporting fully general self-modifying code limits the compiler-writer's options, making it difficult or impossible to perform many optimizations that would otherwise be straightforward. These reasons explain why Lisp programmers are discouraged from using EVAL, and encouraged to use weaker constructions like closure creation instead. It's a lot easier to understand closures, because even though their associated data (environments) may be different, a closure's code is fixed by the code for the lambda expression or procedure definition that created it. It helps in understanding the program that you can see ALL of the code, even if you can't see all of the ways code gets interconnected at run time. --- Weaker Forms of Metalevel Computation Serious reflection is clearly too powerful to be a good thing to use under many circumstances---it's so general that it's easy to screw things up. Weaker forms of metalevel computation may be useful in many circumstances and easier to use safely and efficiently. For example, using macros allows you to write program transformations within a program. For macro systems like Lisp's, these transformations can be written in the same language as the one they'll be used with---expressions in the language are first-class objects in the language, can be computed over in the language, and the result can causally affect the program because they affect how it will be compiled. On the other hand, this typically all occurs at compile time, before the program starts running. This makes it much easier to reason about the program, and to compile it to efficient code. The macros may cause strange transformations, but all of the transformations can be figured out statically. The resulting code can be understood by the programmer or optimized by the compiler without thinking about the possibility of the program code changing as it runs. Still, macros can definitely cause confusion. A proliferation of nonstandard special forms can make it difficult to parse the basic syntax of the language. Heavy use of macros that transform code in subtle ways can obscure the semantics as well. Similarly, as we mentioned before, using higher-order functions can make programs harder to reason about, because they blur the distinction between code and data. What a procedure will do depends on runtime details of which environment it is closed in. --- OK, SO WHY DO IT (Part I)? Given these problems, there's a really good question as to whether reflection (or weaker forms of metalevel programming) are good ideas at all. The main reason is that not all modules of all programs can be sensibly written using the same abstractions. Some modules only need to know about the normal interfaces to other modules, while other modules need to know more. Metalevel programming allows you to program a system using multiple interfaces at different levels of abstraction. This in itself is a powerful abstraction tool, allowing you to express multiple interfaces more or less explicitly. Any powerful abstraction tool is going to be subject to serious abuse, but often the cleanest solution will be the one using powerful abstractions. I believe that often a program must be written with different parts operating at different levels of abstraction, and that the language itself must have different levels of abstraction as well as supporting program modules that do. Before giving an example, here's a metaphor. Consider the different interfaces to a car. There's the standard driving interface, where pushing on the accelerator makes the car go faster, turning the wheel to the left makes it turn left, and so on. But that's not the only interface you need to a car. You need to be able to change the oil, adjust the timing, and so on. The former interface might be called the "normal" interface, and the others might be called the "maintenance" interface. A crucial part of this metaphor is that there IS a mainenance interface, which is limited. There's a set of things that most relatively mechanically inclined people can do to a car, given the owner's manual, even if not all drivers are competent to do this. And that's different from the "expert mechanic" interface, which allows you to tear the car apart and put it back together again. --- Now here's a programming example: suppose you want to write a debugger or data structure inspector, which lets you examine an arbitrary object. A normal program, doing normal things, only needs to understand the standard interface to an object, i.e., what generic functions or messages it responds to it, and some set of rules for using it, and what kinds of things will result---all at some "normal" level of abstraction. That interface is supposed to be all that normal code relies on. An inspector, on the other hand, may be required to display the contents of an object so that it can be understood better by a programmer. The programmer may need to see INSIDE the object, past the usual abstraction barriers. The inspector needs to have "metalevel" priveleges to break the usual abstraction barriers. On the other hand, that does NOT mean that the browser should just throw away ALL abstraction and look at a bunch of raw bits. It should probably be able to ask some module to tell it the names and types of the fields of the objects, and things like that. Then it can draw some representation of the object on the screen, e.g., following all of the pointers in an object and displaying their referents too. Another (similar) example is a PICKLER. A pickler is a program that writes a data structure out to a file, and allows it to be read back in again by an UNPICKLER. (This is like Lisp READ and WRITE, but a little fancier---when it writes a data structure out, the pickler notices shared structure and encodes it specially, i.e., it doesn't turn DAGs into trees, etc. When the unpickler reads the structure back in, it gets a data structure with the same shape, including cycles and whatnot.) Browsers and picklers therefore need to be able to view objects at a lower level, violating the normal abstractions but still seeing a certain level of abstraction---things with fields. --- Another example, in the area of procedures rather than plain data structures, is a code analyzer. For simplicity, assume we have a language like Pascal where all procedure calls are resolved statically, but unlike Pascal, procedures are first class. (A code analyzer for a more interesting language is more complicated.) We might want to be able to write a program that looks at each procedure to see what procedures it calls, and displays a call graph showing which procedures depend on other procedures. Similarly, in an object-oriented system with first-class classes, you may want to know all of the direct and indirect superclasses of a given class, or all of the direct and indirect subclasses. You'd like the class objects to support this, by having methods that return lists of superclasses or subclasses. This is a particularly instructive example. First-class class objects are a very good place to put the information about the instances of a class. If you want to know how an object is structured, you ask the object that controls its structure---the class object that created it. This is a very natural organization; the object encodes its own state, but the class object describes the general characteristics it has by virtue of being an instance of that class. In effect, the normal objects provide interfaces to normal data for normal purposes, and the class objects provide a structured interface to the implementations of the objects. They provide (among other things) as a structured interface to the compiler or interpreter. Notice that in conventional language implementations, the compiler must build class-like objects. When a compiler encounters a class definition, it builds some reprsentation of the class, which it uses when compiling code that refers to the instances of that class. For example, it must decide how to lay out the fields, and it uses that information later when compiling code that accesses those fields. A conventional compiler then throws most of this information away, making it difficult to write code that must cross abstraction boundaries. --- Metaobjects We're now talking about metaobject-based programming systems. The best Example of this is the CLOS (Common Lisp Object System) MOP (MetaObject protocol). (A lot of the features of the CLOS MOP came from a generalization of concepts that were in Smalltalk before that. There are also other new MOP-based systems.) A metaobject is just an object that's ABOUT other objects. Classes are metaobjects, because they're "about" their instances. Generic functions may be viewed as metaobjects, because they're "about" the classes they dispatch for and the methods they dispatch to. There are other types of metalevel programming systems, which don't depend on object-oriented programming. In an object-oriented system, however, it's natural that the metalevel facilities should be organized in an object-oriented way. (We will focus on object-oriented systems, but there are also reflective logic programming and functional programming systems. There are also reflective object-oriented systems that aren't class based, but we believe the class framework is useful, at least for our current explanatory purposes.) --- OK, SO WHY DO IT (Part II)? Besides the need to write low-level "systemsy" code like inspectors and picklers, there are several important motivations for building a system that allows metalevel programming. The basic idea is to expose parts of the language implementation in a controlled, comprehensible way, to allow it to be reprogrammed fairly flexibly. In effect, parts of the compiler (and maybe the runtime support system) are exposed, allowing the language to be extended or reimplemented from within the language This is convenient for several reasons: * Providing a Comprehensible Framework. It allows the language implementation itself to be modular and comprehensible, separating out high-level and low-level concerns. The high-level issues are dealt with in the metalevel programming system, and the low-level issues are dealt with by a fairly conventional compiler for the "base" (simple, nonreflective) part of the language. * Integrating code in different dialects of the language. Since the compiler is programmable at a high level, it can be used to provide alternative compilation modes to translate different dialects of a language. (This was originally one of the major goals of the CLOS MOP: it allowed integration of code written in several different dialects of Common Lisp, with different object systems.) * Extending or changing the language. It allows the language to be extended in new ways, without requiring understanding or modification of the guts of the main compiler. * Reimplementing parts of the language to improve performance. While people often think of reflective and metalevel programming as ways to change languages, it is important to recognize that often the goal is to change the implementation of the language while preserving the old abstractions. This lets you view the language implementation as modular, with the ability to plug in a new version of a module to improve performance while preserving the same "interface" (i.e., language semantics). That is, the semantics may be preserved while changing the mapping from the high-level language to the base language. (This may be done in an application-specific way, to adjust design tradeoffs to favor what the application benefits from.) --- Providing a Comprehensible Framework There are several advantages of splitting compiler design into base-level and meta-level components. One is simply that it works, and separation of concerns has obvious advantages for developing and debugging the system. Where it is difficult to separate the concerns of the levels, it is often a valuable educational experience---it reveals deep issues that should be dealt with explicitly, rather than by developing a compiler as a monolithic mass of code with many interdependencies. It can be argued that this is not unique to metalevel programming systems, because any compiler can be designed in a modular, layered way. In a metalevel programming system, however, the developer exposes key parts of the internal design to other users (systems programmers) as a supported interface. This means that the designer is forced to make more issues clear and (ideally) deal with them cleanly. Another advantage is that providing a published interface provides a means for sharing code across different implementations of the base language. Developers of different base-language compilers can share code that implements high-level features. This ability of (relatively) normal programmers to do metalevel programming can be viewed as a liability, because it may lead to excessive language tinkering and a proliferation of incompatible dialects. It has a large advantage, though, in that it provides a means of testing the robustness and generality of the metalevel programming system---a conventionally structured compiler is unlikely to have its mechanisms thoroughly tested and its design assumptions exposed early. Early experimentation may lead to consensus on a better language design, and reduce proliferation of incompatible dialects in the long term. In our view, bringing high-level language implementation decisions into the open leads to a better design in the long run. --- Integrating Different Dialects of a Language A crucial aspect of language design is providing for interoperatibility with existing code in different dialects of an evolving language. Metalevel programming can be used to program a compiler to accept some code in one language and some code in another, and let them interoperate. Naturally, this is limited by the semantic differences between the languages, but for relatively similar languages, it is possible to support relatively clean and efficient interoperability. An example of this is the integration of modules written in the New Flavors and CommonLoops dialects of object-oriented CommonLisp. With the CLOS MOP, it is possible to program CLOS to emulate New Flavors or Loops, and let code written in one invoke objects created by the other. The base language is the same (Common Lisp), and a single dynamic dispatch mechanism can suffice for both. Differences in syntax, inheritance resolution, and other important features can be handled by metalevel programming---each language can be compiled in a different way to work with the same base language and runtime dispatch mechanism. Metalevel programming facilites also appear to offer support for creating "foreign function interfaces" between modules written in very different languages, such as Lisp and C. Macros and metaobject methods in one language can be used to provide semi-automatic mechanisms for analyzing the types used in one language, and converting them to the types needed in another automatically. --- Extending or Changing the Language As in the examples of the data structure inspector and pickler, it is often necessary for "systems" programs to operate at a lower level of abstraction than normal programs. A well-designed system should have a well-specified "systems" programming interface. It should be possible to write code at a fairly low level of abstraction, without losing all abstraction, e.g., having to deal with objects as patterns of bits. This is important for a variety of "systems" programming tasks, such as writing an RPC stub generator or foreign function interface, and for adding features for concurrency and fault tolerance. Consider the case of adding checkpointing to a language. This is usually difficult and awkward, but with a well-designed metalevel programming language it might not be. The metalevel programming system could be used to redefine the low-level code used for assignments, and add bookkeeping code that keeps track of which objects or areas of memory are "dirty" (modified since the last checkpoint), and write them out at the next checkpoint. Another case is persistence. The PCLOS (Persistent Common Lisp Object System) provides persistence by changing the way classes are implemented, so that objects can be automatically faulted into memory from disk, and stored back to disk. This is done by providing a new kind of class (using metaclasses) whose instances' methods actually check to ensure that the object is present in memory before doing the normal work of the method. If it's not, they invoke code to fetch the object. --- Reimplementing Parts of the Language Another useful form of metalevel programming is changing the implementation of an existing language construct. For example, one might provide a library that analyzes CASE statements and compiles them to particularly efficient forms. This analyzer might be better than the one built into the base compiler, and it would be convenient to be able to load the new definition of case (perhaps as a macro that does code analysis) as part of a library. Another example is the reimplementation of the layouts of objects. One might provide a library that analyzes data structures and provides a different mapping onto low-level storage, to save space or time. (For example, fields might be packed to save space, or padded to word boundaries to make them faster to access, or stored sparsely if most fields usually have a certain default value. Likewise, an object might be stored in compressed form and uncompressed as needed to operate on it.) The key thing to notice about these examples is that they do not change any of the semantics of the language, but instead adjust the implementation's performance characteristics. Naturally, if these things are implemented incorrectly, many things may break. But that's true of any module that lots of other modules depend on. (If it's an argument against allowing reimplementation of the language, it's also an argument against allowing reimplementation of any important, shared module of a program.) Another example we find interesting is to allow the reimplementation of the storage manager of the language, within the language. To a first approximation, you can do this in C---you can write your own malloc and free routines, and replace the standard ones with those. This is trickier for a language with more interesting storage management, such as Eiffel or Smalltalk's garbage collectors. To support replacement of the GC by metalevel programming, it would be necessary to have a well-defined GC interface, and the ability to write the new GC in the language. We think that this is more appropriate for a language at approximately the level of C, and are interested in designing a systems programming language which supports garbage collection in a modular, replaceable way. (This language should also let you bootstrap higher-level language features such as a strongly-typed but dynamic object system, from within the language.) ---