4 ms·

Theoretical Computer Science for the Working Category Theorist [pdf]

76 points by aq3cn 9y ago

100ideas 9y ago
I'm enjoying the Category Theory party this week on HN!
mathgenius 9y ago
The thing is, any "working category theorist" can see the objects and morphisms of a category from a mile away and don't really need these things pointed out. This paper seems to be a fairly superficial dressing of some computer science ideas using category theory language. No mention of natural transforms, which is the real meat of category theory (or at least, the first layer of meat.) No mention of monads or adjunctions. And these things play a big part in theoretical computer science (eg. Denotational Semantics.) I'm not saying it's a bad paper, but it doesn't deserve this title, or at least, needs much more justification for why it should have this title. Digging a bit deeper I do see some limit diagrams, but still, this is fairly easy stuff to see for the expert.
- jimhefferon 9y ago
  Can you name a better source?
  - mathgenius 9y ago
    Better source for applications of category theory in computer science? This is a very big subject... I see that the author of the paper has some references in his conclusion that dig a bit deeper into this.
  - danharaj 9y ago
    For a professional category theorist interested in theoretical computer science? The thing is, they could easily just dive into reading some papers on the subject. The intuition and mechanical skill of category theory is easily adapted to thinking about computation. Here are some relatively introductory treatments of some parts of CS in category theory: Introduction to Higher-Order Categorical Logic - Lambek and Scott Categorical Logic from a categorical point of view - Mike Shulman [0] Classical Lambda Calculus in Modern Dress - Martin Hyland [1] Computer Science page on the nlab - great place to get lost [2] [0] http://mikeshulman.github.io/catlog/catlog.pdf http://mikeshulman.github.io/catlog/catlog.pdf [1] https://arxiv.org/abs/1211.5762 https://arxiv.org/abs/1211.5762 [2] https://ncatlab.org/nlab/show/computer+science https://ncatlab.org/nlab/show/computer+science
- jonsterling 9y ago
  Not only this, but strangely it doesn't use standard methods or names in the categorical understanding of computer science. All this business about "CompFunc" as a category of sets and computable functions, but I see nothing about partial combinatory algebras or realizability.
- dang 9y ago
  The title is meant to be playful, since it reverses a famous trope that (as you probably know) comes from https://en.wikipedia.org/wiki/Categories_for_the_Working_Mathematician https://en.wikipedia.org/wiki/Categories_for_the_Working_Mat... and has been used many times: https://imgur.com/21umyW8 https://imgur.com/21umyW8. It's the blah-considered-harmful of its class.
- Tomminn 9y ago
  Never assume mathematicians can see past their little definition/lemma/theorem games to solve actual problems where those definitions/lemmas/theorems are "obviously" applicable. Some can, but a surprising number can't. I think this is due to a destructive meme that has crippled the minds of many mathematicians, causing them to instinctively equate applying their definition/lemma/theorem games to actual problems with low status.

76 points by aq3cn 9y ago

I'm enjoying the Category Theory party this week on HN!

The thing is, any "working category theorist" can see the objects and morphisms of a category from a mile away and don't really need these things pointed out. This paper seems to be a fairly superficial dressing of some computer science ideas using category theory language. No mention of natural transforms, which is the real meat of category theory (or at least, the first layer of meat.) No mention of monads or adjunctions. And these things play a big part in theoretical computer science (eg. Denotational Semantics.) I'm not saying it's a bad paper, but it doesn't deserve this title, or at least, needs much more justification for why it should have this title. Digging a bit deeper I do see some limit diagrams, but still, this is fairly easy stuff to see for the expert.

jimhefferon 9y ago
Can you name a better source?
- mathgenius 9y ago
  Better source for applications of category theory in computer science? This is a very big subject... I see that the author of the paper has some references in his conclusion that dig a bit deeper into this.
- danharaj 9y ago
  For a professional category theorist interested in theoretical computer science? The thing is, they could easily just dive into reading some papers on the subject. The intuition and mechanical skill of category theory is easily adapted to thinking about computation. Here are some relatively introductory treatments of some parts of CS in category theory: Introduction to Higher-Order Categorical Logic - Lambek and Scott Categorical Logic from a categorical point of view - Mike Shulman [0] Classical Lambda Calculus in Modern Dress - Martin Hyland [1] Computer Science page on the nlab - great place to get lost [2] [0] http://mikeshulman.github.io/catlog/catlog.pdf http://mikeshulman.github.io/catlog/catlog.pdf [1] https://arxiv.org/abs/1211.5762 https://arxiv.org/abs/1211.5762 [2] https://ncatlab.org/nlab/show/computer+science https://ncatlab.org/nlab/show/computer+science
jonsterling 9y ago
Not only this, but strangely it doesn't use standard methods or names in the categorical understanding of computer science. All this business about "CompFunc" as a category of sets and computable functions, but I see nothing about partial combinatory algebras or realizability.
dang 9y ago
The title is meant to be playful, since it reverses a famous trope that (as you probably know) comes from https://en.wikipedia.org/wiki/Categories_for_the_Working_Mathematician https://en.wikipedia.org/wiki/Categories_for_the_Working_Mat... and has been used many times: https://imgur.com/21umyW8 https://imgur.com/21umyW8. It's the blah-considered-harmful of its class.
Tomminn 9y ago
Never assume mathematicians can see past their little definition/lemma/theorem games to solve actual problems where those definitions/lemmas/theorems are "obviously" applicable. Some can, but a surprising number can't. I think this is due to a destructive meme that has crippled the minds of many mathematicians, causing them to instinctively equate applying their definition/lemma/theorem games to actual problems with low status.