# Too Much Theory, Part 3

This is the 3rd and last part of this blog!  (thank heavens!), where I wax poetic about Lattices and Type Theory, and their applications to Compilers and in particular Java JITs. Part 1: Too Much Theory Part 2:  Too Much Theory, Part 2 ## A Quick Recap We’re building a lattice, to allow us to do exciting optimizations on Java programs.  Our lattice has distinguished top and bottom types, and is Commutative, Associative, and Symmetric.  We understand pointers can be null, not_null, or unknown (e.g. bottom).  Because of symmetry across the lattice centerline, we also have the dual of not_null which we’ll call any_null.  For this recap, we’ll also have Java Classes (e.g. String), but we’re going to ignore subclassing for the moment.  Our lattice looks something like this: Wow, that’s getting fancy…  lets revisit some of the elements in this lattice real quick: * bottom: All possible values, including null, as computed by running the program.  No constants. * String:bot: All possible Strings, including null, as computed by running the program.  No constants, no XMLNodes.  For brevity I will sometimes refer to this as String (no trailing :bot notation). * XMLNode:bot or plain XMLNode: All possible XMLNodes, including null, as computed by running the program.  No constants, no Strings. * bottom:not_null: All possible values, as computed by running the program.  No constants, no null. * String:not_null: All possible Strings, as computed by running the program.  No constants, no XMLNodes, no null. * String:hello_world: The constant String “hello world”, and nothing else. * null: The constant null. * String:any_null: All possible String constants, all at once.  No XMLNodes, nor null.  An impossible situation in a real program, but a useful mathematical notion when running Constant Propagation. * String:top: All possible String constants and the null constant, all at once.  No XMLNodes. * top: All possible constants, including all Strings and all XMLNodes and null, and all them all at once. Notice the symmetry: ever Node below the centerline of constants also appears in dual form above the centerline.  The edges are also symmetric: e.g. top has 4 edges out and bottom has 4 edges in, String:top has 1 in, 2 out, and String:bot has 2 in, 1 out, etc. This lattice will let us find the constants in code like this example from last time:

final class LinkedListThing {
LinkedListThing _next; // instance field
int hashCode() {
int hash = 0;
Object x = this; // x is LinkListThing:not_null
while( x != null ) {
hash += x.hashCode(); // x is LinkListThing:not_null
if( x instanceof LinkedListThing )
x = ((LinkedListThing)x)._next; // x is LinkedListThing
else // with Conditional Constant Propagation...
x = "fail"; // ...this path is dead
// x is LinkedListThing:bottom and not a String
}
return hash;
}
}

## And Now Gentle Readers, Let Us Ponder Subtypes Java, of course, has subtypes. So does C++ and many other languages. Lets take a look at what it would take to add subtypes to our lattice. This tiny program snippet makes exactly a Hashtable:

  Hashtable x = new Hashtable(); y = x.get(); // Calls Hashtable.get

And this snippet makes a known subclass of Hashtable, but treats it like a Hashtable:

  Hashtable x = new Provider();  y = x.get(); // Calls Provider.get

And this snippet mentions an UNknown subclass of Hashtable:

  void foo( Hashtable x ) {      y = x.get(); // Calls ???