What Type Systems Are and Are Not – Part 1

Introduction

Programmers are typically taught to think of the type system in languages (particularly object-oriented languages) as being a way to express the ontology of a problem.  This means it gives us a way to model whether one thing “is a” other thing.  The common mantra is that inheritance lets us express an “is a” relationship, while composition lets us express a “has a” relationship.  We see some common examples used to demonstrate this.  One is taxonomy: a dog is a mammal, which is an animal, which is a living creature.  Therefore, we would express this in code with a class LivingCreature, a class Animal that is a subclass of LivingCreature, a class Mammal that is a subclass of Animal, and a class Dog that is a subclass of Mammal.  Another one is shapes: a rectangle is a quadrilateral, which is a polygon, which is a shape.  Therefore, we similarly have a class hierarchy Shape -> Polygon -> Quadrilateral -> Rectangle.

There are problems with thinking of the type system in this way.  The biggest one is that the distinction between “is a” and “has a” is not as clear-cut as it is made out to be.  Any “is-a” relationship we can think of can be converted into a “has-a” expression, and vice versa.  A dog is a mammal, but that is equivalent to saying a dog has a class (a taxonomic class, as in “kingdom phylum class order…”, not a programming language class) that is equal to “mammal”.  A quadrilateral is a polygon, but that is equivalent to saying it has a side count, which equals 4.  We can define a rectangle with “has-a” expressions too: it has four angles, and all are equal to 90 degrees.

We can also express what we might typically model in code as “has-a” relationships with “is-a” statements as well.  A car has a color, which can equal different values like green, red, silver, and so on.  But we could also define a “green car”, which is a car.  We could, though we probably wouldn’t want to, model this with inheritance: define a subclass of Car called GreenCar, another called RedCar, another called SilverCar, and so on.

There are well-known examples of when something we might naturally think of as an “is-a” relationship turns out to be poorly suited for inheritance.  Probably the most common example is the “square-rectangle” relationship.  When asked if a square is a rectangle, almost everyone would answer yes.  And yet, defining Square to be a subclass of Rectangle can cause a lot of problems.  If I can construct a Rectangle with any length and width, I will end up with a Square if I pass in equal values, but the object won’t be an instance of Square.  I can try to mitigate this by making the Rectangle constructor private, and define a factory method that checks if the values are equal and returns a Square instance if they are.  This at least encapsulates the problem, but it remains that the type system isn’t really capturing the “squareness” of rectangles because the instance’s type isn’t at all connected to the values of length and width.

If these objects are mutable, then all bets are off.  You simply can’t model squareness with inheritance for the simple reason that an object’s type is immutable.  But if the length and width of a rectangle are mutable, then its “squareness” is also mutable.  A rectangle that was not a square can become a square, and vice versa.  But the instance’s type is set in stone at construction.  Most of the discussions I’ve seen around this focus on the awkwardness or arbitrariness of how to implement setLength and setWidth on a Square.  Should these methods even exist on Square, and if so, does setting one automatically set the other to keep them equal?  But I believe this awkwardness is a mere side effect of the underlying problem.  No matter what, if I can set the length and width of a Rectangle, I can make it become a Square, and yet it won’t be a Square according to the type system.  I simply can’t encapsulate the disconnect between the Square type and actual squareness (which is defined by equality of the side lengths) for mutable Rectangles.

So what do I do?  I use composition instead of inheritance.  Instead of Square being a subclass of Rectangle, Rectangle has a property isSquare, a bool, and it checks the equality of the two side lengths.  That way, the answer to the “is it a square” question correctly consults the side lengths and nothing else, and it can change during the lifetime of a particular rectangle instance.  This also correctly prevents me from even trying to “require” that a Rectangle is, and will be for the rest of its life, a Square; a promise that simply can’t be made with mutable Rectangles.

The same problem exists elsewhere on a type hierarchy of shapes.  If a Rectangle is a subclass of Quadrilateral, then the quadrilateral’s angles (or more generally, vertices) better not be mutable, or else we’ll end up turning a quadrilateral into a rectangle while the type system has no idea.  We have the same problem with immutable quadrilaterals that we would have to make the constructor private and check the angles/vertices in a factory method to see if we need to return a Rectangle (or even Square) instance.  The problem exists again if Quadrilateral is a subclass of Polygon.  If the number of sides/vertices is mutable, we can turn a Quadrilateral into a Triangle or Pentagon, and we’d similarly have to worry about checking the supplied vertices/sides in a factory method.

