Christophe is a software architect at Hewlett-Packard. He worked on the HP C++ compiler for IA-64 and on an IA-64 virtual machine. He can be reached at [email protected].
Java has been successful, in part, because of its simplicity. On the other hand, this simplicity also means that some useful techniques are not easily available to Java programmers. For instance, in "Does Java Support Design by Contract?" (DDJ, November 1999), Krishnan Rangaraajan discussed various ways to add contract programming, popularized by Eiffel, to Java programs. In this article, I'll examine another way of adding not only programming by contract, but also other features (such as symbolic derivation) to Java and (in the future) other languages.
Listing One is a simple Java extension. Obviously, the code is not valid Java. The troublesome (yet interesting) part is the line:
double y = d(Math.sin(2 * omega * t + theta) * Math.exp(-decay * t))/dt;
Because this is not valid Java, you get an error (there is no function d, and no variable dt) if you run it as-is through a Java compiler. Interestingly, the errors the compiler emits are semantic errors, not syntactic ones. In other words, this line could be a valid statement with the proper definitions.
Even if the code is not valid Java, it is clear to any mathematician that that line is a computerized approximation of the standard notation for the derivative. But Java does not include derivative as part of its definition. This is not a problem for most users. But if you need them, having to manually compute derivatives on a regular basis can be tedious and error prone. It's even more frustrating knowing that the process is easy to automate and that even some pocket calculators today contain symbolic derivation packages.
Moka is a tool designed for precisely this kind of situation. Symbolic derivation is not useful to most people, so chances are that it will never become part of a mainstream computer language. Yet, when you need it, you need it badly. In this case, you would like to extend Java to support it. That's exactly what Moka lets you do. Listing Two is a work session with Moka in which Listing One is compiled. As you can see from the resulting intermediate file, Moka (more precisely, the derivation plug-in invoked through the +derivation command-line option) has processed the symbolic derivative and turned it into the corresponding legal Java statement.
The way this works is conceptually simple. Moka turns the Java input into a parse tree, just like any Java compiler would. The parse tree is richer, however, so that it can be used to reconstruct the source code almost identically. Even comments are preserved so that tools such as javadoc keep working. Also, Moka trees are designed as an exchange format rather than as a private structure that lives only inside a single compiler. This is important for the second phase, where the +derivation command-line option instructs Moka to invoke the corresponding derivation plug-in, and pass it the parse tree. The derivation plug-in then loops over the parse tree, recognizing what looks like derivative notations, and applies simple tree rewrite rules corresponding to computing a symbolic derivative. The plug-in then returns the parse tree to Moka. The last phase is where Moka renders the modified parse tree as a well-formatted Java source code.
Separation of Roles
The physical separation between Moka and the plug-ins is important. Moka itself is a fairly large piece of code: Parsing and rendering Java code is not trivial, although in that respect Java is one of the simplest existing languages. On the other hand, the tree manipulations involved for symbolic derivation are simpler. Proper separation of the roles allows simple plug-ins to be short and simple to write. For example, the derivation plug-in is less than 500 lines of simple C++ code, including comments. (The complete Mozart package, including Moka, is available electronically from http://mozart-dev.sourceforge.net/ and DDJ; see "Resource Center," page 5.)
This simplicity is important. It is possible to perform some kind of symbolic derivation in C++ using template metaprogramming. But this approach is complex and puts a high workload on the poor C++ compiler. Moka is an alternative that is simpler for you. What's more, it is available for Java developers who are unable to use templates and template meta-programming techniques.
Plug-ins can easily be chained, making them powerful tools. This is similar to how UNIX pipes can be used to combine UNIX text-processing tools such as awk or grep to perform more complex operations. Getting back to the derivation example, Listing Two contains unfortunate inefficiencies, such as this subexpression:
(0*omega*2*0)*t+2*omega *1+0
This is a natural result of the automated process used to compute the symbolic derivative. Naturally, the derivation plug-in could be enhanced to automatically simplify the result, but this is not the best way to do it. Expression simplification may have other uses, so why not make it a separate task, hence a separate plug-in? This other plug-in, called "constantfold," not only does normal constant folding (such as replacing 1+1 with 2), but also performs additional mathematical simplifications (such as replacing 0*X with 0 and 1*X with X). Listing Three shows how the constantfold plug-in can be applied on the output of the derivation plug-in, resulting in a much more legible (and efficient) Java code.
The overall objective of Moka is that you can develop custom plug-ins to perform chores that are specific to the application you are developing. This turns Moka into a user-extensible Java compiler, which can be used to implement application-specific Java idioms. This does not prevent the most useful plug-ins to be shared between programmers. It is not impossible that some particularly useful Java extension becomes somewhat standard. Hopefully, an ecosystem of Moka plug-ins will emerge, offering Java programmers a powerful toolchest. But the existence of standard plug-ins is not necessary for Moka to be useful because its primary goal is to let you write your own plug-ins.
Semantic Extensions
Recall I said that the errors a normal Java compiler emitted for Listing One were semantic errors, not syntactic ones. The reason this was important may be easier to understand now. Moka needs to turn the input into a tree that it can pass to the plug-ins. While Moka does not run a Java semantics phase (and therefore does not detect, for instance, that there is no variable named dt), it contains a relatively standard Java parser. So input files need to be syntactically valid. Since there is no clear definition of what is a syntactically valid but semantically invalid Java program, Moka accepts some inputs that are arguably not even syntactically valid. But this is an artifact of the actual implementation rather than a design choice.
Moka therefore implements semantic extensions, not syntactic ones. Most other tools and Java preprocessors generally focus on syntactic extensions. For instance, other Java preprocessors that implement assertions rely on invalid Java tokens, such as @assert. Moka will not accept an input that contains @assert any more than any other standard Java compiler. On the other hand, it accepts an input containing assert(X==0) because this is a valid syntax for a function call. This is why a Moka-based assertions plug-in adds support for assertions using, for instance, a syntax similar to a function call with a special function name (assert being a good choice).
The Moka package contains such a plug-in, implementing Eiffel-like Design-by-Contract with assertions, preconditions, postconditions, and class invariants. Listing Four is an implementation of the traditional Java stack using the extension. Listing Five shows the result of preprocessing the source in Listing Four with the assert plug-in and assertions enabled. Listing Six shows the result with assertions disabled. Listing Five is invalid as long as an assertion_failed method is not supplied. As another illustration of the simplicity of Moka plug-ins, the whole assert plug-in is less than 400 lines of C++ (including comments).
The semantics-based design ensures that all Moka-based Java extensions will look like Java to a large extent. This is important for lowering the learning curve. Plug-ins must not only be easy to implement, they should also be easy to use. This also eases cooperation between various plug-ins as they all operate on similar-looking structures. Lastly, this design fits well in a complete Java compiler implementation. In the long run, Moka will likely turn into a full-blown Java compiler, possibly by reusing the existing GNU Java compiler back-end. This makes the current "render to Java source code" phase unnecessary and will speed up compilation significantly. In such a complete implementation, the plug-ins would be invoked right after parsing the source code, and the result fed to normal semantics and code generation phases.
Language and Compiler Independence
In the context of an ecosystem of Java extensions, plug-in developers need to take into consideration how their extensions cooperate with other extensions. For plug-ins to cooperate, they need to work correctly not only on standard Java, but also on extended Java versions (such as our Java + symbolic derivative example). The simplest way to achieve these objectives is to make sure that plug-ins are focused. Having tiny, very specific plug-ins makes cooperation much easier. For instance, the derivation plug-in only looks for combinations similar to df(expression)/dX or d(expression)/dX, respectively. The rest of the program is ignored. This makes the plug-in insensitive to many other source-code manipulations that might occur because of other plug-ins.
At this point, you might ask why the plug-in should be Java dependent at all. After all, something like d(2*X+sin(X))/dX is a syntactically valid C/C++ expression as well. It would even be accepted in non-C languages such as Pascal, Ada, or Eiffel. Not only does the expression look similar, but its structure is identical (at the parse-tree level), regardless of the language. For instance, even if the syntax is slightly different, the two following statements (the first one in C and the second one in Pascal) would have similar, if not identical, parse trees:
Y = *ptr + f(X).field; /* C version */
Y := ptr^ + f(X).field; (* Pascal version *)
For this reason, the Moka parse trees have been designed from the ground up to be language independent to the maximum possible extent.
In fact, the term "Moka plug-in" is a slight misnomer. Moka is a contraction of "Mozart's Kafee" and is a Java front-end for a development environment called "Mozart." Mozart is a set of APIs, file formats, and utilities that help development tools cooperate and exchange information about the application under development. What I called "Moka plug-ins" are actually Mozart tools that perform simple transformations on a Mozart tree.
Moka was the first front-end developed for Mozart, for a couple of reasons: Java is a simple language to parse, compared, for instance, to C++; and Java has a large audience, making Moka quite useful to many developers.
Other front-ends and Mozart tools are currently being designed or implemented. Most of my work currently is on a new language called "LX" that takes full advantage of Mozart's capabilities. All these tools share a common way to exchange data, so a plug-in that works for Java and does not rely on Java-specific structures is likely to work for C, LX, or any other language. And since Mozart is an open-source project (released under the GNU General Public License), you can contribute your own tools.
The Mozart Object Model
Before implementing a simple plug-in, you need to understand the overall Mozart architecture and, in particular, the Mozart object model, which is characterized by properties such as: introspection, run-time extension of objects, dynamic dynamic dispatch, persistence, and garbage collection.
Introspection is the possibility for the application to query type information (such as the fields of a class, the size of an object, and so on), based on the dynamic type of the object. Introspection simplifies the description of recursive algorithms on trees composed of objects of different types. For instance, an if has three children (the condition, the then part and the else part); a while has only two (the condition and the body). However, semantics can be described in a fairly generic way for both: Apply semantics recursively on all children, then apply type-specific semantics. The same is true for large numbers of compilation-related algorithms. Java users are accustomed to reflection, which is an introspection superset.
Run-time extension of objects lets tools scribble their own private data on existing objects. This makes it simpler for tools to cache information about objects they manipulate, possibly in a persistent way. For instance, the derivation plug-in records the basic operations it performs on the various arithmetic nodes, so that users can understand how the result was formed.
Normal dynamic dispatch is the invocation of methods based on the dynamic type of objects, rather than their static types. In C++, virtual functions implement dynamic dispatch. Dynamic dynamic dispatch is a kind of dynamic dispatch where new methods and new classes can be added at run time, and where the actual method invoked for a given (type, signature) pair can be updated at run time. For instance, the derivation plug-in adds a DoDerive method to implement the actual derivation, which is then applied to standard Mozart classes.
Persistence is the possibility to store objects in a persistent format, for instance on disk. Persistence is much simplified with introspection. The Mozart persistence model is particular only because type information is persistent, allowing tools to operate on objects of unknown types. In particular, the derivation plug-in doesn't have any built-in knowledge about Java-specific constructs such as the synchronized statement. It can still process these nodes correctly thanks to type information passed by Moka.
Garbage collection is an automatic way to manage memory. Data structures manipulated by development tools are generally arbitrary graphs. This makes it complex to keep track of who owns a particular node and is responsible for its destruction. This is even more problematic when a tool operates on a graph that it did not create. In Mozart, the system keeps track of how various objects reference each other. For performance reasons, the Mozart garbage collector is a simple mark-and-sweep collector that uses reflective information to know where pointers are in the various objects. Garbage collection in Mozart is explicit; it happens only when the application requests it. Applications can avoid garbage collection when the graph is in an inconsistent state.
Neither Java nor C++ offer all the necessary functionality. The Mozart object model was therefore built on top of C++ classes. Mozart objects are called "notes." The particular notes representing source-code elements derive from the Coda class and are collectively called "Coda notes." The reflective type information is stored in special notes called "tones." The information about methods and method dispatch is represented by "performers." The persistent format is called a "melody" file. Table 1 summarizes the main Mozart entities you need to know about. Table 2 lists some of the most important Coda classes.
To make it easier to create Mozart notes and tones, four pseudokeywords were added to C++: tone, ref, performer, and perform. These keywords are eliminated by the standard C++ preprocessor when compiling C++ sources, but they are used by a separate tool to generate reflective type information and method dispatch tables.
- tone defines a Mozart class. Its usage is similar to that of class.
- ref defines a reflective class data member, which is visible in the reflective type description. It is used before the member declaration.
- performer declares a method and the method arguments. performer(X) is used as a pseudofunction name.
- perform declares or defines the implementation. perform(X,Y) indicates the application of performer(X) to the tone Y.
Example 1 is a Point class (tone) containing two integer data members called x and y. For the sake of illustration, Point derives from the CodaTerminal class that represents terminal values such as names, integral constants, and so on. Since the declarations of x and y are prefixed with ref, they will be stored in the corresponding tone and available at run time.
Example 2 declares a performer called Offset, which offsets the first terminal with the second one. It also shows two implementations of the performer for types CodaInteger and Point.
The Tracer Plug-In
The tracer plug-in insert calls to methods called BeenThere and DoneThat at the beginning and end of every method, respectively. The idea is that tracer can be used as a poor man's debugging tool letting you, for instance, take the time spent in every method or check other, more application-specific conditions. Listing Eight shows the output of the plug-in when applied to input in Listing Seven. The DoneThat calls are laced in a finally structure so that they are invoked whether the method exits because of an exception or through natural return.
Listing Nine is the complete tracer implementation:
- The mozart.h include file contains all public Mozart declarations. This is normally the only file a plug-in needs to include to refer to Mozart entities.
- The Tool::Init() call initializes the Mozart run time.
- The GCRoot class is a template class that behaves like a pointer but serves as a root for the garbage collector. Anything referenced from a root will not be discarded by garbage collection. GCRoot<Note> behaves like a Note pointer.
- The Melody::Read static method reads a Melody file and returns the corresponding top-level note. When a plug-in is invoked, Moka passes it the name of a temporary file containing a Melody representation of the source file. In the future, plug-ins that can be invoked as shared libraries will be supported as well, avoiding the Melody serialization process.
- The NoteIterator iterates over all notes referenced from the top note. This particular form of a note iterator returns pointers to note pointers. This makes it possible to replace elements of the tree in place. Be aware that this simple form of note iterator will not necessarily work well on arbitrary graphs.
- In the main loop, a condition filters the definition of methods. Method definitions are represented by a CodaDeclaration entity with a CodaFunctionType type and a nonnull CodaBlock initializer. This excludes, for instance, C function declarations (which have no initializer) or object declarations (whose type is not a CodaFunctionType). IsA checks if a given object belongs to a given class (the Mozart equivalent of the Java instanceof operator). "X_T" is the name of the tone generated by tpp for the C++ class named "X."
- The name of the declaration is isolated because this is precisely the name I will insert as an argument to the BeenThere and DoneThat calls. I also add an integer argument in second position with a unique integral identifier for every method I trace.
- The plug-in replaces the function body with a single try-finally statement containing the initial block in the try, following a newly created BeenThere call. In the final part, I simply insert a DoneThat call.
- At the end of the loop, the plug-in invokes the garbage collector using the GC() function. This is not strictly necessary in that case, since I am about to exit the plug-in.
- The plug-in finally writes the modified source code back to the temporary melody file it came from. This is how the result is returned to Moka, which will then display the corresponding Java source code.
Conclusion
Mozart is a fairly complex environment, but effort has been put into making it both easy to use and immediately useful. By letting you tailor your Java environment to suit your needs, Moka offers significant improvements in productivity. For more information and plug-in examples, visit the Mozart web site at http://mozart-dev.sourceforge.net/.
DDJ
Listing One
// This example demonstrates the symbolic derivation "plugin"
class Test
{
public static final double omega = 3.276;
public static final double theta = 0.227;
public static final double decay = 1.447E-3;
public static int main(String args[]) {
// Tabulate the following expression
for (double t = 0.0; t < 50.0; t += 0.01) {
double y = d(Math.sin(2 * omega * t + theta)
* Math.exp(-decay * t))/dt;
System.out.println("t=" + t + ", y=" + y);
}
return 0;
}
}
Listing Two
[~/Development/mozart/moka] ddd% ./moka tests/derivation.java
+derivation -o /tmp/derivation.java ; javac /tmp/derivation.java
[~/Development/mozart/moka] ddd% cat /tmp/derivation.java
/* Generated by Moka using moka.stylesheet */
// This example demonstrates the symbolic derivation "plugin"
class Test
{
public static final double omega = 3.276;
public static final double theta = 0.227;
public static final double decay = 0.001447;
public static int main(String[] args)
{
// Tabulate the following expression
for(double t = 0; t < 50; t += 0.01)
{
double y = Math.cos (2 * omega * t + theta) * ((0 * omega + 2 * 0)
* t + 2 * omega * 1
+ 0) * Math.exp
(-decay * t) + Math.sin (2 * omega * t + theta)
* (Math.exp (-decay * t) * (-decay * t + -decay * 1));
System.out.println ("t=" + t + ", y=" + y);
}
return 0;
}
}
/* Thank you for using Moka. */
[~/Development/mozart/moka] ddd%
Listing Three
[~/Development/mozart/moka] ddd% ./moka tests/derivation.java
+derivation +constantfold -out
/* Generated by Moka using moka.stylesheet */
// This example demonstrates the symbolic derivation "plugin"
class Test
{
public static final double omega = 3.276;
public static final double theta = 0.227;
public static final double decay = 0.001447;
public static int main(String[] args)
{
// Tabulate the following expression
for(double t = 0; t < 50; t += 0.01)
{
double y = Math.cos (2 * omega * t + theta) * (2 * omega) * Math.exp
(-(decay * t)) + Math.sin (2 * omega * t + theta)
* -(Math.exp (-(decay * t)) * (decay + decay * t));
System.out.println ("t=" + t + ", y=" + y);
}
return 0;
}
}
/* Thank you for using Moka. */
Listing Four
class Stack
{
public Stack() { objects = new Object[MAX]; top = 0;
}
public void Push(Object o) { objects[top] = o; top++; }
public Object Pop() { top--;assert(top >= 0);return
objects[top]; }
public int Size() { return top; }
private int Remaining() { return MAX - top; }
private Object[] objects;
private int top;
private static final int MAX = 10;
preconditions()
{
Push: top < MAX;
Pop: top > 0;
}
postconditions()
{
Push: top > 0;
}
invariants()
{
top >= 0;
top <= MAX;
}
}
Listing Five
/* Generated by Moka using moka.stylesheet */
class Stack
{
Stack()
{
objects = new Object[MAX];
top = 0;
}
public void Push(Object o)
{
try
{
if(!(top >= 0))
assertion_failed ("invariant #1 on entry in Push", 1);
if(!(top <= MAX))
assertion_failed ("invariant #2 on entry in Push", 2);
if(!(top < MAX))
assertion_failed ("Push precondition #1", 0);
objects[top] = o;
top++;
}
finally
{
if(!(top > 0))
assertion_failed ("Push postcondition #1", 3);
if(!(top >= 0))
assertion_failed ("invariant #1 on exit from Push", 4);
if(!(top <= MAX))
assertion_failed ("invariant #2 on exit from Push", 5);
}
}
public Object Pop()
{
try
{
if(!(top >= 0))
assertion_failed ("invariant #1 on entry in Pop", 7);
if(!(top <= MAX))
assertion_failed ("invariant #2 on entry in Pop", 8);
if(!(top > 0))
assertion_failed ("Pop precondition #1", 6);
top--;
if(!(top >= 0))
assertion_failed ("Pop assert #11", 11);
return objects[top];
}
finally
{
if(!(top >= 0))
assertion_failed ("invariant #1 on exit from Pop", 9);
if(!(top <= MAX))
assertion_failed ("invariant #2 on exit from Pop", 10);
}
}
public int Size()
{
try
{
if(!(top >= 0))
assertion_failed ("invariant #1 on entry in Size", 12);
if(!(top <= MAX))
assertion_failed ("invariant #2 on entry in Size", 13);
return top;
}
finally
{
if(!(top >= 0))
assertion_failed ("invariant #1 on exit from Size", 14);
if(!(top <= MAX))
assertion_failed ("invariant #2 on exit from Size", 15);
}
}
private int Remaining()
{
return MAX - top;
}
private Object[] objects;
private int top;
private static final int MAX = 10;
}
/* Thank you for using Moka. */
Listing Six
/* Generated by Moka using moka.stylesheet */
class Stack
{
Stack()
{
objects = new Object[MAX];
top = 0;
}
public void Push(Object o)
{
objects[top] = o;
top++;
}
public Object Pop()
{
top--;
// Nop;
return objects[top];
}
public int Size()
{
return top;
}
private int Remaining()
{
return MAX - top;
}
private Object[] objects;
private int top;
private static final int MAX = 10;
}
/* Thank you for using Moka. */
Listing Seven
class Point {
int x, y;
Point() { System.out.println("default"); }
Point(int x, int y) { this.x = x; this.y = y; }
// Point instance is explicitly created at class initialization time:
static Point origin = new Point(0,0);
// A String can be implicitly created by a + operator:
public String toString() {
return "(" + x + "," + y + ")";
}
}
Listing Eight
/* Generated by Moka using moka.stylesheet */
class Point
{
int x, y;
Point()
{
try
{
BeenThere ("Point", 0);
System.out.println ("default");
}
finally
{
DoneThat ("Point", 0);
}
}
Point(int x, int y)
{
try
{
BeenThere ("Point", 1);
this .x = x;
this .y = y;
}
finally
{
DoneThat ("Point", 1);
}
}
// A Point instance is explicitly created at class initialization time:
static Point origin = new Point (0, 0);
// A String can be implicitly created by a + operator:
public String toString()
{
try
{
BeenThere ("toString", 2);
return "(" + x + "," + y + ")";
}
finally
{
DoneThat ("toString", 2);
}
}
}
/* Thank you for using Moka. */
Listing Nine
#include "mozart.h"
ulong uid = 0;
int main(int argc, char **argv)
{
if (argc < 2)
{
fprintf(stderr, "Usage: %s <filename>\n", argv[0]);
exit(1);
}
// Initialize, parse parameters and read input
Tool::Init();
GCRoot<Note> top = Melody::Read(argv[1]);
// Loop on all notes, and identify declarations of interest
NoteIterator it;
for (Note **n = it.First(&top.ptr); n; n = it.Next())
{
CodaDeclaration *dcl = (CodaDeclaration *) *n;
if (dcl
&& dcl->IsA(CodaDeclaration_T)
&& dcl->initializer
&& dcl->decl_type
&& dcl->decl_type->IsA(CodaFunctionType_T)
&& dcl->initializer->IsA(CodaBlock_T)
&& dcl->name
&& dcl->name->IsA(CodaName_T))
{
CodaBlock *block = (CodaBlock *) dcl->initializer;
String name = ((CodaName *) dcl->name)->value;
Tune<CodaExpression *> args;
// Create the "BeenThere" and "DoneThat" calls
args.Append(new CodaString(name)).Append(new CodaInteger(uid++));
CodaCall *pre = new CodaCall(new CodaName("BeenThere"),args);
CodaCall *post = new CodaCall(new CodaName("DoneThat"),args);
// Insert "BeenThere" at beginning
block->instructions.Insert(0, pre);
// Create finally block for "DoneThat"
CodaBlock *final = new CodaBlock;
final->instructions.Append(post);
Tune<CodaCatch *> finally_clauses;
finally_clauses.Append(new CodaFinally(final));
CodaTry *only_statement = new CodaTry(block,finally_clauses);
block = new CodaBlock();
block->instructions.Append(only_statement);
dcl->initializer = block;
}
}
GC();
Melody::Write(argv[1], top);
return 0;
}
