Applied abstraction
The Endeavour 2024-05-01
“Good general theory does not search for the maximum generality, but for the right generality.” — Saunders Mac Lane
One of the benefits of a scripting language like Python is that it gives you generalizations for free. For example, take the function sorted. If you give it a list of integers, it will return a list of numerically sorted integers. But you could also give it a list of strings, and it will return a list of alphabetically sorted strings. In fact, you can give it more general collections of more general things. The user gets generality for free: more functionality without complicating the syntax for the most concrete use case.
Here’s a similar example in math. Suppose you prove that for invertible matrices A and B of the same size
(AB)−1 = B−1 A−1.
You can prove just as easily that the same is true for any elements A and B in a group. In fact, the proof may be simpler. Because you have less to work with in a group, you’re lead by the nose to a simple proof.
But not all generalizations are free. In the sorting example, suppose you want your code to do more than sort lists, but instead perform any operation on lists that satisfies some properties that sorting has. This is the kind of thing some Haskell programmers love to do. The result is a kind of impenetrable code that takes talent to write.
Mathematical theorems are usually discovered in some concrete setting, then codified in a more general setting. There is some optimal level of generality that clarifies the original discovery without introducing more difficulty. But it is possible to push past this degree of generality at the cost of less intuitive hypotheses and more complicated proofs. The generalization comes at a cost. The cost may be worthwhile or not, depending on one’s motivations.
A gratuitous abstraction is one that has no apparent benefit and comes at some cost. A gratuitous abstraction may turn out to be useful in the future, but this rarely happens. And if it does happen, it will likely be because someone was lead to re-discover the abstract result while pursuing a particular problem, not because they read the abstract result and thought of an application.
This post was motivated by looking at generalizations of the Möbius inversion formula. Mr. Möbius introduced his formula nearly two centuries ago in the context of a concrete problem in number theory. The formula has been greatly generalized since then in ways that would appear to be gratuitous, introducing incidence algebras and so forth. But these generalizations have made the formula more widely applicable, particularly to problems in combinatorics.
I won’t get into Möbius inversion now, but I may in the future. Here is a post I wrote a couple years ago that touches on Möbius inversion.
I was uncritical of generalization as an undergrad. Striving for maximum generality was fine with me. Then I hit my abstraction tolerance in grad school, and became leery of gratuitous abstraction. I’ve been disappointed by going down highly abstract rabbit holes that never paid off. But Möbius inversion reminds me that levels of abstraction that seem gratuitous may be practical after all.