Theoretical Computer Science for the Working Category Theorist [pdf] | Hacker News Reader

Theoretical Computer Science for the Working Category Theorist [pdf]

arxiv.org

76 pointsaq3cn8 comments

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.

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_Mat... and has been used many times: https://imgur.com/21umyW8. It's the blah-considered-harmful of its class.

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.

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.

Can you name a better source?

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

[1] https://arxiv.org/abs/1211.5762

[2] https://ncatlab.org/nlab/show/computer+science

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.

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

Reply on news.ycombinator.com