Category Theory for Programmers: Preface

Original author: Bartosz Milewski
  • Transfer
For some time now, I have been considering the idea of ​​writing a book on category theory for programmers. Not computer theorists, programmers - more engineers than scientists. I know this sounds crazy and I'm scared enough. I know that there is a huge difference between science and technology, because I worked on both sides of the barricades. But I always had a very strong urge to explain things. I admire Richard Feynman, who was a master of simple explanations. I know, I'm not Feynman, but I will try my best. I start with the publication of this introduction, which should motivate the reader to study the theory of categories, and I hope for the beginning of the discussion and feedback.

I will try in several paragraphs to convince you that this book is written for you, and to dispel all your doubts about the need to study this, one of the most abstract areas of mathematics, in my precious free time.

My optimism is based on several observations. First, category theory is a treasury of extremely useful programming ideas. Haskell programmers have been drawing from it for a long time, and these ideas are slowly leaking into other languages, but this process is too slow. We need to speed it up.

Secondly, there are many different types of mathematics, and all of them are intended for different audiences. You may be allergic to mathematical analysis or algebra, but this does not mean that you will not like the theory of categories. I’m not afraid to say that category theory is exactly the kind of mathematics that is especially suitable for thinking programmers. This is because category theory, instead of dealing with details, operates on structure. It operates with concepts that make programs composable.

Composition is at the very core of category theory; it is part of the very definition of a category. And I affirm that composition is the essence of programming. We combined things for a very long time, long before some great engineer came up with routines. Some time ago, the principles of structural programming revolutionized programming — they made code blocks combinable. Then came object-oriented programming, the essence of which is in combining objects. Functional programming is not only about combining functions and algebraic data structures, it also makes parallelism composable, which is almost impossible with other paradigms.

Thirdly, I have a secret weapon, a butcher’s knife, with which I will shred math to make it clearer for programmers. When you are a professional mathematician, you must be very careful to determine all your assumptions accurately, write out each expression properly, and build all your evidence strictly. This makes math articles and books extremely difficult to read by the uninitiated. I am a physicist by education, and in physics we have achieved amazing success using informal reasoning. Mathematicians laughed at the Dirac delta function, which was invented by the great physicist, P. A. M. Dirac, to solve some differential equations. They stopped laughing when they came up with a completely new branch of analysis, formalizing Dirac’s ideas and called the theory of distributions.

Of course, with the help of waving your arms you run the risk of saying something frankly wrong, so I will try to make sure that there is a solid mathematical theory behind the informal arguments in this book. I have a shabby copy of Sanders McLane’s book, Category Theory for Mathematicians, on my nightstand.

Since this book is about category theory for programmers, I will illustrate all the basic concepts using computer programs. You probably know that functional languages ​​are closer to mathematics than more popular imperative languages. They can also create more powerful abstractions. I had a natural temptation to say: you have to learn Haskell before category theory becomes available to you, but that would mean that category theory has no use outside functional programming, and that’s simply not true. So, I will give many examples in C ++. Of course, you will have to overcome the ugly syntax, and it will be more difficult to see patterns due to verbosity, and you may have to do a lot of copy-paste instead of using higher-order abstractions, but this is already a big part of the life of a C ++ programmer.

However, not everything is so simple with Haskell. You do not need to become a programmer on it, but you will have to master it as a language for sketching ideas that will later be implemented in C ++. That is how I started programming in Haskell. Its concise syntax and powerful type system helped me a lot with understanding and implementing C ++ - templates, data structures and algorithms. However, since I cannot expect readers to already know Haskell, I will introduce it gradually and explain everything on the go.

If you are an experienced programmer, you may think: I have been programming for a long time and do not worry about any category theory or functional methods, why change something? Of course, you cannot help but notice that in imperative languages ​​there is a steady trend towards the addition of new functionalities. Even Java, the bastion of object-oriented programming, added lambdas. C ++ has recently begun to grow at a frantic pace - new standards every few years - trying to catch up with a changing world. All this activity is preparation for destructive changes or, as we physicists call it, phase change. If you heat the water, it will finally boil. Now we are in the position of a frog, which must decide whether to continue swimming in warming water, or start looking for alternatives.

image

One of the driving forces for big change is the multi-core revolution. The predominant programming paradigm, object-oriented programming, does not give you anything in the field of concurrency, but instead encourages a dangerous and error-prone design. The basic principles of object orientation: the concealment, co-ownership and mutation of data is an ideal environment for data racing. The idea of ​​combining data with a mutex that protects them is good, but unfortunately locks are not composable, and hiding locks makes deadlocks more likely and less debugged.

Even in the absence of concurrency, the growing complexity of software systems is experiencing the scalability of imperative programming. Simply put, side effects get out of hand. Functions with side effects are easy and convenient to write. Side effects can, in principle, be encoded in their names and comments. A function called SetPassword or WriteFile obviously changes a certain state and has side effects, and we are used to it. And only when we start writing functions that have side effects, work with other functions that have side effects, and so on, then things start to get complicated. It’s not that the side effects are initially bad, the fact that they are hidden from the eyes is bad. Because of this, on a larger scale, it becomes impossible to manage them. Side effects are not scalable,

Changes in hardware and the growing complexity of software make us rethink the basics of programming. Just like the builders of the great Gothic cathedrals of Europe, we, in our craft, approach the limits of materials and structure. In Beauvais, France, there is an unfinished Gothic cathedral that witnesses this human struggle with natural restrictions. It was thought that he would break all the previous records of height and lightness, but in the process of construction a number of collapses occurred. “Crutches” protect him from complete destruction: iron rods and wooden supports. From a modern point of view, it is a miracle that so many Gothic structures were successfully completed without the help of modern materials science, computer modeling, finite element analysis and general mathematics and physics. I hope, that future generations will also be delighted with the programming skills we demonstrate by building sophisticated operating systems, web servers, and the Internet infrastructure. And, frankly, they should, because we did all this on a very flimsy theoretical basis. Our task is to improve these foundations if we want to move forward.

image
Crutches protecting the Beauvais Cathedral from destruction.

To be continued.

Category theory for programmers: a preface
Category: the essence of the composition
Types and functions
Categories, large and small
Categories Klesley

Also popular now: