チャーチエンコーディング – 日本語百科事典辞書

Church_encoding

数学、教会符号化は、データと演算子を表現する手段であるラムダ計算を。教会数字はラムダ表記を使用して自然数の表現です。このメソッドは、最初にラムダ計算でデータをこの方法でエンコードしたAlonzoChurchにちなんで名付けられました。
他の表記法（整数、ブール値、ペア、リスト、タグ付き共用体など）で通常プリミティブと見なされる用語は、チャーチエンコードの下で高階関数にマップされます。チャーチ・チューリングの論文は、任意の計算演算子（およびそのオペランドが）教会符号化の下で表現することができると主張しています。で型なしラムダ計算のみプリミティブデータ型が関数です。
チャーチ数化は意図されていませんプリミティブデータ型の実用的な実装として。その使用法は、計算を表すために他のプリミティブデータ型が必要ないことを示すことです。完全性は表象的です。表現を一般的なデータ型に変換して、人々に表示するには、追加の関数が必要です。教会の定理からの等価性の決定不可能性のために、2つの関数が拡張的に等しいかどうかを一般に決定することはできません。変換は、何らかの方法で関数を適用して、それが表す値を取得したり、その値をリテラルラムダ項として検索したりする場合が
ラムダ計算は通常、内包的等式を使用していると解釈されます。平等の内包的定義と外延的定義の違いのため、結果の解釈には潜在的な問題が

コンテンツ
1 チャーチ数
1.1 チャーチ数による計算 1.2 チャーチ数の関数の表 1.3 先行機能の導出
1.3.1 バリューコンテナ
1.3.2 株式会社
1.3.3 エキス
1.3.4 定数
1.3.5 predを定義する別の方法
1.4 分割 1.5 符号付き数値 1.6 プラスとマイナス 1.7 掛け算と割り算 1.8 有理数と実数 1.9 他の表現による翻訳
2 教会のブール値4 教会のペア
5 リストエンコーディング
5.1 リストノードとしての2つのペア 5.2 リストノードとしての1つのペア 5.3 使用してリストを表す右倍に 5.4 スコットエンコーディングを使用してリストを表す
6 も参照してください
7 ノート
8 参考文献

チャーチ数
チャーチ数は、チャーチ数での自然数の表現です。高次機能の自然数を表し、nは任意の機能をマッピングする関数であります f { f}
$f""$
そのn倍の構成に。簡単に言うと、数値の「値」は、関数が引数をカプセル化する回数に相当します。f ∘ n = f ∘ f ∘ ⏟ n
タイムズ { f ^ { circ n} = underbrace {f circ f circ cdots circ f} _ {n { text {times}}}。、}
すべてのチャーチ数は、2つのパラメーターをとる関数です。教会の数字0、1、2、…、定義されていますが、次のようにラムダ計算。
始まる 0 すべての機能を適用していない、と進ん 1は、一度関数を適用2 回関数を適用し、3 など、機能を3回適用します：
番号
関数の定義
ラムダ式0 0fX =X 0 = λ
f λ
X X 1fX = fX 1 = λ
f λ
X fX 2fX = f（（ fX
）。2 = λ
f λ X f （（ fX
）。 3fX = f（（ f（（ fX ）。）。3 = λ
f λ X f （（ f（（ fX ）。）。
⋮⋮ ⋮ n n fX = fnX n = λ
f λ f ∘ nX
{ { begin {array} {r | l | l} { text {Number}}＆{ text {関数定義}}＆{ text {ラムダ式}} \ hline0＆0 f x = x＆0 = lambdaf。 lambda xx \ 1＆1 f x = f x＆1 = lambdaf。 lambda xf x \ 2＆2 f x = f （f x）＆2 = lambda f。 lambda xf （f x）\ 3＆3 f x = f （f （f x））＆3 = lambdaf。 lambda xf （f （f x）） \ vdots＆ vdots＆ vdots \ n＆n f x = f ^ {n} x＆n = lambdaf。 lambda xf ^ { circ n} x end {array}}}
チャーチ数3は、任意の関数を値に3回適用するアクションを表します。提供された関数は、最初に提供されたパラメーターに適用され、次にそれ自体の結果に連続して適用されます。最終結果は数字の3ではありません（指定されたパラメーターがたまたま0であり、関数が後継関数である場合を除く）。関数自体は、その最終結果ではなく、チャーチ数3です。チャーチ数3は、単に3回何かをすることを意味します。これは、「3回」が何を意味するのかを示す大げさなデモンストレーションです。

チャーチ数による計算
数の算術演算は、チャーチ数の関数で表すことができます。これらの関数は、ラムダ計算で定義することも、ほとんどの関数型プログラミング言語で実装することもできます（ラムダ式の関数への変換を参照）。
加算機能
プラス（（ m n
）。= m + n
{ operatorname {plus}（m、n）= m + n}

IDを使用します
f ∘ （（ m+ n ）。（（ X
）。= f ∘ m （（ f ∘ n （ X ）。）。 { f ^ { circ（m + n）}（x）= f ^ { circ m}（f ^ { circ n}（x））}

。
プラス≡ λ m λ n λ
f λX m f （（ n fX ）。
{ operatorname {plus} equiv lambdam。 lambdan。 lambdaf。 lambda xm f （n f x）}
後継機能
サク（ n ）。= n + 1
{ operatorname {succ}（n）= n + 1}

であるβ-同等に（（プラス 1 ）。 {（ operatorname {plus} 1）}

。
サク≡ λ
n λ
f λX f（（ n fX ）。
{ operatorname {succ} equiv lambdan。 lambdaf。 lambda xf （n f x）}
乗算関数
マルチ（（ m n
）。= m ∗ n
{ operatorname {mult}（m、n）= m * n}

IDを使用します
f ∘ （（ m ∗ n ）。（（ X
）。 = （（ f ∘ n
）。 ∘ m （ X ）。
{ f ^ { circ（m * n）}（x）=（f ^ { circ n}）^ { circ m}（x）}

。
マルチ≡ λ m λ n λ
f λX m（（ n f ）。X
{ operatorname {mult} equiv lambdam。 lambdan。 lambdaf。 lambda xm （n f） x}
べき乗関数 exp （（ m n
）。= m n
{ operatorname {exp}（m、n）= m ^ {n}}

