4 ms·

I would be really interested in hearing what patterns from abstract algebra you noticed. Also would you say the patterns are more due to the nature of the probl

by Dn_Ab 14y ago

I would be really interested in hearing what patterns from abstract algebra you noticed. Also would you say the patterns are more due to the nature of the problem or something common to all programming?

tikhonj 14y ago
First, I should note that I've been doing a lot of language stuff in Haskell and OCaml lately, so I might not be entirely representative. Also, I've only begun looking into abstract algebra. While I have a good idea of the very basics, I don't know much besides. The first thing that got me interested in the subject was rather domain-specific. I was writing a simple Prolog interpreter. In Prolog, there is the concept of a "most general unifier" (MGU). Given two expressions like f(X, 1) and f(2, Z) it's something like (X=2, Z=1). If the two expressions can be unified without any substitutions, you have an empty unifier. The match can also fail (you can't unify f(1) with f(2), for example). During resolution, you have to combine these MGUs together. This combination behaves algebraically. I'm pretty sure it's associative and commutative. The empty match is the identity and the failed match acts like zero. I think there is also another reasonable operation--rather than combining them, we alternate on different possibilities. This then acts like addition: the failed match becomes the identity element. (That is, given a choice between any match and a failed match, you can only choose the other match.) If I had known more about the subject, I suspect writing some of the code would have been much easier. Since then, I've also looked into more general uses of ideas from abstract algebra. The Haskell standard library has some types from abstract algebra like Monoid, and there are some other packages based on those ideas as well. And, of course, abstract algebra ties into category theory naturally, which is going to be useful in both haskell and OCaml. So the first patterns I noticed were inherent in the problem, but using Haskell and OCaml is convincing me that they are common to programming in general.
- Dn_Ab 14y ago
  I only just saw your reply. I hope it is not too late to reach you. Yeah, I was going to say that the most common algebra in programming seems to be monoids. Being aware of them would probably make some patterns people apply ritualistically more clear and obvious but I think that most experienced people have the notion implicitly. Category theory formulations are not as common in OCaml and I am hard pressed to find any practical use for them. No that is not quite true. Knowing concepts like fusion, natural polymorphisms, initial and final algebras, ana/cata/hylo morphisms make many fuzzy patterns concrete. And motivate many algorithms. But I have never found a use where a theorem was useful in deriving some part of a program.

by Dn_Ab 14y ago

tikhonj 14y ago

First, I should note that I've been doing a lot of language stuff in Haskell and OCaml lately, so I might not be entirely representative. Also, I've only begun looking into abstract algebra. While I have a good idea of the very basics, I don't know much besides. The first thing that got me interested in the subject was rather domain-specific. I was writing a simple Prolog interpreter. In Prolog, there is the concept of a "most general unifier" (MGU). Given two expressions like f(X, 1) and f(2, Z) it's something like (X=2, Z=1). If the two expressions can be unified without any substitutions, you have an empty unifier. The match can also fail (you can't unify f(1) with f(2), for example). During resolution, you have to combine these MGUs together. This combination behaves algebraically. I'm pretty sure it's associative and commutative. The empty match is the identity and the failed match acts like zero. I think there is also another reasonable operation--rather than combining them, we alternate on different possibilities. This then acts like addition: the failed match becomes the identity element. (That is, given a choice between any match and a failed match, you can only choose the other match.) If I had known more about the subject, I suspect writing some of the code would have been much easier. Since then, I've also looked into more general uses of ideas from abstract algebra. The Haskell standard library has some types from abstract algebra like Monoid, and there are some other packages based on those ideas as well. And, of course, abstract algebra ties into category theory naturally, which is going to be useful in both haskell and OCaml. So the first patterns I noticed were inherent in the problem, but using Haskell and OCaml is convincing me that they are common to programming in general.

Dn_Ab 14y ago
I only just saw your reply. I hope it is not too late to reach you. Yeah, I was going to say that the most common algebra in programming seems to be monoids. Being aware of them would probably make some patterns people apply ritualistically more clear and obvious but I think that most experienced people have the notion implicitly. Category theory formulations are not as common in OCaml and I am hard pressed to find any practical use for them. No that is not quite true. Knowing concepts like fusion, natural polymorphisms, initial and final algebras, ana/cata/hylo morphisms make many fuzzy patterns concrete. And motivate many algorithms. But I have never found a use where a theorem was useful in deriving some part of a program.