Grokking the Y-combinator
Most people think of the startup incubator when they hear Y-Combinator. Few people know though that it is also a functional programming concept that “allows you to implement recursion in a language that doesn’t necessarily support it natively.” And though there are multiple explanations that tell you how it works or how to derive it, few people intuitively grok what it has to do with incubating startups.
The explanation given on the FAQ site of Y-combinator though technically correct, skips over a lot of subtlety and depth.
Why did you choose the name “Y Combinator?”
The Y combinator is one of the coolest ideas in computer science. It’s also a metaphor for what we do. It’s a program that runs programs; we’re a company that helps start companies.
Hopefully by presenting an intuitive idea of what it does and connecting it to a few non-computer-science concepts, I can show just how interesting it is.
What it does
The Y-combinator is in essence, a method to get around the limitation of a function not being able to reference itself, i.e. the language doesn’t support recursion.
An example is this factorial function in Javascript. Because the factorial function references itself, it is not allowed.
It isn’t a very useful tool nowadays for most programmers as being unable to simply use recursion is not a common problem.
What’s interesting however is the abstracted version of the self-reference problem. Put in another way you can frame the limitation as:
“How does the self utilize the self if self cannot refer to self?”
“How does the nameless become named?”
Or more practically:
“How do you bootstrap yourself?”
Understanding the approach that the Y-combinator uses to resolve the recursion problem also indirectly helps us understand these more poetic and pragmatic questions.
The Y-Combinator in a Nutshell
The first thing to know about the Y-combinator is that it is possible to implement only in languages where functions are a first-class citizen and have the ability to return functions themselves. In other words, functions must be able to do things that do other things.
Here is an example showing partial-application in Javascript. Make sure you understand how functions are building functions in this example before going on.
Once the above is understood we can take a leap to the core of the Y-combinator. The way to write a factorial function without self-reference is to create a function that returns a function and then invoke it immediately, passing in a copy of itself .
Here’s a more annotated example.
And that’ s it! The essence of the Y-combinator is about looping together 2 anonymous functions to have the same effect of recursion. Because the function cannot point to itself via naming, it points to a “reflection” or “copy” which then points back!
This is incredibly beautiful in a way which I’ll expand on later.
This is what I believe to be the essence of the Y-combinator. This doesn’t go into too much depth, for example we don’t actually create a Y-combinator, but the links given at the top provide much more rigor and depth if you’re interested. I’ll also provide the Y-combinator derivation steps at the bottom but it’s mostly syntactic sugar and extricating of the Y-combinator as a generic tool.
The core insight is how the self-realization happens via reflection.
Implications
A tooth cannot bite itself, a hand cannot feel itself, the eye cannot see itself. Everything can realize “itself” only by a method of reflection such as the eye looking at the eye in a mirror or interaction with the world such as the tooth having a concept of it’s own hardness because of the various things it bites.
This works similar to a human table. By laying on someone who is laying on someone who is laying on someone in a chain that eventually leads back to you, you end up indirectly supporting yourself despite not being able to do so directly.
The Y-combinator thus is a way for functions to “self-actualize” the way that YC as an incubator allows startups to “self-actualize”. By utilizing the self as an input in a roundabout way, you create a Strange Loop and thus a degree of self-consciousness.
Of course, this is only possible in environments where functions can do things that do other things. If such higher-order functions are not possible, the Y-combinator is useless.
Large hierarchies for example often create cultures where being higher-order functions are disliked because of lack of predictability and control. Individuals should predictably only do 1 thing, otherwise the complex machinery cannot be controlled.
Startups however don’t have an existing identity to manage or protect. They must self-actualize or “die”. If a startup does not truly trust and delegate to its employees, it gives up the chance of truly becoming a living thing and instead becomes a dead machine, a lurching zombie mocking a semblance of life, or a virus replicating without thought or reason.
“How does the self utilize the self if self cannot refer to self?”
You utilize the reflections of the environment. The more you observe, the more you can make out who you are and with that knowledge are able to utilize yourself. Though you can never find or create a “true reflection.”
“How do you bootstrap yourself?”
Trust and delegate. You cannot pick up yourself up, but if you can help and trust others they will help and trust you. Raise the tide to raise yourself. Be open to serendipity by inspiring other. Don’t control things to such a large extent that the only surprises that can happen are bad surprises. Create an environment where higher-order functionality is possible whether this is your own life or a company’s life.
“How does the nameless become named?”
To name a thing is not to know a thing. To know a thing is to name a thing. To know a thing which already is named, you must first un-name it to begin the process of knowing it. Self-actualization is the same as self-realization.
Additional
Here’s the full derivation of the Y-combinator function which roughly maps to the post here.