チャーチ数の定義によって与えられます、n hX = h n X
{ n h x = h ^ {n} x}

。定義の代用h m X f
{ h to m、x to f}

取得するためn m f = m n
f { n m f = m ^ {n} f}

と、exp m n = m n =n m
{ operatorname {exp} m n = m ^ {n} = n m}
ラムダ式を与える、exp ≡ λ
m λn n m
{ operatorname {exp} equiv lambdam。 lambda nn m}

The pred （ n ）。
{ operatorname {pred}（n）}

機能を理解するのはもっと難しいです。pred ≡ λ
n λ
f λX n（（ λ
g λ h h （（ g f ）。）。（（ λ u X ）。（（ λ u u ）。
{ operatorname {pred} equiv lambdan。 lambdaf。 lambda xn （ lambdag。 lambda hh （g f））（ lambda ux）（ lambda uu）}
チャーチ数は関数をn回適用します。先行関数は、そのパラメーターをn-1回適用する関数を返す必要がこれは、関数の最初の適用を省略した方法で初期化されるfとxの周りにコンテナーを構築することによって実現されます。より詳細な説明については、前任者を参照して
減算関数は、先行関数に基づいて記述できます。
マイナス≡ λ
m λ
n （（ n pred ）。 m { operatorname {minus} equiv lambdam。 lambda n。（n operatorname {pred}） m}

チャーチ数の関数の表関数代数身元
関数の定義ラムダ式
後継n + 1
{ n + 1}
f n + 1 X = f（（f n X ）。 { f ^ {n + 1} x = f（f ^ {n} x）}

サクn fX = f（（ n fX ）。
{ operatorname {succ} n f x = f （n f x）}
λ n λ
f λX f（（ n fX ）。
{ lambdan。 lambdaf。 lambda xf （n f x）}

..。
添加m + n
{ m + n}
f m + n X =
fm （f n X ）。
{ f ^ {m + n} x = f ^ {m}（f ^ {n} x）}

プラスm n fX = m f（（ n fX ）。
{ operatorname {plus} m n f x = m f （n f x）}
λ m λ
n λ
f λX m f （（ n fX ）。
{ lambdam。 lambdan。 lambdaf。 lambda xm f （n f x）}
λ m λ n n サク m { lambdam。 lambda nn operatorname {succ} m}

乗算m ∗ n
{ m * n}
f m ∗
nX =（（f m ）。n X
{ f ^ {m * n} x =（f ^ {m}）^ {n} x}

かけるm n fX = m（（ n f ）。X
{ operatorname {multiply} m n f x = m （n f） x}
λ m λ
n λ
f λX m（（ n f ）。X
{ lambdam。 lambdan。 lambdaf。 lambda xm （n f） x}
λ m λ
n λ f m （（ n f ）。
{ lambdam。 lambdan。 lambda fm （n f）}

べき乗m n
{ m ^ {n}}
n m f =
m n f { n m f = m ^ {n} f}
exp m n fX =（（ n m ）。 fX { operatorname {exp} m n f x =（n m） f x}
λ m λ
n λ
f λX （（ n m ）。 fX { lambdam。 lambdan。 lambdaf。 lambda x。（n m） f x}
λ m λn n m
{ lambdam。 lambda nn m}

前任者*n − 1
{ n-1}

株式会社 n 詐欺= val（（f n − ）。 { operatorname {inc} ^ {n} operatorname {con} = operatorname {val}（f ^ {n-1} x）}
I f（（ n== 0 ）。0 e l s e（（ n− 1 ）。 { if（n == 0） 0 else （n-1）}
λ n λ
f λX n（（ λ
g λ h h （（ g f ）。）。（（ λ u X ）。（（ λ u u ）。
{ lambdan。 lambdaf。 lambda xn （ lambdag。 lambda hh （g f））（ lambda ux）（ lambda uu）}
減算*m − n
{ mn}
f m −
nX =（（f − 1
）。n （f m X ）。
{ f ^ {mn} x =（f ^ {-1}）^ {n}（f ^ {m} x）}

マイナスm n =（（ n pred ）。 m { operatorname {minus} m n =（n operatorname {pred}） m}

..。 λ m λn n pred m
{ lambdam。 lambda nn operatorname {pred} m}

*チャーチエンコーディングでは、 pred （（ 0
）。= 0
{ operatorname {pred}（0）= 0}

m <=n m − n = 0
{ m <= n to mn = 0}

