Compiler Writing: A Basic Static Type System

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:

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

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