Subclasses and Typeclasses
Today, I'd like to focus on some software development ideas by expanding on something I shared on the fediverse recently; namely, that the concept of subtypes necessarily couples the idea of types with that of typeclasses. In doing so, I'll assume some working knowledge of object-oriented programming (OOP); though I'll use examples in a variety of different languages, none of them should require substantial experience in those languages beyond common OOP concepts. I'll also take a somewhat high-level view, necessarily glossing over some important details in favor of simplicity; this is an introduction, not a complete treatise on the topic.
In any case, it helps to start by revisiting what types actually are. When we write software, we typically work by assigning values to variables. For instance, suppose that in a fictional language, we write something like the following:
let x = 42;
We might read this as assigning the value 42 to a variable named x. The value 42 happens to represent a natural number, but often, languages will let us assign different kinds of values as well:
let y = "hello";
let z = false;
Where this can cause problems is if we write a program that assumes something about what values a given variable can hold. Those assumptions may or may not hold in practice, leading to logic errors. For example, in Python:
>>> def square(x):
... return x * x
...
>>> print(square("circle"))
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 2, in square
TypeError: can't multiply sequence by non-int of type 'str'
(If you don't have Python installed, you can run this example in your browser by using the PyScript REPL example. Just copy and paste the code above in, without the >>> and ... prompts, and you should get your error.)
Here, square looks like a perfectly reasonable function, but it implicitly assumes that its argument is a value that can be multiplied by itself — when we violate that assumption, we get an error at runtime.
The concept of types helps us prevent that kind of error by allowing us to reason about what kinds of programs may or may not be valid based on what assumptions they make about values.
For example, we might write a similar program in TypeScript:
let square = (x) => x * x;
console.log(square("circle"))
If we do, the TypeScript compiler immediately tells us there might be a problem, before we run the program:
Parameter 'x' implicitly has an 'any' type.
If we fix that by telling TypeScript that x is a number, we get a new error where we call square:
let square = (x: number) => x * x;
console.log(square("circle"))
// Argument of type 'string' is not assignable to parameter of type 'number'.
Here, x: number tells TypeScript that only numbers are valid values for the parameter x. That is, x has as number as its type. Formally, we can think of types as sets of values. In pseudocode, we might write something like number ≔ {-42, 0, 1.1, 3.14, 29104062225468, ...} to indicate that number can include values representing positive numbers, negative numbers, floating-point numbers, integers, and so forth. Critically, though, number doesn't include "circle", and so we get an error.
This might seem very different than how you may have first encountered types, as we're often taught in programming to think of types as specifying behavior, rather than values. For example, we implicitly assumed that * is something that makes sense for the number type. When we change the type of x to string, TypeScript helpfully points out that that assumption doesn't hold for the type string:
let square = (x: string) => x * x;
// The left-hand side of an arithmetic operation must be of type 'any', 'number', 'bigint' or an enum type.
// The right-hand side of an arithmetic operation must be of type 'any', 'number', 'bigint' or an enum type.
Thinking of types as behavior makes a lot of sense in languages like C++, Java, C#, and Python where you can define new types by specifying the structure and behavior of those types. It's common to see examples like this in intro programming classes (sorry):
class Drawable():
@abstractmethod
def draw(self, surface):
pass
class Circle(Drawable):
def __init__(self, radius):
self.radius = radius
def draw(self, surface):
# TODO: draw a circle onto surface
class Rectangle(Drawable):
def __init__(self, width, height):
self.width = width
self.height = height
def draw(self, surface):
# TODO: draw a rectangle onto surface
Here, the type Drawable tells us only about some behaviour, namely that Drawable instances can be drawn to some surface. We need to make concrete subclasses to understand what kind of data we need to draw each different shape.
Thinking of types this way, we can easily work with Drawable instances without knowing the exact sort of values — only knowing that they have some desired behavior. Even the name Drawable suggests that interpretaion! For example,
def draw_all(drawables, surface):
for drawable in drawables:
drawable.draw(surface)
Here, we've implicitly required that the drawables argument has as its type some collection of Drawable instances, but we can also be more explicit — in many languages, we have to be. In C#, for example, we could write out the same draw_all function as a method that takes Drawable as a type:
void DrawAll(IEnumerable<Drawable> drawables, Surface surface)
{
foreach (var drawable in drawables)
{
drawable.Draw(surface);
}
}
This implicitly uses a key idea behind object-oriented programming, namely that instances of a class are also instances of all of its superclasses. In particular, instances of Circle are also instances of Drawable. Thinking of types as classes of values, we might write something like Circle ⊆ Drawable. That is, Circle is a subtype of Drawable.
As an aside, Python is a bit of an odd duck when it comes to defining types, since all Python types are also values in the language. In particular, type is the type of all types, leading to such fun edge cases as type(type) returning type. All types in Python are also values, but not all values are types. There's good reasons Python is that way, but they make this discussion significantly more confusing, so I'll largely set Python aside for the rest of the post.
Anyway, going back to thinking of types as collections of values rather than specifications of behavior, the situation gets somewhat odd when we consider subtypes — effectively they both play the role of constraining behavior and specifying the data structures for various values, but those two roles are quite different in practice. Consider the problem of specifying behavior of the form "can be added to other values of the same type." In C#, we might write this as an interface that specifies behavior without specifying data:
interface IAdd
{
IAdd Add(IAdd other);
}
If we do this, though, we quickly hit limits when we try to implement that interface for a particular data structure. What should happen if we try to add a 32-bit integer to a 64-bit integer? String concatenation is a form of addition, so can we add a floating point number to a string?
All of these limitations hit us smack in the face if we try to write something like a method to sum various IAdd instances:
IAdd Sum(IEnumerable<IAdd> summands)
{
var sumSoFar = ?????; // ← how do we define zero?
for (var summand in summands)
{
// What happens if we pass a list containing
// both strings and integers?
sum = summand.Add(sumSoFar);
}
}
Thankfully, C# lets us solve that by introducing type parameters for our method:
T Sum<T>(IEnumerable<T> summands)
where T: IAdd
{
var sumSoFar = ?????; // ← how do we define zero?
for (var summand in summands)
{
sum = summand.Add(sumSoFar);
}
}
Here, the bound on the type parameter T, namely where T: IAdd tells us that whatever specific type we assign to T, it must implement the IAdd interface. There's still some problems, such as finding the zero value for a given type T, but the concept of a type parameter bound allows us to express that a type parameter can be assigned to any type satisfying some constraint.
If that sounds a lot like the idea of types themselves, you're completely correct. In particular, a typeclass is a set of types in precisely the same sense that a type is a set of values. What makes this seem a bit complicated at first is that when we define something like IAdd or Drawable we're defining both a type and a typeclass. For example, as a typeclass, Drawable is the set containing Rectangle, Circle, and whatever other types someone might define as inheriting from Drawable.
Similarly, in the example of where T: IAdd above, IAdd is acting as a set of types — as a typeclass — rather than any specific type. C# doesn't really have a concept of typeclasses as distinct from types, so when we define IAdd as a typeclass, we also define a type with the same name whose values are all values of every type in the IAdd typeclass. On the face of it, it's a bit silly to have both integers and strings in the same summation just because they're both values of types in the IAdd typeclass, but that's precisely what it means to declare a value as having type IAdd.
Not all languages couple types and typeclasses by giving them the same name, though. In Rust, typeclasses are a fundamental part of the language, known in Rust as traits. For example, the same concept as IAdd is expressed in the Rust standard library as a trait:
pub trait Add<Rhs = Self> {
type Output;
fn add(self, rhs: Rhs) -> Self::Output;
}
(This is the actual code from the standard library, by the way, with only some metadata and comments removed.)
Basically, this trait says that a type T is in the typeclass Add<Rhs> if it can be added to a type Rhs to get some output. The trait on its own doesn't say anything about what members of that typeclass look like, but we can use impl blocks to tell the compiler that a particular type is in a given typeclass:
impl Add<u64> for u64 {
type Output = u64;
fn add(self, other: u64) -> u64 { self + other }
}
This says that a u64 value (Rust syntax for the type of 64-bit unsigned integers) can be added to another u64 value to get a u64 value as output. Declaring that the type u64 is in the Add<u64> typeclass then lets us use u64 in functions that generalize over the entire Add<T> typeclass:
use std::ops::Add;
fn double<T: Copy + Add<T>>(x: T) -> T::Output {
x.add(x)
}
fn main() {
println!("2 + 2 = {}", double(2));
println!("3.1 + 3.1 = {}", double(3.1));
}
(If you don't have Rust installed, you can use the Rust Playground to run this example in your browser.)
Here, we also had to specify that T also satisfies the typeclass Copy, since Rust doesn't assume it can make copies of arbitrary values, but for the most part, the double function acts like you'd expect. The + operator acting on typeclasses let us easily express the intersection of Add<T> and Copy (that is, the typeclass of types that are in both the typeclass Copy and Add<T>). In C#, we can do similar by adding multiple classes or interfaces to a where clause, but that breaks the correspondence between types and typeclasses, making it confusing to reason about when a type is acting to constrain values and when it's acting to constrain other types.
This works because we've made a strict separation between types, that specify data structures and values, and typeclasses that specify behaviors. Since behaviors compose nicely, it makes perfect sense for a single type to be in multiple typeclasses (in Rust parlance, to implement multiple traits), while the idea of a value simultaneously being of multiple different types is more difficult to work with. For example, a 32-bit unsigned integer is not also a 64-bit signed integer, even though both kinds of integer support addition — they have entirely different sizes in memory, and the implementation of that addition behavior is entirely different.
My fediverse post earlier was making the point that whenever you define a class in an object-oriented language, you also implicitly also define a typeclass comprised of all that classes' subclasses, inextricably linking the specification of data structures with types to the specification of behavior with typeclasses. That in turn can often overconstrain software design by reducing expressiveness, impacting how we develop and organize code.
For example, if a data structure admits some kind of behavior, we have to know about that behavior when we define the data structure. In our C# example, the IAdd interface has to exist before we implement it, while in our Python example, we couldn't define how to make something like namedtuple("x", "y") Drawable since that class didn't exist when the standard library defined namedtuple.
That restriction makes perfect sense for extending and manipulating data structures, but the corresponding restriction on defining behaviors comes about only because of types and typeclasses are often conflated with each other in object-oriented languages. Separating the two apart can make it significantly easier to reason about how behavior generalizes over types, and can help us dramatically simplify our code.
Postscript: You may have caught me sliding a little something under the rug, namely that void DrawAll<T>(IEnuerable<T> drawables) where T: Drawable would be far less useful than void DrawAll(IEnumerable<Drawable> drawables), as it would impose that everything we try to draw must be of the same shape. That a collection can have values of various types so long as they support the same behavior is difficult to express using typeclasses, since that behavior could be implemented differently for every element of the collection. Effectively, we need each element to be paired with a pointer telling us where to find the right implementation — in many languages, that pointer is called a vtable. The virtual and abstract keywords in C# add methods to a type's vtable, while in Rust, the dyn keyword turns a typeclass into a type by constructing a vtable for each different part of the behavior specified by that typeclass. We might write something like draw_all in Rust as:
fn draw_all<T: Iterator<Item = Box<dyn Drawable>>>(drawables: T, surface: &Surface) {
for ref drawable in drawables {
drawable.draw(surface)
}
}
Here, Box is needed to make each vtable something we can store in a list, since not all vtables will be of the same size in memory. In C#, vtables are implicit as a part of reference types, such that Box<dyn Drawable> in Rust is similar to Drawable in C# when Drawable is used as a type and not as a typeclass.