教会のエンコーディング – 日本語百科事典辞書

Church_encoding
数学では、チャーチエンコーディングはラムダ計算でデータと演算子を表す手段です。チャーチ数字は、ラムダ表記を使用した自然数の表現です。このメソッドは、この方法でラムダ計算でデータを最初にエンコードしたAlonzo Churchにちなんで名付けられました。
通常、他の表記法 (整数、ブール値、ペア、リスト、タグ付き共用体など) で原始的と見なされる用語は、Church エンコーディングの下で高階関数にマップされます。Church-Turing 論文では、計算可能な演算子 (およびそのオペランド) はすべて Church エンコーディングで表現できると主張しています。型指定されていないラムダ計算では、唯一のプリミティブデータ型は関数です。

コンテンツ
1 使用する
2 教会の数字
2.1 教会数字による計算 2.2 チャーチ数字の機能表 2.3 先行機能の導出
2.3.1 値のコンテナー
2.3.2 株式会社
2.3.3 エキス
2.3.4 定数
2.3.5 pred を定義する別の方法
2.4 分割 2.5 署名された番号 2.6 プラスとマイナス 2.7 掛け算と割り算 2.8 有理数と実数 2.9 他の表現による翻訳
3 チャーチブーリアン5 チャーチペア
6 エンコーディングの一覧表示
6.1 リストノードとしての 2 つのペア 6.2 リストノードとしての 1 つのペア 6.3 右折を使ってリストを表現する 6.4 Scott エンコーディングを使用してリストを表現する
7 こちらもご覧ください
8 ノート
9 参考文献

使用する
Church エンコーディングを直接実装すると、一部のアクセス操作が遅くなります。〇 ( 1 ) { O(1)}
$O(1)""$ 〇( n ) { O(n)}

、どこ n { n}

はデータ構造のサイズであり、Church エンコーディングは実用的ではありません。調査によると、これは的を絞った最適化によって対処できることが示されていますが、ほとんどの関数型プログラミング言語は代数データ型を含むように中間表現を拡張しています。それにもかかわらず、部分的な評価と定理証明の自然な表現であるため、教会の符号化は理論的な議論でよく使用されます。演算は上位の型を使用して型付けでき、およびプリミティブ再帰に簡単にアクセスできます。関数が唯一の基本データ型であるという仮定は、多くの証明を合理化します。
教会のエンコーディングは完全ですが、表現のみです。表現を一般的なデータ型に変換して人々に表示するには、追加の関数が必要です。チャーチの定理による等価性の決定不能性により、2 つの関数が拡張的に等しいかどうかを決定することは一般に不可能です。翻訳は、何らかの方法で関数を適用して、それが表す値を取得したり、その値を文字通りのラムダ項として検索したりできます。ラムダ計算は通常、内包的等価性を使用していると解釈されます。平等の内的定義と外的定義の違いにより、結果の解釈に問題が生じる可能性が

教会の数字
チャーチ数字は、チャーチ符号化の下での自然数の表現です。自然数nを表す高階関数は任意の関数を写像する関数へ { f}

そのn倍の構成に。簡単に言えば、数値の「値」は、関数がその引数をカプセル化する回数に相当します。へ ∘ n = へ ∘ へ
∘ ⏟ n 回 .
{ f^{circ n}=underbrace {fcirc fcirc cdots circ f} _{n{text{ 回}}}.，}

すべての教会数字は、2 つのパラメーターを取る関数です。チャーチ数 0、1、2 、 … は、ラムダ計算で次のように定義されます。
関数をまったく適用しない0 から始めて、1関数を1回適用する、 2関数を 2 回適用する、3関数を 3 回適用する、などのように進みます。
番号
関数定義
ラムダ式0 0へX =X 0 = λ
へ. λ X .X 1へX = へX 1 = λ へ. λ
X . へX 2へX = へ( へX) 2 = λへ. λ X. へ( へX
) 3へX = へ( へ( へX) ) 3 = λへ. λ X. へ ( へ( へX) )
⋮⋮ ⋮ n n へX=へ nX n = λ
へ. λ
X. へ ∘ nX
{ {begin{array}{r|l|l}{text{数値}}&{text{関数定義}}&{text{ラムダ式}}\hline 0&0 f x =x&0=lambda f.lambda xx\1&1 f x=f x&1=lambda f.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=lambda f.lambda xf (f (f x)) \vdots &vdots &vdots \n&n f x=f^{n} x&n=lambda f.lambda xf^{circ n} xend{配列}}}

チャーチ数字の3は、任意の関数を値に 3 回適用する動作を表します。提供された関数は、最初に提供されたパラメーターに適用され、次にそれ自体の結果に適用されます。最終結果は数字の 3 ではありません (指定されたパラメーターがたまたま 0 で、関数が後続関数である場合を除きます)。関数自体は、その最終結果ではなく、教会の数字3です。教会の数字の3は、単純に、何事も 3 回行うことを意味します。これは、「3 回」が何を意味するかを表向きに示したものです。

教会数字による計算
数の算術演算は、チャーチ数字の関数で表すことができます。これらの関数は、ラムダ計算で定義するか、ほとんどの関数型プログラミング言語で実装できます (ラムダ式を関数に変換するを参照してください)。
加算機能
プラス( メートル n) =
メートル+ n
{ operatorname {plus} (m，n)=m+n}

