Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

January 26, 2022

Learning Computer Science With Categories

Posted by John Baez

The first book in Bob Coecke’s series on applied category theory is out, and the pdf is free — legally, even! — until 8 February 2022. Grab a copy now:

There are already books on category theory for theoretical computer scientists. Why the reverse? Yanofsky explains:

There’s just one catch: you need to know category theory. But if you’re here, maybe you do. If you don’t, it’s worth learning, because it’s like a magic key to many subjects. It helps you learn more, faster.

Posted at January 26, 2022 6:07 PM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/3376



3 Comments & 0 Trackbacks

Re: Learning Computer Science With Categories

It will be a shame if this book is not free forever, because I’m not sure what I’d rather link to folks who are interested in the topic.

I couldn’t help but notice that “compiler” only occurs once in the entire page:

One can think of any compiler as a functor from the category of a higher-level programming language to machine language, or to circuits.

Further, since compilers are just programs in Turing-complete languages, I think that we get some sort of ∞-category of compilers.

In order to show that these procedures are actually functors, we would have to show that they respect composition. In order to show that they are actually symmetric monoidal functors, we would have to show that they respect parallel composition. There is a lot of work!

I suppose that this second part, where it is hard to actually set up such a ∞-category, is the main reason that nobody has written up an explanation. It sounds like folks have been aware of the idea for a while.

Posted by: Corbin on January 27, 2022 5:50 AM | Permalink | Reply to this

Re: Learning Computer Science With Categories

Corbin wrote:

It will be a shame if this book is not free forever, because I’m not sure what I’d rather link to folks who are interested in the topic.

This book is published by Cambridge University Press, and publishers do want to sell things. But if this book is like most others, it will be made free, illegally, on a certain well-known website.

Posted by: John Baez on January 28, 2022 7:00 PM | Permalink | Reply to this

Re: Learning Computer Science With Categories

I looked briefly at the book. While being titled “Theoretical Computer Science” (which is a very big field) the book is only about computability and complexity theory.

it started out with an additional chapter which is available from the author’s website http://www.sci.brooklyn.cuny.edu/~noson/TCStext.html.

Other Fields of Theoretical Computer Science 132 7.1 Formal Language Theory 132 7.2 Cryptography 144 7.3 Kolmogorov Complexity Theory 154 7.4 Algorithms 159

That site also has the file “Answers to Selected Problems” which was omitted from the published version.

Posted by: RodMcGuire on January 28, 2022 8:38 PM | Permalink | Reply to this

Post a New Comment