Baking the Y Combinator from Scratch

Summary

It's a pedagogical pet peeve of mine when technical concepts are simply listed in their fully developed state, with little in the way of motivation, derivation, or historical context. This, I think, is like publishing a cookbook filled with beautiful pictures of cakes, but no recipes.My aim with the "Baking <x> from scratch" series is to describe not only what, but how and why, with the hope that this will lead to a richer and more durable understanding.The Famous Y combinatorThis post is about the Y combinator. Not Y Combinator the accelerator, but the mathematical construct that it's named after - the Y combinator.The Y combinator looks like this:$$ Y = \lambda f. \enspace (\lambda x. \enspace f(x \enspace x)) \enspace (\lambda x. \enspace f(x \enspace x)) $$Confronted with this definition, you might ask yourself: Why does it look like that? What is it used for? Why do people still talk about it? (What the heck is a combinator?) The one-line answer to all of these is: "the Y combinator implements recursion in functional languages that don't allow for explicit self-reference", but it's worth going a little deeper than that. In my opinion, the easiest way to understand what the Y combinator is, at a fundamental level, is to focus on how it produces fixed points. The easiest way to understand why it's important is to focus on how it can be used to implement recursion. In Part 1 we'll do the former (answering 1. and half of 2. in the process) and in Part 2 we'll do the latter (answering 3. and the other half of 2.) (We'll answer bonus question 4 later in this article!) The Y combinator was devised by Haskell Curry, an influential logician who has the unique distinction of lending his name to both a programming technique and a programming language. It is also known as the "Fixpoint Combinator" (for reasons we'll soon discuss) and the "Paradoxical Combinator" (for reasons we'll investigate in the second half of this post.)The Lambda CalculusThis post presumes that you'r...