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)        .reduce((a, b) => a..addAll(b));}

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:

@overridebool 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!

Follow me on Twitter: https://twitter.com/thosakwe