Build a basic static type system, and prevent unnecessary runtime bugs!

For many, if not all programming languages, a significant part of static analysis is data type analysis. If a compiler can categorize expressions into predictable types, then you can prevent many errors, such as passing a string into a function where an integer was expected. Type theory can often be complex to understand, so let's create a very basic one.

The type system we create today, for a fictional language called "Bloop" will be similar to that of C or Java and take the shape of a tree.

## Type Model

First, let's figure out what a type looks like:

class BloopType {
String name;
BloopType parent;
List<BloopType> children;
List<BloopField> fields;
}

class BloopField {
String name;
BloopType type;
}

• Every type needs some sort of name to distinguish it from other types. At the end of the day, a type system doesn't really undersand that a Foo is different than a Bar; the only difference is the name.
• In future continuations of this article, we'll replace basic names with more descriptive signatures, so that we can support composable types like tuples.
• Because our type system is a tree, every type has a parent. The only "orphan" type is the type at the root of our tree. In a language like Java, the root type is Object.
• In addition, types are aware of their children.
• Types often define fields, which are symbols local to instances of that type.

## Hierarchy

The benefit of having a tree-based type system is that we can easily traverse it and analyze relationships by means of simple loop constructs.

For example, to find the root type:

BloopType get root {
BloopType type = this;

while (type.parent != null)
type = type.parent;

return type;
}


You can also get a list of every type that extends the current type.

List<BloopType> get allDescendants {
return children
.map((c) => c.children)
}


## Comparing types

That being said, it is trivial to determine that two types are exactly equal to each other, provided that the names of types are unique:

@override
bool operator==(other) {
return other is BloopType
&& other.parent == parent
&& other.name == name;
}


In practice, compilers often need to determine if a type a is assignable to a type b; that is to say, a is either equal to or a child of b.

The following logic is taken from my current project, Bonobo:

static BloopType findCommonAncestor(BloopType a, BloopType b) {
BloopType compare = b;

// Try comparisons, left to right
do {
if (a == compare) return compare;
compare = compare.parent;
} while (!compare.isRoot);

// Try comparisons, right to left
compare = a;
do {
if (b == compare) return compare;
compare = compare.parent;
} while (!compare.isRoot);

// Other
return Root;
}

bool isAssignableTo(BloopType other) {
return other == Root || findCommonAncestor(this, other) != Root;
}


The above will function where Root represents the type at the root of the tree.

## Conclusion

Though static typing is often complicated and involves multiple computations, a tree-based type hierarchy can make type resolution much more efficient and simpler to understand. Go out and try it yourself!