AI BriefingThe Origin of Y Combinator's Name: Lambda Calculus and the Essence of Recursion
Key point
This explains the Y Combinator concept in Lambda Calculus—the background behind Paul Graham naming Y Combinator—and the principle of implementing recursion, using Clojure and JavaScript.
Details
The Mathematical Background of Y Combinator
The Y Combinator is an important concept in functional programming and Lambda Calculus, and Paul Graham took the startup incubator's name from it. This name expresses 'a way to take another program and recursively amplify it,' which connects to the company's philosophy of helping startups grow recursively.
The Problem of Recursion in Lambda Calculus
In Lambda Calculus, functions cannot have names, so implementing recursion, which calls itself, is difficult to do directly. For example, when defining a factorial function, referencing the name factorial inside it becomes a free variable, causing an error.
- Omega Combinator: In the form
(fn [x] (x x)), it can call itself to create an infinite loop. - JavaScript example: The code
(function (a) { return a(a); })(function (a) { return a(a); })causes a stack overflow, demonstrating the principle of the Omega Combinator.
Solving Recursion via Y Combinator
Y Combinator is a higher-order function that creates a recursive function without self-reference. Using Y Combinator implemented in Clojure and JavaScript, you can compute factorial as follows.
- Clojure:
(Y (fn [f] (fn [n] (if (zero? n) 1 (* n (f (dec n))))))) - JavaScript:
Y((f) => (n) => (n === 0 ? 1 : n * f(n - 1)))
This approach proves that even if a language does not directly support recursion, a trick from Lambda Calculus can be used to implement recursive functionality.
