Closing the Loop on Category Theory: Polymorphism, Currying, and More
Oct 02, 2013/
On September 18, I traveled to St. Louis, MO to give a talk at Strange Loop, an annual developer's conference. Strange Loop is reputed to be one of the most exciting and thought-provoking conferences about programming. Unlike many conferences, Strange Loop is unique in that it doesn't focus on a particular programming language or style. Instead, the talks vary widely in content and scope. For example, talks at this year's conference ranged in topic from "Spores: Distributable Functions in Scala" to "Programming a 144-Computer Chip to Minimize Power" to "Learn fun and Playfun: A Nintendo Automation." (Video recordings of all talks will be posted online throughout the next few months.)
Since I come to programming with a background in mathematics, I decided to give a talk on a field in math that relates deeply to programming: Category Theory. Specifically, I presented a handful of examples showing how Category Theory provides us with the tools and vocabulary to abstract the idea of a transformation from one function to another. I find abstraction fascinating, since the ability to abstract an idea allows one to see how it connects with other ideas in ways that might not be immediately obvious. Hence I called my talk "Category Theory: An Abstraction for Anything.
My first example of a category was a git merge history graph. In a directed acyclic graph of git commits, the commits become objects in the category, while the parent-child relationships between them become the morphisms. With this structure in mind, one can categorize the structure of their git history.
Next I dove into some more profound category theory: functors. A functor provides a way to transform one category into another (or back into itself). For example, you can transform the category of all graphs to the category of all sets, by simply "forgetting" the graph structure, and only retaining the nodes. This is an example of a forgetful functor.
Additionally, I wanted to include a categorical explanation of a couple common ideas in programming: currying and polymorphism. These two concepts each serve as an example of a natural transformation, which is a mapping from one functor to another. Currying (also known as schonfinkelzation) is the transformation of function of two arguments into a function of one argument that returns a second function of one argument. Specifically, currying is the transformation from all functions of the form ((A x B) -> C) to all functions of the form (A -> (B -> C)). Secondly, in a polymorphism (see example below), one abstracts over a type so that the user chooses the type at the call site. This flexibility in the type lets one transform, say, a Scala Option to a Scala List.
In short, morphisms map objects within a category, functors map one category to another, and natural transformations map one functor to another. In this way, the abstractions in Category Theory order themselves into a hierarchy, with one abstraction utilizing another.
Overall, Strange Loop was filled with bold and thoughtful talks, including a keynote by the author Douglas Hofstadter, who coined the term "strange loop" in his book Gödel, Escher, Bach. Add in the adventurous conference party at the St. Louis City Museum, and the hundreds of conference attendees who were each willing to share valuable knowledge about their specific domain, and without a doubt, this combination makes for a stimulating experience in “the Loop.”