Is Category Theory Practical?
Attempts at concrete applications for a decidely non-concrete field
I had a post last month about category theory and how it was useful from a big-picture, philosophical point of view.
I think that that alone is sufficient to justify its study—I’ll talk a bit more about why in a second.
Furthermore, category theory is certainly very useful in pure mathematics—for example, the modern viewpoint of algebraic topology is that it is the study of finding functors from the category of topological spaces (or some subcategory) to an algebraic category, like the category of groups. And I will eventually write an article expanding on this, but that isn’t what I want to do here.
My main goal is to try to answer the question “What real-world applications does category theory have?” This is a deceptively tricky question, for various reasons, including this: what counts as an application anyway?
Say, for example, I have constructed a beautiful mathematical theory, and later someone points out that some particular result that is a consequence of that theory happens to give the exact insight that you need to make cold fusion a reality. Does that count as an application of my theory? You might be tempted to say ‘yes.’ What if the particular corollary doesn’t really use anything substantive about my theory and you could have deduced it in much simpler ways? You might now be tempted to say ‘no.’ What if the only reason why anyone would think to consider this corollary was in the context of my theory? You might have been convinced to say ‘yes’ again.
Why is this relevant to category theory? Well, it is very easy to find examples of real-life problems that have a categorical structure—I’ll show some later, together with lots of citations. Do these then count as applications of category theory? I think that the answer is undoubtedly ‘yes’ if you use some theorem in category theory (which you would probably not have come up with otherwise) to show that something is true for such examples. But I also think the answer might be ‘yes’ even without satisfying that requirement.
Let me give an example. I used to do a fair amount of my programming in SageMath, an open-source computer algebra system that was built on top of Python. One of the great things about Sage, in my opinion, is that it incorporates a category framework. When you define an object in Sage, it doesn’t just track what the class of this object is—it also tracks what categories it is an element of, and it freely uses this information to work out how the various attributes of the object should behave.
This might sound like it is just inheritance, which is a concept used in many programming languages, including Python itself—you can have objects that are members of classes that are sub-classes of other classes, and then you can just import the attributes of the super-classes to the sub-classes. So, for instance, I might have a class called bird which has a method called fly(). I might then define a sub-class of bird called albatross, and now I don’t have to rewrite the method fly() again—I can just have any instance of albatross “borrow” the necessary code from bird.
But Sage actually goes a little farther than just this—it isn’t just that it can import attributes, but that everything is forced to compose nicely due to the category-theoretic structure. As a result, Sage can construct new methods from existing ones by figuring out how things should compose, and it does this completely automatically, without you, the programmer, worrying about it. Here’s an abstract algebra example, for anyone who might be familiar with it: you can teach Sage that there is a ring homomorphism from ℤ to ℤ/2ℤ, teach it the concept of a matrix ring Mat(n, R), and then it can figure out how to compose these things together to produce a ring homomorphism Mat(n, ℤ)→Mat(n, ℤ/2ℤ) all by itself.1
You need to learn a bit to make proper use of this framework, but when you do, it makes life a heck of a lot more pleasant. Thus, I think that introducing category theory is completely worthwhile here, and even if we aren’t really using any theorems about category theory, this should still be counted as an application. One could write a lot about why this frame of mind is a good approach to a lot of programming, even if you aren’t primarily interested in mathematics, as I am. I won’t go into this, but I will note that there are now textbooks on category theory written specifically with computer scientists in mind. I should note that Sage is hardly the only and certainly not the first programming language to be directly built with a category-theoretical framework in mind—Haskell is much more famous and probably more widely used.
With this giant aside out of the way, the first question that I want to answer is: why should we expect category theory to show up anywhere in real-world situations? This will have the surprising answer that we should expect it to show just about everywhere. But, first, let’s quickly remind ourselves what categories and such are.
Definition: A category C consists of a collection of objects and a collection of morphisms (also called arrows). Any morphism f has two objects associated to it—a source (also called a domain) and a target (also called a codomain). Usually, we signify this by writing f: A→B, where f is the name of the morphism, A is the source, and B is the target.
If we have morphisms f: A→B and g: B→C, then we can compose them together to form a morphism g∘f: A→C. This composition ∘ has to satisfy the following additional properties:
It is associative—that is, for any f: A→B, g: B→C, and h: C→D, h∘(g∘f)=(h∘g)∘f.
For every object A, there exists a morphism (called the identity morphism) idA: A→A such that for any morphisms f: A→B, g: B→A, f∘idA=f and idA∘g=g.
If you want to see some examples of how this comes up in mathematics, I recommend that you read the previous post—there are various natural examples, such as the category of sets, groups, rings, topological spaces, vector spaces (over a given field), and much more.
We’ll go at this from a different perspective. We noted in the original article that we could build a category “from scratch,” so to speak, by just drawing nodes and labeled arrows between them, as long as you make sure that the arrows follow the rules laid out in the definition of a category.
This is significant because these kinds of arrow diagrams actually show up in lots of applied settings. Let’s be entirely concrete and consider the following diagram.
This is a simplified chemical diagram. The nodes are possible collections of molecules in our system, and they are connected by arrows if there is a chemical reaction that will take us from one state to the other. There are essentially just two kinds of chemical reactions here: the first is the breakdown of the simple sugar C6H12O6 and oxygen into carbon dioxide and water; the second is the dissolution of carbon dioxide in water, producing carbonic acid. I have not drawn in all of the existing arrows for ease of viewing—there are, of course, identity arrows on each node signifying that the state has not changed, and there are arrows that you can get from one state to another via composing drawn arrows in the diagram. But, the point is, we have produced a category.
You might be able to guess that this can be generalized a fair bit. In some sense, whenever you come up against some kind of flowchart, you can try to interpret it as a category. This connects you not just to chemical processes, but to models of computation in computer science, business process modeling, Feynman diagrams in physics, and much, much more.
Furthermore, the category-theoretical structure isn’t just some weird add-on—it is actually telling us something salient about the compositionality of the system. To show what I mean, I’m going to borrow a diagram from Tai-Danae Bradley’s excellent article What Is Applied Category Theory? (which is itself borrowed from Seven Sketches in Compositionality by Fong and Spivak):
This is part of a category constructed out of the flowchart associated with baking. (There are some things I am not telling you here because to understand this as a category you really need to understand how to tensor arrows together—more on this in a bit.) But the thing is that if we have any further diagrams where one of the steps is to prepare a lemon pie,
we can just paste the diagram up above into the red box if we need to actually understand how to do it in detail. Or, we could equivalently leave it off if we don’t want to worry about it, because it will be handled by some other party, for instance. That both of these approaches will give valid diagrams is assured by the fact that these are categories and so the composition of morphisms is associative.
We use this kind of black boxing in our real lives all the time without even thinking about it, but it is not altogether a trivial concept. It has to be drilled into young programmers that all of their code should ideally follow this paradigm where individual steps are handled as their own functions, which can be called and edited separately from everything else. There are many reasons why this is important, including that:
it makes code easier to read,
it allows those basic steps to be altered separately from everything else, and
it allows these basic steps to be executed by different machines, which is especially important if your code is being run on a network of computers rather than just one.
However, I am really just telling you part of the story, because categories are not quite enough to accurately capture flowcharts. To show why, let’s get back to our chemical reaction network example.
Here are two examples of simple chemical reactions. The top is the reaction of hydrazinium with hydroxide, which produces hydrazine and water; the bottom is the reaction of methane with oxygen, which produces carbon dioxide and water. While these are two separate chemical reactions, there is an obvious way in which we ought to be able to combine them together—simply combine the starting and ending states for both.
This makes a difference because there are new chemical reactions that can happen with this new mix that could not have happened with the two separate states.
The problem is, in a base category, there is no way to combine objects and morphisms in the way that we just did. Thankfully, there is a solution in category theory to this problem: introduce monoidal categories.
(Rough) Definition: A monoidal category is a category C together with a (partial) binary operation ⊗ on objects and morphisms such that:
Given morphisms f: A→B, g: C→D, there is a morphism f⊗g: A⊗C→B⊗D.
For all objects A, B, idA⊗idB=idA⊗B.
For all morphisms f,g,h,k, (g∘f)⊗(k∘h)=(f⊗h)∘(g⊗k) (provided the compositions make sense).
For all morphisms f,g,h, f⊗(g⊗h)≈(f⊗g)⊗h.
There exists an identity object I such that for all objects A, I⊗A≈A⊗I≈A.
This isn’t a precise definition in that I haven’t explained what the heck is meant by ≈ rather than =. What is going on is simple: we would very much like there to be an exact equality in those places in the definition, but practically speaking, most examples that we come up with in mathematics aren’t quite so neat. Instead, we have to say that these objects and morphisms are “naturally isomorphic”—there are maps between them that identify them in some precise way, even though they are technically different objects. But then, since they aren’t exactly equal and you want to preserve the idea of compositionality, you need to specify that in some natural diagrams that come up, it doesn’t matter in which direction you go around composing arrows. If you want to learn more about the precise details, I recommend starting with something like Bradley’s What is Applied Category Theory?
Here’s an applied example: in the chemical composition networks that we have studied, we can think of ∘ as signifying that we do one chemical reaction followed by another, and we can think of ⊗ as signifying that we have two separate chemical reactions where we combine the products together. This idea generalizes immensely: for all sorts of different flowcharts, you can think of ∘ as saying that you have two processes that must happen sequentially, and ⊗ as saying that you have two processes that happen in parallel and then combined.
In this way, monoidal categories have tremendous descriptive power. There is, for example, a very well-cited paper by Baez and Pollard that shows that Petri nets can be described in terms of monoidal categories. Petri nets were originally designed to understand chemical reaction networks as dynamical systems, but they have since been used in all manner of different areas, including computer science, business modeling, and computational biology. And all of these disparate applications can be understood in terms of a single, unifying framework: monoidal categories.
Is this now an application of category theory? Arguably no, not yet: we’ve shown that categories (and partially monoidal categories) describe a vast array of different applied systems, but we haven’t shown that you can actually get any use out of this. Here, I think it is worthwhile to take a look at the papers citing Baez and Pollard’s aforementioned paper A Compositional Framework For Reaction Networks, since they are fairly easy to track down using Google Scholar. Many of the citations come from other category theorists extending these results, but then you also get much more surprising citations, such as from a paper published in the Water Resources Research journal.
Evidently, there is interest in actually applying this formalism. How? Why?
To start getting at an answer, we need to remind ourselves of one more category-theoretical construction.
Definition: Let C, D be categories. A functor F: C→D is a map sending objects A in C to objects F(A) in D, and morphisms f: A→B in C to morphisms F(f): F(A)→F(B) in D such that:
For all objects A in C, F(idA)=idF(A).
For all morphisms f,g, F(g∘f)=F(g)∘F(f).
Why are functors interesting? One possible answer is that functors allow you to translate results (which can be phrased in category-theoretical language) about one category to results about another category. After all, since functors preserve composition ∘, there are lots of properties of arrows that have to stay the same from the first category to the second for there to be a functor between them. And, as it turns out, you can express a lot just in terms of properties of arrows.
Another possible answer is that we can sometimes think of a functor as a kind of evaluation or interpretation. For instance, there is a functor that takes topological spaces (if this is too abstract for you, picture, say, surfaces) and matches them to groups. One might think about the functor as evaluating the topological space to this particular group. One way to use this is by noting that if the groups don’t match, the topological spaces must be different. But there is more that you can pull out because when we “evaluate” like this, we get morphisms (relations) between the evaluations, which is not something that you get when you evaluate a function on a set. And that extra information tells you about how everything has to fit together.
In applied category theory, this is sometimes summarized as saying that the category C provides the syntax (the rules for composing things together), the category D provides the semantics (the actual meaning behind it), and the functor F: C→D tells you how to connect the two. For example, in Baez and Pollard’s paper on Petri nets, they don’t just show that there is a monoidal category of Petri nets—they show that there is a functor between this category and the category of dynamical systems, such that we match each Petri net with the dynamical system it represents. If we think about chemical reaction networks, what is being said is that we can take a diagram like
and match it to the dynamical system representing how our molecules will react with each other over time. One huge benefit of this is that, due to the fact that this is a category, if we can understand very simple chemical reaction networks and the dynamical systems they represent, then we can understand very complicated chemical reaction networks by just breaking them down into smaller pieces and using compositionality.
Another example is in natural language processing. There is a category of phrases (in, say, the English language) such that you only connect them by morphisms if this is grammatically correct (so, for instance, you can connect an arrow between a noun and a verb, but not a noun and a noun)—this is the syntax category. You can construct a functor from this category to some other kind of category that “evaluates” the meanings of these phrases (that is, if two phrases are close in meaning, the corresponding objects in the category should be “close together” in some sense), which is the semantics category. This is, for example, what Kartsaklis, Sadrzadeh, Pulman, and Coecke did in their paper Reasoning about Meaning in Natural Language with Compact Closed Categories and Frobenius Algebras.2
Are these examples of applications of category theory or not? I have seen some pooh-pooh such examples as needless abstraction. But as we discussed at the beginning of this post, sometimes just having an organizational framework can be hugely beneficial, even if you don’t get any deeper results—and one thing that category theory absolutely excels at is providing organizational frameworks.
Moreover, I think that, in at least some of these areas, there are going to be far more instances of category theory being used in non-trivial ways. In part, I say this because applied category theory is a very young field—the only journal that I know of that is devoted to it, Compositionality, was only started in 2018. But I can also give an example of how I think category theory is going to be potentially useful going forward: compiler design.
Let’s say that you write some code in your favorite programming language, and then you want to execute it. The computer has to turn your code into machine code—actual instructions that a CPU can perform. It does this by way of special software called a compiler, which takes your code as an input and outputs machine code that performs the functions that the code describes. However, often we want a compiler to do more than just this: we want it to produce the most efficient machine code that it can, which will perform the functions that the code describes. In other words, we want an optimizing compiler.
There is an inherent danger to an optimizing compiler, though: you want it to tinker with the original code as specified by the programmer, but you emphatically do not want it to change what that code does—if that ever happens, then the programmer will get odd behavior that they will have extreme difficulty debugging.3 Therefore, whatever changes the compiler makes, the resulting code has to provably (in the mathematical sense) have the same behavior as the original—just faster/using less memory/draining less power.
Here’s one possible technique to do this (which I originally learned from an undergraduate thesis, of all things). If your language is designed like a category, then there are sorts of theorems you automatically have about its objects. Category theory can be terrific at proving, for instance, that you can take various constructions and permute the order in which you do them without changing the result.
But changing the order in which you do two operations in computer science can have a massive effect on how quickly they get executed! (Here is a basic example: if you want to compute 99999999999999^5 % 3, you should really take the modulus first and then raise the result to some power, rather than the other way around.)
To be fair, I have yet to see anything but very basic theorems proved this way, but I don’t think that this should dissuade us much: as we already discussed, in applied category theory, it is often enough to understand the simple things and use compositionality to bootstrap to more complicated things.
Strictly speaking, Sage already knows about such ring homomorphisms and matrix rings, so there is no new code that needs to be written here, but you get the idea.
To be honest, I don’t know how much interest there still is in pursuing this idea. My sense is that most attention in natural language processing is now devoted to AI.
Since the problem is not with their code, nor any of their collaborators’!
I've been studying linear logic, and that tensor product seems very familiar from there.
Database theory is another big application especially comming from Spivaks work. His and Nius Mathematical Theory of Interaction is also really neat and will get you seeing categories as comonoids in the category of polynomial functors