고정점 조합기

컴퓨터 과학을 위한 조합 논리에서 고정점 조합기(^{[1]: p.26} fix-point combinator)는 인수 함수의 고정점(자체에 매핑된 값)이 존재하는 경우 이를 반환하는 고차 함수(즉, 함수를 인수로 취하는 함수)입니다.

형식적으로 ${\displaystyle \text{수정}}$ ${\$이(가) 고정 소수점 조합자이고 $함수{\displaystyle }$ f ${\displaystyle f}$에 하나 이상의 고정 소수점이 있는$$ 경우 ${\displaystyle 수정}$ ${\displaystyle {\textrm {fix}}\f}$은(는) 이러한 고정 소수점 중 하나입니다.

${\displaystyle f\({\textrm {fix}}\ f)={\textrm {fix}\ f\.}$

고정점 조합기는 람다 미적분학 및 함수 프로그래밍 언어로 정의할 수 있으며 재귀적 정의를 허용하는 수단을 제공합니다.

람다 미적분학에서 Y 조합기

전형적이지 않은 람다 미적분학에서는 모든 함수에 고정점이 있습니다. ${\displaystyle \text{수정}}$ ${\$의 특정 구현은$$ 다음과^{[2]: 131 [note 1]} 같습니다.

${\displaystyle Y=\lambda f.\(\lambda x.f\(x\x))\(\lambda x.f\(x\x))}$

(여기서는 람다 미적분학의 표준 표기법과 규칙을 사용합니다. Y는 하나의 인수 f를 취하고 첫 번째 마침표 이후의 전체 식을 반환하는 함수이며, 식${\displaystyle }$λ ${\displaystyle x}$ .${\displaystyle \text{f}}$ ($x$ ) ${\displaystyle \lambda$x.$f\$ (x\ x )}는 하나의 인수 x를 취하고 함수로 생각하여${\displaystyle \text{식}}$f ($$x ) ${\displaystyle f\$ $($x\ x )}를 반환하는 함수입니다. 여기서${\displaystyle }$( ${\displaystyle \text{x})}$ ${\displaystyle(x\x)}$은(는) 자체에 적용된 x를 나타냅니다$$. 식의 병치는 함수 적용을 나타내며, 왼쪽 연관형이며, 기간보다 높은 우선순위를 갖습니다.)

검증

다음 계산은 ${\displaystyle \mathrm{Yg}}$ ${\displaystyle Yg}$이 실제로 함수 $g{\displaystyle }$ ${\displaystyle g}$의 고정점임을 확인합니다$.$

${\displaystyle Y\g\ }$	${\displaystyle =(\lambda f.(\lambda x.f\(x\x))\(\lambda x.f\(x\x))\ g\ \ }$	$Y{\displaystyle }$ ${\displaystyle$ Y$}$의 정의에 따라
	${\displaystyle =(\lambda x.g\(x\x))\(\lambda x.g\(x\x))\ }$	β-reduction에 의한: Y의 형식적 인수 f를 실제 인수 g로 대체
	${\displaystyle =g\ ((\ lambda x.g\ (x\ x))\ (\ lambda x.g\ (x\ x))\ }$	β-reduction에 의해: 첫 번째 함수의 형식 인수 x를 실제 인수(λ$x$.${\displaystyle \text{g}}$(x$))$ {\$displaystyle$(\lambda$x.$g\(x\x))}
	${\displaystyle =g\ (Y\g)}$	제2의 평등으로, 위에

람다 용어 $g{\displaystyle }$(${\displaystyle \text{Yg})}$ ${\displaystyle$ $g$$\ (Y\g))}$는 일반적으로 ${\displaystyle \text{Yg}}$ ${\displaystyle$ $Y$$\g}$라는 용어로 β-환원되지 않을 수$$ 있습니다$.$ 그러나, 도시된 바와 같이, 두 용어 모두 β-환원되는 동일한 용어입니다.

사용하다

변수가 하나인 함수에 적용하면 일반적으로 Y 조합기가 종료되지 않습니다. 두 개 이상의 변수의 함수에 Y 조합기를 적용하면 더 흥미로운 결과를 얻을 수 있습니다. 추가 변수는 카운터 또는 인덱스로 사용할 수 있습니다. 결과 함수는 명령어에서 잠시 또는 for 루프처럼 동작합니다.

이와 같이 사용되는 Y 콤비네이터는 간단한 재귀를 구현합니다. 람다 미적분학에서는 자신의 몸 안에 있는 함수의 정의를 이름으로 언급할 수 없습니다. 그러나 재귀는 기본적으로 재귀를 지원하는 언어에서 수행되는 것처럼 함수 자체의 이름을 사용하는 대신 인수로 전달된 동일한 함수를 얻은 다음 해당 인수를 사용하여 재귀 호출을 수행함으로써 달성할 수 있습니다.

Y 조합기는 Curry의 역설을 구현하는 데에도 사용될 수 있습니다. Curry의 역설의 핵심은 입력되지 않은 람다 미적분이 연역 체계로서 불건전하다는 것이고, Y 조합기는 익명의 표현을 사용하여 0 또는 심지어 많은 값을 나타낼 수 있다는 것을 보여줍니다. 이것은 수학적 논리에서 일관성이 없습니다.

구현 예

두 언어로 된 Y 조합기의 구현 예는 아래에 제시되어 있습니다.

# 파이썬의 Y Combinator  Y=람다 f: (람다 x: f(x(x)))(람다 x: f(x(x)))  Y(Y) 

// C++ 14 확장을 사용하는 C++의 Y Combinator  인트의 주된() {     오토 Y = [](오토 f) {         오토 f1 = [f](오토 x) -> 활자가 없는(f) {             돌아가다 f(x(x));         };         돌아가다 f1(f1);     };      Y(Y); } 

이 두 프로그램은 형식적으로는 맞지만 실제로는 쓸모가 없습니다. 스택 오버플로를 통해 종료될 때까지 무한 루프를 합니다. 일반적으로 Python과 C++ 둘 다 엄격한 평가를 사용하기 때문에 일반적으로 이러한 언어에서는 Y 컴비네이터가 쓸모가 없습니다. 엄격한 ptograming 언어에서 사용될 수 있는 Z 컴비네이터에 대해서는 아래를 참조하십시오.

고정점 조합기

Y 콤비네이터는 람다 미적분학에서 고정점 콤비네이터를 구현한 것입니다. 고정 소수점 결합기는 다른 기능 언어와 명령어로도 쉽게 정의할 수 있습니다. 람다 미적분학의 한계로 인해 람다 미적분학의 구현이 더 어렵습니다. 고정 소수점 결합기는 다양한 영역에서 사용될 수 있습니다.

• 일반수학
• 유형화되지 않은 람다 미적분
• 유형 람다 미적분
• 함수프로그래밍
• 명령형 프로그래밍

고정 소수점 결합기는 다양한 함수 범위에 적용될 수 있지만, 추가 매개변수가 없는 한 일반적으로 종료되지 않습니다. 수정할 함수가 해당 매개 변수를 참조하면 함수에 대한 다른 호출이 호출되므로 계산이 시작되지 않습니다. 대신 추가 파라미터를 사용하여 계산 시작을 트리거합니다.

고정점의 유형은 고정 중인 함수의 반환 유형입니다. 이것은 실제 또는 함수 또는 다른 유형일 수 있습니다.

입력되지 않은 람다 미적분학에서 고정점 조합기를 적용하는 함수는 Church 인코딩과 같은 인코딩을 사용하여 표현할 수 있습니다. 이 경우 특정 람다 항(함수를 정의함)이 값으로 간주됩니다. "Running"(베타 축소) 인코딩의 고정점 조합기는 결과에 대한 람다 항을 제공하며, 이는 고정점 값으로 해석될 수 있습니다.

또는 함수는 순수하게 람다 미적분학에서 정의된 람다 항으로 간주될 수 있습니다.

이러한 다양한 접근 방식은 수학자와 프로그래머가 고정 소수점 조합자를 어떻게 간주할 수 있는지에 영향을 미칩니다. 수학자는 함수에 적용된 Y 조합자를 고정점 방정식을 만족하는 식으로, 따라서 해로 볼 수 있습니다.

반대로, 일부 일반 프로그래밍 작업에 고정 소수점 조합기를 적용하려는 사람은 재귀를 구현하는 수단으로만 볼 수 있습니다.

값 및 도메인

$많은$ 함수에는 f$n$ = n${\displaystyle }$+ ${\displaystyle f:\$$mathbb${$N}$ $\to \mathbb {N} }$과 같이 고정된 점이 없습니다$.$ Church 인코딩을 사용하여 자연수를 람다 미적분학으로 나타낼 수 있으며, 이 함수 f를 람다 미적분학으로 정의할 수 있습니다. 그러나 이제 도메인에는 자연수를 나타내는 것뿐만 아니라 모든 람다 표현식이 포함됩니다. f에 적용된 Y 조합기는 f에 대한 고정 소수점을 산출하지만, 이 고정 소수점은 자연수를 나타내지 않습니다. 실제 프로그래밍 언어로 Yf를 계산하려고 하면 무한 루프가 발생합니다.

기능 대 구현

고정 소수점 조합기는 수학에서 정의된 다음 다른 언어로 구현될 수 있습니다. 일반 수학은 함수의 확장 속성을 기반으로 함수를 정의합니다.^[3] 즉, 두 기능은 동일한 매핑을 수행하면 동일합니다. 람다 미적분학과 프로그래밍 언어는 함수의 동일성을 집약적 속성으로 간주합니다. 기능의 정체성은 구현을 기반으로 합니다.

람다 미적분 함수(또는 항)는 수학 함수의 구현입니다. 람다 미적분학에는 고정 소수점 결합기의 수학적 정의를 만족하는 여러 결합기(구현)가 있습니다.

"조합자"라는 용어의 정의

조합 논리는 고차 함수 이론입니다. 결합기는 닫힌 람다 식이며, 이는 자유 변수가 없다는 것을 의미합니다. 결합자는 변수로 이름을 지정하지 않고 식에서 올바른 위치로 값을 유도하기 위해 결합될 수 있습니다.

재귀적 정의 및 고정 소수점 조합기

고정 소수점 결합기를 사용하여 함수의 재귀적 정의를 구현할 수 있습니다. 그러나 실제 프로그래밍에서는 거의 사용되지 않습니다.^[4] 단순하게 입력된 람다 미적분학과 같은 강력한 정규화 유형 시스템은 종료할 수 없으므로 고정 소수점 조합기에 유형을 할당할 수 없거나 복잡한 유형의 시스템 기능이 필요한 경우가 많습니다. 또한 고정 소수점 결합기는 상호 재귀적 정의의 각 그룹에 대해 더 많은 기능 감소를 요구하고 튜플을 구성하고 분리하기 때문에 재귀를 구현하기 위한 다른 전략에 비해 종종 비효율적입니다.^{[1]: page 232}

요인 함수

요인 함수는 고정 소수점 결합기를 사용하여 재귀 함수를 정의하는 방법에 대한 좋은 예를 제공합니다. 수학에서 계승 함수의 표준 재귀적 정의는 다음과 같이 쓸 수 있습니다.

${\displaystyle \operatorname {fact} \n={\begin {case}1&{\text{if}}~n=0\n\times \operatorname {fact} (n-1)&{\text{otherwise.}}\end{case}}$

여기서 n은 음이 아닌 정수입니다. 교회 인코딩을 사용하여 정수를 표현하는 람다 미적분학에서 이를 구현하려면 람다 미적분학이 함수의 정의에 함수의 이름('사실')을 사용할 수 없도록 하는 문제에 직면합니다. 이 문제는 다음과$$ 같이 고정 소수점 조합기 ${\displaystyle \mathsf{\text{수정}}}$ ${\textsf {fix}}$을(를) 사용하여 회피할 수 있습니다.

f와 n의 두 인수의 함수 F를 정의합니다.

${\displaystyle F\ f\ n= (\operatorname {IsZero} \n)\ 1\ (\operatorname {multiply} \n)}$

(여기서$$(${\displaystyle \text{IsZero}}$ ⁡ n) ${\displaystyle(\operatorname {IsZero}$ \n)}은(는) 두 개의 인수를 사용하고 n=0인 경우 첫 번째 인수를 반환하는 함수이며$,$ $n$ pred0인 경우 두 번째 인수를 반환하지 않는 경우 이전 ⁡ n${\displaystyle \operatorname$ {pred} \n}은(는) n-1로 평가합니다.)

${\displaystyle \mathrm{이제}}$ fact = ${\displaystyle \mathsf{\text{fix}}}$ ${\displaystyle F}$ ${\displaystyle \operator$ name ${fact}$ = ${\$texts$f${fix$}}\$F}를 정의합니다. ${\displaystyle \mathrm{그러면}}$fact {\$displaystyle \operator name$ {fact$}$은 F의 고정점이며, 다음과 같습니다.

${\displaystyle {begin{aligned}\operatorname{fact} n&=F\ \operatorname{fact} \n\&=(\operatorname{IsZero} \n)\ 1\ (\operatorname{multiply} \n)\ (\operatorname{fact} \(\operatorname{pred} \n))\end{aligned}}}$

요망대로

람다 미적분학의 고정점 조합기

해스켈 B가 발견한 Y 콤비네이터. 카레는 다음과 같이 정의됩니다.

${\displaystyle Y=\lambda f.(\lambda x.f\(x\x))\(\lambda x.f\(x\x))}$

기타 고정점 조합기

유형이 지정되지 않은 람다 미적분 고정 소수점 결합기는 특별히 드물지 않습니다. 사실 그것들은 무한히 많습니다.^[5] 2005년 Mayer Goldberg는 유형이 지정되지 않은 람다 미적분학의 고정점 조합자 집합이 재귀적으로 셀 수 있음을 보여주었습니다.^[6]

Y 콤비네이터는 SKI-calculus에서 다음과 같이 표현할 수 있습니다.

${\displaystyle Y=S(K(SII))(S(S(KS)K)(K(SII)))}$

추가 조합기(B, C, K, W 시스템)를 사용하면 훨씬 짧은 정의가 가능합니다. $S{\displaystyle }$(${\displaystyle K}$ ${\displaystyle x}$) y z = ${\displaystyle x}$(${\displaystyle y}$ z${\displaystyle }$) = ${\displaystyle B}$ ${\displaystyle \mathrm{xy}}$ ${\displaystyle z}$ ${\$$displaystyle$U = $SII}$를 사용하면 S (K x ) ${\displaystyle y}$ ${\displaystyle z}$ = Xy z {\$displaystyle S (Kx) yz$ = $x (yz)$$=Bxyz}$및 $Sx{\displaystyle (\mathrm{Ky}}$) z${\displaystyle }$$=$${\displaystyle \mathrm{xzy}}$ $=$$$ ${\displaystyle Sx(Ky)z$$=$$xzy$$=$$Cxyz},$위는

${\displaystyle Y=S(KU)(SB(KU))=BU(CBU)}$

존 트롬프(John Tromp)가 발견한 SK-계산기에서 가장 단순한 고정점 조합기는

${\displaystyle Y'=SSK(S(K(SS(S(SSK))))K)}$

그러나 정상적인 형태가 아니라는 점에 유의해야 합니다. 이 조합기는 람다 식에 해당합니다.

${\displaystyle Y'=(\lambda xy.xx)(\lambda yx.y(xx))}$

다음의 고정점 결합기는 Y 결합기보다 간단하고 β-는 Y 결합기로 환원되며, 때때로 Y 결합기 자체로 인용됩니다.

${\displaystyle X=\lambda f.(\lambda x.xx)(\lambda x.f(xx))}$

또 다른 일반적인 고정점 조합기는 튜링 고정점 조합기(발견자 앨런 튜링의 이름을 따서 명명됨)입니다.^{[7][2]: 132}

${\displaystyle \Theta = (\ lambda xy.y(xy))\ (\ lambda xy.y(xy))}$

Its advantage over ${\displaystyle Y}$ is that ${\displaystyle \Theta \ f}$ beta-reduces to ${\displaystyle f\ (\Theta f)}$,^{[note 2]} whereas ${\displaystyle Y\ f}$ and ${\displaystyle f\ (Yf)}$ only beta-reduce to a common term.

$θ {\displaystyle$\Theta}에도 간단한 호출 방식이 있습니다.

${\displaystyle \Theta _{v}=(\lambda xy.y(\lambda z.xxyz))\(\lambda xy.y(\lambda z.xxyz))}$

상호 재귀를 위한 아날로그는 Y*로 표시될 수 있는 다변수 고정점 조합기입니다.^[8][9][10]

엄격한 고정점 조합기

엄격한 프로그래밍 언어에서 Y 컴바이네이터는 스택 오버플로가 될 때까지 확장되거나 테일 콜 최적화의 경우 중지되지 않습니다.^[11] Z 콤비네이터는 엄격한 언어(응용 평가 순서가 적용되는 열 언어라고도 함)에서 작동합니다. Z 결합기에는 다음 인수가 명시적으로 정의되어 있어 정의 오른쪽에$$ ${\displaystyle \mathrm{Zg}}$ ${\displaystyle Zg}$이(가) 확장되지 않습니다.^[12]

${\displaystyle Zgv=g(Zg)v\ .}$

람다 미적분학에서는 Y 콤비네이터의 에타 확장입니다.

${\displaystyle Z=\lambda f.(\lambda x.f(\lambda v.xxv))\(\lambda x.f(\lambda v.xxv))\.}$

비표준 고정 소수점 결합기

F가 입력되지 않은 람다 미적분학에서 고정점 조합자라면, 다음과 같습니다.

${\displaystyle F=\lambdax.Fx=\lambda x.x(Fx)=\lambda x.x(x(Fx))=\cdots }$

고정 소수점 결합기와 동일한 Böhm 트리를 갖는 용어, 즉 동일한 무한 확장${\displaystyle }$λ ${\displaystyle x.x(}$x${\displaystyle (}$x$$⋯))${\displaystyle \lambda$x.x$($x(x)cdots))}를 비표준 고정 소수점 결합기라고 합니다. 모든 고정 소수점 결합기도 비표준 결합기이지만 모든 비표준 고정 소수점 결합기가 "표준" 결합기를 정의하는 고정 소수점 방정식을 충족하지 못하기 때문에 고정 소수점 결합기인 것은 아닙니다. 이러한 결합기를 엄격하게 비표준 고정 소수점 결합기라고 하며, 예를 들어 다음과 같은 결합기가 있습니다.

${\displaystyle N=BM(B(BM))}$

어디에

${\displaystyle B=\lambda xyz.x(yz)}$

${\displaystyle M=\lambda x.xx\}$

비표준 고정 소수점 조합자 집합은 재귀적으로 열거할 수 없습니다.^[6]

다른 언어로 구현

Y 콤비네이터는 람다 미적분학에서 고정점 콤비네이터의 특정 구현입니다. 그 구조는 람다 미적분학의 한계에 의해 결정됩니다. 다른 언어로 고정 소수점 조합기를 구현할 때 이 구조를 사용하는 것이 필요하거나 도움이 되지 않습니다.

일부 프로그래밍 패러다임에서 구현된 고정 소수점 조합기의 간단한 예는 다음과 같습니다.

게으른 기능 구현

Haskell과 같이 게으른 평가를 지원하는 언어에서는 기존에 명명된 고정점 조합기의 정의식을 사용하여 고정점 조합기를 정의할 수 있습니다. fix. Haskell은 데이터 유형이 게으르기 때문에 이 결합기를 사용하여 데이터 생성자의 고정 지점을 정의할 수도 있습니다(재귀 함수를 구현하는 데 사용할 수 있을 뿐만 아니라). 여기에 정의가 나와 있으며 몇 가지 사용 예가 있습니다. Hackage에서 원본 샘플은 다음과 같습니다.

고치다, 고치다 :: (a -> a) -> a 고치다 f = 허락하다 x = f x 안에 x         -- 람다가 떨어졌습니다. 공유.                                  -- 데이터의 원래 정의입니다.기능. -- 대안: 고치다 f = f (고치다 f)              -- 람다 들렸습니다. 공유 불가.  고치다 (\x -> 9)                    -- 이것은 9로 평가됩니다.  고치다 (\x -> 3:x)                  -- 게으른 무한 목록에 대한 평가 [3,3,3,3,...]  사실 = 고치다 얼굴의                   -- 요인 함수에 대한 평가   어디에 얼굴의 f 0 = 1         얼굴의 f x = x * f (x-1)  사실 5                           -- 120으로 평가합니다. 

엄격한 기능 구현

엄밀한 함수 언어에서는 OCaml을 사용하여 아래와 같이 f 의 인수가 미리 확장되어 무한 호출 시퀀스가 생성됩니다.

${\displaystyle f}$( ${\displaystyle f}$.${\displaystyle }$.${\displaystyle }$( ${\displaystyle \mathsf{f}x}$ f${\displaystyle }$)${\displaystyle }$.${\displaystyle }$) ${\displaystyle \text{x}}$ ${\displaystyle f\ (f...(f\ ({\mathsf {fix}}\$f ) $.)\ x$

이는 추가 매개변수로 수정을 정의함으로써 해결할 수 있습니다.

허락하다 레크 고치다 f x = f (고치다 f) x (* extra x; 여기 fix f = \x-> f (fix f) x *)  허락하다 팩탭스 사실 = 기능.   (* factabs에는 람다 추상화 수준이 추가됩니다*)    0 -> 1    x -> x * 사실 (x-1)  허락하다 _ = (고치다 팩탭스) 5       (* 평가값은 "120" *) 

Lisp와 같은 다중 패러다임 함수 언어(명령적 기능으로 장식된 언어)에서 Landin(1963)^{[full citation needed]}은 Scheme을 사용하여 아래 예와 같이 고정 소수점 조합기를 만드는 변수 할당의 사용을 제안합니다.

(정의를 내리다 Y!   (람다 (f)     ((람다 (i)                               (세트! i (f (람다 (x) (i x)))) ;; (set! i express) i에 express의 값을 할당합니다.        i)                              ;; 현재 어휘 범위에서 대체      #f))) 

할당문에 대한 공리가 있는 람다 미적분학을 사용하면 다음을 알 수 있습니다. Y! 값별 호출 Y 조합기와 동일한 고정 소수점 법칙을 만족합니다.^[14][15]

${\displaystyle (Y_{!}\ \ lambda x.e)e'=(\ lambda x.e)\ (Y_{!}\ \ lambda x.e)e'}$

더 관용적인 현대 리스프 사용법에서는 일반적으로 어휘 범위 레이블(a)을 통해 처리됩니다. let 표현), 어휘 범위는 1970년대까지 리스프에 도입되지 않았습니다.

(정의를 내리다 Y*   (람다 (f)     ((람다 (i)        (허락하다 ((i (f (람다 (x) (i x))))) ;; (let (i expr) i) local로 i를 expr로 정의합니다.       i))                             ;; recurs이 아닌 경우: 따라서 i in express는 express가 아닙니다.      #f))) 

또는 내부 라벨이 없는 경우:

(정의를 내리다 Y   (람다 (f)     ((람다 (i) (i i))      (람다 (i)        (f (람다 (x)          (적용합니다. (i i) x))))))) 

명령어 구현

이 예제는 고정 소수점 조합기를 약간 해석적으로 구현한 것입니다. 클래스는 fixer라고 하는 fixer 함수를 포함하는 데 사용됩니다. 수정할 함수는 수정자로부터 상속되는 클래스에 포함됩니다. 수정 기능은 수정하고자 하는 기능에 접근하여 가상 기능으로 수정합니다. 엄격한 함수 정의의 경우 수정에는 추가 매개 변수 x가 명시적으로 주어지는데, 이는 게으른 평가가 필요하지 않다는 것을 의미합니다.

템플릿 <활자명 R, 활자명 D> 학급 고친 사람 { 일반의:     R 고치다(D x)     {         돌아가다 f(x);     } 사적인:     가상의 R f(D) = 0; };  학급 사실 : 일반의 고친 사람<긴, 긴> {     가상의 긴 f(긴 x)     {         한다면 (x == 0)         {             돌아가다 1;         }         돌아가다 x * 고치다(x-1);     } };  긴 결과 = 사실().고치다(5); 

타자 치기

시스템 F(다형성 람다 미적분)에서 다형성 고정점 조합기는 유형을^{[citation needed]} 갖습니다.

∀a.(a → a) → a

여기서 a는 유형 변수입니다. 즉, fix는 함수를 취하는데, 함수는 a → a를 매핑하고 이를 사용하여 a 유형의 값을 반환합니다.

재귀적 데이터 유형으로 확장된 단순하게 입력된 람다 미적분학에서는 고정점 연산자를 쓸 수 있지만 "유용한" 고정점 연산자의 유형(응용 프로그램이 항상 반환되는 연산자)은 제한될 수 있습니다.

단순하게 입력된 람다 미적분학에서 고정 소수점 조합기 Y는 어느 시점에서 응용 규칙에 의해$$ 자체 응용 하위 항 x ${\displaystyle x~x}$를 처리하기 때문에 유형을^[16] 할당할 수 없습니다.

${\displaystyle {\Gamma \vdash x\!:\!t_{1}\to t_{2}\quad \Gamma \vdash x\!:\!t_{1}} \over {\Gamma \vdash x~x\!:\!t_{2}}$

여기서 $x$ ${\displaystyle$ x$}$에는 무한 유형 t ${\displaystyle 1_{}}$ = t ${\displaystyle 1_{}}$ → t ${\displaystyle 2_{}}$ ${\displaystyle t_{1}$= $t_{1}\to t_{2}}$가 있습니다$.$ 실제로 고정 소수점 조합자를 입력할 수 없습니다. 이러한 시스템에서는 재귀 지원을 언어에 명시적으로 추가해야 합니다.

Y 조합기에 대한 유형

재귀적 데이터 유형을 지원하는 프로그래밍 언어에서는 유형 수준에서 재귀를 적절하게 고려하여 Y 조합기를 입력할 수 있습니다. 변수 x를 자가 적용해야 하는 필요성은 유형을 사용하여 관리할 수 있습니다.Rec a)와 동형이 되도록 정의됩니다.Rec a -> a).

예를 들어, 다음 해스켈 코드에서, 우리는 In 그리고. out 동형 사상의 두 방향의 이름으로, 유형은 다음과 같습니다.^[17][18]

인 :: (Rec a -> a) -> Rec a 나가. :: Rec a -> (Rec a -> a) 

다음과 같은 글을 쓸 수 있습니다.

신식 Rec a = 인 { 나가. :: Rec a -> a }  y :: (a -> a) -> a y = \f -> (\x -> f (나가. x x)) (인 (\x -> f (나가. x x))) 

또는 OCaml에서 동등하게:

유형 'a 되짚어 보다 = 인 의 ('a 되짚어 보다 -> 'a) 허락하다 나가. (인 x) = x  허락하다 y f = (재밌어요 x a -> f (나가. x x) a) (인 (재밌어요 x a -> f (나가. x x) a)) 

또는:

허락하다 y f = (재밌어요 x -> f (재밌어요 z -> 나가. x x z)) (인 (재밌어요 x -> f (재밌어요 z -> 나가. x x z))) 

일반정보

고정점 조합기를 사용하여 재귀를 구현할 수 있으므로 고정점 반복, 반복 방법, 관계형 데이터베이스의 재귀 조인, 데이터 흐름 분석, 문맥이 없는 문법의 비종단의 FIRST 및 FOLLOW 집합과 같은 특정 유형의 재귀 계산을 설명하는 데 사용할 수 있습니다. 임시 폐쇄 및 기타 유형의 폐쇄 작업.

모든 입력이 고정점인 함수를 항등 함수라고 합니다. 형식:

$모든 x(f\ x=x)}에 대한 {\displaystyle \$

$모든{\displaystyle }$ x ${\displaystyle x}$에 대한 보편적인 정량화와 달리$$고정 소수점 조합기는 $f{\displaystyle }$ ${\displaystyle f}$의 고정 소수점인 하나의 값을 구성합니다$.$ 고정 소수점 결합기의 주목할 만한 특성은 임의의 주어진 $함수{\displaystyle }$ f ${\displaystyle f}$에 대한 고정 소수점을 구성한다는 것입니다$.$

다른 기능들은 한 번 적용된 후에는 더 이상의 응용 프로그램이 아무런 효과가 없다는 특별한 특성을 가지고 있습니다. 보다 형식적으로:

${\displaystyle \ for all x(f\ (f\ x))= f\ x)}$

이러한 함수를 idempotent라고 합니다(투영(수학) 참조). 이러한 함수의 예로는 모든 짝수 정수에 대해 0을 반환하고 모든 홀수 정수에 대해 1을 반환하는 함수가 있습니다.

람다 미적분학에서는 계산 관점에서 항등식 함수 또는 멱함수에 고정점 조합기를 적용하면 일반적으로 비종료 계산이 발생합니다. 예를 들어, 우리는

${\displaystyle (Y\ \ lambda x.x)=(\ lambda x.(xx))\ \ lambda x.(xx))}$

여기서 결과적인 항은 그 자체로만 축소될 수 있고 무한 루프를 나타냅니다.

고정 소수점 결합기가 더 제한적인 계산 모델에 반드시 존재하는 것은 아닙니다. 예를 들어, 그것들은 단순하게 입력된 람다 미적분학에 존재하지 않습니다.

Y 콤비네이터를 사용하면 언어의 기본 재귀 지원 없이 ^[19]재귀를 재귀 규칙 집합으로 정의할 수 있습니다.^[20]

익명 함수를 지원하는 프로그래밍 언어에서 고정 소수점 조합기를 사용하면 익명 재귀 함수를 정의하고 사용할 수 있습니다. 즉, 이러한 함수를 식별자에 바인딩할 필요가 없습니다. 이 설정에서는 고정 소수점 조합기를 사용하는 것을 익명 재귀라고 부르기도 합니다.^{[note 3][21]}

참고 항목

• 익명함수
• 고정점 반복
• Lambda 미적분 #재귀 및 고정점
• 람다 리프팅
• 표현하자.

메모들

참고문헌

• Werner Kluge, 추상 컴퓨팅 머신: 람다 미적분학 관점, Springer, 2005, ISBN 3-540-21146-2, 페이지 73-77
• Mayer Goldberg, (2005) 고정 소수점 조합자의 재귀적 계수 가능성에 관한 연구, Arhus 대학, BRICS Report RS-05-1
• 마티아스 펠라이센, Y의 이유에 관한 강의

외부 링크

위키북스에는 다음과 같은 주제의 책이 있습니다. 해스켈/고침 및 재귀

• 재귀 이론과 기쁨, 만프레드 폰 툰(Manfred von Thun, 2002 또는 그 이전)
• 람다 미적분학 - 돈 블라헤타 주석, 2000년 10월 12일
• Y 콤비네이터
• "루비에서 Y 콤비네이터의 사용"
• "아다의 기능 프로그래밍"
• 로제타 코드 - Y 조합기