와이 콤비네이터

와이 콤비네이터(Y-combinator)는 람다 대수 및 함수형 프로그래밍에서 사용되는 고정점 콤비네이터(fixed-point combinator) 중 하나이다. 이는 함수에 이름을 붙이거나 직접적인 재귀(recursion) 메커니즘이 없는 환경(특히 순수 람다 대수)에서 재귀 함수를 정의하고 구현하는 데 사용되는 고계 함수(higher-order function)이다.

개요 고정점 콤비네이터는 어떤 함수 f가 주어졌을 때, f(x) = x를 만족하는 f의 고정점(fixed point) 중 하나인 x를 찾는 함수이다. 와이 콤비네이터 Y는 순수 람다 대수 표현식으로 이러한 고정점을 계산한다. 즉, Y는 함수 f를 인자로 받아 Y f를 계산하며, 이 Y f는 f (Y f)와 동일한 속성을 가진다.

작동 방식 및 필요성 많은 프로그래밍 언어는 함수 내에서 자신의 이름을 직접 호출함으로써 재귀를 지원한다. 그러나 순수한 형태의 람다 대수에서는 모든 것이 익명 함수(anonymous function)이며, 함수 정의 시 자기 자신을 참조할 수 있는 메커니즘이 기본적으로 없다. 이러한 제약 하에서, 와이 콤비네이터는 함수 G가 주어졌을 때 Y G가 G와 자기 자신(Y G)을 인자로 받아 호출되는 것처럼 작동하게 하여 재귀를 시뮬레이션한다.

예를 들어, 어떤 함수 F가 재귀적으로 정의될 때 F = G F와 같은 형태로 표현될 수 있다면 (여기서 G는 재귀 호출을 포함하는 함수의 '몸체' 역할을 한다), 와이 콤비네이터는 이 F 역할을 하는 고정점 Y G를 제공한다.

종류 표준적인 와이 콤비네이터 정의(Y = λf.(λx.f (x x)) (λx.f (x x)))는 지연 평가(lazy evaluation) 방식을 사용하는 언어에서 잘 작동한다. 엄격한 평가(strict evaluation, call-by-value) 방식을 사용하는 언어에서는 표준 와이 콤비네이터가 무한 루프에 빠질 수 있으므로, 엄격한 평가를 위한 변형된 고정점 콤비네이터(예: Z 콤비네이터)가 사용되기도 한다.

역사 와이 콤비네이터는 미국의 수학자 해스켈 커리(Haskell Curry)에 의해 발견되었다. 이는 람다 대수의 이론적 연구와 함수형 프로그래밍의 기초에 중요한 역할을 한다.