Category Theory for Programmers: Preface
For some time now I have been thinking about the idea of writing a book on category theory for programmers. Not computer theorists, programmers - rather engineers than scientists. I know it 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 impulse to explain things. I admire Richardm 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 preface, which should motivate the reader to study category theory, and I hope to start a discussion and feedback.
I will try to convince you in a few paragraphs that this book is written for you, and dispel all your doubts about the need to study this, one of the most abstract areas of mathematics, in your precious free time.
My optimism is based on several observations. First, category theory is a treasure trove of extremely useful programming ideas. Haskell programmers have been drawing from it for a long time, and these ideas slowly seep 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 category theory. I’m not afraid to say that category theory is exactly the kind of mathematics that is particularly well suited for programmer thinking. This is because category theory, instead of dealing with details, operates on structure. It operates with such concepts that make programs composable.
')
Composition is at the very core of category theory; it is part of the category definition itself. And I argue that composition is the essence of programming. We combined things a long time ago, long before any great engineer came up with subroutines. Some time ago, the principles of structured programming made a revolution in programming - they made blocks of code 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 define all your assumptions accurately, write out each expression properly, and build all your evidence strictly. This makes mathematical articles and books extremely difficult for the uninitiated to read. 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, which formalized the ideas of Dirac and called the theory of distributions.
Of course, with the help of waving your arms, you risk saying something frankly wrong, so I will try to make sure that behind the informal arguments in this book there is a solid mathematical theory. I have a shabby copy of Sanders McLane's Theory of Categories 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 the more popular imperative languages. They can also create more powerful abstractions. I had a natural temptation to say: you must learn Haskell before category theory is available to you, but it would mean that category theory has no application beyond functional programming, which is simply not true. So, I will cite many examples in C ++. Of course, the ugly syntax will have to be overcome, and the patterns will be harder to see because of the verbosity, and you may have to do a lot of copy-paste, instead of using higher order abstractions, but this is a big part of the C ++ programmer’s life.
However, not everything is so simple with Haskell. You do not need to become a programmer on it, but you have to learn it as a language for sketching ideas that will later be implemented in C ++. This is how I started programming in Haskell. His short 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 as we go.
If you are an experienced programmer, you may think: I have been programming for a long time and have not been worried about any category theory or functional methods, so why change something? Of course, you cannot but notice that in imperative languages there is a steady trend towards the addition of new functionality. Even Java, the bastion of object-oriented programming, added lambdas. C ++ has recently begun to develop at a frantic pace — new standards every few years — trying to catch up with the changing world. All this activity is preparation for destructive changes or, as we physicists call it, a phase change. If you heat the water, it will eventually boil. We are now in the position of a frog, which must decide whether to continue swimming in the warming water, or start looking for alternatives.
One of the driving forces for big change is a multi-core revolution. The prevailing programming paradigm, object-oriented programming, does not give you anything in the field of parallelism, but instead encourages a dangerous and error-prone design. The basic principles of object orientation: covering, co-ownership and data mutation is the 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 with no concurrency, the growing complexity of software systems is experiencing the limits of scalability of imperative programming. Simply put, the side effects go out of control. 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 some 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. 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, and imperative programming is completely built on side effects.
Changes in hardware and the increasing complexity of software make us rethink the basics of programming. Just as the builders of the great Gothic cathedrals of Europe, we, in our craft, come to the limits of materials and structure. In Beauvais, in France, there is an unfinished Gothic cathedral, which stands to witness this human struggle with natural limitations. It was thought that he would beat all previous records of height and lightness, but during the construction process a number of collapses occurred. Crutches protect it from complete destruction: iron rods and wooden supports. From the modern point of view, it’s 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 impressed with the programming skills that we demonstrate, building complex operating systems, web servers and Internet infrastructure. And, frankly, they should, because we did all this on a very flimsy theoretical basis. Our task is to improve these fundamentals if we want to move forward.
Crutches protecting the Cathedral in Beauvais from destruction.
To be continued.
Category Theory for Programmers: Preface
Category: essence of composition
Types and functions
Categories big and small
Categories
I will try to convince you in a few paragraphs that this book is written for you, and dispel all your doubts about the need to study this, one of the most abstract areas of mathematics, in your precious free time.
My optimism is based on several observations. First, category theory is a treasure trove of extremely useful programming ideas. Haskell programmers have been drawing from it for a long time, and these ideas slowly seep 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 category theory. I’m not afraid to say that category theory is exactly the kind of mathematics that is particularly well suited for programmer thinking. This is because category theory, instead of dealing with details, operates on structure. It operates with such concepts that make programs composable.
')
Composition is at the very core of category theory; it is part of the category definition itself. And I argue that composition is the essence of programming. We combined things a long time ago, long before any great engineer came up with subroutines. Some time ago, the principles of structured programming made a revolution in programming - they made blocks of code 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 define all your assumptions accurately, write out each expression properly, and build all your evidence strictly. This makes mathematical articles and books extremely difficult for the uninitiated to read. 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, which formalized the ideas of Dirac and called the theory of distributions.
Of course, with the help of waving your arms, you risk saying something frankly wrong, so I will try to make sure that behind the informal arguments in this book there is a solid mathematical theory. I have a shabby copy of Sanders McLane's Theory of Categories 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 the more popular imperative languages. They can also create more powerful abstractions. I had a natural temptation to say: you must learn Haskell before category theory is available to you, but it would mean that category theory has no application beyond functional programming, which is simply not true. So, I will cite many examples in C ++. Of course, the ugly syntax will have to be overcome, and the patterns will be harder to see because of the verbosity, and you may have to do a lot of copy-paste, instead of using higher order abstractions, but this is a big part of the C ++ programmer’s life.
However, not everything is so simple with Haskell. You do not need to become a programmer on it, but you have to learn it as a language for sketching ideas that will later be implemented in C ++. This is how I started programming in Haskell. His short 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 as we go.
If you are an experienced programmer, you may think: I have been programming for a long time and have not been worried about any category theory or functional methods, so why change something? Of course, you cannot but notice that in imperative languages there is a steady trend towards the addition of new functionality. Even Java, the bastion of object-oriented programming, added lambdas. C ++ has recently begun to develop at a frantic pace — new standards every few years — trying to catch up with the changing world. All this activity is preparation for destructive changes or, as we physicists call it, a phase change. If you heat the water, it will eventually boil. We are now in the position of a frog, which must decide whether to continue swimming in the warming water, or start looking for alternatives.
One of the driving forces for big change is a multi-core revolution. The prevailing programming paradigm, object-oriented programming, does not give you anything in the field of parallelism, but instead encourages a dangerous and error-prone design. The basic principles of object orientation: covering, co-ownership and data mutation is the 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 with no concurrency, the growing complexity of software systems is experiencing the limits of scalability of imperative programming. Simply put, the side effects go out of control. 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 some 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. 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, and imperative programming is completely built on side effects.
Changes in hardware and the increasing complexity of software make us rethink the basics of programming. Just as the builders of the great Gothic cathedrals of Europe, we, in our craft, come to the limits of materials and structure. In Beauvais, in France, there is an unfinished Gothic cathedral, which stands to witness this human struggle with natural limitations. It was thought that he would beat all previous records of height and lightness, but during the construction process a number of collapses occurred. Crutches protect it from complete destruction: iron rods and wooden supports. From the modern point of view, it’s 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 impressed with the programming skills that we demonstrate, building complex operating systems, web servers and Internet infrastructure. And, frankly, they should, because we did all this on a very flimsy theoretical basis. Our task is to improve these fundamentals if we want to move forward.
Crutches protecting the Cathedral in Beauvais from destruction.
To be continued.
Category Theory for Programmers: Preface
Category: essence of composition
Types and functions
Categories big and small
Categories
Source: https://habr.com/ru/post/245797/
All Articles