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 aBar
; 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 isObject
.- In addition, types are aware of their
children
.
- In addition, types are aware of their
- 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