先行機能の導出
チャーチエンコーディングで使用される先行関数は、 pred （（ n
）。 = {{ 0 もしも
n= 0 n − 1
それ以外は
{ operatorname {pred}（n）= { begin {cases} 0＆{ mbox {if}} n = 0、\ n-1＆{ mbox {otherwise}} end {cases}}}

。
前任者を構築するには、関数1をより少ない時間で適用する方法が必要です。数字のnは、関数f をxにn回適用します。先行関数は、関数nを-1回適用するために、数字nを使用する必要が
先行関数を実装する前に、コンテナ関数で値をラップするスキームを次に示します。fとxの代わりに使用するincとinitと呼ばれる新しい関数を定義します。コンテナ関数はvalueと呼ばれます。表の左側は、incとinitに適用された数字nを示しています。
番号
initの使用
constの使用 0 初期化 = 価値X 1 株式会社
初期化 = 価値（（ fX ）。株式会社const =
価値X 2 株式会社（（株式会社
初期化
）。 = 価値（（ f（（ fX ）。）。
株式会社（（株式会社 const ）。 = 価値（（ fX
）。 3 株式会社（（株式会社（（株式会社
初期化）。）。 = 価値（（ f（（ f（（ fX ）。）。）。株式会社（（株式会社（（株式会社 const ）。
）。 = 価値（（ f（（ fX ）。）。
⋮⋮ ⋮ n n
株式会社
初期化 = 価値（（ f nX ）。 = 価値（（ n fX ）。 n 株式会社const =
価値（（ fn − 1X
）。 = 価値（（（（ n − 1
）。 fX ）。
{ { begin {array} {r | r | r} { text {Number}}＆{ text {Using init}}＆{ text {Using const}} \ hline 0＆ operatorname {init } = operatorname {value} x＆\ 1＆ operatorname {inc} operatorname {init} = operatorname {value} （f x）＆ operatorname {inc} operatorname {const} = operatorname {value} 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 {inc} （ operatorname {inc} operatorname {init}））= operatorname {value} （f （f （f x）））＆ operatorname {inc} （ operatorname {inc} （ operatorname {inc} operatorname {const }））= operatorname {value} （f （f x））\ vdots＆ vdots＆ vdots \ n＆n operatorname {inc} operatorname {init} = operatorname {value} （f ^ {n} x）= operatorname {value} （n f x）＆n operatorname {inc} operatorname {const} = operatorname {value} （f ^ {n-1} x）= o peratorname {value} （（n-1） f x）\ end {array}}}
一般的な再発ルールは、
株式会社（（価値 v ）。 = 価値（（ f v ）。
{ operatorname {inc} （ operatorname {value} v）= operatorname {value} （f v）}
コンテナから値を取得する関数（extractと呼ばれる）もある場合は、
エキス（（価値 v ）。= v
{ operatorname {extract} （ operatorname {value} v）= v}
次に、extractを使用して、samenum関数を次のように定義できます。samenum = λ
n λ
f λX エキス（（ n
株式会社
初期化
）。= λ
n λ
f λX エキス（（価値（（ n fX ）。
）。= λ
n λ
f λX nfX = λ n n
{ operatorname {samenum} = lambdan。 lambdaf。 lambdax。 operatorname {extract} （n operatorname {inc} operatorname {init}）= lambdan。 lambdaf。 lambdax。 operatorname {extract} （ operatorname {value} （n f x））= lambdan。 lambdaf。 lambda xn f x = lambda nn}
samenumの機能は、本質的に有用ではありません。ただし、incはfの呼び出しをそのコンテナー引数に委任するため、最初のアプリケーションでincが引数を無視する特別なコンテナーを受け取り、fの最初のアプリケーションをスキップできるようにすることができます。この新しい初期コンテナをconstと呼びます。上記表に示す展開のの右側N INC CONST。次に、同じ関数の式でinitをconstに置き換えることにより、先行関数を取得します。pred = λ
n λ
f λX エキス（（ n
株式会社 const ）。= λ
n λ
f λX エキス（（価値（（（（ n− 1
）。 fX ）。
）。= λ
n λ
f λX （（ n− 1
）。fX = λ
n （（ n− 1 ）。 { operatorname {pred} = lambdan。 lambdaf。 lambdax。 operatorname {extract} （n operatorname {inc} operatorname {const}）= lambdan。 lambdaf。 lambdax。 operatorname {extract} （ operatorname {value} （（n-1） f x））= lambdan。 lambdaf。 lambda x。（n-1） f x = lambda n。（n-1）}
以下で説明するように、関数inc、init、const、value、extractは、次のように定義できます。
価値= λ
v （（ λ h v ）。エキスk = k λ u
株式会社= λ
g λ h h （（ g f ）。
初期化= λ hX onst = λ X
{ { begin {aligned} operatorname {value}＆= lambda v。（ lambda hh v）\ operatorname {extract} k＆= k lambda uu \ operatorname {inc}＆= lambdag。 lambda hh （g f）\ operatorname {init}＆= lambda hh x \ operatorname {const}＆= lambda ux end {aligned}}}
これにより、predのラムダ式は次のようになります。pred = λ
n λ
f λX n（（ λ
g λ h h （（ g f ）。）。（（ λ u X ）。（（ λ u u ）。
{ operatorname {pred} = lambdan。 lambdaf。 lambda xn （ lambdag。 lambda hh （g f））（ lambda ux）（ lambda uu）}
バリューコンテナ編集値コンテナは、その値に関数を適用します。それはによって定義されます、
価値v h = h v
{ operatorname {value} v h = h v}

それで、値 = λ
v （（ λ h v ）。 { operatorname {value} = lambda v。（ lambda hh v）}

株式会社編集株式会社機能が含ま値とるべきVを、そして含む新しい値を返すFVを。
株式会社（（価値 v ）。 = 価値（（ f v ）。
{ operatorname {inc} （ operatorname {value} v）= operatorname {value} （f v）}

gを値コンテナとすると、
g = 価値 v { g = operatorname {value} v}

それから、
gf =
価値v f = f v
{ g f = operatorname {value} v f = f v}

それで、
株式会社g =
価値（（ g f ）。
{ operatorname {inc} g = operatorname {value} （g f）}

株式会社= λ
g λ h h （（ g f ）。
{ operatorname {inc} = lambdag。 lambda hh （g f）}

エキス編集値は、恒等関数を適用することによって抽出できます。
I= λ u
{ I = lambda uu}

Iを使用して、
価値v I = v
{ operatorname {value} v I = v}

それで、
エキスk = k I
{ operatorname {extract} k = k I}

定数編集 predを実装するには、init関数をfを適用しないconstに置き換えます。満たすにはconstが必要です。
株式会社const =
価値X
{ operatorname {inc} operatorname {const} = operatorname {value} x}
λ h h（（ const f ）。= λ hX
{ lambda hh （ operatorname {const} f）= lambda hh x}

次の場合、どちらが満たされますかonst f =X
{ operatorname {const} f = x}

またはラムダ式として、onst = λ X
{ operatorname {const} = lambda ux}

predを定義する別の方法
Predは、ペアを使用して定義することもできます。f = λ
p ペア（（ 2番目 p ）。（（サク（（ 2番目 p ）。）。零 = （（ λ
f λ X X ）。c0 =
ペア零零 red = λ
n 初め（（ nf pc0 ）。 { { begin {aligned} operatorname {f} =＆ lambdap。\ operatorname {pair} （ operatorname {second} p）（ operatorname {succ} （ operatorname {second } p））\ operatorname {zero} =＆（ lambdaf。 lambdax。 x）\ operatorname {pc0} =＆ operatorname {pair} operatorname {zero} operatorname {zero} \ operatorname {pred} =＆ lambdan。\ operatorname {first} （n operatorname {f} operatorname {pc0}）\ end {aligned}}}
これはより単純な定義ですが、predのより複雑な式につながります。の拡張pred つ
{ operatorname {pred} operatorname {three}}

： pred 三つ = 初め（（ f（（ f（（ f（（ペア零零）。）。）。）。 = 初め（（ f（（ f（（ペア零 1 ）。）。
）。 = 初め（（ f（（ペア1 2 ）。）。 = 初め（（ペア 2 三つ
）。 2
{ { begin {aligned} operatorname {pred} operatorname {three} =＆ operatorname {first} （ operatorname {f} （ operatorname {f} （ operatorname {f} （ operatorname {pair} operatorname {zero} operatorname {zero}））））\ =＆ operatorname {first} （ operatorname {f} （ operatorname {f} （ operatorname {ペア} operatorname {zero} operatorname {one}）））\ =＆ operatorname {first} （ operatorname {f} （ operatorname {pair} operatorname {one} operatorname {two}））\ =＆ operatorname {first} （ operatorname {pair} operatorname {two} operatorname {three}）\ =＆ operatorname {two} end {aligned} }}

分割
自然数の除算は、によって実装できます。n /
m = もしもn ≥ m
それから1 +（（ n− m
）。 / m
それ以外 0 { n / m = operatorname {if} n geq m operatorname {then} 1+（nm）/ m operatorname {else} 0}
計算n − m
{ nm}

多くのベータ版の削減が必要です。手作業で削減を行わない限り、これはそれほど重要ではありませんが、この計算を2回行う必要がないことが望ましいです。数値をテストするための最も単純な述語はIsZeroであるため、条件を考慮して IsZero （（マイナスn m ）。 { operatorname {IsZero} （ operatorname {マイナス} n m）}
しかし、この条件は同等ですn ≤ m
{ n leq m}

、いいえn < m
{ n
。この式を使用すると、上記の除算の数学的定義は、チャーチ数の関数に次のように変換されます。
除算1n m fX =（（ λd IsZero d（（ 0 fX ）。（（ f（（除算1d m fX ）。）。）。（（マイナスn m ）。 { operatorname {divide1} n m f x =（ lambdad。 operatorname {IsZero} d （0 f x）（f （ operatorname {divide1} d m f x）））（ operatorname {マイナス} n m）}
この定義には
マイナス
n m
{ operatorname {マイナス} n m}

。ただし、結果として、この式は次の値を与えます。（（ n− 1
）。/ m
{（n-1）/ m}

。
この問題は、divideを呼び出す前にnに1を追加することで修正できます。除算の定義は次のとおりです。
分けるn =
除算1（（サク n ）。
{ operatorname {divide} n = operatorname {divide1} （ operatorname {succ} n）}
split1は再帰的定義です。Yコンビネータは、再帰を実装するために使用されてもよいです。divby ;という新しい関数を作成します。
左側に
除算1div c
{ operatorname {divide1} rightarrow operatorname {div} c}
右側に
除算1 c { operatorname {divide1} rightarrow c}
取得するため、div = λ c λ n λ m λ
f λX （（ λd IsZero d（（ 0 fX ）。（（ f（（ cd m fX ）。）。）。（（マイナスn m ）。 { operatorname {div} = lambdac。 lambdan。 lambdam。 lambdaf。 lambda x。（ lambdad。 operatorname {IsZero} d （0 f x）（f （c d m f x）））（ operatorname {マイナス} n m）}
それで、
分ける= λ
n 除算1（（サク n ）。
{ operatorname {divide} = lambdan。 operatorname {divide1} （ operatorname {succ} n）}
どこ、
除算1= Y div ク = λ
n λ
f λ X f （（ n fX ）。
Y= λ
f （（ λ X f （（ XX ）。）。（（ λ X f （（ XX ）。）。
0= λ
f λ X sZero = λ n（（ λ X false ）。 true { { begin {aligned} operatorname {divide1}＆= Y operatorname {div} \ operatorname {succ}＆= lambdan。 lambdaf。 lambda xf （n f x ）\ Y＆= lambda f。（ lambda xf （x x））（ lambda xf （x x））\ 0＆= lambdaf。 lambda xx \ operatorname {IsZero} ＆= lambda nn （ lambdax。 operatorname {false}） operatorname {true} end {aligned}}}
true
≡ λ a λb a false
≡ λ a λ b b { { begin {aligned} operatorname {true}＆ equiv lambdaa。 lambda ba \ operatorname {false}＆ equiv lambdaa。 lambda bb end {aligned}}}

マイナス= λ
m λ n pred m red = λ
n λ
f λ X n （（ λ
g λ h h （（ g f ）。）。（（ λ u X ）。（（ λ u u ）。
{ { begin {aligned} operatorname {minus}＆= lambdam。 lambda nn operatorname {pred} m \ operatorname {pred}＆= lambdan。 lambdaf。 lambda xn （ lambdag。 lambda hh （g f））（ lambda ux）（ lambda uu） end {aligned}}}
与える、
分ける= λ
n （（（（ λ
f （（ λ X XX ）。（（ λ X f （（ XX ）。）。）。（（ λc λ n λ m λ f λ
X （（ λ
d （（ λ n n （（ λ
X （（ λ
a λ b b ）。）。（（ λ
a λ b a ）。
）。 d （（（（ λ
f λ X X ）。 fX ）。（（ f（（ cd m fX ）。）。）。（（（（ λ
m λ n n （（ λ
n λ
f λ X n （（ λ
g λ h h （（ g f ）。）。（（ λ u X ）。（（ λ u u ）。
）。 m ）。n m ）。）。）。（（（（ λ
n λ
f λ X f （（ n fX ）。
）。 n ）。
{ scriptstyle operatorname {divide} = lambda n。（（ lambda f。（ lambda xx x）（ lambda xf （x x）））（ lambdac。 lambda n 。 lambdam。 lambdaf。 lambda x。（ lambda d。（ lambda nn （ lambda x。（ lambdaa。 lambda bb））（ lambdaa。 lambda ba）） d （（ lambdaf。 lambda xx） f x）（f （c d m f x）））（（ lambdam。 lambda nn（ lambdan。 lambdaf。 lambda xn （ lambdag。 lambda hh （g f））（ lambda ux）（ lambda uu））m） n m）））（（ lambda n 。 lambdaf。 lambda xf （n f x）） n）}
またはテキストとして、λにを使用します。
除算=（ n。（（ f。（ xx x）（ xf（xx）））（ c。 n。 m。 f。 x。（ d。（ nn（ x 。（ a。 bb））（ a。 ba））d（（ f。 xx）fx）（f（cdmfx）））（（ m。 nn（ n。 f。 xn（ g。 hh（gf））（ ux）（ uu））m）nm）））（（ n。 f。x。f（nfx））n））
たとえば、9/3は次のように表されます。
除算（ f。 xf（f（f（f（f（f（f（f（fx））））））））））（ f。 xf（f（fx）））
ラムダ計算機を使用すると、上記の式は通常の順序で3になります。
f。 xf（f（f（x）））

符号付き数値
チャーチ数値を符号付き数値に拡張するための簡単なアプローチの1つは、正と負の値を表すチャーチ数値を含むチャーチペアを使用することです。整数値は、2つのチャーチ数の差です。
自然数は、によって符号付き数に変換されます。
変換s =
λX ペアX 0 { operatorname {convert} _ {s} = lambdax。 operatorname {pair} x 0}
否定は、値を交換することによって実行されます。
ネガs =
λX ペア（（ 2番目X ）。（（初めX ）。 { operatorname {neg} _ {s} = lambdax。 operatorname {pair} （ operatorname {second} x）（ operatorname {first} x）}
ペアの1つがゼロの場合、整数値はより自然に表されます。OneZeroの機能は、この条件を達成し、OneZero =
λX IsZero（（初めX ）。X （（ IsZero（（ 2番目X ）。X （（ OneZero
ペア（（ pred（（初めX ）。）。（（ pred（（ 2番目X ）。）。）。）。
{ operatorname {OneZero} = lambdax。 operatorname {IsZero} （ operatorname {first} x） x （ operatorname {IsZero} （ operatorname {second} x） x （ operatorname {OneZero} operatorname {pair} （ operatorname {pred} （ operatorname {first} x））（ operatorname {pred} （ operatorname {second} x）））） }
再帰は、Yコンビネータを使用して実装できます。OneZ = λ
c λX IsZero（（初めX ）。X （（ IsZero（（ 2番目X ）。X （（ c
ペア（（ pred（（初めX ）。）。（（ pred（（ 2番目X ）。）。）。）。
{ operatorname {OneZ} = lambdac。 lambdax。 operatorname {IsZero} （ operatorname {first} x） x （ operatorname {IsZero} （ operatorname {second} x ） x （c operatorname {pair} （ operatorname {pred} （ operatorname {first} x））（ operatorname {pred} （ operatorname {second} x）））） }

OneZero = Y OneZ
{ operatorname {OneZero} = Y operatorname {OneZ}}

プラスとマイナス
加算は、ペアで数学的に次のように定義されます。X+ y = [X p X n ] + [ yp y n ] =X p −X n+ y p − y n = （（ Xp + y p
）。 − （（ Xn + y n
）。= [X p + y p X n+ y n ]
{ x + y = [x_ {p}、x_ {n}] + [y_ {p}、y_ {n}] = x_ {p} -x_ {n} + y_ {p} -y_ {n} =（x_ {p} + y_ {p}）-（x_ {n} + y_ {n}）= [x_ {p} + y_ {p}、x_ {n} + y_ {n}]}
最後の式は、次のようにラムダ計算に変換されます。
プラスs =
λX λ y OneZero （（ペア（（プラス（（初めX ）。（（初め y ）。）。（（プラス（（ 2番目X ）。（（ 2番目 y ）。）。）。
{ operatorname {plus} _ {s} = lambdax。 lambday。 operatorname {OneZero} （ operatorname {pair} （ operatorname {plus} （ operatorname {first} x）（ operatorname {first} y））（ operatorname {plus} （ operatorname {second} x）（ operatorname {second} y）））}
同様に減算が定義され、X− y = [X p X n ] − [ yp y n ] =X p −X n− y p + y n = （（ Xp + y n
）。 − （（ Xn + y p
）。= [X p + y n X n+ y p ]
{ xy = [x_ {p}、x_ {n}]-[y_ {p}、y_ {n}] = x_ {p} -x_ {n} -y_ {p} + y_ {n} =（ x_ {p} + y_ {n}）-（x_ {n} + y_ {p}）= [x_ {p} + y_ {n}、x_ {n} + y_ {p}]}
与える、
マイナスs =
λX λ y OneZero （（ペア（（プラス（（初めX ）。（（ 2番目 y ）。）。（（プラス（（ 2番目X ）。（（初め y ）。）。）。
{ operatorname {minus} _ {s} = lambdax。 lambday。 operatorname {OneZero} （ operatorname {pair} （ operatorname {plus} （ operatorname {first} x）（ operatorname {second} y））（ operatorname {plus} （ operatorname {second} x）（ operatorname {first} y）））}

掛け算と割り算
乗算は、によって定義できます。X∗ y = [X p X n ] ∗ [ yp y n ] =（（ Xp −X n
）。 ∗ （（ yp − y n
）。 = （（ Xp ∗ y p +X n ∗y n
）。 − （（ Xp ∗ y n +X n ∗y p
）。= [X p ∗ y p +X
n∗ y n X p ∗ y n+X n ∗ y p ]
{ x * y = [x_ {p}、x_ {n}] * [y_ {p}、y_ {n}] =（x_ {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}]}
最後の式は、次のようにラムダ計算に変換されます。
マルチs =
λX λ
y ペア（（プラス（（マルチ（（初めX ）。（（初め y ）。）。（（マルチ（（ 2番目X ）。（（ 2番目 y ）。）。）。（（プラス（（マルチ（（初めX ）。（（ 2番目 y ）。）。（（マルチ（（ 2番目X ）。（（初め y ）。）。）。
{ operatorname {mult} _ {s} = lambdax。 lambday。 operatorname {pair} （ operatorname {plus} （ operatorname {mult} （ operatorname {first} x）（ operatorname {first} y））（ operatorname {mult} （ operatorname {second} x）（ operatorname {second} y）））（ operatorname {plus} （ operatorname {mult} （ operatorname {first} x）（ operatorname {second} y））（ operatorname {mult} （ operatorname {second} x）（ operatorname {first} y）））}}
除算についても同様の定義がありますが、この定義では、各ペアの1つの値がゼロでなければなりません（上記のOneZeroを参照）。divZの機能は、私たちはゼロ成分を有する値を無視することができます。divZ =
λX λy IsZero y 0（（分けるX y ）。
{ operatorname {divZ} = lambdax。 lambday。 operatorname {IsZero} y 0 （ operatorname {divide} x y）}
次に、divZは次の式で使用されます。これは乗算の場合と同じですが、multがdivZに置き換えられます。
分けるs =
λX λ
y ペア（（プラス（（ divZ（（初めX ）。（（初め y ）。）。（（ divZ（（ 2番目X ）。（（ 2番目 y ）。）。）。（（プラス（（ divZ（（初めX ）。（（ 2番目 y ）。）。（（ divZ（（ 2番目X ）。（（初め y ）。）。）。
{ operatorname {divide} _ {s} = lambdax。 lambday。 operatorname {pair} （ operatorname {plus} （ operatorname {divZ} （ operatorname {first} x）（ operatorname {first} y））（ operatorname {divZ} （ operatorname {second} x）（ operatorname {second} y）））（ operatorname {plus} （ operatorname {divZ} （ operatorname {first} x）（ operatorname {second} y））（ operatorname {divZ} （ operatorname {second} x）（ operatorname {first} y）））}}