Types as Constness Constraints

We can see that, because whether something is an “is-a” or “has-a” relationship is not really a meaningful distinction (we can always express one as the other), this doesn’t tell us whether it is appropriate to express a concept using the type system of a programming language.  The square-rectangle example hints at what the real purpose of the type system is, and what criteria we should be considering when deciding whether to define a concept as a type.  The fundamental consideration is constness.  What do we know, 100%, that will never be different, at the time we write code?  When a certain block of code is executed, what are we sure is going to be the same every time it executes, vs. what could be different each time?  The type system is a technique for expressing these “known to always be the same” constraints.

Such constraints exist in all programming languages, not just compiled languages.  This is why I must resist the temptation to refer to them as “compile-time constants”.  There may be no such thing as “compile time”.  Really, they are author-time constraints.  They are knowledge possessed at the time the code is written, as opposed to when it is executed.

These constraints come in several forms.  If I call a function named doThisThing, I am expressing the knowledge, at authorship time, that a function called doThisThing exists.  Furthermore, this function has a signature.  It takes n parameters, and each of those parameters has a type.  This means every time the doThisThing function is executed, there will be n parameters of those types available.  This is a constant across every execution of the function.  What varies is the variables: the actual values of those parameters.  Those can be different every time the function executes, and therefore we cannot express the values as authorship-time constraints.

Where function signatures express what we know at authorship time about the invocation of a code block, the type system is a way of expressing what we know about a data block.  If we have a struct SomeStruct, with three members firstMember, secondMember and thirdMember of types int, float and string respectively, and we have an instance of SomeStruct in our code, we are saying that we know, for every execution of that code, that it is valid to query and/or assign any of those three members, with their respective types.  The other side of this coin is we know it is invalid to query anything else.  If we write someStruct.fourthMember, we know at authorship time that this is a programming error.  Fundamentally, we don’t have to wait to execute the code and have it throw an exception to discover this error.  The error exists and is plainly visible in the written code, simply by reading it.  The type system provides a parsable syntax that allows tools like the compiler to detect and report such an error.

Inheritance vs. Composition

The implication of this is that the fundamental question we should be asking when deciding to model something with a type is: are we modeling an authorship-time known constant?  If the need is to create a constraint where something is known to be true every time code is executed, the type system is the way to do that.  Inheritance and composition represent different levels of constness.  Or, rather, they represent different aspects of constness.  If I define a GreenCar as a subclass of Car, I am creating the ability to say I know this car is green, and will always be green.  If I instead define a Car to have a member called color, then I am saying I know that every car always has a color, but that color can change at any time.

What can I do with the composition approach that I can’t do with the inheritance approach?  I can change the color of a car.  What can I do with the inheritance approach that I can’t do with the composition approach?  Well, the exact opposite: I can guarantee a car’s color will never change, which allows me to do things like define a function that only takes a green car.  I can’t do that with the composition approach because I would be able to store a passed-in reference to a GreenCar, then later someone with the equivalent reference to the Car could change its color.

The more “const” things are, the more expressive I can be at compile time.  On the other hand, the less I can mutate things.  Both are capabilities that have uses and tradeoffs.  The more dynamic code is, the more it can do, but the less it can be validated for correctness (another way to think of it is the more code can do, the more wrong stuff it can do).  The more static code is, the less it can do, but the more it can be validated for correctness.  The goal, I believe, is to write code that is just dynamic enough to fulfill all of our needs, but no more, because extra dynamism destroys verifiability with no advantage.  It is also possible to allocate dynamism in different ways.  If we need code to be more flexible, instead of relaxing the constraints on existing code, we can create new code with different constraints, and concentrate the dynamism in a place that decides, at runtime, which of those two codepaths to invoke.

Now, you’re probably thinking: “that’s not why I would chose not to model a car’s color as types”.  The obvious reason why that would be insane is because the number of colors is, at least, going to be about 16.7 million.  So to exhaustively model color in this way, we’d have to write literally tens of millions of subclasses.  Even if we delegated that work to code generation, that’s just an absurd amount of source code to compile (and it would probably take forever).  It simply isn’t practical to do this with the type system.

