요즘은 전산 전공자조차도 와이 컴비네이터(Y Combinator)가 Paul Graham이 설립한 실리콘밸리 스타트업 인큐베이터라고만 아는 경우가 많은 것 같습니다. 하지만 Y Combinator는 전산학에서 아주 중요한 개념입니다. 함수 언어, 특히 Lisp의 예찬론자인 Paul Graham도 여기서 회사 이름을 따왔습니다.

일단 combinator란 말은 Moses Schönfinkel와 Haskell Curry가 만든 Combinatory logic에서 왔습니다. Combinatory logic은 lambda calculus와 마찬가지로 전산학에서는 계산을 모델링하는 방법으로 사용되는데, 몇 가지 함수의 조합만으로 새로운 함수를 만들어내는 방법을 뜻합니다. 여기서 combinator는 free variable이 없는 함수라고 생각하면 됩니다. Combinatory logic에서는 다음과 같이 3개의 가장 기본적인 combinator를 정의합니다.

• I combinator

var I = function (x) {
            return x;
        };

• K combinator

var K = function (x) {
        return function(){
            return x;}
        };

• S combinator

var S = function (x) {
           return function (y) {
               return function (z) {
                   return x(z)(y(z));
               }
           }
       };

(모든 combinator는 curried function으로 표현하였습니다.)

여기서 I combinator는 인자 그대로 리턴하는 identity 함수이고, K combinator는 항상 첫 번째 인자를 리턴하는 const 함수입니다. S combinator만 조금 복잡한 계산을 수행하는 것처럼 보입니다. Combinatory logic의 놀라운 점은 S와 K 단 2개의 combinator의 조합만으로 Turing machine이 계산 가능한 모든 계산을 할 수 있다는 점입니다. (I combinator는 S, K로 만들어 낼 수 있습니다.)

Y combinator는 fixed point combinator라고 불리는데, 재귀 함수를 만들어주는 combinator입니다. JavaScript 같이 재귀 함수를 직접 지원하는 언어만 사용하신 분은 이 개념이 다소 생소할 수 있습니다. 예를 들어, JavaScript로 팩토리얼을 구하는 함수 fac을 작성하면 다음과 같습니다. fac 함수 내에서 fac(n-1)을 호출하는 것을 확인할 수 있습니다.

function fac(n) {
    if (n === 1)
        return 1;
    else
        return n * fac(n - 1);
}

console.log(fac(5));
// 120

하지만 익명 함수(anonymous function)으로만 이 함수를 작성해야 한다면 어떨까요? 함수 내에서 자기 자신을 부를 수 있는 방법이 없기 때문에 더 이상 재귀 함수를 만들 수가 없게 됩니다.

var fac = function (n) {
    if (n === 1)
        return 1;
    else
        return n * ??(n - 1);
}

여기서 등장하는 함수가 Y combinator입니다. Y combinator를 이용하면 다음과 같이 fac 함수를 정의할 수 있습니다.

var fac = Y(function (fac) {
    return function (n) {
        return n === 1 ? n : n * fac(n - 1);
    };
});

JavaScript로 Y combinator를 다음과 같이 정의할 수 있습니다.

function Y(le) {
    return (function (f) {
        return f(f);
    }(function (f) {
        return le(function (x) {
            return f(f)(x);
        });
    }));
}

물론 S, K combinator만으로 모든 계산 가능한 함수를 만들어낼 수 있기 때문에 Y combinator를 S, K로 표현할 수도 있습니다.

Y = S S K (S (K (S S (S (S S K)))) K)

이 글은 Y combinator의 개념만 간단히 소개하는 것으로 마치고, 다음 글에서 fixed point의 개념 및 Y combinator 유도 과정에 대해 살펴보겠습니다.