有理数と実数
有理数と計算可能な実数もラムダ計算でエンコードできます。有理数は、符号付き数値のペアとしてエンコードできます。計算可能な実数は、実数との差が必要なだけ小さくできる数だけ異なることを保証する制限プロセスによってエンコードされる場合が与えられた参考文献は、理論的にはラムダ計算に変換できるソフトウェアを説明しています。実数が定義されると、複素数は自然に実数のペアとしてエンコードされます。
上記のデータ型と関数は、任意のデータ型または計算がラムダ計算でエンコードされる可能性があることを示しています。これはチャーチチューリングの論文です。

他の表現による翻訳
ほとんどの実世界の言語は、マシンネイティブの整数をサポートしています。教会とunchurch機能は非負整数とその対応教会の数字の間の変換します。関数はここHaskellで与えられ、ラムダ計算のλに対応します。他の言語での実装も同様です。
入力教会 = （- > ）- > – > A
教会 :: 整数 -> 教会整数教会 0 = f- > x- > x教会 n = f- > x- > f （教会（n – 1 ） f x ）unchurch :: 教会整数 – > 整数unchurch CN = CN （+ 1 ） 0

教会のブール値
チャーチブール値は、ブール値trueおよびfalseのチャーチエンコードです。一部のプログラミング言語は、これらをブール演算の実装モデルとして使用します。例としては、SmalltalkやPicoが
ブール論理が選択肢と見なされる場合が真と偽のチャーチ符号化は、2つのパラメーターの関数です。
trueは最初のパラメーターを選択します。
falseは、2番目のパラメーターを選択します。
2つの定義はChurchBooleansとして知られています。true ≡ λ a λ a alse ≡ λ a λ b b { { begin {aligned} operatorname {true}＆ equiv lambdaa。 lambda ba \ operatorname {false}＆ equiv lambdaa。 lambda bb end {aligned}}}
この定義により、述語（つまり、論理値を返す関数）をif句として直接機能させることができます。ブール値を返す関数は、2つのパラメーターに適用され、最初または2番目のパラメーターを返します。p r e d I c a
te -X t h e n –
cl a u s e e l
se – c l a u s e { operatorname {predicate-} x operatorname {then-clause} operatorname {else-clause}}
predicate-xがtrueと評価された場合はthen-clauseに評価され、predicate-xがfalseと評価された場合はelse-clauseに評価されます。
trueとfalseは最初または2番目のパラメーターを選択するため、それらを組み合わせて論理演算子を提供できます。notの実装は複数ある可能性があることに注意してと = λ
p λ p q p た = λ
p λ p p q
いいえ1 = λ
p λ
a λ p b a
いいえ2 = λ p（（ λ
a λ b b ）。（（ λ
a λ b a ）。= λ p false true or = λ a λ b a （（いいえ b ）。 b もしも= λ
p λ
a λ p a b
{ { begin {aligned} operatorname {and}＆= lambdap。 lambda qp q p \ operatorname {or}＆= lambdap。 lambda qp p q \オペレーター名{not} _ {1}＆= lambdap。 lambdaa。 lambda bp b a \ operatorname {not} _ {2}＆= lambda pp （ lambdaa。 lambda bb ）（ lambdaa。 lambda ba）= lambda pp operatorname {false} operatorname {true} \ operatorname {xor}＆= lambdaa。 lambda ba （ operatorname {not} b ） b \ operatorname {if}＆= lambdap。 lambdaa。 lambda bp a b end {aligned}}}
いくつかの例：と true false =（（ λ
p λ p q p
）。true false = true false true =（（ λ
a λ b a ）。false true = false た true false = （（ λ
p λ p p q ）。（（ λ
a λ b a ）。（（ λ
a λ b b ）。 = （（ λ
a λ b a ）。（（ λ
a λ b a ）。（（ λ
a λ b b ）。 = （（ λ
a λ b a ）。= true
いいえ1 true =（（ λ
p λ
a λ p b a ）。（（ λ
a λ b a ）。= λ
a λ
b （（ λ
a λ b a ）。b a = λ
a λ
b （（ λ c b ）。a = λ
a λ b = false
いいえ2 true =（（ λ p p （（ λ
a λ b b ）。（（ λ
a λ b a ）。）。（（ λ
a λ b a ）。 = （（ λ
a λ b a ）。（（ λ
a λ b b ）。（（ λ
a λ b a ）。 = （（ λ
b （（ λ
a λ b b ）。）。（（ λ
a λ b a ）。= λ
a λ b = false
{ { begin {aligned} operatorname {and} operatorname {true} operatorname {false}＆=（ lambdap。 lambda qp q p） operatorname {true} operatorname {false } = operatorname {true} operatorname {false} operatorname {true} =（ lambdaa。 lambda ba） operatorname {false} operatorname {true} = operatorname {false} \ operatorname {または} operatorname {true} operatorname {false}＆=（ lambdap。 lambda qp p q）（ lambdaa。 lambda ba）（ lambdaa。 lambda bb）=（ lambda a 。 lambda ba）（ lambdaa。 lambda ba）（ lambdaa。 lambda bb）=（ lambdaa。 lambda ba）= operatorname {true} \ operatorname {not} _ { 1} operatorname {true}＆=（ lambdap。 lambdaa。 lambda bp b a）（ lambdaa。 lambda ba）= lambdaa。 lambda b。（ lambdaa。 lambda ba） b a = lambdaa。 lambda b。（ lambda cb） a = lambdaa。 lambda bb = operatorname {false} \ operatorname {not} _ {2} operatorname {true}＆=（ lambda pp （ lambdaa。 lambda bb）（ lambdaa。 lambda ba））（ lambdaa。 lambda ba）=（ lambdaa。 lambda ba）（ lambdaa。 lambda bb）（ lambdaa。 lambda ba）=（ lambda b。（ lambdaa。 lambda bb））（ lambdaa。 lambda ba）= lambdaa。 lambda bb = operatorname {false} end {整列}}}

