교회 부호화

수학에서 처치 인코딩은 람다 미적분학에서 데이터와 연산자를 나타내는 수단입니다.교회 숫자는 람다 표기법을 사용한 자연수의 표현이다.이 방법은 람다 미적분의 데이터를 처음으로 이런 방식으로 인코딩한 Alonzo Church의 이름을 따서 명명되었습니다.

일반적으로 다른 표기법(정수, 부울란, 쌍, 목록 및 태그 부착 결합 등)에서 원시적인 것으로 간주되는 용어는 교회 인코딩에서 상위 함수에 매핑됩니다.Church-Turing 논문은 계산 가능한 연산자(및 그 피연산자)는 Church 인코딩으로 ^{[dubious – discuss]}표현될 수 있다고 주장한다.비정형 람다 미적분학에서 유일한 원시 데이터 유형은 함수입니다.

사용하다

Church 인코딩을 직접 구현하면 O${\displaystyle }$( $1$)에서${\displaystyle O}$( n $)$ ( n ) ( n \ $displaystyle$O ($n$ $)$로의 액세스 조작이 느려지고, 여기서$n{\displaystyle }$ \ $displaystyle$n은$$ 데이터 구조의 크기이므로 Church 인코딩이 ^[1]실용적이지 않습니다.연구에 따르면 이는 표적 최적화를 통해 해결할 수 있지만, 대부분의 기능적 프로그래밍 언어는 대신 중간 표현을 확장하여 대수적 데이터 유형을 ^[2]포함합니다.그럼에도 불구하고 Church 인코딩은 부분 평가와 정리 ^[1]증명에 대한 자연스러운 표현이기 때문에 이론적인 논쟁에서 종종 사용된다.상위 ^[3]유형을 사용하여 작업을 입력할 수 있으며 원시 재귀에 쉽게 액세스할 ^[1]수 있습니다.함수가 유일한 원시 데이터 유형이라는 가정은 많은 증거를 합리화합니다.

교회 인코딩은 완전하지만 대표적으로만 가능합니다.표현을 일반 데이터 유형으로 변환하여 사람들에게 표시하기 위해서는 추가 기능이 필요합니다.처치의 정리에서 등가의 결정 불가능으로 인해 두 함수가 확장적으로 동일한지 결정하는 것은 일반적으로 가능하지 않다.변환은 함수를 적용하여 함수가 나타내는 값을 가져오거나 해당 값을 리터럴 람다 용어로 검색할 수 있습니다.람다 미적분은 보통 강약적 등식을 사용하는 것으로 해석됩니다.평등에 대한 집중적 정의와 확장적 정의 간의 차이 때문에 결과의 해석에 잠재적인 문제가 있다.

교회 숫자

교회 숫자는 교회 부호화에서 자연수를 표현한 것입니다.자연수 n을 나타내는 고차 함수는 임의의 $함수{\displaystyle }$ f${displaystyle$ f$}$를 n배 구성에 매핑하는 함수입니다.간단히 말하면, 숫자의 "값"은 함수가 인수를 캡슐화한 횟수와 동일합니다.

${\displaystyle f^{\display n}=\underbrace {f\display f\cdots\cdots\cdots f}_{ndisplaytext{times}}},$

모든 교회 숫자는 두 가지 매개변수를 사용하는 함수입니다.교회 숫자 0, 1, 2, ...는 람다 미적분학에서 다음과 같이 정의된다.

함수를 전혀 적용하지 않는 0부터 시작하여 1회 적용, 2회 적용, 3회 적용 등으로 진행합니다.

${\displaystyle {begin {array} {r l} {\text {Number}} & {\text{함수 정의}}&{\text {Lambda expression}}\hline 0&0\f\x=0=\lambda f.\sysda x.x\1&1\f\x=f\x&1=\sysda f.\seconda x.f\x\2&2\f\x=f\(f\x)&2=\seconda f.\seconda x.f\(f\x)\3\f\x=f\(f\x)&3=\seconda f.\sqda x.f\(f\(f\x)\\\vdots &\vdots &\vdots \\n&n\f\x=f^{n}\x&n=\contextda f.\sysda x.f^{\sysn}\x\end{array}}$

교회 숫자 3은 주어진 함수를 한 값에 세 번 적용하는 동작을 나타냅니다.제공된 함수는 먼저 제공된 파라미터에 적용된 후 자체 결과에 순차적으로 적용됩니다.최종 결과는 숫자 3이 아닙니다(지정된 파라미터가 0이고 함수가 후계 함수인 경우를 제외).최종 결과가 아니라 함수 자체가 교회 숫자 3이다.Church number 3은 단순히 어떤 것이든 세 번 한다는 것을 의미한다.그것은 "세 번"이 의미하는 바를 과시하는 것이다.

교회 숫자를 사용한 계산

숫자에 대한 산술 연산은 교회 숫자에 대한 함수로 나타낼 수 있다.이러한 함수는 람다 미적분으로 정의하거나 대부분의 함수 프로그래밍 언어로 구현할 수 있습니다(람다 식을 함수로 변환 참조).

$더하기{\displaystyle {}^{}}$ ${\displaystyle \mathrm{함수}}$ ${\displaystyle (}$ (${\displaystyle m}$ ,${\displaystyle n}$ ) ${\displaystyle =m}$ +$$ ( \ $displaystyle \operatorname { plus }$ (${\displaystyle {}^{}}$$m$ , n )${\displaystyle {}^{}=}$ m + ${\displaystyle n{}^{}\}}$ ($$x ) ${\displaystyle {=}^{}}$ ${\displaystyle f^{}}$ ${\displaystyle {}^{}}$ $m$ ( ${\displaystyle f^{}}$ ${\displaystyle n}$ ){ $display$ f^ { \ display $style$f + n$$} ( x ) =$f ^$ { f } { f + n } { f + $n }$ { f } { f } { f } { f } { f } { f } n$$ }

$\displaystyle \operatorname {plus} \equiv \displayda m.\420da n\contextda f.\sqda x.m\f\(n\f\x)}$

${\displaystyle \mathrm{후속}}$ ${\displaystyle \mathrm{함수}}$ succ ${\displaystyle (}$ (${\displaystyle n}$ ) ${\displaystyle =n}$ +$$ { $displaystyle \operatorname$ {$}$( n ) =$n+1$$}$ 은 ( +${\displaystyle \text{1}\mathrm{}}$1$$){$displaystyle$ ( \$operatorname$ {$plus}$ \ 1$)}$와${\displaystyle }$β등가 됩니다.

$\displaystyle \operatorname {display} \equiv \displayda n.\contextda f.\sqda x.f\(n\f\x)}$

곱셈 ${\displaystyle \mathrm{함수}}$ mult ${\displaystyle (}$ (${\displaystyle m}$ ,${\displaystyle n}$ ) ${\displaystyle =}$ ${\displaystyle mn}$ n$${ $displaystyle \operatorname${$mult$} ($$${\displaystyle m}$ , n )${\displaystyle {}^{}=}$$$${\displaystyle m^{}}$ * $n$${\displaystyle {}^{}}$（ x${\displaystyle n^{}}$n${\displaystyle {}^{}{}^{}{）}^{}{}^{})}$ m${\displaystyle {}^{}}$( $x$) { $displaystyle f^{$ \ $displaystyle$ f^{ n } ($m*n)$=$$f * n } $）$ \ n \ \ \ n ∘ ${\displaystyle {\circ }^{}}$ \ \ \ ${\displaystyle {\backslash }^{}}$ $n{\displaystyle {}^{}}$ \ \ \ \ \ \ ∘ ∘ ∘ ∘ \ \ \ \

$\displaystyle \operatorname {mult} \equiv \displayda m.\420da n\contextda f.\sqda x.m\(n\f)\x}$

${\displaystyle \mathrm{지수함수}}$ exp${\displaystyle {}^{}}$( m${\displaystyle }$, n ) ${\displaystyle =}$ n \$$$displaystyle$$\operatorname${$exp }$ ( m , n ) ${\displaystyle \to }$ m$^${ n$$ $}$ 은 교회 숫자의 $정의$에 의해 ${\displaystyle \text{지정}}$됩니다.$정의{\displaystyle }$ 대체 m$→$ ${\displaystyle m}$ ${\displaystyle \to }$$$$h$$^{n$} \$$$x$} . ,$ystyle$ n$\m\f=m^{n}\f}$ 및$$,

$\displaystyle \operatorname {exp} \m\n=m^{n}=n\m}$

람다 표정을 짓는데

$\displaystyle \operatorname {exp} \equiv \displayda m.\sysda n.n\m}$

