You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.
Daniel Geisler (Apr 21 2020 at 04:32):Much of the nineties I spent writing object oriented code. I developed almost a mystical idea that the object oriented code I wrote was an aspect of the original object out there in the Universe. I wrote a few systems six, seven layers deep of objects. After a while the code seemed to self-organize out of complexity and I would check to see if the system already implemented features before I added them. At the time I was sure there was a CT connection. Is this what a monad is in software?
sarahzrf (Apr 21 2020 at 04:59):not really
sarahzrf (Apr 21 2020 at 05:00):i'm not sure i see the category theory
Johannes Drever (Apr 21 2020 at 05:17):OOP is mainly concerned about encapsulation and does not have a real notion of composition, IMHO. There are some attempts to base UML on category theory.
Daniel Geisler (Apr 21 2020 at 05:19):@Johannes Drever Can you elaborate on it not having a notion of composition? What about refactoring to break components into smaller more sophisticated systems?
sarahzrf (Apr 21 2020 at 05:23):that's kind of a general programming thing, it's not really oop-specific
sarahzrf (Apr 21 2020 at 05:23):er, hold on, "smaller more sophisticated systems"?
sarahzrf (Apr 21 2020 at 05:24):that description sounds strange to me
Daniel Geisler (Apr 21 2020 at 05:42):Sophisticated is often smaller. Please note I was pounding large amounts of code at the time using multiple best practices including CASE tools. My experience is practical, not theoretical. I have more than once felt software systems come alive.
sarahzrf (Apr 21 2020 at 05:46):im just unsure what you mean by "sophisticated"
sarahzrf (Apr 21 2020 at 05:47):usually i think of it as being roughly in opposition to "simple", and "simple" as being correlated with "small"
sarahzrf (Apr 21 2020 at 05:48):like, one major purpose of refactoring is to reduce complexity, no? and "complex" seems aligned with "sophisticated" to me
Daniel Geisler (Apr 21 2020 at 05:50):Sorry, I disagree. It doesn't go with my experience. That's OK. :slight_smile:
sarahzrf (Apr 21 2020 at 05:50):i mean
sarahzrf (Apr 21 2020 at 05:50):i'm asking, which part of that do you disagree with?
Daniel Geisler (Apr 21 2020 at 05:53):Sorry, I'm moderately autistic. Can you elaborate on sophistication?
sarahzrf (Apr 21 2020 at 05:56):i'm not sure what to say about it
sarahzrf (Apr 21 2020 at 05:56):if anything, i want to know what you mean by sophisticated
sarahzrf (Apr 21 2020 at 05:56):in this context
sarahzrf (Apr 21 2020 at 05:56):um, well, this is drifting off topic, it's not super important
Daniel Geisler (Apr 21 2020 at 05:59):Watch jewel like multilayered code where everything fits together in a wonderful fashion. Folks claimed they learned a lot about programming doing code reviews of my work. It is beautiful. :slight_smile: If the beauty of the code blows people's mind's then it is sophisticated.
sarahzrf (Apr 21 2020 at 06:10):ah
sarahzrf (Apr 21 2020 at 06:10):usually i think of "sophisticated" as meaning "complex"
sarahzrf (Apr 21 2020 at 06:10):or at least being similar in connotation
Daniel Geisler (Apr 21 2020 at 06:12):Sounds like I still don't know what a monad is. Back to the books.
Alexis Hazell (Apr 21 2020 at 06:14):I'm mainly aware of monads in the context of FP, rather than OOP. In FP, monads can be used to contain state / side-effects. But OOP comes in many forms, so we'd need to specify what particular form of OOP we're discussing first. E.g. are we talking class-based or prototype-based? Are interfaces / roles / traits involved?
Daniel Geisler (Apr 21 2020 at 06:26):Bill Gates wrote 4K Basic when others thought there wasn't enough memory. Or Waz's floppy drive with half the normal chips. All surprisingly small. All sophisticated.
sarahzrf (Apr 21 2020 at 06:29):it wouldntve occurred to me to describe them that way :shrug:
sarahzrf (Apr 21 2020 at 06:29):but it aint a formally defined term so im not gonna claim youre wrong!
Alexis Hazell (Apr 21 2020 at 06:36):Complexity in software often arises from lots of interacting state. OOP usually involves objects with mutable state, making analysis of behaviour more difficult than if one 'quarantines' mutability and uses pure functions as much as possible.
Daniel Geisler (Apr 21 2020 at 06:44):Maybe the moral of my story is if you are reading John Baez and programming, that your code could end up being CT flavored.
Alexis Hazell (Apr 21 2020 at 06:50):Haskell is very CT-flavoured, so you don't need to be reading John's work to end up making use of CT concepts. :-) Monads and optics (e.g. lenses) play a central role.
Daniel Geisler (Apr 21 2020 at 06:57):@Alexis Hazell thanks, now I have to download Haskell. :slight_smile:
Alexis Hazell (Apr 21 2020 at 07:02):If you've not already seen it, you might be interested in this post on the n-Category Café blog: https://golem.ph.utexas.edu/category/2020/01/profunctor_optics_the_categori.html
Johannes Drever (Apr 21 2020 at 07:10):Daniel Geisler said:
Johannes Drever Can you elaborate on it not having a notion of composition? What about refactoring to break components into smaller more sophisticated systems?
Parser combinators are a good example for composition. If you have a parser a :: Parser Expr and a parser b :: Parser Expr you can compose them and get another a <|> b :: Parser Expr. The type system gives some guarantees, so a lot of reasoning can be offloaded to the compiler.
Of course you can refactor code in OOP. But most OOP-language lack referential transparency which makes refactoring more difficult. Basically you have to manage a lot of coherence conditions in your head which might be taken care of the compiler and type system.
And there is parametric polymorphism. In Haskell it is quite common to write functions with parametric polymorphism. In OOP it is the default that a functions is attached to a class and manages specifically the state that object. There are for sure some libraries which are polymorphic, such as java.util.Collections. But already the fact that it lives in package util shows that it is somehow second-class.
Stelios Tsampas (Apr 21 2020 at 14:30):Daniel Geisler said:
Much of the nineties I spent writing object oriented code. I developed almost a mystical idea that the object oriented code I wrote was an aspect of the original object out there in the Universe. I wrote a few systems six, seven layers deep of objects. After a while the code seemed to self-organize out of complexity and I would check to see if the system already implemented features before I added them. At the time I was sure there was a CT connection. Is this what a monad is in software?
Hello Daniel :). I guess there might be more than one ways to abstract stuff. One that I definitely recommend in t his case is the coalgebraic approach found in Jacobs' Introduction to Coalgebra book (http://www.cs.ru.nl/B.Jacobs/CLG/JacobsCoalgebraIntro.pdf), Section 6.9. The key for this approach is that methods are a form of interaction, and hence observation, on a class (and of course observation is what coalgebras are about). But it gets more involved with the introduction of assertions as properties for classes.
Verity Scheel (Apr 21 2020 at 19:37):It’s hard to compare OOP and monads specifically. Monads are one tool in a toolbox, they’re great for expressing the sequencing of effects (including side effects like mutability, and some sorts of control flows, like exceptions and nondeterminacy and even continuations). Functions are of course the most essential part of a functional tooblox. And then with algebraic data types and other goodies you can express many other patterns, including not only monads but also recursion schemes and lenses. And the cherry on top is that typeclasses make it much more convenient. It’s like having a handle and a good organization scheme for your toolbox.
OOP is what would happen if you took the whole toolbox and tried to smelt it together or something. It doesn’t neatly correspond to any single tool, since it mixes parts of other tools in weird ways: OOP classes can be used to represent types of (usually mutable!) data, but it’s also mixed together with functions, and those functions can have effects, and you literally cannot separate out the mutable state and potentially cyclic interactions amongst objects, unless you adhere to quasi-FP guidelines.
What I love about FP is that you can tease apart these separate tools. (In fact, you’re encouraged or even forced to.) You can work in the StateT monad transformer and act as if you have mutable state (and you can use lenses to target specific portions of the state!), but you always know that the whole state you’re manipulating is contained in one gestalt and inert data object that you can pull out of the control flow at any time, so you can trivially do things like rolling back the state for failed transactions or whatnot.
Anyways, it’s a little like comparing apples to trees, monads to OOP, but those are my first thoughts.
Alexis Hazell (Apr 22 2020 at 04:40):Rongmin Lu said:
I think people had figured out the formal semantics of imperative programming early on, while functional programming had been substantially shaped by category theory itself.
I've been keeping an eye out for historic papers on FP + CT for the nLab 'functional programming' page, so if you know of any that should be added, please feel free to let me know. :-)
Alexis Hazell (Apr 22 2020 at 10:38):I presume you mean "the references on the Wikipedia page", since the nLab itself is a wiki. :-) But if so, since nLab entries are supposed to be from the nPOV, that nLab page should mainly be about the connections between FP and CT, not about FP in general, and I don't know which (if any) of those references discuss those connections.
Mike Stay (Apr 22 2020 at 19:26):Daniel Geisler said:
Much of the nineties I spent writing object oriented code. I developed almost a mystical idea that the object oriented code I wrote was an aspect of the original object out there in the Universe. I wrote a few systems six, seven layers deep of objects. After a while the code seemed to self-organize out of complexity and I would check to see if the system already implemented features before I added them. At the time I was sure there was a CT connection. Is this what a monad is in software?
Object-oriented programming is most closely connected with Lawvere theories and their variants. Generic interfaces with purely functional methods are very nearly presentations of categories with finite products. For example, here is a Java interface for a monoid:
interface Monoid<M> {
M mult(M a, M b);
M unit();
}
This interface presents a cartesian category T whose objects are tuples of Ms and whose morphisms are given by all compositions of the built-in morphisms duplication and deletion and the morphisms mult and unit from the interface.
Most OO languages don't allow you to enforce axioms as part of the type declaration, so instead of proofs, we resort to a comment on the interface and a test suite.
// Valid implementations satisfy
// associativity: for all a, b, c, mult(a, mult(b, c)) == mult(mult(a, b), c)
// unitality: for all a, mult(unit(), a) == a == mult(a, unit())
interface Monoid<M> {
M mult(M a, M b);
M unit();
}
This is a presentation of T modded out by associativity and unit laws; we call the resulting category Th(Mon), the "Lawvere theory of monoids".
Implementations of this interface are the same as product-preserving functors from Th(Mon) to the category Set of sets and functions.
class Add implements Monoid<Integer> {
public Integer mult(Integer a, Integer b) {
return a + b;
}
public Integer unit() {
return 0;
}
}
Note in this special case that we would usually call + "addition" instead of "multiplication", but we have to use the same method name as the interface.
The functor presented by this code maps the object M to the set of integers. Because the functor is product-preserving, it maps the tuple (M, M) to the tuple (Integer, Integer), and so on for all the other lengths. It maps the formal morphism M mult(M a, M b) to the actual function Integer mult(Integer a, Integer b), etc.
The category of product-preserving functors from Th(Mon) to Set and natural transformations between them is equivalent to the category Mon of monoids and monoid homomorphisms.
Given any implementation X of Monoid<M>, we can forget the monoid structure and just consider the set of values of type X. Similarly, given any monoid homomorphism, we can forget that it preserves multiplication and unit and consider it merely a function between two sets. That operation is a "forgetful functor" U:Mon -> Set.
U has a left adjoint F:Set -> Mon that picks out the "free monoid" on the given set, i.e. the set of strings on the alphabet S. Every monoid is the free monoid on some generators modulo some equations. For example, Add is the free monoid on the set of integers (whose elements are lists of integers) modulo the relation that a list is equivalent to the one-element list containing its sum.
You get a monad by composing the free and forgetful functors, though it's not usually presented that way in OO programming languages. Instead, a monad is a design pattern that's very similar to the interface for the monoid above. Instead of being generic in a datatype M, it is generic in a generic M<>. Java doesn't support this syntax, but Scala does. If Java did, the interface for a monad would probably look something like this:
interface Monad<M<>, X> {
M<X> mult(M<M<X>> mmx);
M<X> unit(X x);
}
Instead of mult taking two instances of a datatype M, mult now takes two iterations of a generic M on X. Similarly, instead of unit taking zero instances of a datatype M, unit now takes zero iterations of a generic M on X.
There are lots of different kinds of monads in use in OO languages. Parallel programming, exceptions, parsers, futures/promises, communication streams, continuations, loggers, gatekeepers (for ocaps-style revocation), and many other language features are implementable as monads. While OO languages tend to have specialized syntax for the most common of these, functional languages tend to support all monads with a common syntax, allowing programmers to extend the language with new monads while maintaining readability.
Aleksandar M. Bakic (May 12 2020 at 15:49):https://dev.to/amb007/comment/j23 I wonder if this is helpful