Z 컴비네이터 (Y 컴비네이터)

일급 함수 있는 언어에서 익명 재귀함수 만드는 테크닉. 재귀함수를 인자로 넘기는 상황이나 딱 한 번만 쓸 때 써봄직하다. 재귀 없는 언어에선 재귀 구현이 가능하게 해주나, 그런 언어는 안 쓰이니 실용성은 없다.

Z 컴비네이터에 적당한 규격의 함수, 예를 들어 Z(self => n => (n ? n + self(n - 1) : 0)) 처럼 넣으면 n까지의 합을 구하는 익명 재귀함수를 만들 수 있다. 그래서 이걸 어떻게 만들까?

우선 f에서 자기자신을 호출하기 위해 스스로를 인자로 받아야 하므로, 첫 번째 인자인 self를 f로 채워주는 함수 M = f => f(f)를 선언한다. 그러면 M(f)를 했을 때 self에 f 자신, self => n => ... 부분이 들어갈 것이다. f에선 self(self)를 해서 n => ... 부분을 얻을 수 있으므로, 사실 이걸로 이미 익명 재귀함수가 만들어진다. 당황스러울 만큼 쉽지 않은가?

다만 self(self)를 안 하고 예시처럼 쓸 수 있으면 좋을 것이다. f 대신 M(f)를 주면 어떨까? Z = f => f(Z(f)) 같이 말이다. 다만 이러면 재귀를 무한히 돌기 때문에, Z(f) 호출은 실제로 얘를 써야 할 때까지 지연시켜야 한다. 이는 그냥 함수로 한 번 감싸주면 되며, Z = f => f((...args) => Z(f)(...args))가 된다.

코드가 살짝 길어지니 지연시키는 함수를 따로 빼보자. W = f => (...args) => f(...args)(...args) 정도면 될 것이다. 이 함수는 f가 반환한 함수에 인자를 되먹임하는데, 함수 호출을 지연시키는 것 외로도 여러 함수를 체이닝하는 데 쓸 수 있다. 아무튼 이를 활용하면 Z = f => f(W(_ => Z(f))) 정도가 된다.

기능 자체는 마무리됐지만, 아직 Z가 익명이 아닌 재귀함수이기에 정의에 맞지 않는다. 다행히 우린 M으로 임의의 재귀함수를 익명으로 바꿀 수 있음을 알고 있다 (self(self)처럼 써야 한단 점이 아쉬웠을 뿐). 적당히 바꿔보면 최종적으로 Z = M(z => f => f(W(_ => z(z)(f))))다.

이걸로 완성이다! 꽤 재밌지 않은가? 기회가 된다면 다른 다양한 컴비네이터들도 만들면서 놀아보면 좋을 것 같다.