Problems of practicality can’t be ignored, but it’s important to understand they are different than the problem of whether it would correctly express the constness of a constraint to model it with types.  This is because practicality problems are problems with the expressiveness of a language, including its type system.  These problems are often different across different languages, and can be eliminated in future iterations of languages in which they currently exist.  If it is simply inappropriate to use the type system because something is genuinely dynamic, this isn’t going to change across languages or language versions, nor is it something that could be sensibly “fixed” with a new language version.

To illustrate this, it is possible to practically model a color property with types in C++.  C++ has templates, and unlike generics in other languages, template parameters don’t have to be types.  They can be values, as long as those values are compile-time constants (what C++ calls a constexpr).  We can define a color as:

struct Color
{
  uint8_t r, g, b;
};

Then we can define a colored car as:

template<Color CarColor> class ColoredCar : public Car
{
  …
  Color color() const override { return CarColor };
  …
};

Then we can instantiate cars of any particular color, as long as the color is a constexpr:

ColoredCar<Color {255, 0, 0}> redCar;

We will presumably have constexpr colors defined somewhere:

namespace Colors
{
  static constexpr Color red {255, 0, 0};
  static constexpr Color yellow {255, 255, 0};
  static constexpr Color green {0, 255, 0};
  static constexpr Color blue {0, 0, 255};
  …
} 

Then we can write:

ColoredCar<Colors::red> redCar;

We can define a function that only accepts red cars:

function acceptRedCar(const ColoredCar<Color::red> redCar);

Of course none of this makes sense unless color is a const member/method on Car.  If a car’s color can change, it’s simply wrong to express it as a type, which indicates an immutable property of an object.

This kind of thing isn’t possible in any other language I know of.  So if you aren’t working in C++, you simply can’t use the type system for this, for the simple reason that the language isn’t expressive enough to allow it.  It may be a different type of problem, but it’s a problem nonetheless.  So the decision to use the type system to express something must take into account both whether it the thing being expressed is really an authorship-time constant, and whether the language’s type system is expressive enough to handle it.

Even in C++, there are other problems with modeling color this way.  Just like with the square-rectangle, if we construct a Car (not a ColoredCar), whose color happens to be red, it doesn’t automatically become a ColoredCar<Colors::red>.  A dynamic cast from Car to ColoredCar wouldn’t inspect the color member/method as we might expect it to.  We would have to ensure at construction that the correct ColoredCar type is selected with a factory method.  Now, there are likely other properties of a car we might want to model this way.  I often use cars as a way to demonstrate favoring composition over inheritance.  A car has a year, make, model, body type, drivetrain, engine, and so on.  Notice I said has a.  I could also say a car is a 2010 Honda Civic sedan, automatic transmission, V4.  The “classic” reason to avoid inheritance is the fact that “is-a” relationships are very often not simple trees.  We would need full-blown multiple inheritance, which would cause a factorial explosion of subtypes.  If I wanted to model all these aspects of a car with inheritance, I would really need something like:

template<uint Year, CarMake Make, CarModel<Make> Model, CarBodyType BodyType, TransmissionType TransmissionType, Engine Engine, Color CarColor> TypedCar : public Car
{
  ...
}

That’s already a pretty big mess, and it’s only that tidy (which isn’t so tidy) thanks to the unique power of C++ templates.  In any other language, you’re now talking about writing the classes 2010RedHondaCivicSedanAutoV4, 2011RedHondaCivicSedanAutoV4, 2010GreenHondaCivicSedanAutoV4, 2010RedHondaAccordSedanAutoV4, and so on more or less ad infinitum.  God forbid you’d actually start going down this path before you realize the lack of multiple inheritance blows the whole thing up even while ignoring the utter impracticality of it.

But this isn’t really enough.  With this two-level inheritance structure, I can either say to the compiler “I know this object is a car, and I know nothing else about it”, or “I know everything about this car, including its year, make, model, etc.”.  To be fully expressive I would want to be able to model between these extremes, like a car where I know its make, model and color, but I don’t know anything else.  I don’t even think C++ templates can generate the full web of partially specialized templates inheriting each other that you’d need for this (though I’m hesitant to assert that, I’ve been consistently shocked at what can be done, albeit in ridiculous and circuitous fashions, with C++ templates.  That doesn’t really change the conclusion here though).

