Y Combinator 이름의 유래: Lambda Calculus와 재귀의 본질

Y Combinator의 수학적 배경

Y Combinator는 함수형 프로그래밍과 Lambda Calculus에서 중요한 개념으로, 폴 그레이엄이 스타트업 인큐베이터 이름을 이에서 따왔다. 이 이름은 '다른 프로그램을 받아 재귀적으로 증폭시키는 방법'을 표현하며, 스타트업이 재귀적으로 성장하도록 돕는 회사의 철학과 맞닿아 있다.

Lambda Calculus와 재귀의 문제

Lambda Calculus에서는 함수가 이름을 가질 수 없으므로, 자기 자신을 호출하는 **재귀(recursion)**를 직접 구현하기 어렵다. 예를 들어 팩토리얼 함수를 정의할 때 내부에서 factorial이라는 이름을 참조하면 이는 free variable이 되어 오류를 발생시킨다.

• Omega Combinator: (fn [x] (x x)) 형태로 자기 자신을 호출하여 무한 루프를 만들 수 있다.
• JavaScript 예시: (function (a) { return a(a); })(function (a) { return a(a); }) 코드는 스택 오버플로우를 일으키며 Omega Combinator의 원리를 보여준다.

Y Combinator를 통한 재귀 해결

Y Combinator는 자기 참조 없이 재귀 함수를 생성하는 고차 함수다. Clojure와 JavaScript로 구현된 Y Combinator를 사용하면 다음과 같이 팩토리얼을 계산할 수 있다.

• 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)))

이 방식은 언어가 재귀를 직접 지원하지 않더라도 Lambda Calculus의 트릭으로 재귀 기능을 구현할 수 있음을 증명한다.