pred ${\displaystyle (}$ (${\displaystyle n}$ )$${ $displaystyle \operatorname${$pred$} ($n$ ) 함수는$$ ${\displaystyle \mathrm{이해}}$하기 어렵습니다.

$\displaystyle \operatorname {display} \equiv \displayda n.\contextda f.\contextda x.n\ (\contextda g).\subda h.h\(g\f)\(\subda u.x)\(\subda u.u)}$

교회 숫자는 함수를 n회 적용합니다.이전 함수는 매개 변수를 n - 1회 적용하는 함수를 반환해야 합니다.이것은 f와 x 주위에 컨테이너를 구축함으로써 달성되며, f와 x는 함수의 적용을 최초로 생략하는 방식으로 초기화됩니다.자세한 설명은 이전 문서를 참조하십시오.

감산 함수는 이전 함수를 기반으로 작성할 수 있습니다.

$\displaystyle \operatorname {display} \equiv \displayda m.\sysda n. (n\operatorname {syslog})\m}$

교회 숫자 함수표

기능.	대수학	신원	함수 정의	람다 식
후계자	${\displaystyle n+1}$	${\displaystyle f^{n+1}\x=f(f^{n}x)}$	${\displaystyle \operatorname {display}\n\f=f\(n\f\x)}$	$(\ displaystyle \ displayda n )\contextda f.\sqda x.f\(n\f\x)}$	...
추가	${\displaystyle m+n}$	${\displaystyle f^{m+n}\x=f^{m}(f^{n}x)}$	$\displaystyle \operatorname {plus} \ m \ n \ f \ x = m \ f \ ( n \ f \ x )$	$(\displaystyle\displayda m).\420da n\contextda f.\sqda x.m\f\(n\f\x)}$	$(\displaystyle\displayda m).\sysda n.n\operatorname {sys}m}$
곱셈	${\displaystyle m*n}$	${\displaystyle f^{m*n}\x=(f^{m})^{n}\x}$	$\displaystyle \operatorname {display} \m\n\f\x=m\(n\f)\x}$	$(\displaystyle\displayda m).\420da n\contextda f.\sqda x.m\(n\f)\x}$	$(\displaystyle\displayda m).\420da n\sqda f.m\(n\f)}$
지수화	${\displaystyle m^{n}}$	${\displaystyle n\m\f=m^{n}\f}$[4]	$\displaystyle \operatorname {exp} \m\n\f=(n\m)\f\x}$	$(\displaystyle\displayda m).\420da n\contextda f.\sqda x. (n\m)\f\x}$	$(\displaystyle\displayda m).\sysda n.n\m}$
이전 버전*	${\displaystyle n-1}$	${\displaystyle \operatorname {inc} ^{n}\operatorname {con} =\operatorname {val}(f^{n-1}x)}$	${{displaystyle if(n==0)\ 0\ other\ (n-1)}$	$(\ displaystyle \ displayda n )\contextda f.\contextda x.n\ (\contextda g).\subda h.h\(g\f)\(\subda u.x)\(\subda u.u)}$
감산*	${\displaystyle m-n}$	${\displaystyle f^{m-n}\x=(f^{-1})^{n}(f^{m}x)}$	$\displaystyle \operatorname {display}\m\n=(n\operatorname {display})\m}$	...	$(\displaystyle\displayda m).\sysda n.n\operatorname {sys}m}$

