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

남영환, 이종립 게시 날짜: 2021.04.30.

폴 그레이엄은 스타트업을 지원하는 회사명을 와이 콤비네이터(Y Combinator)라고 지었습니다.

그런데 Y Combinator는 단순히 멋있는 회사 이름이 아닙니다. 함수형 프로그래밍의 중요한 개념 중 하나이기도 합니다.

폴 그레이엄의 Y Combinator 람다 계산법의 Y Combinator Lisp의 Combinator
image \(\lambda f . (\lambda x . ( f ( x x ) ) \lambda x . ( f ( x x )))\) image

세계 최고의 Lisp 해커인 폴 그레이엄은 아마도 함수형 프로그래밍의 Y Combinator에서 회사의 이름을 따왔을 것입니다.

Y Combinator의 의미를 알아보면 그가 무엇을 꿈꿨을지 엿볼 수 있지 않을까요?

Clojure - 오늘 사용할 언어

일전에 기술 블로그에서 lambda calculus에 대해서 글을 적었습니다.

앞의 글에서는 lamda calculus의 표현식을 사용했지만 이번에는 Clojure라는 언어를 간단하게 소개하고, Y Combinator를 설명하는 데 사용하려 합니다. Clojure는 Lisp의 변형으로 문법이 아주 단순합니다. 물론 키워드, 예외적인 문법 등이 있지만 오늘은 필요한 문법만을 소개하겠습니다.

이 글에서는 간단하고 명료하게 설명하기 위해 몇몇 디테일한 정보는 생략하겠습니다.

Clojure 문법 소개

Clojure의 문법은 기본적으로 아래의 형태를 가집니다.

(operator operand-1 operand-2 ...)

끝입니다. 폴 그레이엄의 말을 빌리자면 Lisp은 문법이 단순하다기보다 문법이 없기에 특이하다고 할 수 있습니다.

이제 대표적인 operator 들을 알아보겠습니다.

defn - 함수 생성

함수를 생성할 때는 defn이라는 operator를 사용합니다.

  • 그다음부터 위치되어 있는 요소들은 operand입니다.
  • 두 번째 operand - 함수명을 말합니다.
  • 세 번째 operand - [...] 이런 대괄호로 감싸서 나열된 값(벡터라고 부른다)을 매개변수로 받으며
  • 네 번째부터 나열되는 operand 들 - 평가될 값들(함수 포함)

형태는 아래와 같습니다.

(defn function-name [arg1 arg2]
	(println arg1 arg2)
	"return value")

실행 결과.

(function-name 1 2)
1 2  ;; 출력된 값
"return value"  ;; 리턴된 값 (마지막에 평가된 값을 리턴한다)

fn - 람다

람다(lambda)는 fn이라는 이름의 operator를 사용합니다.

함수명을 지정하는 것 빼고는 defn과 동일합니다.

(fn [a b] (+ a b))

실행 결과.

((fn [a b] (+ a b)) 1 2)
3   ;; 출력된 값

혹은 좀 더 짧게 쓰는 방법도 있습니다.

#(+ x %)    ;; (fn [x] (+ x 1)) 와 동일
#(+ %1 %2)  ;; (fn [x y] (+ x y)) 와 동일

def - 정의

def는 데이터에 이름을 정의한다고 생각하면 좋겠습니다.

첫 번째 인자(operand)에는 이름을 정의하면 되고, 두 번째 인자(operand)에는 연결될 값을 지정합니다.

(def a 1)
a ;; 1

Clojure는 함수도 값이기 때문에 defn으로 정의된 함수는 def로도 표현할 수 있습니다.

즉, 아래의 두 코드는 동일한 일을 합니다.

(defn sum [a b] (+ a b))

(def sum (fn [a b] (+ a b)))

if - 조건문

Clojure에서 if문은 lambda calculus의 if문과 유사합니다.

(if predicate true-expression false-expression) 형태로 이루어집니다.

아래 사용 예시를 보겠습니다.

(if true "1" "2")
;; "1"

(if false "1" "2")
;; "2"

factorial - 예제

예시로 factorial을 만들어 보겠습니다.

zero? , * , - 는 코드의 간단함을 위해 기본적으로 주어진다고 가정하겠습니다.

(defn factorial [n]
	(if (zero? n)
		1
		(* n (factorial (- n 1)))))

;; 실행해보면
(factorial 5)
120

Y Combinator를 맛보기 전에…

Combinator란?

위키의 말을 빌리자면

Combinator : functions without free variables

콤비네이터 : 자유 변수가 없는 함수

즉, 콤비네이터는 자유 변수를 사용하지 않습니다.

따라서 콤비네이터 람다를 만들 때에는 body에서 모두 매개변수로 연결(bind)된 변수만 사용합니다.

다음은 Combinator의 한 예입니다.

(fn [a] a)

a는 매개변수로 들어온 이름이기 때문에 자유 변수가 아니므로 사용할 수 있습니다.

같은 이유로 다음은 Combinator가 아닙니다.

(fn [a] b)

b는 매개변수로 들어온 이름이 아니며, 출처가 불분명합니다(free variable).

I Combinator