So, long story short, it’s probably never a good idea to model a car’s color, or any of its other attributes, even if they are const, with the type system, because it’s not practical.  However, I want to emphasize that this really is a problem of practicality.  Future languages or language versions may become expressible enough to overcome these limitations. The point is we need to augment our “do I know this now, at authorship time, or only at runtime?” question, particularly when the answer “I know it at authorship time”, with another question: is it practical, given the language capabilities, to express a constraint with the type system? If the answer is no, then we fall back to composition and must sacrifice the automatic authorship time validation. We can instead do the validation with an automated test.

Demonstrating the Concepts

Okay, after all that theory, let’s go through an example to illustrate what the real lesson is here.  The type system is a tool available to you to turn runtime errors into compile time errors.  If there’s ever a point in your code where you need to throw an exception (and throwing an exception is definitely better than trying to cover up the problem and continue executing), think carefully about whether the error you’re detecting is detectable at authorship-time.  Are you catching an error in an external system, that you genuinely don’t control, or are you catching a programming error you might have made somewhere else in your code?  If it’s the latter, try to design your type system to make the compiler catch that error where it was written, without having to run the code.

If you ever read the documentation for a library and you see something like this:

You must call thisMethod before you call thisOtherMethod.  If you call thisOtherMethod first, you will get a OtherMethodCalledBeforeThisMethod exception

That’s a perfect example of not using the type system to its full advantage.  What they should have done was define one type that has only thisMethod on it, whose return value is another type that has only thisOtherMethod on it.  Then, the only way to call thisOtherMethod is to first call thisMethod to get an instance of the type that contains thisOtherMethod.

Let’s say we have a File class that works this way:

class File
{

public:

  File(const std::string& path); // Throws an exception if no file at that path exists, or if the path is invalid

  void open(bool readOnly); // Must call this before reading or writing

  std::vector<char> read(size_t count) const; // Must call open before calling this method;

  void write(const std::vector<char>& data); // Must call open with readOnly = false before calling this method

  void close(); // Must call when finished to avoid keeping the file locked.  Must not call before calling open
};

Now, let’s list all of the programming errors that could occur with using this class:

  1. Calling the constructor with an invalid path
  2. Calling the constructor with the path for a nonexistent file
  3. Calling read, write or close before calling open
  4. Calling write after calling open(true) instead of open(false)
  5. Calling read, write or open after calling close
  6. Not calling close when you’re done with the file

Think about all of these errors.  How many are genuinely runtime errors that we cannot know exist until the code executes?  There’s only one.  It’s #2.  #1 might be a runtime error if the path is built at runtime.  If the path is a compile-time constant, like a string literal, then we can know at compile-time if it’s an invalid path or not.  We can’t know whether a file at a particular valid path exists at the time of execution until we actually execute the code, and it can be different each time.  We simply must check this at runtime and emit a runtime error (exception) appropriately.  But the rest of those errors?  Those are all authorship-time errors.  It is never correct to do those things, which means we know at the time the code was written we did something wrong.

So, let’s use the type system to turn all of those errors, except #2, and #1 for dynamically built paths, into compile time errors.

First, let’s consider #1.  The underlying issue is that not every string is a valid file path.  Therefore, it’s not appropriate to use std::string as the type for a file path.  We need a FilePath type.  Now, we can build a FilePath from a string, including a dynamically built string, but we might not end up with a valid FilePath.  We can also build a FilePath in a way that’s guaranteed (or at least as close as the language allows) to be valid.  A valid file path is an array of path elements. What makes a valid path element depends on the platform, but for simplicity let’s assume that it’s any string made of one or more alphanumeric-only characters (ignoring drive letters and other valid path elements that can contain special characters). We can therefore define a FilePath as constructible from a std::vector of path elements:

class FilePath
{

public:

  FilePath::FilePath(const std::vector<FilePathElement>& pathElements) : _pathElements(pathElements) { }

  std::string stringValue() const
  {
    // Code to join the path elements by the separator “/“
  }

private:

  std::vector<FilePathElement> _pathElements;
};