* Church 인코딩에서는

• ${\displaystyle\operatorname{display}(0)=0}$
• ${\displaystyle m<=n\to m-n=0}$

이전 함수의 도출

Church 인코딩에 사용된 이전 함수는 다음과 같습니다.

） { - 、 { $displaystyle \operatorname { parames$} ( n ) $= cases$} 0 & { \ $mbox$ { $cases }$n=0 , \ n - 1 & { $\ mbox$ { cases } }}

이전 버전을 구축하려면 기능을 1시간 단축하는 방법이 필요합니다.숫자 n은 함수를 x에 fn회 적용한다.이전 함수는 숫자 n을 사용하여 함수를 n-1번 적용해야 합니다.

이전 함수를 구현하기 전에 컨테이너 함수로 값을 정리하는 스킴을 다음에 나타냅니다.f와 x 대신 inc와 init이라고 하는 새로운 함수를 정의합니다.컨테이너 함수를 값이라고 합니다.표의 왼쪽에는 inc와 init에 적용되는 숫자n이 표시되어 있습니다.

${\displaystyle{\begin{배열}{rrr}{\text{번호}}&{\text{init를 사용하여}}&{\text{const를 사용하여}}\\\hline 0&,\operatorname{init}=\operatorname{값})x&, \\1&,\operatorname{inc})\operatorname{init}=\operatorname{값})(f\))&,\operatorname{inc})\operatorname{const}=\operatorname{값})x\\2&, \operatorname{inc.}년(\operatorname{inc}))operatorname {init} =\operatorname {value} \(f\(f\x))&\operatorname {inc} \ (\operatorname {inc} \ operatorname {const} )=\operatorname {value} \ (f\x)\3&\operatorname {inc} \ (\operatorname {init} )= \operatorname {value} \ f}&\operatorname {inc} \ (\operatorname {inc} \ (\operatorname {inc} \ \ \operatorname {const} )=\operatorname {value} \ (f\x)\\\vdots &\vdots &\vdots \\n&n\operatorname {inc} \\operatorname {init} =\operatorname {value} \ (f^{n}\x)=\operatorname {inc} \operatorname {inc} \operatorname {inc}$

일반적인 반복 규칙은 다음과 같습니다.

${\displaystyle \operatorname {inc} \ (\operatorname {value} \ v)=\operatorname {value} \ (f\ v)}$

컨테이너에서 값을 검색하는 기능도 있는 경우(추출이라고 함),

${\displaystyle \operatorname {value} \ (\operatorname {value} \ v)=v}$

그런 다음 추출물을 사용하여 다음과 같이 새넘 함수를 정의할 수 있습니다.

$\displaystyle \operatorname {samenum} =\displayda n.\contextda f.\capda x.\operatorname {cap} \ (n\operatorname {inc} \operatorname {init} )=\capda n.\contextda f.\operatorname {value} \ (\operatorname {value} \ (n\f\x))=\120da n.\contextda f.\sysda x.n\f\x=\sysda n.n}$