述語
述語はブール値を返す関数です。最も基本的な述語は IsZero { operatorname {IsZero}}

、を返します true { operatorname {true}}

その引数がチャーチ数の場合 0 { 0}

、と false { operatorname {false}}

その引数が他のチャーチ数である場合：IsZero = λ n n（（ λX false
）。 true { operatorname {IsZero} = lambda nn （ lambdax。 operatorname {false}） operatorname {true}}
次の述語は、最初の引数が2番目の引数以下であるかどうかをテストします。LEQ = λ
m λ n IsZero （（マイナスm n ）。 { operatorname {LEQ} = lambdam。 lambdan。 operatorname {IsZero} （ operatorname {マイナス} m n）}

、
アイデンティティのために、X= y ≡（（ X≤ y ∧ y ≤X ）。 { x = y equiv（x leq y land y leq x）}
同等性のテストは、次のように実装できます。EQ = λ m λ n と（（ LEQm n ）。（（ LEQn m ）。 { operatorname {EQ} = lambdam。 lambdan。 operatorname {and} （ operatorname {LEQ} m n）（ operatorname {LEQ} n m）}

教会のペア
参照：
短所
チャーチペアは、ペア（2タプル）タイプのチャーチエンコードです。ペアは、関数の引数を取る関数として表されます。引数が与えられると、ペアの2つのコンポーネントに引数が適用されます。ラムダ計算の定義は、
ペア ≡ λ
X λ
y λ zX y め ≡ λ p p（（ λ
X λ y X ）。
2番目 ≡ λ p p （（ λ
X λ y y ）。
{ { begin {aligned} operatorname {pair}＆ equiv lambdax。 lambday。 lambda zz x y \ operatorname {first}＆ equiv lambda pp （ lambda x 。 lambda yx）\ operatorname {second}＆ equiv lambda pp （ lambdax。 lambda yy） end {aligned}}}
例えば、
初め（（ペアa b
）。 = （（ λ p p （（ λ
X λ y X ）。）。（（（（ λ
X λ
y λ zX y
）。a b
）。 = （（ λ p p （（ λ
X λ y X ）。）。（（ λ z a b
）。 = （（ λ z a b ）。（（ λ
X λ y X ）。 = （（ λ
X λ y X ）。a b = a
{ { begin {aligned}＆ operatorname {first} （ operatorname {pair} a b）\ =＆（ lambda pp （ lambdax。 lambda yx））（（ lambdax。 lambday。 lambda zz x y） a b）\ =＆（ lambda pp （ lambdax。 lambda yx））（ lambda zz a b） =＆（ lambda zz a b）（ lambdax。 lambda yx）\ =＆（ lambdax。 lambda yx） a b = a end {aligned}}}