Now, for the path elements, the tricky part is checking at compile-time that a constexpr string (like a string literal) is nonempty and alphanumeric.  I won’t go into the implementation, but the signature would look like this:

constexpr bool isNonEmptyAndAlphaNumeric(constexpr std::string& string);

Then, we would use this in the constructor for FilePathElement:

FilePathElement::FilePathElement(constexpr std::string& string)
{
  static_assert(isNonEmptyAndAlphaNumeric(string), “FilePathElement must be nonempty and alphanumeric”);
}

If you aren’t familiar with some of this C++ stuff, static_assert is evaluated at compile time, and therefore will cause a compiler error if the passed in expression evaluates to false.  This of course means the expression must be evaluatable at compile time, which is what the constexpr keyword indicates.  The constexpr on the string parameter indicates the passed in string must be a compile time constant.  That’s the only way we could possibly check that it’s alphanumeric at compile time.

We sometimes will need to construct a FilePathElement out of a dynamically built string.  But since we can’t confirm at compile time, we instead do a runtime check, and if needed create a runtime error:

FilePathElement::FilePathElement(const std::string& string)
{
  if(!isNonEmptyAndAlphaNumeric(string))
    throw std::invalid_argument(“FilePathElement must be nonempty and alphanumeric”);
}

Now we can define constructors for a FilePath that take strings.  Since we can’t know statically if it’s valid, it needs to throw a runtime exception:

FilePath::FilePath(const std::string& string)
{
  // Try to split the string into a vector of strings separated by “/“
  std::vector<std::string> strElements = splitString(string, “/“);

   // Try to convert each string element to a FilePathElement.  If any of them are invalid, this will cause an exception to be thrown
  std::transform(
    strElements.begin(), 
    strElements.end(), 
    std::back_inserter(_pathElements), 
    [] (const std::string& element) { return FilePathElement(element); // This constructor might throw }
  );
}

If you have no idea what’s going on in that std::transform call, this is just the STL’s low-level way of doing a collection map. It’s equivalent to this in Swift:

_pathElements = strElements
  .map({ strElement in 
    
    return FilePathElement(strElement); // This constructor might throw
  });

You might be thinking: couldn’t we make a FilePath constructor that takes a constexpr string and validates at compile time that it can be split into a vector of FilePathElements?  Maybe with C++17 or C++20, or earlier depending on how you to do it.  C++ is rapidly expanding the expressivity of compile-time computations.  Anything involving containers (which traditionally require heap allocation) at compile time is a brand spanking new capability.

Now, we can form what we know at compile-time is a valid FilePath:

FilePath filePath = {“some”, “location”, “on”, “my”, “machine”};

If we did this:

FilePath filePath = {“some”, “location?”, “on”, “my”, “machine”};

Then the second path element would hit the static_assert and cause a compiler error.

Okay, so what if we’re not using C++?  Well, then you can’t really prove the path elements are nonempty and alphanumeric at compile time.  You just have to settle for run-time checks for that.  You can at least define the FilePath type that is built from a list of path elements, but you can’t get any more assurance than this. The language just isn’t expressive enough. That’s an example of the practicality problem. Due to limitations of the language, we can’t bake the validity of a path element’s string into the FilePathElement type, and we therefore lose automatic compile errors if we accidentally try to create a file path from an invalid string literal. If we want static validation, we need to write a test for each place we construct path elements from string literals to confirm they don’t throw exceptions.

Okay, the next problem is #2.  That’s an inherently runtime problem, so we’ll deal with it by throwing an exception in the constructor for File.

Moving on, all the methods on File are always supposed to be called after open.  To enforce this statically, we’ll define a separate type, let’s say OpenFile, and move all the methods that must be called after open onto this type.  Then we’ll have open on File return an OpenFile:

class File
{

public:

  File(const std::string& path);

  OpenFile open(bool readOnly) 
  {
    // Code to actually open the file, i.e. acquire the lock 
    return OpenFile(*this, readOnly); 
  } 
};

class OpenFile
{

public:

  std::vector<char> read(size_t count) const;

  void write(const std::vector<char>& data); // Must have been called with readOnly = false

  void close(); // Must call when finished to avoid keeping the file locked.

  friend class File;

private:

  OpenFile(File& file, bool readOnly) : _file(file), _readOnly(readOnly) { }

  File& _file;
  bool _readOnly;
};

Notice that the constructor for OpenFile is private, but it makes File a friend, thus allowing File, and only File, to construct an instance of OpenFile.  This helps us guarantee that the only way to get ahold of an OpenFile is to call open on a File first.  Note that we can do the actual work to “open” a file (i.e. acquire the underlying OS lock on the file) in the constructor for OpenFile, instead of in the open method.  That’s an even better guarantee that this work must happen prior to being able to read, write or close a file.  Then, it won’t really matter if we make the constructor private, and open would just be syntactic sugar.

Now we have a compile-time guarantee that a file gets opened before it gets read/written to/closed.  We still have the problem that even if we pass in the literal true for readOnly and then call write, the failure will happen at runtime.  We need to move this to compile-time failure.  One idea would be to use constness for this purpose.  After all, we have already made read a const method and write a non-const method.  However, since const classes in C++ aren’t quite full-blown types (particularly, we can’t define a “const” constructor), this won’t really work here.  We need to make two separate types ourselves.  Then, we can split the open method into two variants for read-only and read-write:

class File
{

public:

  File(const std::string& path);

  ConstOpenFile openReadOnly() { return ConstOpenFile(*this); }
  OpenFile openReadWrite() { return OpenFile(*this); }
};

class ConstOpenFile
{

public:

  ConstOpenFile(File& file) : ConstOpenFile(file, true) { }

  std::vector<char> read(size_t count) const;

  void close(); // Must call when finished to avoid keeping the file locked.

protected:

  ConstOpenFile(File& file, bool readOnly) : _file(file)
  {
    // Code to acquire the lock on the file.  We pass in readOnly so we can acquire the right kind of lock
  }

  File& _file; // Do we even need to store this anymore?
};

class OpenFile : public ConstOpenFile
{

public:

  OpenFile(File& file) : ConstOpenFile(file, false) { }

  void write(const std::vector<char>& data);
};

We’re almost finished.  The remaining problems are preventing read, write and open from being called after calling close, and making sure close gets called when we’re done. Both of these problems boil down to: calling close must be the last thing that happens with an OpenFile. This is a perfect candidate for RAII.  We’re already acquiring a resource in initialization (a.k.a. construction).  This means we should release the resource in the destructor:

class ConstOpenFile
{

public:

  ConstOpenFile(File& file) : ConstOpenFile(file, true) { }
  ~ConstOpenFile()
  {
    // Code to release the lock on the file
  }

  std::vector<char> read(size_t count) const;

protected:

  ConstOpenFile(File& file, bool readOnly) : _file(file)
  {
    // Code to acquire the lock on the file.  We pass in readOnly so we can acquire the right kind of lock
  }

  File& _file;
};

By closing the file in the destructor (and only in the destructor), we’re making the guarantee that this won’t happen while we still have an instance on which to call other stuff like read and write (we could have a dangling reference, but that’s a more general problem that is solved with various tools to define and manage ownership and lifecycles), and the guarantee that it will happen once we discard the instance.

In reference counting languages like Obj-C and Swift, we can do this in the deinit.  In garbage collect languages like C# and Java, we don’t have as ideal of a choice.  We shouldn’t use the finalizer because it won’t get called until much later, if at all, and that will result in files being left open (and therefore locked, blocking anyone else from opening them) long after we’re done using them.  The best we can do is implement IDisposable (C#) or AutoCloseable (Java), and make sure we remember to call Dispose or close, or wrap the usage in a using (C#) or try-with-resources (Java) block.

And now, all those programming errors that can be detected at compile time, are being detected at compile time.

This is how you use the type system.  You use it to take any constraint you have identified is always satisfied every time your code gets executed, and express it in a way that allows it to be statically verified, thereby moving your runtime errors earlier to authorship-time.  The ideal we aim for is to get all program failures into the following two categories:

  • Failures in external systems we don’t and can’t control (network connections, other machines, third party libraries, etc.)
  • Static (compilation/linting) errors

In particular, we aim to convert any exception that indicates an error in our code into an error that our compiler, or some other static analysis tool, catches without having to execute the code. The best kinds of errors are errors that are caught before code gets executed, and one of the main categories of such errors are the ones you were able to tell the type system to find.