ID を使用するへ ∘( メートル+ n ) X )= へ ∘
メートル( へ ∘ nX ) )
{ f^{circ (m+n)}(x)=f^{circ m}(f^{circ n}(x))}
. プラス≡ λ
メートル. λ n . λへ . λX .
メートルへ ( nへX )
{ operatorname {plus} equiv lambda m.lambda n.lambda f.lambda xm f (n f x)}

後継機能継 n ) = n+ 1
{ operatorname {成功} (n)=n+1}

はβ に等しい( プラス 1 ) { (operatorname {プラス} 1)}
. 継 ≡ λ n
.λ へ . λX . へ ( nへX )
{ operatorname {succ} equiv lambda n.lambda f.lambda xf (n f x)}

乗算関数
マルチ( メートル n) =
メートル∗ n
{ operatorname {mult} (m，n)=m*n}

ID を使用するへ ∘( メートル ∗ n) X ) =( へ ∘ n) ∘
メートルX )
{ f^{circ (m*n)}(x)=(f^{circ n})^{circ m}(x)}
. マルチ≡ λ
メートル. λ n . λへ . λX .
メートル( nへ )X
{ operatorname {mult} equiv lambda m.lambda n.lambda f.lambda xm (n f) x}

累乗関数
指数( メートル n) =
メートル n { operatorname {exp} (m，n)=m^{n}}

教会数の定義によって与えられ、 n 時間X = 時間n X
{ n h x=h^{n} x}

. 定義置換で
時間
メートル X へ { hto m，xto f}

取得するため n メートルへ =
メートル n へ { n m f=m^{n} f}
と、指数
メートルn =
メートルn = n
メートル
{ operatorname {exp} m n=m^{n}=n m}

ラムダ式を与える、
指数≡ λ
メートル. λ n . n
メートル
{ operatorname {exp} equiv lambda m.lambda nn m}
捕食 n )
{ operatorname {pred} (n)}

機能がわかりにくい。
捕食≡ λ n . λへ . λX . n ( λg . λ
時間 . 時間( gへ ) )( λ
あなた.X )( λ
あなた . あなた ) { operatorname {pred} equiv lambda n.lambda f.lambda xn (lambda g.lambda hh (g f)) (lambda ux) (lambda uu)}

チャーチ数字は関数をn回適用します。先行関数は、そのパラメーターをn – 1回適用する関数を返す必要がこれは、最初の関数の適用を省略する方法で初期化されるfとxの周りにコンテナーを構築することによって実現されます。詳細な説明については、前任者を参照して
減算関数は、先行関数に基づいて記述できます。
マイナス≡ λ
メートル. λ n . ( n 捕食 ) メートル
{ operatorname {minus} equiv lambda m.lambda n.(noperatorname {pred} ) m}

チャーチ数字の機能表関数代数身元
関数定義
ラムダ式
後継n + 1
{ n+1}
へ n + 1 X= へ(へ n X ) { f^{n+1} x=f(f^{n}x)}
継 n へX = へ( nへX )
{ operatorname {成功} n f x=f (n f x)}
λ n . λ へ. λX . へ( nへX )
{ lambda n.lambda f.lambda xf (n f x)}
.. 添加
メートル+ n
{ m+n}
へメートル+ n X = へメートルへ n
X ) { f^{m+n} x=f^{m}(f^{n}x)}

プラス
メートルn へX =
メートルへ ( nへX )
{ operatorname {plus} m n f x=m f (n f x)}
λ メートル. λ n . λへ . λX .
メートルへ ( nへX )
{ lambda m.lambda n.lambda f.lambda xm f (n f x)}
λ メートル. λ n . n
後継
メートル
{ lambda m.lambda nnoperatorname {成功} m}

乗算
メートル∗ n
{ m*n}
へメートル ∗ nX = (へメートル) n X
{ f^{m*n} x=(f^{m})^{n} x}

かける
メートルn へX =
メートル( nへ )X
{ operatorname {multiply} m n f x=m (n f) x}
λ メートル. λ n . λへ . λX .
メートル( nへ )X
{ lambda m.lambda n.lambda f.lambda xm (n f) x}
λ メートル. λ n . λへ .
メートル( nへ )
{ lambda m.lambda n.lambda fm (n f)}

累乗
メートル n { m^{n}}
n メートルへ =
メートル n へ { n m f=m^{n} f}

指数
メートルn へX = ( n メートル) へX
{ operatorname {exp} m n f x=(n m) f x}
λ メートル. λ n . λへ . λX . ( n メートル) へX
{ lambda m.lambda n.lambda f.lambda x.(n m) f x}
λ メートル. λ n . n
メートル
{ lambda m.lambda nn m}

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

株式会社 n 詐欺= 値(へ n − ) { operatorname {inc} ^{n}operatorname {con} =operatorname {val} (f^{n-1}x)}
I へ ( n ==0 ) 0 e ls e( n− 1 )
{ if(n==0) 0 else (n-1)}
λ n . λ へ. λX . n( λg . λ
時間 . 時間( gへ ) )( λ
あなた.X )( λ
あなた . あなた ) { lambda n.lambda f.lambda xn (lambda g.lambda hh (g f)) (lambda ux) (lambda uu)}

