Python으로 구현하는 Y 컴비네이터
람다 대수는 계산 이론의 기초 체계로서 존중받는 위치를 차지하고 있으며, 프로그래밍 언어와 패러다임에 영향을 미쳐 왔습니다. 람다 대수의 흥미로운 응용 중 하나는 처치 인코딩으로, 이를 이용하면 함수만으로 데이터와 연산자를 표현할 수 있습니다. 이 블로그 글에서는 Python에서 처치 인코딩을 구현하여 불리언 값, 기본 산술 연산, 나아가 피보나치 수열과 같은 복잡한 함수까지 표현하는 방법을 자세히 살펴봅니다.
처치 인코딩은 람다 대수에서 데이터와 연산자를 표현하는 수단으로, 데이터 타입 대신 함수를 사용합니다. 수, 불리언 값, 기본 산술 연산과 같은 전형적인 구성 요소는 순전히 함수 추상화와 적용만으로 표현할 수 있습니다.
먼저 Python의 람다 함수를 사용하여 불리언 값과 필수적인 논리 연산을 인코딩해 봅시다.
처치 인코딩에서 TRUE와 FALSE는 두 개의 매개변수를 받아 각각 첫 번째 매개변수와 두 번째 매개변수를 반환하는 함수로 정의할 수 있습니다.
TRUE = lambda x: lambda y: x
FALSE = lambda x: lambda y: y
이 정의를 사용하면 논리 연산을 정의할 수 있습니다. 예를 들어 AND 연산은 다음과 같이 표현할 수 있습니다.
And = lambda x: lambda y: x(y)(x)
산술 연산 역시 이 체계에서 표현할 수 있습니다. 예를 들어 수의 후속자, 덧셈, 곱셈은 다음과 같이 정의됩니다.
Succ = lambda n: lambda f: lambda x: f(n(f)(x))
Add = lambda m: lambda n: lambda f: lambda x: m(f)(n(f)(x))
Mul = lambda m: lambda n: lambda f: m(n(f))
이제 더 복잡한 예로 피보나치 수열을 다루며, 이를 Python에서 람다 대수의 구성 요소로 구현합니다. 람다 대수는 본래 재귀를 지원하지 않으므로, 재귀를 처리하기 위해 Y 컴비네이터를 사용합니다.
Y = lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v)))
Fib = Y(lambda f: lambda n: Add(f(Pred(n)))(f(Sub(n)(TWO))) if Gt(n)(ONE) else n)
이렇게 인코딩된 논리를 Python으로 구현하고 실행해 보는 것은 계산의 더 깊은 기초를 이해하는 데 훌륭한 도구가 됩니다. 몇 가지 피보나치 위치를 어떻게 계산하는지 살펴봅시다.
print(Fib(1)) # Output: 1
print(Fib(2)) # Output: 1
print(Fib(8)) # Output: 21
여러분의 비틀린 즐거움을 위해 준비한 전체 코드는 아래와 같습니다.
TRUE = lambda x: lambda y: x
FALSE = lambda x: lambda y: y
Product = lambda x: lambda y: lambda z: (z)(x)(y)
And = lambda x: lambda y: (x)(y)(x)
Not = lambda x: lambda y: lambda z: (x)(z)(y)
Boolean = (Product)(True)(False)
Succ = lambda x: lambda y: lambda z: (y)((x)(y)(z))
Pred = lambda x: lambda y: lambda z: x(lambda i: lambda j: j(i(y))) (lambda k: z) (lambda k: k)
Y = lambda g: (lambda z:z(z)) (lambda f: g(lambda arg: f(f)(arg)))
Nth = Y(lambda f: lambda n: Succ(f(n-1)) if n else Zero)
Dec = lambda a: (a)(lambda b: b + 1)(0)
Add = lambda x: lambda y: lambda z: lambda w: (x)(z)((y)(z)(w))
Sub = lambda x: lambda y: (y)(Pred)(x)
Mul = lambda x: lambda y: lambda z: (y)((x)(z))
Null = lambda x: x(lambda y: Zero)(TRUE)
Eq = lambda x: lambda y: (And)((Null)((Sub)(y)(x)))((Null)((Sub)(x)(y)))
Gt = lambda x: lambda y: (And)((Null)((Sub)(y)(x)))((Not)((Eq)(y)(x)))
Lt = lambda x: lambda y: (And)((Not)((Gt)(x)(y)))((Not)((Eq)(x)(y)))
IfThenElse = lambda a: lambda b: lambda c: ((a)(b))(c)
Range = lambda a,b: map(Nth,range(a,b))
# Minimal
Fib = Y(lambda f: lambda n: Add(f(Pred(n)))(f((Sub)(n)(Two))) if (Boolean)((Gt)(n)(One)) else n)
# Exapnded
Fib = lambda x: (lambda a: (a)(lambda b: b + 1)(0))(
(
(
lambda g: (lambda f: g(lambda arg: f(f)(arg)))(
lambda f: g(lambda arg: f(f)(arg))
)
)(
lambda f: lambda n: (
(lambda x: lambda y: lambda z: lambda w: (x)(z)((y)(z)(w)))(
f(
(
lambda x: lambda y: lambda z: x(
lambda i: lambda j: j(i(y))
)(lambda k: z)(lambda k: k)
)(n)
)
)(
f(
(
(
lambda x: lambda y: (y)(
(
lambda x: lambda y: lambda z: x(
lambda i: lambda j: j(i(y))
)(lambda k: z)(lambda k: k)
)
)(x)
)
)(n)(
(
(lambda x: lambda y: lambda z: (y)((x)(y)(z)))(
(
(lambda x: lambda y: lambda z: (y)((x)(y)(z)))(
(lambda x: lambda y: y)
)
)
)
)
)
)
)
if (
(
((lambda x: lambda y: lambda z: (z)(x)(y)))(
lambda x: lambda y: x
)(False)
)
)(
(
(
lambda x: lambda y: (lambda x: lambda y: (x)(y)(x))(
(
(
lambda x: x(lambda y: (lambda x: lambda y: y))(
lambda x: lambda y: x
)
)
)(
(
(
lambda x: lambda y: (y)(
(
lambda x: lambda y: lambda z: x(
lambda i: lambda j: j(i(y))
)(lambda k: z)(lambda k: k)
)
)(x)
)
)(y)(x)
)
)(
((lambda x: lambda y: lambda z: (x)(z)(y)))(
(
(
lambda x: lambda y: (
lambda x: lambda y: (x)(y)(x)
)(
(
(
lambda x: x(
lambda y: (
lambda x: lambda y: y
)
)(lambda x: lambda y: x)
)
)(
(
(
lambda x: lambda y: (y)(
(
lambda x: lambda y: lambda z: x(
lambda i: lambda j: j(
i(y)
)
)(
lambda k: z
)(
lambda k: k
)
)
)(x)
)
)(y)(x)
)
)(
(
(
lambda x: x(
lambda y: (
lambda x: lambda y: y
)
)(lambda x: lambda y: x)
)
)(
(
(
lambda x: lambda y: (y)(
(
lambda x: lambda y: lambda z: x(
lambda i: lambda j: j(
i(y)
)
)(
lambda k: z
)(
lambda k: k
)
)
)(x)
)
)(x)(y)
)
)
)
)(y)(x)
)
)
)
)(n)(
(
(lambda x: lambda y: lambda z: (y)((x)(y)(z)))(
(lambda x: lambda y: y)
)
)
)
)
else n
)
)
)(
(
(
lambda g: (lambda f: g(lambda arg: f(f)(arg)))(
lambda f: g(lambda arg: f(f)(arg))
)
)(
lambda f: lambda n: (
(lambda x: lambda y: lambda z: (y)((x)(y)(z)))(f(n - 1))
if n
else (lambda x: lambda y: y)
)
)
)(x)
)
)