CITkit

Hobbes Tree Intermediate Representation

Hobbes is a language based on Andrew Appel's Tiger language which he invented for his Modern Compiler Implementation in X books. (If doing Java, look for an early edition with Tiger.) Appel made certain "interesting" choices to make implementing the compiler "interesting" (like dealing with the dangling else problem). I didn't want my students at Calvin College worrying about these things, so I tweaked the language to make it a bit simpler. I've used and developed this library during compiler and programming-language courses at Calvin.

And, yes, Hobbes is Calvin's Tiger. Ha!

Visitor Pattern

The most important (and best tested) part of the library is the ExpressionTIR hierarchy. It provides the hierarchy of types for an implementation of the visitor pattern. The visitor half is provided by the ExpressionTIRVisitor<T> interface. Each of the subclasses of ExpressionTIR has an accept(ExpressionTIRVisitor<T>) method which, in turn, triggers the appropriate method from the given visitor.

I could write this Java code:

class ShellOfAVisitor implements ExpressionTIR<String> {
  public String visitIntegerETIR(IIntegerETIR i) {
    return "an integer";
  }
  public String visitStringETIR(IStringETIR s) {
    return "a string"
  }
  // and many more visit methods...
}

IntegerETIR (which implements the IIntegerETIR interface) has an accept(ExpressionTIR<String>) method which will trigger the visitIntegerETIR(IIntegerETIR i). This is done for all of the subclasses of ExpressionTIR, each calling the appropriate visit method. Check out this sequence diagram:

You can implement algorithms over the hierarchy by implementing a visitor. In the sequence diagram above, you'd only have to implement Main and the Visitor.

If you find the hierarchy too much for your needs (not going to implement records?), feel free to generically implement the appropriate visitor methods.

Interfaces for Testing

The whole ExpressionTIR hierarchy is implemented with interfaces. This is to make testing easier with mock objects. (I recommend JMock and really recommend EasyMock.) Each IType interface has a corresponding Type class which implements the interface.

If you're not interested in having working software, you're free to ignore testing and use just the implementing classes.

The Hierarchy

I've broken the hierarchy into several parts so that we don't have to read one giant UML class diagram. First, the primitives:

Nil/null, integers, and strings. Straightforward. Second, core expressions:

IOperatorETIR is for arithmetic operations. ISequenceETIR is for a sequence of expressions that would be executed in sequence (e.g., a block of statements in Java). The rest are self explanatory.

Next, variables and functions:

You can create some simple environments with a ILetETIR. Functions are saved as lambdas and can be called.

L-value expressions are a bit tricky. Hobbes has support for records and arrays, so an l-value consists of one variable and as many field access and array subscripts as you want. ILValueReferenceETIR is for a l-value expression reference; IAssignmentETIR is for an assignment to an l-value. To implement an actual l-value expression, you need the LValueTIR hierarchy:

This has its own LValueTIRVisitor<T> interface.

Finally, you'll want to create records and arrays:

IRecordETIR is for a list of field assignments (each one implemented as a IFieldAssignmentTIR, not part of the expression hierarchy). IArrayETIR is for creating a new array.