減算*
メートル− n
{ mn}
へメートル − nX =(へ − 1) n へ
メートル
X ) { f^{mn} x=(f^{-1})^{n}(f^{m}x)}

マイナス
メートルn = ( n 捕食 ) メートル
{ operatorname {マイナス} m n=(noperatorname {pred} ) m}

… λ メートル. λ n . n
捕食
メートル
{ lambda m.lambda nnoperatorname {pred} m}

* 教会のエンコーディングでは、
捕食( 0) = 0
{ operatorname {pred} (0)=0}

メートル
<= n メートル− n = 0
{ m<=nto mn=0}

先行機能の導出
Church エンコーディングで使用される先行関数は、次のとおりです。
捕食( 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を使用して、関数をn -1回適用する必要が
先行関数を実装する前に、コンテナー関数で値をラップするスキームを次に示します。incおよびinitと呼ばれる、 fおよびxの代わりに使用する新しい関数を定義します。コンテナ関数はvalueと呼ばれます。表の左側は、incおよびinitに適用される数値nを示しています。
番号
初期化の使用
const の使用 0 初期化 = 価値X 1 株式会社
初期化 = 価値( へX ) 株式会社
定数 = 価値X 2 株式会社( 株式会社
初期化) =
価値( へ( へX) )
株式会社( 株式会社
定数) =
価値( へX ) 3
株式会社( 株式会社( 株式会社
初期化) ) =
価値 ( へ ( へ( へX) ) )
株式会社( 株式会社( 株式会社
定数) ) =
価値( へ( へX) )
⋮⋮ ⋮ n n
株式会社
初期化 = 価値( へnX ) =
価値( nへX ) n
株式会社
定数 = 価値( へn − 1X ) =
価値( ( n − 1) へX )
{ {begin{array}{r|r|r}{text{Number}}&{text{init の使用}}&{text{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&noperatorname {inc} operatorname {init} =operatorname {value} (f^{n} x)=operatorname {value} (n f x)&noperatorname {inc} operatorname {const} =operatorname {value} (f^{n-1} x)=o peratorname {値} ((n-1) f x)\end{array}}}

一般的な再帰規則は、
株式会社( 価値v ) =
価値( へv )
{ operatorname {inc} (operatorname {value} v)=operatorname {value} (f v)}
コンテナーから値を取得する関数 ( extractと呼ばれる) もある場合、
エキス( 価値v ) = v
{ operatorname {抽出} (operatorname {値} v)=v}
次に、extractを使用して、samenum関数を次のように定義できます。
同数= λ n . λへ . λX .
エキス ( n 株式会社
初期化) = λ n .λ へ . λX . エキス( 価値( nへX ) ) = λ
n. λ へ . λX
.n へX = λ n. n
{ operatorname {samenum} =lambda n.lambda f.lambda x.operatorname {extract} (noperatorname {inc} operatorname {init} )=lambda n.lambda f. lambda x.operatorname {抽出} (operatorname {値} (n f x))=lambda n.lambda f.lambda xn f x=lambda nn}
samenum関数は本質的に有用ではありません。ただし、incはfの呼び出しをそのコンテナー引数に委任するため、最初のアプリケーションでincがその引数を無視する特別なコンテナーを受け取り、fの最初のアプリケーションをスキップできるようにすることができます。この新しい初期コンテナーをconstと呼びます。上の表の右側は、n inc constの展開を示しています。次に、同じ関数の式でinitをconstに置き換えると、先行関数が得られます。
捕食= λ n . λへ . λX .
エキス ( n 株式会社
定数) = λ n .λ へ . λX . エキス( 価値( ( n− 1 ) へX )
)= λ n . λへ . λX .( n− 1 ) へX =λ n .( n− 1 )
{ operatorname {pred} =lambda n.lambda f.lambda x.operatorname {extract} (noperatorname {inc} operatorname {const} )=lambda n.lambda f. lambda x.operatorname {extract} (operatorname {value} ((n-1) f x))=lambda n.lambda f.lambda x.(n-1) f x =lambda n.(n-1)}
以下で説明するように、関数inc、init、const、value、およびextractは次のように定義できます。
価値= λ
v . ( λ間 .
時間v )
エキスk = k λ
あなた . あなた
株式会社= λ
g. λ 間 .
時間( gへ )
初期化= λ 間 .
時間X数 = λ
あなた .X { {begin{aligned}operatorname {value} &=lambda v.(lambda hh v)\operatorname {extract} k&=k lambda uu\operatorname {inc} &= lambda g.lambda hh (g f)\operatorname {init} &=lambda hh x\operatorname {const} &=lambda uxend{aligned}}}
predのラムダ式は次のようになります。
捕食= λ n . λへ . λX . n ( λg . λ
時間 . 時間( gへ ) )( λ
あなた.X )( λ
あなた . あなた ) { operatorname {pred} =lambda n.lambda f.lambda xn (lambda g.lambda hh (g f)) (lambda ux) (lambda uu)}
値のコンテナー編集値コンテナーは、関数をその値に適用します。によって定義されます。
価値 v 時間 = 時間 v { operatorname {値} v h=h v}

それで、
価値= λ
v . ( λ間 .
時間v )
{ operatorname {value} =lambda v.(lambda hh v)}

株式会社編集 inc関数は v を含む値を取り、fvを含む新しい値を返す必要が
株式会社( 価値v ) =
価値( へv )
{ operatorname {inc} (operatorname {value} v)=operatorname {value} (f v)}

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

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

それで、
株式会社g =
価値( gへ )
{ operatorname {inc} g=operatorname {value} (g f)}

株式会社= λ
g. λ 間 .
時間( gへ )
{ operatorname {inc} =lambda g.lambda hh (g f)}

エキス編集値は恒等関数を適用することで抽出できます。I = λ
あなた . あなた
{ I=lambda uu}

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

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

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

λ間 .
時間( 定数へ ) = λ 間 . 時間X
{ lambda hh (operatorname {const} f)=lambda hh x}

次の場合、これは満足されます。
定数へ =X
{ operatorname {const} f=x}

またはラムダ式として、
定数= λ
あなた .X { operatorname {const} =lambda ux}

pred を定義する別の方法
Pred は、ペアを使用して定義することもできます。へ = λ
p . ペア( 2番目p )(後継( 2番目p ) ) ロ = ( λ へ. λ
X.X ) c0 = ペアゼロ
ゼロ食 = λ
n . 最初( nへ pc0 )
{ {begin{aligned}operatorname {f} =& lambda p. operatorname {pair} (operatorname {second} p) (operatorname {succ} (operatorname {second } p))\operatorname {zero} =& (lambda f.lambda x. x)\operatorname {pc0} =& operatorname {pair} operatorname {zero} operatorname {zero} \operatorname {pred} =& lambda n. operatorname {first} (n operatorname {f} operatorname {pc0} )\end{aligned}}}
これはより単純な定義ですが、pred のより複雑な式になります。の展開
捕食三 { operatorname {pred} operatorname {three} }

:
捕食三 =
最初 ( へ ( へ ( へ( ペア
ゼロ
ゼロ) ) ) ) = 最初 ( へ ( へ( ペア
ゼロ1 ) ) ) = 最初( へ( ペア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 { pair} 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 /
メートル = もしもn ≥
メートル
それから1 +( n − メートル) /
メートル
そうしないと 0 { n/m=operatorname {if} ngeq m operatorname {then} 1+(nm)/m operatorname {else} 0}
計算中n −
メートル
{ nm}

多くのベータ削減が必要です。手で計算をしない限り、これはそれほど問題ではありませんが、この計算を 2 回行う必要はありません。数値をテストするための最も単純な述語はIsZeroであるため、条件を考慮して
イズゼロ( マイナス n メートル ) { operatorname {IsZero} (operatorname {minus} n m)}
しかし、この条件はn ≤
メートル
{ nleq m}

、いいえn <
メートル
{ n
. この式が使用される場合、上記の除算の数学的な定義は、次のように教会の数字の関数に変換されます。
除算1 n メートルへX =( λd .
イズゼロ d ( 0へX )( へ( 除算1 d メートルへX ) ) )( マイナス n メートル ) { operatorname {divide1} n m f x=(lambda d.operatorname {IsZero} d (0 f x) (f (operatorname {divide1} d m f x))) (operatorname {マイナス} n m)}
この定義には単一の呼び出しがあります
マイナス
n メートル
{ operatorname {マイナス} n m}

. ただし、結果は、この式が次の値を与えることです。( n− 1 ) /
メートル
{ (n-1)/m}

.
この問題は、除算を呼び出す前にnに1 を追加することによって修正される場合が分割の定義は、
分けるn =
除算1(後継n )
{ operatorname {divide} n=operatorname {divide1} (operatorname {succ} n)}
分割 1は再帰的な定義です。Y コンビネータを使用して、再帰を実装できます。div by;という新しい関数を作成します。左手側除算1
分周 c { operatorname {divide1} rightarrow operatorname {div} c}
右側に
除算1 c { operatorname {divide1} rightarrow c}
取得するため、
分周= λ c . λn . λ
メートル. λ へ . λX . ( λd .
イズゼロ d ( 0へX )( へ( c d メートルへX ) ) )( マイナス n メートル ) { operatorname {div} =lambda c.lambda n.lambda m.lambda f.lambda x.(lambda d.operatorname {IsZero} d (0 f x) (f (c d m f x))) (operatorname {マイナス} n m)}
それで、
分ける= λ n .
除算1(後継n )
{ operatorname {divide} =lambda n.operatorname {divide1} (operatorname {succ} n)}
どこ、
除算1= よ
分周継 = λn. λ へ. λ X. へ( nへX )
よ= λ
へ . ( λ
X. へ (XX ) )( λ
X. へ (XX ) )0= λ へ. λ
X .X イズゼロ= λ . n ( λ
X . 間違い ) 真実
{ {begin{aligned}operatorname {divide1} &=Y operatorname {div} \operatorname {succ} &=lambda n.lambda f.lambda xf (n f x )\Y&=lambda f.(lambda xf (x x)) (lambda xf (x x))\0&=lambda f.lambda xx\operatorname {IsZero} &=lambda nn (lambda x.operatorname {false} ) operatorname {true} end{aligned}}}
真実
≡λ a . λ b. a
間違い
≡λ a . λ b. b
{ {begin{aligned}operatorname {true} &equiv lambda a.lambda ba\operatorname {false} &equiv lambda a.lambda bbend{aligned}}}

マイナス= λ
メートル. λ . n 捕食
メートル食 = λ
n. λ
へ. λ . n ( λ
g. λ 間 .
時間( gへ ) )( λ
あなた.X )( λ
あなた . あなた ) { {begin{aligned}operatorname {minus} &=lambda m.lambda nnoperatorname {pred} m\operatorname {pred} &=lambda n.lambda f.lambda xn (lambda g.lambda hh (g f)) (lambda ux) (lambda uu)end{aligned}}}
与える、
分ける= λ
n . ( ( λ
へ . ( λ
X.XX )( λ
X. へ (XX ) ) ) ( λc. λ n. λ
メートル. λ
へ. λ
X . ( λ
d . ( λ . n ( λ
X . ( λ
a. λ
b. b ) ) ( λ a. λ
b. a ) ) d( ( λ
へ. λ
X.X ) へX )( へ( c d メートルへX ) ) )( ( λ
メートル. λ . n ( λ
n. λ
へ. λ . n ( λ
g. λ 間 .
時間( gへ ) )( λ
あなた.X )( λ
あなた . あなた) )
メートル) n
メートル) ) )( ( λn. λ へ. λ X. へ( nへX ) ) n )
{ scriptstyle operatorname {divide} =lambda n.((lambda f.(lambda xx x) (lambda xf (x x))) (lambda c.lambda n .lambda m.lambda f.lambda x.(lambda d.(lambda nn (lambda x.(lambda a.lambda bb)) (lambda a.lambda ba)) d ((lambda f.lambda xx) f x) (f (c d m f x)) ((lambda m.lambda nn(lambda n. lambda f.lambda xn (lambda g.lambda hh (g f)) (lambda ux) (lambda uu))m) n m))) ((lambda n .lambda f.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)))

署名された番号
Church Numerals を符号付きの数値に拡張する簡単な方法の 1 つは、正の値と負の値を表す Church 数字を含む Church ペアを使用することです。整数値は、2 つの教会数字の差です。
自然数は、次のように符号付き数に変換されます。
変換s = λX .
ペアX 0 { operatorname {convert} _{s}=lambda x.operatorname {pair} x 0}
否定は、値を交換することによって実行されます。
否定s = λX .
ペア( 2番目X ) ( 最初X ) { operatorname {neg} _{s}=lambda x.operatorname {pair} (operatorname {second} x) (operatorname {first} x)}
ペアの一方がゼロの場合、整数値はより自然に表現されます。OneZero関数はこの条件を達成し、
ワンゼロ= λX .
イズゼロ( 最初X )X ( イズゼロ( 2番目X )X ( ワンゼロ
ペア( 捕食( 最初X) )( 捕食( 2番目X) ) ) )
{ operatorname {OneZero} =lambda x.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 コンビネータを使用して実装できます。
ワンズ= λ c . λX . イズゼロ( 最初X )X ( イズゼロ( 2番目X )X ( c
ペア( 捕食( 最初X) )( 捕食( 2番目X) ) ) )
{ operatorname {OneZ} =lambda c.lambda x.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)))) }
ワンゼロ= よ
ワンズ
{ operatorname {OneZero} =Yoperatorname {OneZ} }

プラスとマイナス
加算は、ペアで数学的に定義されます。X+ y = [X p Xn ] +
[ yp y n ] =X p
−Xn + y p −
yn = (X p +
yp ) − (X n+y n ) = [X
p+ y p X n +y n ]
{ x+y=+=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 .
ワンゼロ( ペア( プラス( 最初X ) ( 最初y ) )( プラス( 2番目X ) ( 2番目y ) ) )
{ operatorname {plus} _{s}=lambda x.lambda y.operatorname {OneZero} (operatorname {pair} (operatorname {plus} (operatorname {first} x) (operatorname {first} y)) (operatorname {plus} (operatorname {second} x) (operatorname {second} y)))}
同様に減算が定義され、X− y = [X p Xn ] −
[ yp y n ] =X p
−Xn − y p +
yn = (X p +
yn ) − (X n+y p ) = [X
p+ y n X n +y p ]
{ xy=-=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 .
ワンゼロ( ペア( プラス( 最初X ) ( 2番目y ) )( プラス( 2番目X ) ( 最初y ) ) )
{ operatorname {minus} _{s}=lambda x.lambda y.operatorname {OneZero} (operatorname {pair} (operatorname {plus} (operatorname {first} x) (operatorname {second} y)) (operatorname {plus} (operatorname {second} x) (operatorname {first} y)))}

掛け算と割り算
乗算は次のように定義できます。X∗ y = [X p Xn ] ∗
[ yp y n ] = (Xp −X n ) ∗ ( yp − y n )=(X p ∗ y p+Xn ∗ y n )
−(X p ∗ y n+Xn ∗ y p )=[X p ∗ y p+Xn ∗ y n X p
∗y n +X n ∗y p ]
{ x*y=*=(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}=lambda x.lambda y.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 .
イズゼロy 0( 分けるXy )
{ operatorname {divZ} =lambda x.lambda y.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}=lambda x.lambda y.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)))}

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

他の表現による翻訳
ほとんどの実世界の言語は、機械固有の整数をサポートしています。Church関数とunchurch関数は、非負の整数とそれに対応する Church 数字との間で変換を行います。関数はここではHaskellで与えられます。ここで、はラムダ計算の λ に対応します。他の言語での実装も同様です。
タイプ Church a = ( a -> a ) -> a -> a教会 :: 整数 -> 教会整数教会 0 = f -> x -> x教会 n = f -> x -> f (教会 ( n – 1 ) f x )unchurch :: Church Integer -> Integer unchurch cn = cn ( + 1 ) 0

チャーチブーリアン
Church Booleansは、Boolean 値trueおよびfalse の Church エンコーディングです。一部のプログラミング言語では、これらをブール演算の実装モデルとして使用しています。例はSmalltalkとPicoです。
ブール論理は、選択肢と見なすことができます。trueとfalseの Church エンコーディングは、次の 2 つのパラメーターの関数です。
trueは最初のパラメーターを選択します。
falseは 2 番目のパラメーターを選択します。
2 つの定義は Church Booleans として知られています。
真実
≡ . λ . a 間違い
≡ . λ . b { {begin{aligned}operatorname {true} &equiv lambda a.lambda ba\operatorname {false} &equiv lambda a.lambda bbend{aligned}}}
この定義により、述語 (つまり、論理値を返す関数) が if 句として直接機能することができます。2 つのパラメーターに適用されるブール値を返す関数は、最初または 2 番目のパラメーターのいずれかを返します。p r e d I
ca t e -X t
時間e n – c l a あなたs e e l se – c l a あなた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. λ
q. p q p た= λ
p. λ
q. p p q
いいえ1 = λp. λ a. λ
b. p b a
いいえ2 = λ . p ( λ
a. λ
b. b ) ( λ a. λ
b. a ) = λ . p 間違い
真実or = λ
a. λ . a ( いいえb ) b
もしも= λp. λ a. λ
b. p a b
{ {begin{aligned}operatorname {and} &=lambda p.lambda qp q p\operatorname {or} &=lambda p.lambda qp p q\ operatorname {not} _{1}&=lambda p.lambda a.lambda bp b a\operatorname {not} _{2}&=lambda pp (lambda a.lambda bb ) (lambda a.lambda ba)=lambda ppoperatorname {false} operatorname {true} \operatorname {xor} &=lambda a.lambda ba (operatorname {not} b ) b\operatorname {if} &=lambda p.lambda a.lambda bp a bend{aligned}}}
いくつかの例：と真実
間違い = ( λ
p. λ
q. p q p )
真実
間違い = 真実
間違い
真実 = ( λ
a. λ
b. a )
間違い
真実 = 間違い
また
真実
間違い = ( λ
p. λ
q. p p q ) ( λ a. λ
b. a ) ( λ a. λ
b. b ) = ( λ a. λ
b. a ) ( λ a. λ
b. a ) ( λ a. λ
b. b ) = ( λ a. λ
b. a ) =
真実
いいえ 1 真実 = ( λp. λ a. λ
b. p b a ) ( λ a. λ
b. a ) = λ
a. λ
b . ( λ
a. λ
b. a ) b a= λ
a. λ
b . ( λ
c. b ) a = λ a. λ
b. b =
間違い
いいえ 2 真実 = ( λ . 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. b = false
{ {begin{aligned}operatorname {and} operatorname {true} operatorname {false} &=(lambda p.lambda q.p q p) operatorname {true} operatorname {false} =operatorname {true} operatorname {false} operatorname {true} =(lambda a.lambda b.a)operatorname {false} operatorname {true} =operatorname {false} \operatorname {or} operatorname {true} operatorname {false} &=(lambda p.lambda q.p p q) (lambda a.lambda b.a) (lambda a.lambda b.b)=(lambda a.lambda b.a) (lambda a.lambda b.a) (lambda a.lambda b.b)=(lambda a.lambda b.a)=operatorname {true} \operatorname {not} _{1} operatorname {true} &=(lambda p.lambda a.lambda b.p b a)(lambda a.lambda b.a)=lambda a.lambda b.(lambda a.lambda b.a) b a=lambda a.lambda b.(lambda c.b) a=lambda a.lambda b.b=operatorname {false} \operatorname {not} _{2} operatorname {true} &=(lambda p.p (lambda a.lambda b.b)(lambda a.lambda b.a))(lambda a.lambda b.a)=(lambda a.lambda b.a)(lambda a.lambda b.b)(lambda a.lambda b.a)=(lambda b.(lambda a.lambda b.b)) (lambda a.lambda b.a)=lambda a.lambda b.b=operatorname {false} end{aligned}}}

述語
A predicate is a function that returns a Boolean value. The most fundamental predicate is IsZero { operatorname {IsZero} }

， which returns true { operatorname {true} }

if its argument is the Church numeral 0 { 0}

， and false { operatorname {false} }

if its argument is any other Church numeral:IsZero = λ n . n ( λx . false ) true
{ operatorname {IsZero} =lambda n.n (lambda x.operatorname {false} ) operatorname {true} }
The following predicate tests whether the first argument is less-than-or-equal-to the second:LEQ = λ m .λ n . IsZero( minusm n )
{ operatorname {LEQ} =lambda m.lambda n.operatorname {IsZero} (operatorname {minus} m n)}

，
Because of the identity，x = y ≡( x≤ y ∧ y ≤x )
{ x=yequiv (xleq yland yleq x)}
The test for equality may be implemented as，EQ = λ m .λ n . and( LEQm n )( LEQn m )
{ operatorname {EQ} =lambda m.lambda n.operatorname {and} (operatorname {LEQ} m n) (operatorname {LEQ} n m)}

チャーチペア
See also: Cons Church pairs are the Church encoding of the pair (two-tuple) type. The pair is represented as a function that takes a function argument. When given its argument it will apply the argument to the two components of the pair. The definition in lambda calculus is， pair ≡ . λ
y. λ
z. z x y irst
≡ . p ( λ x. λ
y. x ) econd
≡ . p ( λ x. λ
y. y )
{ {begin{aligned}operatorname {pair} &equiv lambda x.lambda y.lambda z.z x y\operatorname {first} &equiv lambda p.p (lambda x.lambda y.x)\operatorname {second} &equiv lambda p.p (lambda x.lambda y.y)end{aligned}}}
For example， first ( paira b ) = ( λ . p ( λ
x. λ
y. x ) )( ( λx. λ y. λ
z. z x y )a b ) = ( λ . p ( λ
x. λ
y. x ) )( λ
z. z a b ) = ( λ
z. z a b ) ( λ x. λ
y. x ) = ( λ
x. λ
y. x ) a b= a
{ {begin{aligned}&operatorname {first} (operatorname {pair} a b)\=&(lambda p.p (lambda x.lambda y.x)) ((lambda x.lambda y.lambda z.z x y) a b)\=&(lambda p.p (lambda x.lambda y.x)) (lambda z.z a b)\=&(lambda z.z a b) (lambda x.lambda y.x)\=&(lambda x.lambda y.x) a b=aend{aligned}}}

エンコーディングの一覧表示
An (immutable) list is constructed from list nodes. The basic operations on the list are;Function Description nil
Construct an empty list. isnil Test if list is empty. cons Prepend a given value to a (possibly empty) list. head Get the first element of the list. tail Get the rest of the list.
We give four different representations of lists below:
Build each list node from two pairs (to allow for empty lists).
Build each list node from one pair.
Represent the list using the right fold function.
Represent the list using Scott’s encoding that takes cases of match expression as arguments
Two pairs as a list nodeEdit
A nonempty list can be implemented by a Church pair;
First contains the head.
Second contains the tail.
However this does not give a representation of the empty list， because there is no “”null”” pointer. To represent null， the pair may be wrapped in another pair， giving free values，
First – Is the null pointer (empty list).
Second.First contains the head.
Second.Second contains the tail.
Using this idea the basic list operations can be defined like this:Expression Description nil ≡ pairtrue true
{ operatorname {nil} equiv operatorname {pair} operatorname {true} operatorname {true} }
The first element of the pair is true meaning the list is null.isnil ≡ first
{ operatorname {isnil} equiv operatorname {first} }
Retrieve the null (or empty list) indicator.cons ≡ λ h .λ t . pair false ( pairh t )
{ operatorname {cons} equiv lambda h.lambda t.operatorname {pair} operatorname {false} (operatorname {pair} h t)}
Create a list node， which is not null， and give it a head h and a tail t.head ≡ λ z . first ( secondz )
{ operatorname {head} equiv lambda z.operatorname {first} (operatorname {second} z)}
second.first is the head.tail ≡ λ z . second ( secondz )
{ operatorname {tail} equiv lambda z.operatorname {second} (operatorname {second} z)}
second.second is the tail.
In a nil node second is never accessed， provided that head and tail are only applied to nonempty lists.
One pair as a list nodeEdit
Alternatively， definecons ≡ air ead ≡
firstail ≡ econd il ≡alse snil
≡ . l ( λ h. λ t. λ
d. false ) true
{ {begin{aligned}operatorname {cons} &equiv operatorname {pair} \operatorname {head} &equiv operatorname {first} \operatorname {tail} &equiv operatorname {second} \operatorname {nil} &equiv operatorname {false} \operatorname {isnil} &equiv lambda l.l(lambda h.lambda t.lambda d.operatorname {false} )operatorname {true} end{aligned}}}
where the last definition is a special case of the generalp r o c e
ss – l i s t ≡λ l . l( λh . λ t .
λd . h e a
d- a n d –
ta i l – c
la u s e) n
il – c l au s e
{ operatorname {process-list} equiv lambda l.l(lambda h.lambda t.lambda d.operatorname {head-and-tail-clause} )operatorname {nil-clause} }
Represent the list using right foldEdit
As an alternative to the encoding using Church pairs， a list can be encoded by identifying it with its right fold function. For example， a list of three elements x， y and z can be encoded by a higher-order function that when applied to a combinator c and a value n returns c x (c y (c z n)). nil ≡ . λ
n. n snil
≡ . l ( λ h. λ
t. false ) true ons
≡ . λt. λ c. λ
n. c h( tc n ) ead
≡ . l ( λ h. λ
t. h ) false ail
≡ . λ
c. λ . l ( λh. λ t. λ
g. g h( tc ) )( λ
t. n ) ( λ h. λ
t. t )
{ {begin{aligned}operatorname {nil} &equiv lambda c.lambda n.n\operatorname {isnil} &equiv lambda l.l (lambda h.lambda t.operatorname {false} ) operatorname {true} \operatorname {cons} &equiv lambda h.lambda t.lambda c.lambda n.c h (t c n)\operatorname {head} &equiv lambda l.l (lambda h.lambda t.h) operatorname {false} \operatorname {tail} &equiv lambda l.lambda c.lambda n.l (lambda h.lambda t.lambda g.g h (t c)) (lambda t.n) (lambda h.lambda t.t)end{aligned}}}
This list representation can be given type in System F.
Represent the list using Scott encodingEdit
An alternative representation is Scott encoding， which uses the idea of continuations and can lead to simpler code. (see also Mogensen–Scott encoding).
In this approach， we use the fact that lists can be observed using pattern matching expression. For example， using Scala notation， if list denotes a value of type List with empty list Nil and constructor Cons(h， t) we can inspect the list and compute nilCode in case the list is empty and consCode(h， t) when the list is not empty:
list match { case Nil=> nilCode case Cons(h， t) => consCode(h，t)}
The ‘list’ is given by how it acts upon ‘nilCode’ and ‘consCode’. We therefore define a list as a function that accepts such ‘nilCode’ and ‘consCode’ as arguments， so that instead of the above pattern match we may simply write:list nilCode consCode
{ operatorname {list} operatorname {nilCode} operatorname {consCode} }
Let us denote by ‘n’ the parameter corresponding to ‘nilCode’ and by ‘c’ the parameter corresponding to ‘consCode’. The empty list is the one that returns the nil argument:nil ≡ λ n .λ c . n
{ operatorname {nil} equiv lambda n.lambda c. n}
The non-empty list with head ‘h’ and tail ‘t’ is given bycons h t ≡ λ
n. λ c . ch t
{ operatorname {cons} h t equiv lambda n.lambda c. c h t}
More generally， an algebraic data type with m { m}

alternatives becomes a function with m { m}

parameters. When the i { i}

th constructor has
n i { n_{i}}

arguments， the corresponding parameter of the encoding takes
n i { n_{i}}

arguments as well.
Scott encoding can be done in untyped lambda calculus， whereas its use with types requires a type system with recursion and type polymorphism. A list with element type E in this representation that is used to compute values of type C would have the following recursive type definition， where ‘=>’ denotes function type:
type List = C =>
// nil argument (E => List => C) => // cons argument C
// result of pattern matching
A list that can be used to compute arbitrary types would have a type that quantifies over C. A list generic[clarification needed] in E would also take E as the type argument.

こちらもご覧ください Lambda calculus System F for Church numerals in a typed calculus
Mogensen–Scott encoding
Von Neumann definition of ordinals — another way to encode natural numbers: as sets

ノート
^ Trancón y Widemann， Baltasar; Parnas， David Lorge （2008). “”Tabular Expressions and Total Functional Programming””. Implementation and Application of Functional Languages. 5083: 228–229. doi:10.1007/978-3-540-85373-2_13.
^ Jansen， Jan Martin; Koopman， Pieter W. M.; Plasmeijer， Marinus J. （2006). “”Efficient interpretation by transforming data types and patterns to functions””. In Nilsson， Henrik (ed.). Trends in functional programming. Volume 7. Bristol: Intellect. pp. 73–90. CiteSeerX 10.1.1.73.9841. ISBN 978-1-84150-188-8.
^ “”Predecessor and lists are not representable in simply typed lambda calculus””. Lambda Calculus and Lambda Calculators. okmij.org.
^ This formula is the definition of a Church numeral n with f -> m， x -> f. ^ Allison， Lloyd. “”Lambda Calculus Integers””. ^ Bauer， Andrej. “”Andrej’s answer to a question; “”Representing negative and complex numbers using lambda calculus””””. ^ “”Exact real arithmetic””. Haskell. Archived from the original on 2015-03-26. ^ Bauer， Andrej. “”Real number computational software””.
^ Pierce， Benjamin C. （2002). Types and Programming Languages. MIT Press. p. 500. ISBN 978-0-262-16209-8.
^ Tromp， John （2007). “”14. Binary Lambda Calculus and Combinatory Logic””. In Calude， Cristian S (ed.). Randomness And Complexity， From Leibniz To Chaitin. World Scientific. pp. 237–262. ISBN 978-981-4474-39-9.As PDF: Tromp， John (14 May 2014). “”Binary Lambda Calculus and Combinatory Logic”” (PDF). Retrieved 2017-11-24.
^ Jansen， Jan Martin （2013). “”Programming in the λ-Calculus: From Church to Scott and Back”. In Achten， Peter; Koopman， Pieter W. M. (eds.). The Beauty of Functional Code – Essays Dedicated to Rinus Plasmeijer on the Occasion of His 61st Birthday. Lecture Notes in Computer Science. Vol. 8106. Springer. pp. 168–180. doi:10.1007/978-3-642-40355-2_12.

参考文献
Directly Reflective Meta-Programming
Church numerals and booleans explained by Robert Cartwright at Rice University
Theoretical Foundations For Practical ‘Totally Functional Programming’ (Chapters 2 and 5) All about Church and other similar encodings， including how to derive them and operations on them， from first principles
Some interactive examples of Church numerals
Lambda Calculus Live Tutorial: Boolean Algebra”