Basic Category Theory for Programmers, Part 2: Intuitions
In the previous post we gave a quick overview of the main concepts in category theory and briefly noted how they can be applied to a programming language. Before going further, let's step back and think more carefully about what it means to consider a programming language as a category.
A category is made up of objects and arrows. To qualify as a category we need to find something in a programming language which corresponds to objects and arrows. Functions seem like a good fit for arrows. This seems obvious from the fact that function signatures are often represented with an arrow symbol, as in
We say that a function goes from an argument type to a return type. This is similar to how an arrow goes from one object to another.
Once we have chosen functions as the arrows, we do not have much choice for what counts as objects. An arrow in category theory goes from one object to another. A function goes from one type to another. It may also go from a type back to the same type. If we choose functions as the arrows in a category, the types of a programming language seem like a good choice for the category's objects.
There may be many functions that go from one particular type to another. Looking at the arrow between the Number
and Boolean
types, we could have a function called isEven
which returns true
only for even Numbers
, and another function isOdd
which returns true
only for odd Numbers
. Every function is an arrow in the category, but for convenience we don't have to draw all of them in our diagrams. We should just keep in mind that when we see an arrow between two types, it could represent many functions.
We generally don't care about all the individual functions between two types. But at least one function is required from a type back to itself. Remember that a category requires each object to have an identity arrow.
Let's clarify what we mean by "types". Classes, structs, tuples, and primitives such as Number
and Boolean
are all types. Not all programming languages support tuples. They are like structs which don't require names for its fields. For example, the type of a tuple with a Number
and a String
would look like this, (Number,String)
. As far as category theory is concerned, there is little difference between classes, structs and tuples. They are all composite types made up of more primitive elements.
All types represent a set of values. For example, the Boolean
type represents two possible values, true
or false
. The Number
type represents all the possible numbers supported in a particular programming language. Every class or struct you define is a type. Let's say you define a class, Address
, which represents a street address. Address
would then be a type in this category. The different values for this type would be all the possible instances you could create for this class.
All the functions we have talked about so far are "free" functions, or what are generally called "global" functions. Functions may also be associated with classes. These are generally known as "methods" to distinguish them from global functions. How do these fit into category theory? In category theory, the arrows always go from one object to another. There's nothing which corresponds to the idea of calling a method on an object.
Let's see how methods work. Suppose that the Address
class has a method called hasValidZipCode
which returns true if the address has a valid zip code. Let's say the Address
class has a field called zipCode
which is a String
. The method would inspect the value of this field to confirm that it is valid.
The method's return type is Boolean
, but it doesn't seem to have an argument. If we use void
for an empty argument, the method signature would look like this, void→Boolean
. But in fact, the method does have an argument. There is a special property inside methods which is typically called self
or this
. This property represents the instance of the class which the method is performed on. Another way to look at this is that a class method is actually a global function which has a class instance as a default argument. We can fit this method into the PL
category if we see it as a function that looks like this, Address→Boolean
.
But what if a method does have an argument in addition to the class instance? More generally, how do we handle functions with more than one argument? Arrows always go from a single object to another single object. When we have more than one argument, we can consider the set of arguments as a composite type such as a struct or a tuple. This might seem arbitrary since it looks like we're inserting types where they don't exist. But we can't get around the basic restrictions of the theory. We have to find a way to fit what we can into the category. In fact, not everything can make it in.
We need to make a clarification about the terms we're using here. Programmers generally make a distinction between the arguments and the parameters of a function. An argument is usually understood as the value which is passed to a function. A parameter then refers to the variable which handles this value within the function definition. We're going to avoid this distinction to keep things simple. The input of a function will always be referred to as an argument.
What about functions with no arguments or functions which return nothing. Programming languages usually mark this with the void
keyword as we did above.
But in category theory, arrows have to go from one object to another. They cannot start or end at nothing. We can take care of this by adding a Void
object. Some programming languages actually do contain a Void
type. But whether a programming language has a Void
type or not, we need it in PL
so that all arrows have an object at both ends.
What about class initializers or constructors? These are just more functions. For a type A
, its initializers are just functions which return A
. Some initializers we can simply disregard. Let's say we have a class with two fields. An initializer would take two values to populate these two fields. We said that we need to represent multiple arguments with a composite type. So let's say that this initializer takes a tuple with two values. We also said that in category theory classes are sort of equivalent to tuples. So this initializer isn't doing anything as far as category theory is concerned.
This isn't the case for all initializers. An Array
initializer might take a String
as its argument. Since the type of the argument, String
, is different from the type of the return value, Array
, we need to represent this initializer as an arrow in PL
.
Binary operators such as +
and -
are just functions with two arguments. Using a tuple for the argument, their type signature looks like this, (Number,Number)→Number
. But this isn't the only way to represent a binary function. If we want to add 2
to 3
, using a tuple would look like this, (3,2)→5
. But we could also have a function which adds 2
to any Number
. Adding 2
to 3
would then look like this, 3→5
, where the arrow now represents the function which adds 2
. Its type signature looks like this, Number→Number
. To represent addition we would need a separate function to add each different Number
to another Number
. This isn't meant to be a practical solution, of course. The idea is that there are many ways of translating a programming language to the PL
category. As we introduce more concepts from category theory we'll find this flexibility more useful.
In the previous post we saw that we can create categories from subsets of the types in PL
. In the next post we'll start seeing how we can examine the relationships between the structures of these different categories.