I(identity) Combinator는 들어온 인자를 단순히 리턴하는 Combinator입니다.

(fn [a] a)

여기서부터는 Clojure 문법에 익숙하지 않은 분들을 위해 같은 의미를 가진 자바스크립트 코드 예제도 함께 보여드리도록 하겠습니다.

만약 자바스크립트로 I Combinator를 표현한다면 다음과 같을 것입니다.

function i_combinator(a) {
    return a;
}

identity function이라고 불러도 무방합니다. 아무런 효과도 없어 보이는 이 함수가 무슨 의미인가 라고 할 수 있지만 I Combinator는 함수 합성에 기본이 됩니다.

K Combinator

K(constant) Combinator는 constant함수를 리턴하는 Combinator입니다.

(fn [a]
  (fn [b]
    a))

이를 자바스크립트로 표현하면 다음과 같을 것입니다.

fucntion k_combinator(a) {
    return function(b) {
        return a;
    }
}

K Combinator는 b가 어떤 값이 들어오더라도 a를 리턴하는 함수를 만들 수 있습니다.

(def always-3 ((fn [a]
                 (fn [b]
                   a)) 3))

(always-3 10)  ;; 3
(always-3 11)  ;; 3

이 역시 자바스크립트라면 다음과 같을 것입니다.

const always_3 = k_combinator(3);

always_3(10);   // 3
always_3(11);   // 3

Y Combinator로 가는 여정

이름 없는 함수들의 무한루프 \(\Omega\) Combinator

우리는 lambda를 이용하여 무한한 재귀 루프를 만들 것입니다.

간단한 무한 루프를 만들겠다면 아래처럼 자기 자신을 호출하는 것을 생각할 수 있습니다.

(defn a [] (a))

fucntion a() {
    a();
}

하지만 이렇게 body에서 정의한 함수 이름을 바로 사용하는 방식은 함수에 이름을 a라고 지을 수 있을 때나 가능한 일입니다.

좀 더 이해가 쉽게 보여드리기 위해 다음처럼 변경하겠습니다.

(def a (fn [] a))

lambda의 관점에서 본다면 a는 free variable입니다.

함수만으로는 알 수 없는 어디선가에서 연결을 해줘야 하죠. 이건 언어적으로 지원을 해줘야 하는 문제입니다.

만약에 언어에서 지원해주지 않는다면 무한루프조차 만들 수 없는 걸까요?

함수만으로는 할 수 없는 일일까요?

아닙니다. lambda calculus의 트릭만으로 무한루프를 만들 수 있습니다.

바로 자기 자신을 호출하는 형태를 만들어내면 됩니다.

#(% %)

다음은 위의 Clojure 코드와 똑같은 의미를 가진, 자바스크립트 코드입니다.

fucntion (a) {
    return a(a);
}

물론 이 함수를 실행하려면 일반적인 호출이 아니라 다음과 같이 호출해야 합니다.

(function (a) {
    return a(a);
})(function() {
    return 3;
});

이 코드를 축약하면 다음과 같이 표현할 수도 있을 것입니다(웹 브라우저 개발자 도구 콘솔이나 node.js에서 실행해 보세요).

// 짠! JavaScript입니다.
((a) => a(a))(() => 3);

마치 Lisp 코드처럼 보이는군요. 더글라스 크록포드가 "JavaScript: The Good Parts"에서 자바스크립트에 대해 C 언어의 옷을 입은 Lisp이라고 이야기했던 것이 생각나는군요.

자바스크립트의 함수는 어휘적 유효 범위를 가진 일급 객체 (first-class object) 입니다. 또한 주류가 된 첫 번째 람다 (lambda) 언어며, 좀더 깊이 들어가면, 이름처럼 자바에 가깝기보다는 Lisp 언어 그리고 Scheme 언어와 더 많은 공통점이 있습니다. 자바스크립트는 C 의 옷을 입은 Lisp 이라고 할 수 있습니다. 놀라울 정도로 강력한 언어적 특징은 바로 이러한 특성에서 기인한 것입니다.

– 자바스크립트 핵심 가이드, 더글라스 크록포드1

이 함수는 매개변수 1개를 받아 그대로 (operator operand) 형태로 함수 적용을 합니다.

이 함수를 아래와 같은 형태로 만들어줍니다.

