July 20th, 2008

The Y Combinator

OK, I'm going to try to explain what the Y combinator is, why it's interesting, and how it works. I'll have to include a bit of background information to try to make this post self-contained.

The Y combinator has become a bit of a cool buzzphrase since Paul Graham named his startup incubator company Y Combinator. Why did he choose that name? I think the reason is that he wanted to attract the kind of programmers who were smart enough to have heard about the Y combinator, and who actually care about this kind of thing. So if you understand the Y combinator, maybe you can get some brownie points with Paul if you're interested in working with his company. If you meet him, say hi for me.

Before I explain what the Y combinator is or why (no pun intended) it's important, I want to explain the problem that the Y combinator solves. Let's say you have a very simple programming language which does not have recursion as a built-in feature. (If you don't know what recursion is, Wikipedia is your friend.) However, let's say that your programming language does have one fairly advanced feature: it supports first-class functions. This means that functions can be treated as data: they can be passed as arguments to other functions, they can be created on the fly, and they can be returned as the result of a function. As we'll see, some very simple languages do have this property.

So what is the problem that the Y combinator solves? Basically, it's this: The Y combinator allows us to define recursive functions in computer languages that do not have built-in support for recursive functions, but that do support first-class functions.

That's it. That's what the Y combinator allows us to do. It's important to note that the Y combinator is mainly important to theoretical computer scientists, especially programming language theorists who tend to work a lot with minimal programming languages. It's unlikely that you're going to be using it much in practical programming (or at least I haven't; maybe that just means that I'm not enlightened enough yet). So why should you care, other than as a way to impress Paul Graham when you present him with your cool internet startup idea? For this reason: it's one of the most beautiful and counterintuitive ideas in all of computer science. The Y combinator is one of those things that makes me feel like computer science is an art on the level of great painting or poetry. It's the same reaction I have when I think about Godel's incompleteness theorem. Basically, learning about the Y combinator will teach you to appreciate beauty in programming.

Collapse )