왜 폴 그레이엄은 회사 이름을 Y Combinator라고 지었을까

폴 그레이엄이 스타트업 지원 회사 이름을 왜 Y Combinator라고 지었는지를 함수형 프로그래밍의 Y 콤비네이터 개념으로 풀어낸 글이다. Clojure와 자바스크립트 코드로 lambda calculus의 콤비네이터와 재귀 원리를 단계적으로 구현하며 개념을 설명한다.

핵심 포인트

Y Combinator는 멋진 회사 이름이 아니라 함수형 프로그래밍의 중요한 개념
Lisp 변형인 Clojure의 단순한 문법(operator operand)으로 defn·fn·def·if와 factorial을 소개
콤비네이터는 자유 변수가 없는 함수로, I(identity)와 K(constant) 콤비네이터를 예로 설명
자기 자신을 호출하는 형태로 이름 없이 무한 재귀(오메가 콤비네이터)를 만듦
Y 콤비네이터로 언어가 재귀를 지원하지 않아도 람다만으로 재귀를 구현할 수 있음을 보임

상세 정리

언어 선택: 문법이 거의 없다시피 단순한 Clojure로 개념을 설명하고, 접근성을 위해 동일 구현을 자바스크립트로도 병기했다.
기본 문법: defn으로 함수 생성, fn으로 람다, def로 값 정의, if로 조건을 다루고 이를 조합해 재귀 factorial을 구현했다.
문제 제기: factorial 본문에서 자기 이름 factorial을 참조하는 부분은 lambda 관점에서 free variable이라, 이름 없이 재귀를 만들 방법을 묻는다.
Combinator 정의: 위키의 functions without free variables를 인용해, body에서 매개변수로 bind된 변수만 쓰는 함수가 콤비네이터라고 설명했다.
I 콤비네이터: 들어온 인자를 그대로 리턴하는 항등 함수로 함수 합성의 기본이 된다.
K 콤비네이터: 두 번째 인자가 무엇이든 첫 번째 인자를 리턴하는 constant 함수를 만든다.
오메가 콤비네이터: 자기 자신을 인자로 적용하는 함수는 무한 실행되며 브라우저·node에서 Maximum call stack size exceeded를 낸다. 이것이 재귀의 가장 단순한 형태다.
재귀 일반화: factorial의 자기 참조를 인자 f로 넘겨 (f f)로 호출하는 factorial-Y로 바꾸고, 이를 자기 자신에 적용해 이름 없이 재귀가 도는 걸 확인했다.
Y 콤비네이터: 자기 호출 부분을 대신 처리하는 Y를 정의하면, 자기 호출을 제거한 factorial-final을 Y에 넘겨 재귀 실행할 수 있다.
결론: 콤비네이터는 한 프로그램이 다른 프로그램을 실행하는 방법을 표현하며, Y 콤비네이터는 받은 프로그램을 재귀로 증폭시킨다. 폴 그레이엄이 스타트업을 재귀적으로 증폭시키는 회사를 지향해 이 이름을 붙였을 것이라 해석했다.