fixed point combinator

Y Combinator가 인자로 주어진 함수에 대한 fixed point를 만든다는 것의 의미가 잘 이해되지 않아서 정리해보는 중. 헷갈렸던 이유는 재귀를 종료하는 것이 Y의 역할이라고 오해해서였다. Y는 단지 함수를 무한하게 반복시킬 뿐이다.

fixed point의 정의

x = f(x) 일 때, 즉 함수에 입력되는 값과 함수가 출력하는 값이 같을때, x를 f의 fixed point 라고 부른다.

fixed point combinator

재귀가 허용되지 않는 프로그래밍 언어에서 함수를 재귀적으로 반복시키는 방법이다. Y Combinator라고도 불린다.
함수 Y는 입력으로 임의의 함수를 입력 받는다.

Y를 재귀적으로 정의하면 다음과 같다. Y를 비 재귀적으로 정의 할 수도 있는데, 그건 더 읽어보기를 참고하자.

Y f = f (Y f)

Y f를 x로 치환해본다면 x = f(x)와 같은 꼴이다. Y f는 f에 대한 fixed point이다.
정리하면, Y는 임의의 함수 f를 그 자신(f)에 대한 fixed point로 만들어주는 역할을 한다.

Y는 어떻게 재귀 함수를 생성하는가?

Y의 정의는 Y f = f (Y f) 이기 때문에, 우변의 Y f를 f (Y f)로 치환하면

f (f (Y f))

를 얻고, 이 과정이 계속 반복 되기 때문에

f (f (... f (Y f)))

와 같이, f가 무한하게 적용된다.

예시

factorial을 재귀 함수로 작성하면 다음과 같다.

fact = \n = if n == 0 then 1 else n * fact (n - 1)

재귀가 허용되지 않는다면 다음과 같은 익명 함수를 Y에 적용해서 다음과 같이 작성 할 수 있다.

Y (\f n = if n == 0 then 1 else n * f (n - 1))

Y f = f (Y f)에 적용해보면 이렇게 된다. (익명함수에 Y f를 적용한 결과이다.)

(\f n = if n == 0 then 1 else n * f (n - 1)) (Y (\f n = if n == 0 then 1 else n * f (n - 1)))

앞에 있는 익명함수의 인자 f를 Y f로 치환하면

(\n = if n == 0 then 1 else n * (Y (\f n = if n == 0 then 1 else n * f (n - 1))) (n - 1))

이 과정이 계속해서 반복되며, f를 사용하지 않는 코드 (여기서는 n이 0일 때)가 사용되면 적용이 멈추고 계산이 완료된다.

더 읽어보기

더 자세한 설명과 예시는 https://mvanier.livejournal.com/2897.html 여기를 참고.