(#(% %) #(% %))
or
((fn [x] (x x)) (fn [x] (x x)))

자바스크립트로는 다음과 같이 합니다.

(function (a) {
    return a(a);
})(function (a) {
    return a(a);
});

이 함수는 무한으로 실행될 것입니다.

node.js나 웹 브라우저에서 실행하면 Uncaught RangeError: Maximum call stack size exceeded 에러가 발생할 것입니다.

합쳐지는 듯하면서 다시 원래 코드로 돌아오면서 끝없이 펼쳐지고 줄어듭니다.

아무것도 하지 않고 무한루프만 도는 것이 전혀 의미 없는 것처럼 보입니다.

하지만 이것이 재귀의 가장 간단한 형태이므로 재귀를 만들 때 위 코드를 모방할 수 있을 것 같습니다.

이것을 우리는 \(\Omega\)(omega) Combinator라고 합니다.

참고로 lambda calculus에서는 어떤 함수(프로그램)가 무한루프가 돌게 될지 확인할 수 없습니다. 이 문제는 튜링의 정지 문제와 상통하는 문제입니다.

Lisp를 사용하다 보면 모든 것은 () 안에 있는 것처럼 보이기 시작하며, 결국 모두 함수가 아닐까 라는 상상을 하게 만듭니다. 결국 하나의 프로그램은 괄호 하나일 뿐이라고요.

다시 factorial

이전에 만든 factorial을 보겠습니다.

(defn factorial [n]
	(if (zero? n)
		1
		(* n (factorial (- n 1)))))

function factorial(n) {
    return n === 0 ? 1 : factorial(n - 1) * n;
}

'body 안에 factorial이라는 이름을 쓸 수 없다면 어떻게 할 수 있을까'라는 질문을 해야겠습니다.

body 안에 있는 factorial은 free variable입니다.

아래처럼 바꾸면 더 명확해집니다.

(def factorial-Y 
  (fn [f]
    (fn [n]
      (if (zero? n)
        1
        (* n ((f f) (dec n)))))))

function factorial_y(f) {
    return function(n) {
        return n === 0 ? 1 : f(f)(n-1) * n;
    }
}

람다 표현식처럼 보이게 하기 위해 일부러 defn에서 def으로 변경했습니다.

어떻게 사용할까요?

((factorial-Y factorial-Y) 5)
;; 120

factorial_y(factorial_y)(5);
// 120

위의 형태로 실행되도록 하는 함수를 만들어봅시다

그리고 factorial-Y라는 이름은 제거하고 람다만으로 실행이 되는지 확인해봅시다.

(def factorial
  ((fn [f]
     (fn [n]
       (if (zero? n)
         1
         (* n ((f f) (dec n))))))
   (fn [f]
     (fn [n]
       (if (zero? n)
         1
         (* n ((f f) (dec n))))))))
===
(factorial 5)
;; 120

// javascript
let factorial = factorial_y(factorial_y);
factorial(3);

이렇게 람다로 재귀를 도는 함수를 보았습니다.

여기서 잠깐. 두 함수가 중복되어 있습니다. 우리는 함수로 이 형태만을 일반화할 수 있습니다.

(fn [f] (f f))

function (f) {
    return f(f);
}

위 형태에 함수를 적용해봅시다.

(((fn [f]
    (f f))
  (fn [f]
     (fn [n]
       (if (zero? n)
         1
         (* n ((f f) (dec n))))))) 5)
;; 120

(function (f) {
    return f(f);
})(function factorial_y(f) {
    return function(n) {
        return n === 0 ? 1 : f(f)(n-1) * n;
    }
})(5);

자바스크립트 코드를 축약해보면 다음과 같습니다.

((f) => f(f))((f) => (n) => n === 0 ? 1 : f(f)(n-1) * n)(5);

좀 더 표현식이 깔끔해졌습니다.

크롬의 개발자 도구 콘솔에서도 5 팩토리얼을 잘 계산하는군요.

자바스크립트 신택스가 맞지만, 마치 Lisp 코드처럼 보입니다! 재미있지 않습니까?!

그런데 이건 오로지 factorial을 위한 식이어서 아쉽습니다.

Y Combinator

아래의 Clojure 코드는 Y-combinator를 식으로 만든 것입니다. 자세히 보면 위에서 만든 factorial과 아주 유사합니다.

(def Y (fn [f]
         ((fn [x]
            (x x))
          (fn [x]
            (f (fn [y]
                 ((x x) y)))))))

이제 factorial-Y를 다음처럼 자기 자신을 호출하던 부분을 제거합시다. 그 부분은 Y-combinator가 대신해줄 것입니다.

(def factorial-final 
  (fn [f]
    (fn [n]
      (if (zero? n)
        1
        (* n (f (dec n)))))))
===
((Y factorial-final) 5)
;; 120

재귀라는 기능을 언어적으로 지원하지 않더라도 (자기 자신을 참조할 수 없는 경우) 람다 계산식을 통해서 우리는 재귀를 만들어낼 수 있습니다.

폴 그레이엄의 Y Combinator

폴 그레이엄은 자신의 회사를 Y Combinator라고 지었을까요.

기본적으로 Combinator의 의미는 하나의 프로그램이 다른 프로그램을 실행하는 방법을 표현하는 것입니다.

즉, Y-combinator라는 프로그램은 다른 프로그램을 받아서 그것을 재귀로 점점 증폭시키는 방법을 표현하고 있습니다.

스타트업이라는 프로그램을 받아서 그 기업이 재귀적으로 증폭되는 방법을 알려주는 회사가 되려고 이런 이름을 지은 것이 아닐까요!

폴 그레이엄은 아직도 자신의 사업을 프로그래밍을 하고 있는 걸지도 모르겠습니다.

참고문헌

주석

  1. 더글라스 크락포드의 자바스크립트 핵심 가이드 / 더글라스 크락포드 저 / 김명신 역 / 한빛미디어 / 2008년 09월 29일 / 원제 : JavaScript : The Good Parts ↩