リストエンコーディング（不変の）リストは、リストノードから構築されます。リストの基本的な操作は次のとおりです。
関数
説明 nil 空のリストを作成します。 isnil リストが空かどうかをテストします。
短所
指定された値を（おそらく空の）リストの前に追加します。頭リストの最初の要素を取得します。
しっぽ
リストの残りを取得します。
以下に、リストの4つの異なる表現を示します。
2つのペアから各リストノードを構築します（空のリストを許可するため）。
1つのペアから各リストノードを構築します。
右折り関数を使用してリストを表します。
一致式のケースを引数として取るScottのエンコーディングを使用してリストを表します

リストノードとしての2つのペア
空でないリストは、教会のペアによって実装できます。
最初に頭が含まれています。
2番目には尾が含まれています。
ただし、「null」ポインタがないため、これでは空のリストは表示されません。nullを表すために、ペアを別のペアでラップして、自由な値を与えることができます。
最初-nullポインタ（空のリスト）です。
Second.Firstには頭が含まれています。
Second.Secondにはテールが含まれています。
このアイデアを使用すると、基本的なリスト操作は次のように定義できます。
表現
説明nil ≡
ペアtrue true
{ operatorname {nil} equiv operatorname {pair} operatorname {true} operatorname {true}}
ペアの最初の要素はtrueであり、リストがnullであることを意味します。isnil ≡
初め
{ operatorname {isnil} equiv operatorname {first}}
null（または空のリスト）インジケーターを取得します。
短所≡ λ
h λ
t ペア false （（ペアh t ）。 { operatorname {cons} equiv lambdah。 lambdat。 operatorname {pair} operatorname {false} （ operatorname {pair} h t）}
nullではないリストノードを作成し、それにヘッドhとテールtを付けます。頭 ≡ λ
z 初め（（ 2番目 z ）。
{ operatorname {head} equiv lambdaz。 operatorname {first} （ operatorname {second} z）}
second.firstは頭です。
しっぽ≡ λ
z 2番目（（ 2番目 z ）。
{ operatorname {tail} equiv lambdaz。 operatorname {second} （ operatorname {second} z）}
second.secondはテールです。
ゼロノード秒という条件で、アクセスされることはない頭部と尾部が唯一の空でないリストに適用されます。