samenum 함수는 본질적으로 유용하지 않습니다.단, inc는 f의 호출을 container 인수에 위임하므로 첫 번째 어플리케이션에서 f의 첫 번째 어플리케이션을 건너뛸 수 있는 인수를 무시하는 특별한 컨테이너를 받을 수 있습니다.이 새로운 초기 컨테이너를 const라고 부릅니다.위 표의 오른쪽은 n inc const의 확장을 나타냅니다.그런 다음 같은 함수의 식에서 init을 const로 대체하면 이전 함수를 얻을 수 있습니다.

${\displaystyle\operatorname{display}=\displayda n.\contextda f.\capda x.\operatorname {const} \ (n\operatorname {inc} \operatorname {const} )=\capda n.\contextda f.\operatorname {value} \ (\operatorname {value} \ ( (n-1)\ f\ x )=\120da n.\contextda f.\sysda x.(n-1)\f\x=\sysda n.(n-1)}$

아래에 설명된 바와 같이 inc, init, const, value 및 extract 함수는 다음과 같이 정의할 수 있다.

${\displaystyle {displaystyle}\operatorname {value}&=\operatorname {nc} k&=k\operatorname {inc} &=\operatorname {inc} &=g.\sysda h.h\(g\f)\\operatorname {init} &=\sysda h.h\x\\operatorname {const} &=\sysda u.x\end{aligned}}$

그래서 람다 표현은 다음과 같이 나타납니다.

${\displaystyle\operatorname{display}=\displayda n.\contextda f.\contextda x.n\ (\contextda g).\subda h.h\(g\f)\(\subda u.x)\(\subda u.u)}$

pred를 정의하는 또 다른 방법

Pred는 쌍을 사용하여 정의할 수도 있습니다.

${\displaystyle {displaystyle {aligned}\operatorname {f} = &\\\operatorname {second} \(\operatorname {second} \)\ (\operatorname {second} \ p)\\\operatorname {zero} =\ (\operatorname f).\pcda x.\x)\\operatorname {pc0} =&\operatorname {pc0} \\operatorname {zero} \operatorname {zero} \\operatorname {first} \\operatorname {f} \pcorname {f} \operatorname {f}$

이는 보다 단순한 정의이지만 pread에 대한 보다 복잡한 표현으로 이어집니다.${\displaystyle \S }$ 이전 \$displaystyle \operatorname {pred}$ \$operatorname {three$ ${\displaystyle \mathrm{확장}}$:

$(\displaystyle {displaystyle {aligned} \operatorname {three} = &\\operatorname {f} \ (\operatorname {f} \ (\operatorname {f} \ (\operatorname {f} \ (\operatorname {f} \zeratorname {zero} \ } \operatorname {zeratorname {zername} ) {zername {zeratorname} ) {zeratorname {zero}) {zername {zername} ) {zero} 0\=&\operatorname {first} \ (\operatorname {f} \ (\operatorname {f} \ \\operatorname {zero} \ \\operatorname {one} ))\=&\operatorname {first} \ (\operatorname {f} \ (\operatorname {f} \ (\operatorname {one} \\operatorname {first} \ (\operatorname {first} \ ） \ = \ operatorname {f} \ = 3 )$

나누기

자연수의 나눗셈은 다음과 같이 ^[5]실시할 수 있다.

${\displaystyle n/m=\operatorname {if}\n\geq m\\operatorname {then}\1+(n-m)/m\\operatorname {display}\0}$

n${\displaystyle }$-$$ ( $displaystyle$n -$$m )$계산$에는 많은 베타삭감이 필요합니다.손으로 줄이지 않는 한, 이것은 그다지 중요하지 않지만, 이 계산을 두 번 하지 않는 것이 좋습니다.숫자를 테스트하기 위한 가장 간단한 술어는 IsZero이므로 조건을 고려하십시오.

$(\displaystyle \operatorname {IsZero} \ (\operatorname {minus} \n\m)}$

But this condition is equivalent to ${\displaystyle n\leq m}$, not ${\displaystyle n<m}$. If this expression is used then the mathematical definition of division given above is translated into function on Church numerals as,

$\displaystyle \operatorname {sn\m\f=(\displayda d).\operatorname {IsZero} \ d\ (0\ f\ x)\ (f\ (\operatorname {divide1} \ d\ m\ f\ x)\ (\operatorname {minus} \ n\ m)}$

필요에 따라 이 정의에는 ${\displaystyle \text{마이너스n}}$ m$(\displaystyle \operatorname {minus}\n\m$에 대한 단일 콜이 있습니다.단, 이 수식은 (${\displaystyle n}$-${\displaystyle 1}$)${\displaystyle }$/ ${\displaystyle m}${\$displaystyle (n-1)/m$의 값을 나타냅니다.

이 문제는 divide를 호출하기 전에1 ~ n을 추가하는 것으로 해결할 수 있습니다.나눗셈의 정의는 다음과 같습니다.

${\displaystyle \operatorname {displaystyle} \n=\operatorname {display1} \(\operatorname {display} \n)}$

divide1은 재귀적 정의입니다.Y combinator는 재귀 구현에 사용할 수 있습니다.div by라는 새로운 함수를 만듭니다.

• 왼쪽에서 ${\displaystyle \mathrm{div1}}$ ${\displaystyle \to }$ div${\displaystyle \text{c}}$c \ $displaystyle \operatorname${$div1}$ \ $rightarrow \operatorname {div}$ \ $c$}
• 오른쪽 ${\displaystyle \mathrm{분할}}$ 1 ${\displaystyle \to }$ {$displaystyle \operatorname {param1} \오른쪽 화살표$ c$}$

갖기 위해,

$\displaystyle \operatorname {div} =\displayda c.\displayda n.\420da m.\contextda f.\sqda x. (\sqda d).\operatorname {IsZero} \ d\ (0\ f\ x)\ (f\ (c\ d\ m\ f\ x)\ (\operatorname {minus} \ n\ m)}$

그리고나서,

${\displaystyle\operatorname{display}=\displayda n.\operatorname {param1} \(\operatorname {param} \n)}$

어디에,

${{displaystyle}\operatorname {div}\operatorname {div}\operatorname {div}\\operatorname {div}\=\operatorname n.\contextda f.\sqda x.f\(n\f\x)\\Y&=\lambda f.(\lambda x.f\(x\x)\(\lambda x.f\(x\x)))\\0&=\contextda f.\operatorname {IsZero} &=\operatorname {false}\\operatorname {true} \end{aligned}}$

$displaystyle(디스플레이 스타일) &amp; operatorname {true} &amp; equiv \ a aa.a.\capda b.a\\operatorname {false} &\equiv \capda a.\sysda b.b\end {aligned}}$

$&quot;displaystyle&quot;&quot;연산자 이름&quot;=&quota m.\sysda n.n\operatorname {syslog} m\\operatorname {syslog} &=\syslogda n.\contextda f.\contextda x.n\ (\contextda g).\subda h.h\(g\f)\(\subda u.x)\(\subda u.u)\end {aligned}}$

주다,

$\displaystyle \operatorname {displayda} = \displayda n. (\displayda f.\displayda x.x\x)\ (\displayda x.f\x\displayda n).\420da m.\contextda f.\nambda x.(\nambda n.n\)(\nambda x.(\nambda a).\seconda b.b)\(\seconda a).\seconda b.a)\ d\ (\seconda f).\c4da x.x)\f\x(f\(c\d\m\f\x)\(\c4da m).\sysda n.n(\sysda n).\contextda f.\contextda x.n\ (\contextda g).\capda h.h\(g\f)\(\capda u.x)\(\capda u.u)m)\(\capda n).\contextda f.\sqda x.f\(n\f\x)\n)}$

또는 텍스트로서 ,에 \를 사용하고,

나눗셈 = (\n.(\f.\x.x x)(\x.f(x x))(\c.\n.\m.\f).\x.(\n.n(\x.\b.b)(\a.\b.a) d(\f.\x.x) f x)(f(c d m f x))(\m.n(\n.\f).\x.n (\g)\h.h(g f)(\u.x)(\u.u) m) (\n.\f).\x. f (n f x) n)

예를 들어 9/3은 다음과 같이 표시됩니다.

분할(\f)\x.f (f (f (f (f (f (f (f (f (f x)))))))) (\f).\x.f(f(f x))

람다 미적분 계산기를 사용하면 위의 식은 정규 순서를 사용하여 3으로 감소합니다.

\f.\x.f(f(x))

서명된 번호

교회 숫자를 서명된 숫자로 확장하는 간단한 방법 중 하나는 교회 쌍을 사용하는 것입니다. 교회 숫자는 양의 값과 음의 ^[6]값을 나타냅니다.정수값은 두 교회 숫자의 차이입니다.

자연수는 부호 있는 숫자로 변환됩니다.

$\displaystyle \operatorname {display} _{s}=\displayda x.\operatorname {display} \x\0}$

부정은 값을 교환함으로써 실행됩니다.

${\displaystyle \operatorname {neg}=\displayda x.\operatorname {second} \x} \(\operatorname {first} \x)\(\operatorname {first} \x)}$

쌍 중 하나가 0일 경우 정수 값이 더 자연스럽게 표시됩니다.OneZero 함수는 이 조건을 충족합니다.

$\displaystyle \operatorname {OneZero} = \operatorname {IsZero} \ (\operatorname {second} \x) \ x \ (\operatorname {Zero} \operatorname {Zero} \ ） \ （ \operatorname {Zername {Zero} \ ） \ ）$

재귀는 Y combinator를 사용하여 구현할 수 있습니다.

$\displaystyle \operatorname {OneZ} =\operatorname {IsZero} \ (\operatorname {isZero} \ (\operatorname {second} \x) \ (\operatorname { sero} \\ ) \ operatorname {\\\ opername {iszername} \ ）$

${\displaystyle\operatorname{OneZero}=Y\operatorname{OneZ}}$

플러스 마이너스

덧셈은 수학적으로 쌍으로 정의된다.

$\displaystyle x+y=[x_{p},x_{n}+[y_{n}]=x_{p}-x_{n}+y_{p}=(x_{p}+y_{p}-(x_n}+y_{n})-(x_n}+y_n})=[x_{p}+y_{p},x_{n}+y_{n}}$

마지막 표현은 람다 미적분으로 번역된다.

$\displaystyle \operatorname {plus} _{s}=\displayda x.\displayda y.\operatorname {OneZero} \ (\operatorname {pair} \ (\operatorname {first} \x) \ (\operatorname {first} \ y) \ (\operatorname {plus} \ (\operatorname {second} \) \ ) \ (\operatorname {first} \x) \ ）$

마찬가지로 뺄셈도 정의되어 있다.

$\displaystyle x-y=[x_{p},x_{n}-[y_{p}-x_{n}-y_{p}+y_{n}=(x_{p}+y_{n}-(x_{p}+y_{n})-(x_n}+y_{p})=[x_{p}+y_{n},x_{n}+y_{p}}$

부여,

${\displaystyle\operatorname{s}=\displayda x.\displayda y.\operatorname {OneZero} \ (\operatorname {pair} \ (\operatorname {first} \x) \ (\operatorname {second} \ y) \ (\operatorname {plus} \ (\operatorname {second} \) \ ) \ (\operatorname {first y ) \ ） ）$

곱셈과 나눗셈

곱셈은 다음과 같이 정의할 수 있다.

$\displaystyle x*y=[x_{p},x_{n}*[y_{p}-x_{n}*(y_{p}-y_{n})=(x_{p}*y_{p}+x_{n})}*y_{n}-(x_{p}*y_{n}+x_{n})}*y_{p}=[x_{p}*y_{p}+x_{n]}*y_{n},x_{p}*y_{n}+x_{n}}*y_{p}}$

마지막 표현은 람다 미적분으로 번역된다.

$\displaystyle \operatorname {mult}_{s}=\displayda x.\displayda y.\operatorname {second} \ (\operatorname {plus} \ (\operatorname {first} \x) \ (\operatorname {first} \x) \ (\operatorname {mult} \ (\operatorname {second} \x) \ (\operatorname {second y} \operatorname {first} \operatorname {first} \x} \ ） \ ） ）operatorname {second} \ x)\ (\operatorname {first} \ y)}$

나눗셈에 대해서도 같은 정의가 여기에 제시되어 있습니다.단, 이 정의에서는 각 쌍에 1개의 값이 0이어야 합니다(위의 OneZero 참조).divZ 함수를 사용하면 성분이 0인 값을 무시할 수 있습니다.

$\displaystyle \operatorname {divZ} = \displayda x.\displayda y.\operatorname {IsZero} \ y\ 0\ (\operatorname {divide} \ x\ y)}$

그 후 divZ는 곱셈과 동일하지만 다중이 divZ로 대체되는 공식으로 사용됩니다.

${\displaystyle\operatorname{s}=\displayda x.\displayda y.\operatorname {pair} \ (\operatorname {plus} \ (\operatorname {first} \x) \ (\operatorname {first} \ y) \ (\operatorname {divZ} \ (\operatorname {second} x) \ (\operatorname {first} \x} \)operatorname {second} \ x)\ (\operatorname {first} \ y)}$

유리수와 실수수

합리적이고 계산 가능한 실수는 람다 미적분에도 부호화될 수 있다.유리번호는 부호화된 번호의 쌍으로 부호화할 수 있습니다.계산 가능한 실수는 실제 값과의 차이가 ^[7]필요한 만큼 작게 만들어질 수 있는 수만큼 차이가 나는 것을 보장하는 제한 프로세스에 의해 부호화될 수 있습니다.^[8] 주어진 참조는 이론적으로 람다 미적분으로 번역될 수 있는 소프트웨어를 기술한다.실수가 정의되면 복소수는 자연스럽게 실수의 쌍으로 부호화됩니다.

위에서 설명한 데이터 유형 및 함수는 모든 데이터 유형 또는 계산이 람다 미적분으로 인코딩될 수 있음을 보여줍니다.이것은 처치튜링 논문입니다.

다른 표현과의 번역

대부분의 현실 언어들은 기계 원어민 정수를 지원합니다; 교회와 비구치 함수는 음이 아닌 정수와 대응하는 교회 숫자 사이를 변환합니다.함수는 여기 해스켈에서 제공되고 있습니다.\람다 미적분의 of에 해당한다.다른 언어에서도 구현은 비슷합니다.

유형 교회 a = (a -> a) -> a -> a  교회 :: 정수 -> 교회 정수 교회 0 = \f -> \x -> x 교회 n = \f -> \x -> f (교회 (n-1) f x)  언어치 :: 교회 정수 -> 정수 언어치 cn = cn (+ 1) 0 

처치 부울런스

Church Boalans는 True 및 False 부울 값의 Church 인코딩입니다.일부 프로그래밍 언어에서는 Smalltalk와 Pico와 같은 부울 산술의 구현 모델로 사용합니다.

부울 로직은 선택사항으로 간주할 수 있습니다.Church 인코딩(true 및 false)은 다음 두 가지 파라미터의 함수입니다.

• true는 첫 번째 파라미터를 선택합니다.
• false는 두 번째 파라미터를 선택합니다.

두 가지 정의는 Church Bohans로 알려져 있습니다.

$displaystyle(디스플레이 스타일) &amp; operatorname {true} &amp; equiv \ a aa.a.\capda b.a\\operatorname {false} &\equiv \capda a.\sysda b.b\end {aligned}}$

이 정의를 통해 술어(즉, 논리값을 반환하는 함수)가 if-clauses로 직접 작용할 수 있다.부울을 반환하는 함수는 두 개의 파라미터에 적용되며 첫 번째 파라미터 또는 두 번째 파라미터 중 하나를 반환합니다.

${\displaystyle \operatorname {cisco-} x\\operatorname {then-display} \\operatorname {complete}$

fredicate-x가 true로 평가되면 then-fredicate로 평가되며, false로 평가되면 else-fredicate-x가 평가됩니다.

true와 false는 첫 번째 또는 두 번째 파라미터를 선택하기 때문에 논리연산자를 제공하기 위해 조합할 수 있습니다.의 구현에는 여러 가지가 있습니다.

$&#displaystyle &#operatorname &=&#da p.\sysda q.p\p\\operatorname {or} &=\sysda p.\sysda q.p\q\\operatorname {not} _{1}&=\sysda p.\420da a.\sysda b.p\a\\operatorname {not}_{2}&=\sysda p.p\(\sysda a).\seconda b.b)\(\seconda a).\sysda b.a)=\sysda p.p\operatorname {false}\operatorname {true}\\operatorname {xor} &=\sysda a.\paramda b.a\(\operatorname {not} \b)\b\\operatorname {if} &=\paramda p.\420da a.\sysda b.p\a\b\end{aligned}}$

몇 가지 예:

$\displaystyle\operatorname{및}\operatorname{true}\operatorname{false}&=(\displayda p).\operatorname {true} \operatorname {false} =\operatorname {true} \operatorname {false} \operatorname {true} =(\operatorname a).\operatorname {false} \operatorname {true} = \operatorname {false} \\operatorname {or} \operatorname {true} \operatorname {false} &=(\operatorname p).\subda q.p\q)\ (\subda a).\seconda b.a)\(\seconda a).\sysda b.b)=(\sysda a).\seconda b.a)\(\seconda a).\seconda b.a)\(\seconda a).\sysda b.b)=(\sysda a).\sysda b.a)=\operatorname {true} \\operatorname {not} _{1}\\operatorname {true} &=(\sysda p).\420da a.\seconda b.p\b\a) (\seconda a).\sysda b.a)=\sysda a.\sqda b. (\cqda a).\subda b.a)\b\a=\subda a.\sysda b.(\sysda c.b)\a=\sysda a.\sysda b.b=\operatorname {false} \\operatorname {not} _{2}\\operatorname {true} &=(\sysda p.p\(\sysda a).\seconda b.b) (\seconda a).\subda b.a)(\subda a).\sysda b.a)=(\sysda a).\seconda b.a) (\seconda a).\seconda b.b) (\seconda a).\sysda b.a)=(\sysda b.(\sysda a).\seconda b.b)\(\seconda a).\sysda b.a)=\sysda a.\sysda b.b=\operatorname {false} \end{aligned}}$