In the programming language seminar this spring, I will introduce
category theory. I will use a simplified exposition with many examples
from computer science:
Basic Category Theory for Computer Scientists
Benjamin C. Pierce
(Series: Foundations of Computing Series, The MIT Press)
ISBN 0-262-66071-7 1991 paper $17.95
I will also provide several papers that motivate the concepts using
applications. The pre-requisites for the seminar are minimal: anybody
with knowledge of basic set theory, mathematical, and programming
maturity can follow the material. Familiarity with algebra or
functional languages is helpful but not necessary.
What is Category Theory and Why is it Relevant?
-----------------------------------------------
Category theory is a branch of pure mathematics that is becoming an
increasingly important tool in theoretical computer science,
especially in domain theory and programming language semantics where
it is already a standard language of discourse.
Category theory can explain all known programming constructs including
functions, assignments, jumps, concurrency, modules, etc, at an
abstract "syntax-free" level.
It has also proved invaluable in structuring, optimizing, and proving
theorems about recursive programs. Intuitively, category theory
provides generic programming constructs that capture patterns of
recursion for a large class of types in a uniform way. Not only does
this allow the specification of algorithms independently of the data
structures they operate on, but also it provides generic theorems and
optimizations that hold for every type.
Category theory has also found surprising applications in databases,
compiling Algol-like languages, and in specifying compiler
correctness.
Finally category theory is foundational in nature and can be applied
to much of mathematics, logic, and computer science. For example, in
1966, Lawvere wrote an article "The Category of Categories As A
Foundation of Mathematics," and in 1978, Thatcher, Wadner, and Wright
wrote an article about category theory entitled "Algebraic
Fundamentals for Theoretical Computer Science."