リストノードとしての1つのペア
または、を定義します
短所≡ ア
頭≡ め
しっぽ ≡ 2番目il ≡ alse snil ≡ λ l l（（ λ
h λ
t λ d false ）。 true { { begin {aligned} operatorname {cons}＆ equiv operatorname {pair} \ operatorname {head}＆ equiv operatorname {first} \ operatorname {tail}＆ equiv operatorname { 2番目の} \ operatorname {nil}＆ equiv operatorname {false} \ operatorname {isnil}＆ equiv lambda ll（ lambdah。 lambdat。 lambdad。 operatorname {false}）演算子名{true} end {aligned}}}
ここで、最後の定義は一般的な特別な場合ですp r o c e s s- l I s t
≡λ l l（（ λ
h λ
t λd h e a d – a n
d- t a I l – cl a u s
e）。n I l – c l au s e
{ operatorname {process-list} equiv lambda ll（ lambdah。 lambdat。 lambdad。 operatorname {head-and-tail-clause}） operatorname {nil-clause}}

使用してリストを表す右倍に
チャーチペアを使用したエンコードの代わりに、リストを右折り関数で識別することでエンコードできます。たとえば、3つの要素x、y、zのリストは、コンビネータcに適用され、値nがcx（cy（czn））を返す高階関数によってエンコードできます。nil ≡ λ c λ n snil ≡ λ l l（（ λ
h λ t false ）。true 所 ≡ λ h λ
t λ
c λ c h（（ tc n ）。頭 ≡ λ l l （（ λ
h λ t h ）。 false しっぽ ≡ λ
l λ
c λ n l （（ λ
h λ
t λ g h（（ t c ）。）。（（ λ t n ）。（（ λ
h λ t t ）。
{ { begin {aligned} operatorname {nil}＆ equiv lambdac。 lambda nn \ operatorname {isnil}＆ equiv lambda ll （ lambdah。 lambdat。 operatorname { false}） operatorname {true} \ operatorname {cons}＆ equiv lambdah。 lambdat。 lambdac。 lambda nc h （t c n）\ operatorname {head }＆ equiv lambda ll （ lambdah。 lambda th） operatorname {false} \ operatorname {tail}＆ equiv lambdal。 lambdac。 lambda nl （ lambdah。 lambdat。 lambda gg h （t c））（ lambda tn）（ lambdah。 lambda tt） end {aligned}}}
このリスト表現は、システムFでタイプを指定できます。

