fixed point combinator

Jason Kim·2022년 6월 7일

Y Combinator가 인자로 주어진 함수에 대한 fixed point를 만든다는 것의 의미가 잘 이해되지 않아서 정리해보는 중. 헷갈렸던 이유는 재귀를 종료하는 것이 Y의 역할이라고 오해해서였다. 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을 재귀 함수로 작성하면 다음과 같다.

lambda

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

JavaScript

const fact = (n) => {
  if (n === 0) {
    return 1;
  }
  return n * fact(n - 1);
}

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

lambda

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

JavaScript

Y((f) => (n) => {
  if (n === 0) {
    return 1;
  }
  return n * f(n - 1);
});

함수의 이름이 없어지고 맨앞에 f라는 인자가 추가 되었으며, 함수 본문에서는 자기 자신을 반복하는 대신 인자로 전달받은 함수를 호출하도록 변경 되었다.

재귀 함수는 자신의 정의 내부에서 스스로를 호출하는 함수이므로 일반적으로 함수 자신을 참조할 수 있는 이름이 필요하다. 왜냐하면 재귀의 정의 자체가 자기 자신을 호출하는 것이기 때문이다.

한편, Y combinator(fixed point combinator)는 익명 함수만으로도 재귀를 구현할 수 있게 해주는 기법으로, ‘자기 이름 참조’ 없이 재귀 호출을 가능하게 만든다.

익명 함수 형태로 재귀를 구성해야 할 때, 스스로를 참조할 이름이 없으므로 Y combinator는 ‘함수 자체’를 인자로 주고받는 방식을 사용한다. 사실상 f라는 매개변수가 자기 자신을 나타내도록 설계되는 것이다.

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

lambda

(\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)))

JavaScript

((f) => (n) => {
  if (n === 0) {
    return 1;
  }
  return n * f(n - 1);
})(Y((f) => (n) => {
    if (n === 0) {
      return 1;
    }
    return n * f(n - 1);
  }));

익명 함수가 인자로 전달되고 함수 본문이 치환되며 코드가 반복되어 어지러워 보이지만 Y f의 구현은 인자로 전달받은 함수 f에 다시 Y f를 전달하는 것임을 떠올리면 쉽게 이해 할 수 있다.

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

lambda

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

JavaScript

(n) => {
  if (n === 0) {
    return 1;
  }
  return n * Y((f) => (n) => {
    if (n === 0) {
      return 1;
    }
    return n * f(n - 1);
  })(n - 1);
}