categories and the lambda calculus
The n-Category Café is a blog written by mathematical physicists with a focus on the world of Category Theory and its, so to speak, applications. Not the usual recommendation in a programming musing, except for the fact that one of the Café's regulars, John Baez (of This Week's Finds in Mathematical Physics fame), is very interested in the connection between categories and lambda calculus, and has recently posted an article entitled CCCs and the λ-calculus over at the Café.
In case you're wondering, CCC stands for Cartesian-closed category: you'll find a lot of links in John's post explaining what does it exactly mean. He also mentions prominently our beloved SICP, including the emblem of the Knights of the Lambda Calculus, and is very fond of the fact that Abelson and Sussman's work is known as the wizard book, for he has a very funny (and totally unrelated) intro to general relativity called Oz and The Wizard. But there are many more interesting links in John's article. For instance, if you're still wondering what on Earth a Cartesian-closed category is, you can read Mark Chu-Carroll's introductions to lambda calculus and category theory.
But the real reason of this post is that i've found in there a delicious article that i had lost track of: David Keenan's To Dissect a Mockingbird is the nicest introduction to lambda calculus and SKI combinators i've ever read. David takes as inspiration Raymond Smullyan's classic To Mock a Mockingbird (wholeheartedly recommended, as anything written by Smullyan, for that matter), who explains combinators by means of an enchanted forest inhabited by peculiar birds (if you've never read anything by Smullyan, here's an excerpt from his book This book needs not title, put on-line by no other than Donald Knuth). In David's words:
[T]he theory of combinators is an abstract science dealing with objects whose only important property is how they act upon each other. We are free to choose other properties of these objects in any way we like. In his delightful book To mock a mockingbird, Smullyan chooses birds for his combinators, in memory of Haskell Curry, an early pioneer in the theory of combinators and an avid bird-watcher. […] Smullyan also notes in his preface,
"This remarkable subject is currently playing an important role in computer science and artificial intelligence Despite the profundity of the subject, it is no more difficult to learn than high school algebra or geometry."
In the hope of making it even easier I introduce the following graphical notation by extending Smullyan's bird metaphor.
and he goes on developing a sort of lambda calculus by pictures, or by movies. John Baez gives more details of the math involved in his follow-up post Categorifying CCCs: computation as a process, again at the n-Category Café. Too fun and instructive to let it pass, if you ask me.