スコットエンコーディングを使用してリストを表す
別の表現はスコットエンコーディングです。これは継続の概念を使用し、より単純なコードにつながる可能性が（Mogensen–Scottエンコーディングも参照）。
このアプローチでは、パターンマッチング式を使用してリストを観察できるという事実を使用します。たとえば、Scala表記を使用して、リストが空listの型の値とコンストラクターを示す場合、リストを検査して、リストが空の場合とリストが空でない場合に計算できます。ListNilCons(h， t)nilCodeconsCode(h， t)
リスト一致 { ケース無記号=> nilCodeのケースの短所（H 、 T ） => consCode （H 、T ）}
「リスト」は、「nilCode」および「consCode」にどのように作用するかによって与えられます。したがって、リストを引数として「nilCode」や「consCode」などを受け入れる関数として定義します。これにより、上記のパターンマッチの代わりに、次のように記述できます。
リストnilCode consCode
{ operatorname {list} operatorname {nilCode} operatorname {consCode}}
‘nilCode’に対応するパラメータを ‘n’で示し、 ‘consCode’に対応するパラメータを ‘c’で示します。空のリストは、nil引数を返すリストです。nil ≡ λ
n λ c n { operatorname {nil} equiv lambdan。 lambdac。 n}
ヘッド ‘h’とテール ‘t’の空でないリストは、次の式で与えられます。
短所h t ≡ λ
n λc c h t
{ operatorname {cons} h t equiv lambdan。 lambdac。 c h t}
より一般的には、代数的データ型は m { m}

選択肢は次の関数になります m { m}

パラメーター。いつ I { i}

コンストラクターは
n I { n_ {i}}

引数、エンコーディングの対応するパラメータは
n I { n_ {i}}

引数も。
スコットエンコーディングは型なしラムダ計算で実行できますが、型で使用するには、再帰と型多型を備えた型システムが必要です。タイプCの値を計算するために使用される、この表現の要素タイプEのリストには、次の再帰型定義がここで、「=>」は関数型を示します。
type List = C =>
// nil引数（E => リスト => C ） =>
// cons引数 C
//パターンマッチングの結果
任意の型を計算するために使用できるリストには、を定量化する型がありCます。リストジェネリックにはEまた、かかるE型引数として。

も参照してください
ラムダ計算
型付きラムダ計算におけるチャーチ数のシステムF
Mogensen–Scottエンコーディング
序数のフォンノイマン定義—自然数をエンコードする別の方法：集合として

ノート
^ この式は、f-> m、x-> fのチャーチ数nの定義です。
^ アリソン、ロイド。「ラムダ計算の整数」。
^ バウアー、アンドレイ。””質問に対するAndrejの答え;””ラムダ計算を使用して負の複素数を表す”” “”。
^ 「正確な実数演算」。Haskell。
^ バウアー、アンドレイ。「実数計算ソフトウェア」。
^ ピアス、ベンジャミンC.（2002）。タイプとプログラミング言語。MITプレス。p。500. ISBN
978-0-262-16209-8。
^ Tromp、John（2007）。「14.バイナリラムダ計算とコンビネータ論理」。Caludeでは、Cristian S（ed。）ランダム性と複雑さ、ライプニッツからチャイティンまで。世界科学。pp。237–262。ISBN
978-981-4474-39-9。PDFとして：
Tromp、John
「バイナリラムダ計算とコンビネータ論理」（PDF）。
^ Jansen、Jan Martin（2013）。「ラムダ計算でのプログラミング：教会からスコットへ、そしてその逆へ」。LNCS。8106：168–180。土井：10.1007 / 978-3-642-40355-2_12。

参考文献
直接反射メタプログラミング
ライス大学のRobertCartwrightが説明したチャーチ数とブール値
実用的な「完全関数型プログラミング」の理論的基礎（第2章および第5章）第一原理からのそれらの導出方法およびそれらの操作を含む、教会および他の同様のエンコーディングに関するすべて
チャーチ数のいくつかのインタラクティブな例
ラムダ計算ライブチュートリアル：ブール代数

Church_encoding&oldid=1060487318″