CCCs and the λ-calculus
Posted by John Baez
This blog entry is an excuse for continuing our discussion of cartesian closed categories (CCCs) and the λ-calculus in a slightly more organized way. Let’s focus on more or less “traditional” aspects here. If you prefer to talk about categorified or quantized versions of CCCs and the λ-calculus, go to the relevant entry and talk there.
To kick off the discussion, let’s start with a sketchy and highly oversimplified history of CCCs and the λ-calculus.
Categorical semantics was born in Lawvere’s celebrated 1963 thesis on algebraic theories:
- F. William Lawvere, Functorial Semantics of Algebraic Theories.
Algebraic theories are a simple formalism for reasoning about operations that satisfy equations. For example, since the concept of a “group” involves only some operations (multiplication, inverses…) satisfying equations, this concept can be formalized using an algebraic theory called $Th(Grp)$.
The role of semantics enters when we consider “models” of an algebraic theory. Loosely speaking, a model is just one of the things the theory seeks to describe. For example, a “model” of $Th(Grp)$ is just a group. Technically, an algebraic theory $T$ is a category with finite products, and a model is a functor that preserves finite products: $Z: T \to Set$ from $T$ to the category of sets. The basic idea is simple: if for example $T = Th(Grp)$, then $Z$ maps the abstract concept of “group” to a specific set, the abstract concept of “multiplication” to a specific multiplication on the chosen set, and so on, thus picking out a specific group.
Dual to the concept of semantics is the concept of syntax, which deals with symbol manipulation. Just as semantics deals with models, syntax deals with “proofs”. For example, starting from $Th(Grp)$ we can prove consequences of the group axioms merely by juggling equations. In the case of algebraic theories, the syntax often goes by the name of universal algebra:
- Stanley Burris and H.P. Sankappanavar, A Course in Universal Algebra.
In fact, universal algebra was around long before Lawvere introduced algebraic theories; he just modernized it with the realization that a model was a functor - hence his thesis title, “Functorial Semantics”.
The relevance of all this to computer science becomes visible when we note that a proof in $Th(Grp)$, or indeed in any algebraic theory, can be seen as a rudimentary form of computation. The “input” of the computation is a set of assumptions, while the “output” is the equation to be proved.
Treating proofs as computations may seem strained, but it becomes less so when we move to richer formalisms which allow for more complex logical reasoning. One of the most well-known is the lambda calculus, invented by Church and Kleene in the 1930s as a model of computation. Any function computable by the lambda calculus is also computable by a Turing machine, and according to the Church-Turing thesis these are all the functions computable by any sort of systematic process. Moreover, computations in the lambda calculus can actually be seen as proofs.
The aptness of this way of thinking was brought out in Landin’s classic paper
- P. Landin, A correspondence between ALGOL 60 and Church’s lambda-notation, Comm. ACM 8 (1965), 89-101, 158-165.
This began a long and fruitful line of research - see for example this:
- H. Barendregt, The Lambda Calculus, its Syntax and Semantics, North-Holland, 1984.
The power of the lambda calculus is evident in the textbook developed for MIT’s introductory course in computer science, which is available online:
- H. Abelson, G. J. Sussman and J. Sussman, Structure and Interpretation of Computer Programs.
It cites pioneers like Haskell Curry, and it even has a big λ on the cover!
Fans of Oz and the Wizard will be pleased to hear that students call it “the wizard book”, for the obvious reason. It’s used at over 100 colleges and universities, and it has spawned a secret society called The Knights of the Lambda Calculus, whose emblem celebrates the ability of the λ-calculus to do recursion:
In 1980, Lambek made a great discovery:
- Joachim Lambek, From lambda calculus to Cartesian closed categories, in To H. B. Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism, eds. J. P. Seldin and J. Hindley, Academic Press, 1980, pp. 376-402.
He showed that just as algebraic theories can be regarded as certain special categories, so can theories formulated in the lambda calculus: to be precise, these correspond to cartesian closed categories or CCCs for short. These are categories with finite products such that the operation
$a \mapsto x \times a$
has a right adjoint, the internal hom
$b \mapsto hom(x,b)$
In other words, we have a natural isomorphism
$HOM(x \times a, b) \cong HOM(a,hom(x,b))$
Here HOM denotes the usual set of morphisms from one object to another, while hom is the “internal hom”, which is itself an object in our category. If this is befuddling, take our category to be Set and take HOM = hom; then the above equation says:
“a function from $x \times a$ to $b$ is the same as a function from $x$ to the set of functions from $a$ to $b$.”
CCC’s just generalize this idea to other categories!
Lambek’s discovery introduced a semantics for the lambda calculus, since it lets us to speak of “models” of theories formulated in the lambda calculus: $Z: T \to Set$ just as we could for algebraic theories. These are again just functors that preserve finite products. In computer programming, the importance of a model is that it gives a picture of what a program actually accomplishes. A model Z sends any program to an actual function between sets.
There’s no way to list all the interesting references to CCCs and the λ-calculus, but here are some great online places to get started, starting out easy and working up to the harder ones:
- Mark Chu-Carroll, Lambda calculus.
- Mark Chu-Carroll, Category theory.
- Peter Selinger, Lecture notes on the lambda calculus.
- Phil Scott, Some aspects of categories in computer science.
and here’s a classic:
- Joachim Lambek and Phil J. Scott, Introduction to Higher Order Categorical Logic, volume 7 of Cambridge Studies in Advanced Mathematics, Cambridge U. Press, 1986.
Here are some things I’d like to talk about more:
- How do we describe the untyped λ-calculus as a CCC? I hear we just take the free CCC on one object, which I now call CCC[x], and throw in an isomorphism $x \cong hom(x,x)$ Is this enough to make all objects isomorphic, as I’d expect in an untyped world? How do we get an isomorphism $x \times x \cong x$? By adjointness we get a morphism $x \times x \to x$, but why is it an iso?
- What’s PCF? It’s a theory formulated in the lambda calculus; the acronym stands for “programming with computable functions”? Robin Houston says: “For anyone who’s unused to the jargon, PCF is simply typed λ-calculus with integers and booleans as base types, extended with primitives for arithmetic and recursion. It’s possibly the simplest typed language that is Turing complete.” You can read the precise definition in Selinger’s notes. But, I’d like to know more! For example, I’d like a description of the CCC corresponding to PCF. Something like “the free CCC containing a natural numbers object, a truth values object and….”
- Games and the free cartesian closed category on one object. James Dolan has a description of objects in CCC[x] as games, and morphisms as strategies of a certain funny sort where you can “take back” moves. Daniel Steffen has written about this, but I don’t know how to obtain his work. It would be great if we could coax either of these guys to explain this stuff here.
Okay - enough of this blogorrhea. Someone else say something!
Re: CCCs and the λ-calculus
Over in the original comment thread I tried to understand something John said about natural numbers in terms of models of CCCs.
I’ll try to summarize.
Any CCC $C$ has a canonical model $\mathrm{El} : C \to \mathrm{Set}$ which sends every object $x$ of $C$ to the set $\mathrm{El}(x)$ of morphisms $(1 \to x) \in \mathrm{Hom}_C(1,x)$.
Denoting internal Hom-objects by the lower case $\mathrm{hom}(x,y) \in \mathrm{Obj}(C)$, the claim is that for $C$ the free CCC on the single object $x$ we find that
is (isomorphic to) the set of natural numbers.
In order to follow this one has to know that in the free CCC $C$, we have precisely no morphism $1 \to x$.
Hence $\mathrm{El}(x) = \{\}$ is the empty set.
On the other hand, $\mathrm{Hom}( \mathrm{hom}(x,x), \mathrm{hom}(x,x) )$ contains $\mathbb{N}$-worth of morphisms, each of which representing the idea of taking an endomorphism $f$ of $x$ and taking it to the $n$th power, for $n$ some natural number.
I assume this means now that there are also $\mathbb{N}$-worth of morphisms $1 \to \mathrm{hom}( \mathrm{hom}(x,x), \mathrm{hom}(x,x) )$. If so, then, by definition, applying $\mathrm{El}$ to this latter expression produces a set with the cardinality of the natural numbers.
This is slightly counterintuitive in light of the fact that $\mathrm{Hom}(\mathrm{El}(x),\mathrm{El}(x))$ contains just a single element, namely the identity on the empty set.
But, after all, we are dealing with internal $\mathrm{hom}$s, so I am prepared to accept that slightly counterintuitive things may happen.
Hence I was about to say “ok, thanks, now I understand”. But unfortunately I am still confused!
Namely next, John says, we want to pass from the free CCC on $x$ to the category obtained from it by adding lots of isomorphisms, like $x \simeq \mathrm{hom}(x,x)$.
But this immediately implies that
is also the empty set!
Not sure if this is troublesome, but naïvely one tends to deduce from this that
I hope the first step is unjustified, because otherwise, applying $\mathrm{El}$ to this chain of isomorphisms, one finds that there is no natural number at all.
This really confuses me, because from what John said here it sounded like we do want to have all those isomorphisms present.
Personally, it seems to me that we do not want to consider the model $\mathrm{El}$ when thinking about $\lambda$-calculus. After all, we know that we want a model $N$ of our CCC such that $N(x)$ is the set of $\lambda$-expressions, not the empty set.
No?