4.10 재귀 함수의 람다 대수적 표현과 Y 조합자

1. 재귀 함수의 정의적 순환성

재귀 함수(Recursive Function)는 함수의 정의가 자기 자신을 참조하는 함수이다. 팩토리얼 함수 \text{fact}(n) = \text{if } (n = 0) \; 1 \; (n \times \text{fact}(n-1))에서, \text{fact}의 정의에 \text{fact} 자체가 등장한다.

순수 람다 대수에서는 함수에 이름을 부여하는 메커니즘이 없으므로, 자기 참조가 직접적으로 불가능하다. 이 문제를 해결하는 것이 고정점 조합자(Y Combinator)이며, 이를 통해 임의의 재귀 함수를 순수 람다 대수로 표현할 수 있다.

2. 처치 수(Church Numeral)에서의 산술 연산

재귀 함수를 표현하기 전에, 람다 대수에서 자연수와 기본 연산을 정의한다.

2.1 처치 수의 정의

\overline{n} = \lambda f. \lambda x. \underbrace{f \; (f \; (\cdots (f}_{n} \; x) \cdots))

• \overline{0} = \lambda f. \lambda x. x
• \overline{1} = \lambda f. \lambda x. f \; x
• \overline{2} = \lambda f. \lambda x. f \; (f \; x)

후자 함수(Successor)

\text{SUCC} = \lambda n. \lambda f. \lambda x. f \; (n \; f \; x)

검증: \text{SUCC} \; \overline{2} = \lambda f. \lambda x. f \; (\overline{2} \; f \; x) = \lambda f. \lambda x. f \; (f \; (f \; x)) = \overline{3} ✓

2.2 덧셈(Addition)

\text{ADD} = \lambda m. \lambda n. \lambda f. \lambda x. m \; f \; (n \; f \; x)

곱셈(Multiplication)

\text{MULT} = \lambda m. \lambda n. \lambda f. m \; (n \; f)

2.3 영 판별(IsZero)

\text{ISZERO} = \lambda n. n \; (\lambda x. \text{FALSE}) \; \text{TRUE}

여기서 \text{TRUE} = \lambda x. \lambda y. x, \text{FALSE} = \lambda x. \lambda y. y.

선행자 함수(Predecessor)

\text{PRED} = \lambda n. \lambda f. \lambda x. n \; (\lambda g. \lambda h. h \; (g \; f)) \; (\lambda u. x) \; (\lambda u. u)

\text{PRED} \; \overline{0} = \overline{0}, \text{PRED} \; \overline{n+1} = \overline{n}

3. 팩토리얼 함수의 람다 대수적 구현

3.1 단계 1: 비재귀적 골격 정의

팩토리얼의 재귀적 구조를 비재귀적 고차 함수 G로 추출한다:

G = \lambda f. \lambda n. \text{ISZERO} \; n \; \overline{1} \; (\text{MULT} \; n \; (f \; (\text{PRED} \; n)))

G는 “재귀적 팩토리얼 함수 f가 주어지면, n = 0일 때 \overline{1}을, 아닐 때 n \times f(n-1)을 반환하는 함수“이다. G 자체는 재귀적이지 않다.

단계 2: Y 조합자 적용

\text{FACT} = \mathbf{Y} \; G

고정점 성질에 의해:

\text{FACT} = \mathbf{Y} \; G =_\beta G \; (\mathbf{Y} \; G) = G \; \text{FACT}

따라서:

\text{FACT} \; n =_\beta G \; \text{FACT} \; n = \text{ISZERO} \; n \; \overline{1} \; (\text{MULT} \; n \; (\text{FACT} \; (\text{PRED} \; n)))

이는 팩토리얼의 재귀적 정의와 정확히 일치한다.

3.2 단계 3: 구체적 계산의 추적

\text{FACT} \; \overline{3}의 계산:

\text{FACT} \; \overline{3} =_\beta \text{MULT} \; \overline{3} \; (\text{FACT} \; \overline{2})
=_\beta \text{MULT} \; \overline{3} \; (\text{MULT} \; \overline{2} \; (\text{FACT} \; \overline{1}))
=_\beta \text{MULT} \; \overline{3} \; (\text{MULT} \; \overline{2} \; (\text{MULT} \; \overline{1} \; (\text{FACT} \; \overline{0})))
=_\beta \text{MULT} \; \overline{3} \; (\text{MULT} \; \overline{2} \; (\text{MULT} \; \overline{1} \; \overline{1}))
=_\beta \text{MULT} \; \overline{3} \; (\text{MULT} \; \overline{2} \; \overline{1})
=_\beta \text{MULT} \; \overline{3} \; \overline{2}
=_\beta \overline{6}

3! = 6이므로 올바른 결과이다.

피보나치 수열의 람다 대수적 구현

피보나치 수열 \text{fib}(n) = \text{if } (n \leq 1) \; n \; (\text{fib}(n-1) + \text{fib}(n-2))의 구현:

G_{\text{fib}} = \lambda f. \lambda n. \text{ISZERO} \; n \; \overline{0} \; (\text{ISZERO} \; (\text{PRED} \; n) \; \overline{1} \; (\text{ADD} \; (f \; (\text{PRED} \; n)) \; (f \; (\text{PRED} \; (\text{PRED} \; n)))))

\text{FIB} = \mathbf{Y} \; G_{\text{fib}}

상호 재귀(Mutual Recursion)의 표현

두 함수 f와 g가 서로를 참조하는 상호 재귀도 고정점 조합자로 표현 가능하다. 함수 쌍 (f, g)를 하나의 쌍(Pair)으로 결합하고, 이 쌍에 대한 고정점을 구한다.

쌍의 람다 대수적 표현:

• \text{PAIR} = \lambda a. \lambda b. \lambda s. s \; a \; b
• \text{FST} = \lambda p. p \; \text{TRUE}
• \text{SND} = \lambda p. p \; \text{FALSE}

상호 재귀 함수 쌍의 비재귀적 골격을 정의하고, 쌍에 대한 고정점을 \mathbf{Y}로 구하면 상호 재귀가 실현된다.

Y 조합자에 의한 재귀 표현의 이론적 의의

재귀의 탈신비화(Demystification)

Y 조합자는 재귀가 “마법적” 자기 참조가 아니라, 함수의 고정점이라는 수학적 구조에 기반함을 보여준다. 재귀적 정의 f = G \; f에서 f는 G의 고정점이며, Y 조합자는 이 고정점을 명시적으로 구성한다.

튜링 완전성의 확보

Y 조합자에 의한 재귀의 구현은 람다 대수의 튜링 완전성(Turing Completeness)을 보장하는 핵심 요소이다. 처치 수에 의한 자연수 표현, 조건 분기(\text{ISZERO}), 산술 연산, 그리고 Y 조합자에 의한 재귀의 결합으로 임의의 계산 가능 함수(재귀 함수)가 순수 람다 대수로 표현 가능하다.

함수형 프로그래밍에의 영향

Y 조합자의 원리는 현대 함수형 프로그래밍 언어에서 재귀의 구현 기반이다. Haskell에서의 재귀적 함수 정의, Lisp의 재귀적 S-표현식, ML의 rec 키워드 등은 모두 고정점에 의한 재귀의 기제를 언어 수준에서 지원하는 것이다.