教会のエンコーディング

数学において、チャーチ符号化はラムダ計算においてさまざまなデータ型を表現する方法です。

型なしラムダ計算では、プリミティブなデータ型はラムダ抽象化用語で表される関数のみです。他の表記法では通常プリミティブ型とみなされる型（整数、ブール値、ペア、リスト、タグ付き共用体など）は、ネイティブには存在しません。

したがって、これらのさまざまなタイプのデータをラムダ項、つまり関数を引数として受け取り、関数を結果として返す関数によって表現する方法が必要になります。

チャーチ数列は、ラムダ記法を用いた自然数の表現です。この手法は、ラムダ計算で初めてこの方法でデータを符号化したアロンゾ・チャーチにちなんで名付けられました。同様の考え方で他のデータ型を表現するように拡張することも可能です。

この記事では、ラムダ抽象化用語の代替構文をときどき使用します。λ x .λ y .λ z . Nは λ xyz . Nと省略され、必要に応じて2 つの標準コンビネータとも使用されます。 $I\equiv \lambda x.x$ $K\equiv \lambda xy.x$

使用

チャーチ符号化をそのまま実装すると、からへのアクセス操作が遅くなります。ここで、はデータ構造のサイズであるため、チャーチ符号化は実用的ではありません。^[1]研究では、この問題は対象を絞った最適化で対処できることが示されていますが、ほとんどの関数型プログラミング言語では、中間表現を拡張して代数データ型を含めています。^[2]ただし、チャーチ符号化は部分評価や定理証明の自然な表現であるため、理論的な議論ではよく使用されます。^{[1]演算は、}より高位の型を使用して型付けすることができ、^[3]プリミティブ再帰に簡単にアクセスできます。^[1]関数が唯一のプリミティブデータ型であるという仮定により、多くの証明が合理化されます。 $O(1)$ $O(n)$ $n$

チャーチ符号化は完全ですが、表現上のみです。表現を一般的なデータ型に変換し、人々に表示するには、追加の関数が必要です。チャーチの定理による同値性の決定不能性のため、一般に2つの関数が外延的に等しいかどうかを判断することはできません。変換では、関数を何らかの方法で適用してそれが表す値を取得するか、その値をリテラルなラムダ項として参照します。ラムダ計算は通常、内包的等価性を使用するものとして解釈されます。内包的等価性と外延的等価性の定義が異なるため、結果の解釈に潜在的な問題が生じる可能性があります。

教会のブール値

チャーチ・ブール値は、ブール値trueとfalse のチャーチ符号化です。一部のプログラミング言語では、これをブール演算の実装モデルとして利用しています。例としては、SmalltalkやPico などがあります。

ブール論理は選択肢として考えられます。チャーチの真偽の符号化は、 2つのパラメータの関数です。

true は最初のパラメータを選択します。
false は2 番目のパラメータを選択します。

次の 2 つの定義は Church ブール値として知られています。

{\begin{aligned}\operatorname {true} &\equiv \lambda a.\lambda b.a\\\operatorname {false} &\equiv \lambda a.\lambda b.b\end{aligned}}

この定義により、述語（つまり論理値を返す関数）を直接if節として機能させることができます。ブール値を返す関数を2つのパラメータに適用すると、最初のパラメータまたは2番目のパラメータのいずれかが返されます。

\operatorname {predicate-} x\ \operatorname {then-clause} \ \operatorname {else-clause}

述語 x がtrueと評価された場合はthen 節に評価され、述語 x がfalseと評価された場合はelse 節に評価されます。

trueとfalse は第1または第2のパラメータを選択するため、これらを組み合わせて論理演算子を使用することができます。notには複数の実装方法があることに注意してください。

{\begin{aligned}\operatorname {and} &=\lambda p.\lambda q.p\ q\ p\\\operatorname {or} &=\lambda p.\lambda q.p\ p\ q\\\operatorname {not} _{1}&=\lambda p.\lambda a.\lambda b.p\ b\ a\\\operatorname {not} _{2}&=\lambda p.p\ (\lambda a.\lambda b.b)\ (\lambda a.\lambda b.a)=\lambda p.p\operatorname {false} \operatorname {true} \\\operatorname {xor} &=\lambda a.\lambda b.a\ (\operatorname {not} \ b)\ b\\\operatorname {if} &=\lambda p.\lambda a.\lambda b.p\ a\ b\end{aligned}}

例:

{\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}}

教会のペア

チャーチペアは、ペア（2要素組）型のチャーチ符号化です。ペアは関数を引数として受け取る関数として表現されます。引数が与えられると、その引数をペアの2つの要素に適用します。ラムダ計算における定義は、以下の通りです。

{\begin{aligned}\operatorname {pair} &\equiv \lambda xy.\lambda z.z\ x\ y\\\operatorname {first} &\equiv \lambda p.p\ (\lambda xy.x)\\\operatorname {second} &\equiv \lambda p.p\ (\lambda xy.y)\end{aligned}}

例えば、

{\begin{aligned}&\operatorname {first} \ (\operatorname {pair} \ a\ b)\\=&\ (\lambda p.p\ (\lambda xy.x))\ ((\lambda xyz.z\ x\ y)\ a\ b)\\=&\ (\lambda p.p\ (\lambda xy.x))\ (\lambda z.z\ a\ b)\\=&\ (\lambda z.z\ a\ b)\ (\lambda xy.x)\\=&\ (\lambda xy.x)\ a\ b\\=&\ a\end{aligned}}

教会の数字

チャーチ数とは、チャーチ符号化による自然数の表現である。自然数nを表す高階関数は、任意の関数をそのn倍の合成に写像する関数である。簡単に言えば、数値は、任意の開始値から始めて、任意の関数をその回数だけ順番に適用することで、その数を表す。 $f$

n:f\mapsto f^{\circ n}

f^{\circ n}(x)=(\underbrace {f\circ f\circ \ldots \circ f} _{n{\text{ times}}})\,(x)=\underbrace {f(f(\ldots (f} _{n{\text{ times}}}\,(x))\ldots ))

チャーチ符号化は自然数の単項符号化であり、 ^[4]単純な数え上げに対応する。各チャーチ数は、構成によってこれを実現する。

すべてのチャーチ数列は2つのパラメータを取る関数です。チャーチ数列0、1、2 、… はラムダ計算において以下のように定義されます。

0 関数をまったく適用しない ことから始めて、 1 関数を 1 回適用し、2関数を 2 回連続で適用し、 3 関数を 3 回連続で適用する、というように進めます。

{\begin{array}{r|l|l}{\text{Number}}&{\text{Function definition}}&{\text{Lambda expression}}\\\hline 0&0\ f\ x=x&0=\lambda f.\lambda x.x\\1&1\ f\ x=f\ x&1=\lambda f.\lambda x.f\ x\\2&2\ f\ x=f\ (f\ x)&2=\lambda f.\lambda x.f\ (f\ x)\\3&3\ f\ x=f\ (f\ (f\ x))&3=\lambda f.\lambda x.f\ (f\ (f\ x))\\\vdots &\vdots &\vdots \\n&n\ f\ x=f^{\circ n}\ x&n=\lambda f.\lambda x.f^{\circ n}\ x\end{array}}

チャーチ数字3は、任意の関数をある値から順に3回適用する連鎖です。指定された関数はまず指定された引数に適用され、次に関数自身の結果に順次適用されます。最終結果は数値 3 ではありません（指定された引数がたまたま 0 で、関数が後続関数である場合を除く）。チャーチ数字3は、関数自体であり、最終結果ではありません。チャーチ数字3 は、単に何かを3回行うことを意味します。これは「3回」が何を意味するかを示唆するものです。

教会数字を使った計算

数値に対する算術演算は、結果として数値を生成します。チャーチ符号化では、これらの演算はラムダ抽象化によって表現され、オペランドを表すチャーチ数値に適用すると、結果を表すチャーチ数値にベータ還元されます。

加算のチャーチ表現では、次の恒等式が使用されます。 $\operatorname {plus} (m,n)=m+n$ $f^{\circ (m+n)}(x)=(f^{\circ m}\circ f^{\circ n})(x)=f^{\circ m}(f^{\circ n}(x))$

\operatorname {plus} \equiv \lambda mn.\lambda fx.m\ f\ (n\ f\ x)

後続演算は、式 " " をβ 縮小することによって得られます。 $\operatorname {succ} (n)=n+1$ $\operatorname {plus} \ 1$

\operatorname {succ} \equiv \lambda n.\lambda fx.f\ (n\ f\ x)

乗算では、次の恒等式が使用されます。 $\operatorname {mult} (m,n)=m*n$ $f^{\circ (m*n)}(x)=(f^{\circ n})^{\circ m}(x)$

\operatorname {mult} \equiv \lambda mn.\lambda fx.m\ (n\ f)\ x

したがって、 n倍の合成を表現するチャーチ符号化のおかげで、べき乗演算は次のように与えられる。 $b\ (b\ f)\equiv (\operatorname {mult} b\ b)\ f$ $b\ (b\ (b\ f))\equiv (\operatorname {mult} b\ (\operatorname {mult} b\ b))\ f$ $\operatorname {exp} (b,n)=b^{n}$

\operatorname {exp} \equiv \lambda bn.n\ b\equiv \lambda bnfx.n\ b\ f\ x

先行操作は少し複雑です。繰り返した際に、与えられた関数の適用が行われるような操作を考案する必要があります。これは、恒等関数を1回だけ使用し、その後に戻すことで実現できます。 $\operatorname {pred} (n)$ $n+1$ $n$ $f$ $f$

\operatorname {pred} \equiv \lambda nfx.n\ (\lambda ri.i\ (r\ f))\ (\lambda f.x)\ I

前述の通り、は恒等関数です。詳細な説明は以下を参照してください。これは、例えば二分の一化や階乗を同様の方法で実装することを示唆しています。 $I$ $\lambda x.x$

{\begin{aligned}\operatorname {half} &\equiv \lambda nfx.n\ (\lambda rab.a\ (r\ b\ a))\ (\lambda ab.x)\ I\ f\\\operatorname {fact} &\equiv \lambda nf.n\ (\lambda ra.a\ (r\ (\operatorname {succ} a)))\ (\lambda a.f)\ 1\end{aligned}}

たとえば、ベータ還元するとになり、ベータ還元するとになり、ベータ還元するとになります。 $\operatorname {pred} 4\ f\ x\,$ $I(f\ (f\ (f\ x)))$ $\operatorname {half} \ 5\ f\ x\,$ $I\ (f\ (I\ (f\ (I\ x))))$ $\operatorname {fact} 4\,f\,$ $1\ (2\ (3\ (4\ f)))$

減算は、前の演算を指定された回数繰り返して適用することで表現されます。同様に、加算は、後続の演算を指定された回数繰り返して適用することで表現されます。 $minus(m,n)=m-n$

{\begin{aligned}\operatorname {minus} &\equiv \lambda mn.n\operatorname {pred} \ m\\\operatorname {plus} &\equiv \lambda mn.n\operatorname {succ} \ m\\\operatorname {mult} &\equiv \lambda mn.n\ (m\operatorname {plus} )\ 0\\\operatorname {exp} &\equiv \lambda mn.n\ (m\operatorname {mult} )\ 1\\\operatorname {tet} &\equiv \lambda n.n\ (\lambda ra.r\ a\ a)\ 0\end{aligned}}

$\operatorname {tet} n$ はn番目のテトレーション演算であり、を表します。 $\operatorname {tet} \ 3\ a=0\ a\ a\ a\ a=a\ a\ a$ $a^{(a^{a})}$

直接引き算と割り算

繰り返し演算としての加算が直接的なスタイルで表現されるのと同様に、減算も直接的かつより効率的に表現できます。

{\begin{aligned}\operatorname {minus} \equiv \lambda &mnfx.\\&m\ (\lambda rq.q\ r)\ (\lambda q.x)\\&(n\ (\lambda qr.r\ q)\ (\operatorname {Y} \ (\lambda qr.f\ (r\ q))))\end{aligned}}

たとえば、はと同等になります。 $\operatorname {minus} \ 6\ 3\ f\ x$ $f\ (2\ f\ x)$

これにより、別の前身バージョンである beta-reducing も得られます。 $\lambda m.\operatorname {minus} \ m\ 1$

{\begin{aligned}\operatorname {pred'} \equiv \lambda mfx.m\ &(\lambda rq.q\ r)\ (\lambda q.x)\\&(\lambda r.r\ (\operatorname {Y} \ (\lambda qr.f\ (r\ q))))\end{aligned}}

除算の直接的な定義は次のようにほぼ同様に与えられる。

{\begin{aligned}\operatorname {div} \equiv \lambda &mnfx.\\&m\ (\lambda rq.q\ r)\ (\lambda q.x)\\&(\operatorname {Y} \ (\lambda q.n\ (\lambda qr.r\ q)\ (\lambda r.f\ (r\ q))\ (\lambda x.x)))\end{aligned}}

このアプリケーションは、その後のステップを繰り返し発行するアクションのサイクルを作成しながら減算を実現します。 $(\lambda x.x)$ $1$ $f$ $n-1$

上記の 3 つの定義のそれぞれにおいて、の代わりにを使用することもできます。 $\operatorname {Y}$ $(\lambda q.m\,q\,x)$

教会数字の機能表

関数	代数	身元	関数定義	ラムダ式
後継	$n+1$	$f^{\circ (n+1)}=f\circ f^{\circ n}$	$\operatorname {succ} \ n\ f\ x=f\ (n\ f\ x)$	$\lambda nfx.f\ (n\ f\ x)$	...
追加	$m+n$	$f^{\circ (m+n)}=f^{\circ m}\circ f^{\circ n}$	$\operatorname {plus} \ m\ n\ f\ x=m\ f\ (n\ f\ x)$	$\lambda mnfx.m\ f\ (n\ f\ x)$	$\lambda mn.n\operatorname {succ} m$
乗算	$m*n$	$f^{\circ (m*n)}=(f^{\circ m})^{\circ n}$	$\operatorname {multiply} \ m\ n\ f\ x=m\ (n\ f)\ x$	$\lambda mnfx.m\ (n\ f)\ x$	$\lambda mnf.m\ (n\ f)$
累乗	$b^{n}$	$b^{\circ n}=(\operatorname {mult} b)^{\circ n}$	$\operatorname {exp} \ b\ n\ f\ x=n\ b\ f\ x$	$\lambda bnfx.n\ b\ f\ x$	$\lambda bn.n\ b$
前任者^[a]	$n-1$	$first((\langle i,j\rangle \mapsto \langle j,f\circ j\rangle )^{\circ n}\langle I,I\rangle )=f^{\circ (n-1)}$	$\operatorname {pred} (n+1)\ f\ x=I\ (n\ f\ x)$	$\lambda nfx.n\ (\lambda ri.i\ (r\ f))\ (\lambda f.x)\ (\lambda u.u)$
減算^[a] ( Monus )	$m-n$	$m-n=pred^{\circ n}(m)$	$\operatorname {minus} \ m\ n=n\operatorname {pred} m$	...	$\lambda mn.n\operatorname {pred} m$

注記:

^ ab
教会のエンコーディングでは、
- $\operatorname {pred} (0)=0$
- $m\leq n\to m-n=0$

先行関数

先行関数は次のように与えられる。

\operatorname {pred} \equiv \lambda nfx.n\ (\lambda ri.i\ (r\ f))\ (\lambda f.x)\ (\lambda u.u)

このエンコードは本質的にはアイデンティティを使用する

first(\ (\langle i,j\rangle \mapsto \langle j,f\circ j\rangle )^{\circ n}\langle I,I\rangle \ )={\begin{cases}I&{\mbox{if }}n=0,\\f^{\circ (n-1)}&{\mbox{otherwise}}\end{cases}}

または

first(\ (\langle x,y\rangle \mapsto \langle y,f(y)\rangle )^{\circ n}\langle x,x\rangle \ )={\begin{cases}x&{\mbox{if }}n=0,\\f^{\circ (n-1)}(x)&{\mbox{otherwise}}\end{cases}}

predの説明

ここでの考え方は以下のとおりです。チャーチ数に認識されるのは数自体だけです。2つの引数とが与えられた場合、通常通り、チャーチ数にできることは、その数を2つの引数に適用することだけです。この適用は、 n個の長いチェーンのうち、チェーンの1つ（具体的には左端）が恒等関数に置き換えられるように何らかの修正を加えることで実現されます。 $\operatorname {pred} n$ $n$ $f$ $x$ $f$

{\begin{aligned}f^{\circ (n-1)}(x)&=\underbrace {I\ (\underbrace {f(f(\ldots (f} _{{n-1}{\text{ times}}}} _{n{\text{ times}}}\,(x))\ldots )))=(Xf)^{\circ n}(Z\,x)\ A\\&=\underbrace {Xf\ (Xf\ (\ldots (Xf} _{{n}{\text{ times}}}\,(Z\,x))\ldots ))\ A\\&=X\ f\ r_{1}\ A_{1}\,\,\,\{-\ and\ it\ must\ be\ equal\ to:\ -\}\\&=I\ (X\ f\ r_{2}\ A_{2})\\&=I\ (f\ (X\ f\ r_{3}\ A_{3}))\\&=I\ (f\ (f\ (X\ f\ r_{4}\ A_{4})))\\&\ldots \\&=I\ (f\ (f\ \ldots (X\ f\ r_{n}\ A_{n})\ldots ))\\&=\underbrace {I\ (f\ (f\ \ldots (f} _{n{\text{ times}}}\ (Z\ x\ A_{n+1}))\ldots ))\\\end{aligned}}

ここでは変更されたであり、は変更されたです。自体は変更できないため、その動作は追加の引数を通じてのみ変更できます。 $Xf$ $f$ $Z\,x$ $x$ $Xf$ $A$

必要に応じて定義を変更しながら、その追加の引数を外部から内部に渡すことで、目的が達成されます。 $A$

{\begin{aligned}A_{1}\,\,\,\,\,\,\,\,\,\,&=\,I\\A_{\,i>1}\,\,\,\,\,&=\,f\\Z\ x\ f\,\,\,\,&=x=K\ x\ f\\X\ f\ r\ A_{i}&=A_{i}\ (r\ A_{i+1})\,\,\,\,\,\,\{-\ i.e.,\ -\}\\X\ f\ r\ i\,\,\,\,\,&=i\ (r\ f)\end{aligned}}

これはまさに定義のラムダ式に含まれているものです。 $\operatorname {pred}$

今ではそれが簡単にわかります

{\begin{aligned}\operatorname {pred} \ (\operatorname {succ} \ n)\ f\ x&=\operatorname {succ} \ n\ (Xf)\ (K\ x)\ I\\&=X\ f\ (n\ (X\ f)\ (K\ x))\ I\\&=I\ (n\ (Xf)\ (K\ x)\ \,\,f\,\,\,)\\&=\ \ldots \\&=I\ (f\ (f\ \ldots (f\ (K\ x\,\,f\,\,))\ldots ))\\&=I\ (n\ f\ x)\\&=n\ f\ x\ \end{aligned}}

{\begin{aligned}\operatorname {pred} \ 0\ f\ x&=\ 0\ (Xf)\ (K\ x)\ I\\&=\ K\ x\ I\\&=\ x\\&=\ 0\ f\ x\end{aligned}}

すなわち、イータ縮約と帰納法によって、

{\begin{aligned}&\operatorname {pred} \ (\operatorname {succ} \ n)&&=\ n\\&\operatorname {pred} \ 0&&=\ 0\\&\operatorname {pred} \ (\operatorname {pred} \ 0)&&=\ \operatorname {pred} \ 0\ =\ 0\\&\ldots \end{aligned}}

等々。

ペアによる予測の定義

上記の恒等式は、明示的にペアを用いてコード化することができます。例えば、いくつかの方法があります。

{\begin{aligned}\operatorname {f} =&\ \lambda p.\ \operatorname {pair} \ (\operatorname {second} \ p)\ (\operatorname {succ} \ (\operatorname {second} \ p))\\\operatorname {pred} _{2}=&\ \lambda n.\ \operatorname {first} \ (n\ \operatorname {f} \ (\operatorname {pair} \ 0\ 0))\\\end{aligned}}

の展開は次のようになります。 $\operatorname {pred} _{2}3$

{\begin{aligned}\operatorname {pred} _{2}3=&\ \operatorname {first} \ (\operatorname {f} \ (\operatorname {f} \ (\operatorname {f} \ (\operatorname {pair} \ 0\ 0))))\\=&\ \operatorname {first} \ (\operatorname {f} \ (\operatorname {f} \ (\operatorname {pair} \ 0\ 1)))\\=&\ \operatorname {first} \ (\operatorname {f} \ (\operatorname {pair} \ 1\ 2))\\=&\ \operatorname {first} \ (\operatorname {pair} \ 2\ 3)\\=&\ 2\end{aligned}}

これはより単純な定義ですが、より複雑なラムダ式につながります。

{\begin{aligned}\operatorname {pred} _{2}\equiv \lambda n.n\ &(\lambda p.p\ (\lambda abh.h\ b\ (\operatorname {succ} \ b)))\,\,(\lambda h.h\ 0\ 0)\,\,(\lambda ab.a)\end{aligned}}

ラムダ計算におけるペアは、ここでのように内側から外側へ渡す場合でも、元の定義のように外側から内側へ渡す場合でも、本質的には単なる追加の引数です。別のエンコーディングは、先行する恒等式の2番目の変種に直接従います。 $\operatorname {pred}$

{\begin{aligned}\operatorname {pred} _{3}\equiv \lambda nfx.n\ &(\lambda p.p\ (\lambda abh.h\ b\ (f\ b)))\,\,(\lambda h.h\ x\ x)\,\,(\lambda ab.a)\end{aligned}}

この方法は、元の「外から内へ」の定義にかなり近いものとなっており、同様にsの連鎖を生み出しますが、より無駄が多くなっています。しかし、以前の定義よりもはるかに無駄が少なくなっています。実際、その実行過程を辿ると、より合理化されながらも完全に同等の新しい定義に辿り着きます。 $\operatorname {pred}$ $f$ $\operatorname {pred} _{2}$

{\begin{aligned}\operatorname {pred} _{4}\equiv \lambda nfx.n\ &(\lambda rab.r\ b\ (f\ b))\,K\ x\ x\end{aligned}}

これにより、これは単に引数の修正とパスだけに関するものであることが完全に明らかになります。その縮約は次のように進行します。

{\begin{aligned}\operatorname {pred} _{4}3\ f\ x&=\ (..(..(..K)))\ x\ \,x\\&=\ (..(..K))\,\,\,\,\,\,\,x\ \,\,(f\ x)\\&=\ (..K)\,\,\,\,\,\,(f\ x)\ \,\,(f\ (f\ x))\\&=\ K\,\,\,\,(f\ (f\ x))\ \,\,(f\ (f\ (f\ x)))\\&=\ f\ (f\ x)\\\end{aligned}}

何が起こっているかを明確に示しています。それでも、元の定義の方がはるかに優れています。トップダウン方式で動作するため、ユーザー定義関数が短絡した場合にすぐに停止できるからです。トップダウン方式は、次のような他の定義でも使用されます。 $\operatorname {pred}$ $f$

{\begin{aligned}\operatorname {pred} _{5}\equiv \lambda nfx.n\ &(\lambda rab.a\ (r\ b\ b))\,(\lambda ab.x)\ I\ f\\\operatorname {third} \equiv \lambda nfx.n\ &(\lambda rabc.a\ (r\ b\ c\ a))\,(\lambda abc.x)\ I\ I\ f\\\operatorname {thirdRounded} \equiv \lambda nfx.n\ &(\lambda rabc.a\ (r\ b\ c\ a))\,(\lambda abc.x)\ I\ f\ I\\\operatorname {twoThirds} \equiv \lambda nfx.n\ &(\lambda rabc.a\ (r\ b\ c\ a))\,(\lambda abc.x)\ I\ f\ f\\\operatorname {factorial} \equiv \lambda nfx.n\ &(\lambda ra.a\ (r\ (\operatorname {succ} a)))\,(\lambda a.f)\ 1\ x\\\end{aligned}}

一般再帰による除算

自然数の除算は次のように実装できる。^[5]

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

を計算するには、多くのベータ減算が必要になります。手動で減算を行わない限り、これはそれほど問題にはなりませんが、この計算を2回行う必要がない方が望ましいです（直接減算の定義を使用する場合を除く。上記参照）。数値を判定する最も単純な述語はIsZeroなので、その条件を検討してください。 $n-m$ $\lambda nm.m\,\operatorname {pred} \,n$

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

しかし、この条件はと等価であり、ではありません。この表現を用いると、上記の除算の数学的定義はチャーチ数上の関数として次のように変換されます。 $n\leq m$ $n<m$

\operatorname {divide1} \ n\ m\ f\ x=(\lambda d.\operatorname {IsZero} \ d\ (0\ f\ x)\ (f\ (\operatorname {divide1} \ d\ m\ f\ x)))\ (\operatorname {minus} \ n\ m)

期待どおり、この定義にはの呼び出しが 1 つ含まれています。しかし、結果としてこの式はの値を返します。 $\operatorname {minus} \ n\ m$ $(n-1)/m$

この問題は、divideを呼び出す前にnに1を加算することで修正できます。divideの定義は以下のようになります。

\operatorname {divide} \ n=\operatorname {divide1} \ (\operatorname {succ} \ n)

divide1は再帰的な定義です。Yコンビネータを使用して再帰を実装できます。div by; という新しい関数を作成してください。

左側 $\operatorname {divide1} \rightarrow \operatorname {div} \ c$
右側には $\operatorname {divide1} \rightarrow c$

取得するため、

\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 {minus} \ n\ m)

それから、

\operatorname {divide} =\lambda n.\operatorname {divide1} \ (\operatorname {succ} \ n)

どこ、

{\begin{aligned}\operatorname {divide1} &=Y\ \operatorname {div} \\\operatorname {succ} &=\lambda n.\lambda f.\lambda x.f\ (n\ f\ x)\\Y&=\lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))\\0&=\lambda f.\lambda x.x\\\operatorname {IsZero} &=\lambda n.n\ (\lambda x.\operatorname {false} )\ \operatorname {true} \end{aligned}}

{\begin{aligned}\operatorname {true} &\equiv \lambda a.\lambda b.a\\\operatorname {false} &\equiv \lambda a.\lambda b.b\end{aligned}}

{\begin{aligned}\operatorname {minus} &=\lambda m.\lambda n.n\operatorname {pred} m\\\operatorname {pred} &=\lambda n.\lambda f.\lambda x.n\ (\lambda g.\lambda h.h\ (g\ f))\ (\lambda u.x)\ (\lambda u.u)\end{aligned}}

与える、

\scriptstyle \operatorname {divide} =\lambda n.((\lambda f.(\lambda x.x\ x)\ (\lambda x.f\ (x\ x)))\ (\lambda c.\lambda n.\lambda m.\lambda f.\lambda x.(\lambda d.(\lambda n.n\ (\lambda x.(\lambda a.\lambda b.b))\ (\lambda a.\lambda b.a))\ d\ ((\lambda f.\lambda x.x)\ f\ x)\ (f\ (c\ d\ m\ f\ x)))\ ((\lambda m.\lambda n.n(\lambda n.\lambda f.\lambda x.n\ (\lambda g.\lambda h.h\ (g\ f))\ (\lambda u.x)\ (\lambda u.u))m)\ n\ m)))\ ((\lambda n.\lambda f.\lambda x.f\ (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 (f (f (f (f (f (f (f (f (f (fx))))))))) (\f.\xf (f (fx)))

ラムダ計算計算機を使用すると、上記の式は通常の順序で 3 に簡約されます。

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

符号付き数字

チャーチ数字を符号付き数値に拡張する簡単な方法の一つは、正と負の値を表すチャーチ数字を含むチャーチペアを使用することです。^[6] 整数値は2つのチャーチ数字の差です。

自然数は次のように符号付き数に変換される。

\operatorname {convert} _{s}=\lambda x.\operatorname {pair} \ x\ 0

否定は値を交換することによって実行されます。

\operatorname {neg} _{s}=\lambda x.\operatorname {pair} \ (\operatorname {second} \ x)\ (\operatorname {first} \ x)

整数値は、ペアの一方がゼロであればより自然に表現されます。OneZero関数はこの条件を実現します。

\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コンビネータを使って実装できる。

\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} =Y\operatorname {OneZ}

プラスとマイナス

加算は数学的には次のように定義されます。

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}]

最後の式はラムダ計算では次のように翻訳される。

\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},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}]

与えること、

\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},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}]

最後の式はラムダ計算では次のように翻訳される。

\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)))

除算についても同様の定義が示されていますが、この定義では、各ペアの一方の値は必ずゼロでなければなりません（上記のOneZeroを参照）。divZ関数を使用すると、ゼロの要素を持つ値を無視できます。

\operatorname {divZ} =\lambda x.\lambda y.\operatorname {IsZero} \ y\ 0\ (\operatorname {divide} \ x\ y)

次に、 divZが次の式で使用されます。これは乗算の場合と同じですが、multがdivZに置き換えられます。

\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)))

有理数と実数

有理数と計算可能な実数もラムダ計算で符号化できます。有理数は符号付き数のペアとして符号化できます。計算可能な実数は、実数値との差が一定数だけ小さいことを保証する極限処理によって符号化できます。この極限値は必要に応じて小さくすることができます。^[7]^[8] 参考文献に記載されているソフトウェアは、理論的にはラムダ計算に翻訳可能です。実数が定義されれば、複素数は自然に実数のペアとして符号化されます。

上で説明したデータ型と関数は、あらゆるデータ型や計算をラムダ計算で符号化できることを示しています。これがチャーチ＝チューリングのテーゼです。

他の表現による翻訳

現実世界の言語のほとんどは、マシンネイティブな整数をサポートしています。church関数とunchurch関数は、非負整数とそれに対応するチャーチ数との間の変換を行います。これらの関数はHaskellで提供されています。ここで、は\ラムダ計算のλに相当します。他の言語での実装も同様です。

タイプChurch a = ( a -> a ) -> a -> a          church :: Integer -> Church Integer church 0 = \ f -> \ x -> x church n = \ f -> \ x -> f ( church ( n - 1 ) f x )                       unchurch :: Church整数->整数unchurch cn = cn ( + 1 ) 0

述語

述語はブール値を返す関数です。最も基本的な述語はで、引数がチャーチ数の場合はを返し、引数が他のチャーチ数の場合はを返します。 $\operatorname {IsZero}$ $\operatorname {true}$ $0$ $\operatorname {false}$

\operatorname {IsZero} =\lambda n.n\ (\lambda x.\operatorname {false} )\ \operatorname {true}

次の述語は、最初の引数が 2 番目の引数以下かどうかをテストします。

\operatorname {LEQ} =\lambda m.\lambda n.\operatorname {IsZero} \ (\operatorname {minus} \ m\ n)

、

アイデンティティのため、

x=y\equiv (x\leq y\land y\leq x)

等価性のテストは次のように実装できる。

\operatorname {EQ} =\lambda m.\lambda n.\operatorname {and} \ (\operatorname {LEQ} \ m\ n)\ (\operatorname {LEQ} \ n\ m)

リストエンコーディング

（不変の）リストはリストノードから構築されます。リストに対する基本的な操作は以下のとおりです。

関数	説明
ゼロ	空のリストを作成します。
イニル	リストが空かどうかをテストします。
欠点	指定された値を（空の可能性のある）リストの先頭に追加します。
頭	リストの最初の要素を取得します。
しっぽ	リストの残りを取得します。

以下にリストの 4 つの異なる表現を示します。

リストノードごとに 2 つの Church ペア。
リストノードごとに 1 つの Church ペア。
教会リスト –右折り表示。
スコットエンコーディング。

リストノードとしての2つのペア

空でないリストは Church ペアによって実装できます。

まず頭が入っています。
2番目には尾が含まれています。

しかし、これは「null」ポインタが存在しないため、空のリストを表すものではありません。nullを表すには、このペアを別のペアでラップし、3つの値を与えます。

まず、ヌルポインター（空のリスト）。
Second.Firstにはヘッドが含まれます。
Second.Second には末尾が含まれます。

この考え方を用いると、基本的なリスト操作は次のように定義できる。^[9]

表現	説明
$\operatorname {nil} \equiv \operatorname {pair} \ \operatorname {true} \ \operatorname {true}$	ペアの最初の要素はtrueなので、リストは null です。
$\operatorname {isnil} \equiv \operatorname {first}$	null (または空のリスト) インジケーターを取得します。
$\operatorname {cons} \equiv \lambda h.\lambda t.\operatorname {pair} \operatorname {false} \ (\operatorname {pair} h\ t)$	null ではないリストノードを作成し、先頭にh、末尾にtを指定します。
$\operatorname {head} \equiv \lambda z.\operatorname {first} \ (\operatorname {second} z)$	2番目。1番目は頭です。
$\operatorname {tail} \equiv \lambda z.\operatorname {second} \ (\operatorname {second} z)$	2番目。2番目は末尾です。

nilノードでは、 headとtail が空でないリストにのみ適用される場合、 second はアクセスされません。

リストノードとして1組

あるいは、^{[10]を定義する。}

{\begin{aligned}\operatorname {cons} &\equiv \operatorname {pair} \\\operatorname {head} &\equiv \operatorname {\{-first-\}} \equiv \lambda l.\ l\ (\lambda htd.\ h)\ \operatorname {nil} \\\operatorname {tail} &\equiv \operatorname {\{-second-\}} \equiv \lambda l.\ l\ (\lambda htd.\ t)\ \operatorname {nil} \\\operatorname {nil} &\equiv \operatorname {false} \\\operatorname {isnil} &\equiv \lambda l.l\ (\lambda htd.\operatorname {false} )\operatorname {true} \\\end{aligned}}

ここで、最後の定義はリストの安全な使用の一般的なパターンに従っており、とはリストの先頭と末尾を指します。 $h$ $t$

{\begin{aligned}\operatorname {process-list} &\equiv \lambda l.l\ (\lambda htd.\langle \operatorname {head-and-tail-clause} \rangle )\ \langle \operatorname {nil-clause} \rangle \\\end{aligned}}

リストノードとしての1つのペアに対するその他の操作

{\begin{aligned}\operatorname {fold} &\equiv \lambda f.\ \operatorname {Y} \ (\lambda r.\lambda al.\ l\ (\lambda htd.\ r\ (f\ a\ h)\ t)\ a)\\\operatorname {rfold} &\equiv \lambda fa.\ \operatorname {Y} \ (\lambda r.\lambda l.\ l\ (\lambda htd.\ f\ (r\ t)\ h)\ a)\\\operatorname {length} &\equiv \operatorname {fold} \ (\lambda ah.\ \operatorname {succ} \ a)\ \operatorname {zero} \end{aligned}}

{\begin{aligned}\operatorname {map} &\equiv \lambda f.\ \operatorname {rfold} \ (\lambda ah.\ \operatorname {cons} \ (f\ h)\ a)\ \operatorname {nil} \\\operatorname {filter} &\equiv \lambda p.\ \operatorname {rfold} \ (\lambda ah.\ p\ h\ (\operatorname {cons} \ h\ a)\ a)\ \operatorname {nil} \\\operatorname {reverse} &\equiv \operatorname {fold} \ (\lambda ah.\ \operatorname {cons} \ h\ a)\ \operatorname {nil} \\\operatorname {concat} &\equiv \lambda lg.\ \operatorname {rfold} \ (\lambda ah.\ \operatorname {cons} \ h\ a)\ g\ l\\\operatorname {conj} &\equiv \lambda lv.\ \operatorname {concat} \ l\ (\operatorname {cons} \ v\ \operatorname {nil} )\end{aligned}}

{\begin{aligned}\operatorname {drop} &\equiv \lambda n.\ n\ \operatorname {tail} \\&\equiv \operatorname {Y} \ (\lambda r.\lambda nl.\ l\ (\lambda htd.\ \operatorname {IsZero} \ n\ l\ (r\ (\operatorname {pred} \ n)\ t))\ \operatorname {nil} )\\\operatorname {drop-last} &\equiv \lambda nl.\ \operatorname {IsZero} \ n\ l\ \operatorname {second} (\\&\ \ \ \ \ \ \ \ \operatorname {Y} \ (\lambda rl_{r}.\ l_{r}\ (\lambda htd.\\&\ \ \ \ \ \ \ \ \ \ \ \ r\ t\ (\lambda n_{a}l_{a}.\ \operatorname {IsZero} \ n_{a}\\&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (\operatorname {pair} \ \operatorname {zero} \ (\operatorname {cons} \ h\ l_{a}))\\&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (\operatorname {pair} \ (\operatorname {pred} \ n_{a})\ \operatorname {nil} )\ ))\\&\ \ \ \ \ \ \ \ \ \ \ \ (\operatorname {pair} \ n\ \operatorname {nil} )\ )\\&\ \ \ \ \ \ \ \ \ l\ )\\\operatorname {drop-while} &\equiv \lambda p.\ \operatorname {Y} \ (\lambda rl.\ l\ (\lambda htd.\ p\ h\ (r\ t)\ l)\ \operatorname {nil} )\\\operatorname {take} &\equiv \operatorname {Y} \ (\lambda rnl.\ l\ (\lambda htd.\ \operatorname {IsZero} \ n\ \operatorname {nil} \ (\operatorname {cons} \ h\ (r\ (\operatorname {pred} \ n)\ t)))\ \operatorname {nil} )\\\operatorname {take-last} &\equiv \lambda nl.\ \operatorname {IsZero} \ n\ l\ \operatorname {second} (\\&\ \ \ \ \ \ \ \ \operatorname {Y} \ (\lambda rl_{r}.\ l_{r}\ (\lambda htd.\\&\ \ \ \ \ \ \ \ \ \ \ \ r\ t\ (\lambda n_{a}l_{a}.\ \operatorname {IsZero} \ n_{a}\\&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (\operatorname {pair} \ \operatorname {zero} \ l_{a})\\&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (\operatorname {pair} \ (\operatorname {pred} \ n_{a})\ l_{r})\ ))\\&\ \ \ \ \ \ \ \ \ \ \ \ (\operatorname {pair} \ n\ \operatorname {nil} )\ )\\&\ \ \ \ \ \ \ \ \ l)\\\operatorname {take-while} &\equiv \lambda p.\ \operatorname {Y} \ (\lambda rl.\ l\ (\lambda htd.\ p\ h\ (\operatorname {cons} \ h\ (r\ t))\ \operatorname {nil} )\ \operatorname {nil} )\end{aligned}}

{\begin{aligned}\operatorname {all} &\equiv \operatorname {Y} \ (\lambda rpl.\ l\ (\lambda htd.\ p\ h\ (r\ p\ t)\ \operatorname {false} )\ \operatorname {true} )\\\operatorname {any} &\equiv \operatorname {Y} \ (\lambda rpl.\ l\ (\lambda htd.\ p\ h\ \operatorname {true} \ (r\ p\ t))\ \operatorname {false} )\\\operatorname {element-at} &\equiv \lambda nl.\ \operatorname {head} \ (\operatorname {drop} \ n\ l)\\\operatorname {insert-at} &\equiv \lambda nvl.\ \operatorname {concat} \ (\operatorname {take} \ n\ l)\ (\operatorname {cons} \ v\ (\operatorname {drop} \ n\ l))\\\operatorname {remove-at} &\equiv \lambda nl.\ \operatorname {concat} \ (\operatorname {take} \ n\ l)\ (\operatorname {drop} \ (\operatorname {succ} \ n)\ l)\\\operatorname {replace-at} &\equiv \lambda nvl.\ \operatorname {concat} \ (\operatorname {take} \ n\ l)\ (\operatorname {cons} \ v\ (\operatorname {drop} \ (\operatorname {succ} \ n)\ l))\\\operatorname {index-of} &\equiv \lambda p.\ \operatorname {Y} \ (\lambda rnl.\ l\ (\lambda htd.\ p\ h\ n\ (r\ (\operatorname {succ} \ n)\ t))\ \operatorname {zero} )\ \operatorname {one} \\\operatorname {last-index-of} &\equiv \lambda p.\ \operatorname {Y} \ (\lambda rnl.\ l\ (\lambda htd.\ (\lambda i.\ \operatorname {IsZero} \ i\ (p\ h\ n\ \operatorname {zero} )\ i)\ (r\ (\operatorname {succ} \ n)\ t))\ \operatorname {zero} )\ \operatorname {one} \\\operatorname {range} &\equiv \lambda fz.\ \operatorname {Y} \ (\lambda rsn.\ \operatorname {IsZero} \ n\ \operatorname {nil} \ (\operatorname {cons} \ (s\ f\ z)\ (r\ (\operatorname {succ} \ s)\ (\operatorname {pred} \ n))))\ \operatorname {zero} \\\operatorname {repeat} &\equiv \lambda v.\ \operatorname {Y} \ (\lambda rn.\ \operatorname {IsZero} \ n\ \operatorname {nil} \ (\operatorname {cons} \ v\ (r\ (\operatorname {pred} \ n))))\\\operatorname {zip} &\equiv Y\ (\lambda rl_{1}l_{2}.\ l_{1}\ (\lambda h_{1}t_{1}d_{1}.\ l_{2}\ (\lambda h_{2}t_{2}d_{2}.\ \operatorname {cons} \ (\operatorname {pair} \ h_{1}\ h_{2})\ (r\ t_{1}\ t_{2}))\ \operatorname {nil} )\ \operatorname {nil} )\\\end{aligned}}

教会リスト –右折り表現

チャーチペアを用いたエンコードの代替として、リストは右折り畳み関数を用いて識別することでエンコードできます。例えば、3つの要素x、y、zのリストは、コンビネータcと値nに適用するとcx(cy(czn))を返す高階関数でエンコードできます。これは、部分適用の関数的合成の連鎖(cx cy cz) nの適用と同等です。 $\circ$ $\circ$

{\begin{aligned}\operatorname {nil} &\equiv \lambda c.\lambda n.n\\\operatorname {singleton} &\equiv \lambda h.\lambda c.\lambda n.c\ h\ n\\\operatorname {cons} &\equiv \lambda h.\lambda t.\lambda c.\lambda n.c\ h\ (t\ c\ n)\\\operatorname {append} &\equiv \lambda l.\lambda t.\lambda c.\lambda n.l\ c\ (t\ c\ n)\\\operatorname {isnil} &\equiv \lambda l.l\ (\lambda h.\lambda r.\operatorname {false} )\ \operatorname {true} \\\operatorname {nonempty} &\equiv \lambda l.l\ (\lambda h.\lambda r.true)\ \operatorname {false} \\\operatorname {head} &\equiv \lambda l.l\ (\lambda h.\lambda r.h)\ \operatorname {false} \\\operatorname {map} &\equiv \lambda f.\lambda l.\lambda c.\lambda n.l\ (\lambda h.\lambda r.c\ (f\ h)\ r)\ n\\\operatorname {tail} &\equiv \lambda l.\lambda c.\lambda n.l\ (\lambda h.\lambda r.\lambda g.g\ h\ (r\ c))\ (\lambda c.n)\ (\lambda h.\lambda t.t)\end{aligned}}

このリスト表現はSystem Fの型で指定できます。

チャーチ数列との明らかな対応は偶然ではありません。チャーチ数列は単項符号化と見なすことができ、自然数は単位値（つまり重要でない値）のリスト（例えば[() () ()]）で表され、リストの長さが自然数の表現として機能します。このようなリストの右畳み込みは、要素の値を必然的に無視する関数を使用し、チャーチ数列で使用される連鎖関数合成、つまり(c () c () c ()) n = (f f f) nと同等です。 $\circ$ $\circ$ $\circ$ $\circ$

スコット符号化を使用してリストを表す

代替表現としてスコット符号化があり、継続の考え方を利用してより単純なコードを書くことができます。^{[11] （}モーゲンセン・スコット符号化も参照）。

このアプローチでは、パターンマッチング式を用いてリストを観察できるという事実を利用します。例えば、Scala記法を用いると、空リストとコンストラクタを持つlist型の値を表す場合、リストを検査し、リストが空の場合と空でない場合の計算を行うことができます。ListNilCons(h, t)nilCodeconsCode(h, t)

リストマッチ{ case Nil => nilCode case Cons ( h , t ) => consCode ( h , t ) }

は、およびlistに作用する方法によって決まります。したがって、リストを、そのようなおよびを引数として受け取る関数として定義すると、上記のパターンマッチの代わりに、次のように簡単に記述できます。nilCodeconsCodenilCodeconsCode

\operatorname {list} \ \operatorname {nilCode} \ \operatorname {consCode}

nに対応するパラメータをnilCode、cに対応するパラメータをと表記しますconsCode。空のリストは nil 引数を返すものです。

\operatorname {nil} \equiv \lambda n.\lambda c.\ n

h先頭と末尾を持つ空でないリストはt次のように与えられる。

\operatorname {cons} \ h\ t\ \ \equiv \ \ \lambda n.\lambda c.\ c\ h\ t

より一般的には、代替引数を持つ代数的データ型は引数を持つ関数になります。thコンストラクタが引数を持つ場合、対応するエンコーディングの引数も引数を取ります。 $m$ $m$ $i$ $n_{i}$ $n_{i}$

スコット符号化は型なしラムダ計算で実行できますが、型と併用するには再帰と型多態性を備えた型システムが必要です。この表現において要素型Eを持つリストを型Cの値を計算するために使用すると、次のような再帰型定義になります。ここで、「=>」は関数型を表します。

type List = C => // nil 引数( E => List => C ) => // cons 引数C // パターンマッチングの結果

任意の型を計算するために使用できるリストは、を量化する型を持ちます。のCジェネリックなリスト^{[明確化が必要]}も、型引数としてEを取ります。E

参照

ラムダ計算
型付き計算におけるチャーチ数字のシステムF
モーゲンセン・スコット符号化
フォン・ノイマンの順序数の定義— 自然数を集合として符号化する別の方法

参考文献

^ abc Trancón y Widemann, Baltasar; Parnas, David Lorge (2008). 「表形式表現と完全関数型プログラミング」. Olaf Chitil, Zoltán Horváth, Viktória Zsók (編). 関数型言語の実装と応用. 第19回国際ワークショップ, IFL 2007, ドイツ, フライブルク, 2007年9月27日～29日. 改訂版選定論文. コンピュータサイエンス講義ノート. 第5083巻. pp. 228～ 229. doi :10.1007/978-3-540-85373-2_13. ISBN 978-3-540-85372-5。
^ Jansen, Jan Martin; Koopman, Pieter WM; Plasmeijer, Marinus J. (2006). 「データ型とパターンを関数に変換することによる効率的な解釈」. Nilsson, Henrik (編). Trends in functional programming. 第7巻. ブリストル: Intellect. pp. 73– 90. CiteSeerX 10.1.1.73.9841 . ISBN 978-1-84150-188-8。
^ 「先行処理とリストは単純型ラムダ計算では表現できない」ラムダ計算とラムダ計算機okmij.org.
^ Jansen, Jan Martin (2013)、「λ計算によるプログラミング：チャーチからスコットへ、そしてその逆へ」、関数型コードの美しさ、コンピュータサイエンス講義ノート、第8106巻、Springer-Verlag、pp. 168– 180、doi :10.1007/978-3-642-40355-2_12、ISBN 978-3-642-40354-5。
^ アリソン、ロイド、「ラムダ計算整数」。
^ Bauer, Andrej. 「ラムダ計算を用いた負数と複素数の表現」という質問に対するAndrejの回答。
^ “正確な実数演算”. Haskell . 2015年3月26日時点のオリジナルよりアーカイブ。
^ Bauer, Andrej (2022年9月26日). 「実数計算ソフトウェア」. GitHub .
^ ピアス、ベンジャミン・C. (2002).型とプログラミング言語. MITプレス. p. 500. ISBN 978-0-262-16209-8。
^ Tromp, John (2007). 「14. 二項ラムダ計算と組合せ論理」. Calude, Cristian S (編).ランダム性と複雑性、ライプニッツからチャイティンまで. World Scientific. pp. 237– 262. ISBN 978-981-4474-39-9。
PDF: Tromp, John (2014年5月14日). 「二項ラムダ計算と組合せ論理」(PDF) . 2017年11月24日閲覧.
^ Jansen, Jan Martin (2013). 「λ-計算によるプログラミング：チャーチからスコットへ、そしてチャーチからスコットへ」. Achten, Peter、Koopman, Pieter WM (編). 『関数型コードの美しさ ― リーヌス・プラスマイヤー61歳の誕生日に捧げるエッセイ集』 . Lecture Notes in Computer Science. Vol. 8106. Springer. pp. 168– 180. doi :10.1007/978-3-642-40355-2_12. ISBN 978-3-642-40354-5。

Stump, A. (2009). 「直接反射メタプログラミング」（PDF） . High-Order Symb Comput . 22 (2): 115– 144. CiteSeerX 10.1.1.489.5018 . doi :10.1007/s10990-007-9022-0. S2CID 16124152.
カートライト、ロバート. 「教会の数字とブール値の解説」(PDF) . Comp 311 — レビュー2.ライス大学.
ケンプ、コリン (2007). 「§2.4.1 チャーチ自然数、§2.4.2 チャーチブール値、第5章 TFPの導出技法」『実践的「完全関数型プログラミング」の理論的基礎』(PhD). クイーンズランド大学情報技術・電気工学部. pp. 14– 17, 93– 145. CiteSeerX 10.1.1.149.3505 . Churchやその他の類似のエンコーディングについて、その導出方法やその操作方法など、基本原理からすべてを説明します。
教会数字のインタラクティブな例
ラムダ計算ライブチュートリアル：ブール代数

[ce-5] 教会のエンコーディングでは、
$\operatorname {pred} (0)=0$
$m\leq n\to m-n=0$

[2] $\operatorname {pred} (0)=0$

[3] $m\leq n\to m-n=0$

[Widemann-1] Trancón y Widemann, Baltasar; Parnas, David Lorge (2008). 「表形式表現と完全関数型プログラミング」. Olaf Chitil, Zoltán Horváth, Viktória Zsók (編). 関数型言語の実装と応用. 第19回国際ワークショップ, IFL 2007, ドイツ, フライブルク, 2007年9月27日～29日. 改訂版選定論文. コンピュータサイエンス講義ノート. 第5083巻. pp. 228～ 229. doi :10.1007/978-3-540-85373-2_13. ISBN 978-3-540-85372-5。

[2] Jansen, Jan Martin; Koopman, Pieter WM; Plasmeijer, Marinus J. (2006). 「データ型とパターンを関数に変換することによる効率的な解釈」. Nilsson, Henrik (編). Trends in functional programming. 第7巻. ブリストル: Intellect. pp. 73– 90. CiteSeerX 10.1.1.73.9841 . ISBN 978-1-84150-188-8。

[3] 「先行処理とリストは単純型ラムダ計算では表現できない」ラムダ計算とラムダ計算機okmij.org.

[4] Jansen, Jan Martin (2013)、「λ計算によるプログラミング：チャーチからスコットへ、そしてその逆へ」、関数型コードの美しさ、コンピュータサイエンス講義ノート、第8106巻、Springer-Verlag、pp. 168– 180、doi :10.1007/978-3-642-40355-2_12、ISBN 978-3-642-40354-5。

[6] アリソン、ロイド、「ラムダ計算整数」。

[7] Bauer, Andrej. 「ラムダ計算を用いた負数と複素数の表現」という質問に対するAndrejの回答。

[8] “正確な実数演算”. Haskell . 2015年3月26日時点のオリジナルよりアーカイブ。

[9] Bauer, Andrej (2022年9月26日). 「実数計算ソフトウェア」. GitHub .

[10] ピアス、ベンジャミン・C. (2002).型とプログラミング言語. MITプレス. p. 500. ISBN 978-0-262-16209-8。

[11] Tromp, John (2007). 「14. 二項ラムダ計算と組合せ論理」. Calude, Cristian S (編).ランダム性と複雑性、ライプニッツからチャイティンまで. World Scientific. pp. 237– 262. ISBN 978-981-4474-39-9。
PDF: Tromp, John (2014年5月14日). 「二項ラムダ計算と組合せ論理」(PDF) . 2017年11月24日閲覧.

[12] Jansen, Jan Martin (2013). 「λ-計算によるプログラミング：チャーチからスコットへ、そしてチャーチからスコットへ」. Achten, Peter、Koopman, Pieter WM (編). 『関数型コードの美しさ ― リーヌス・プラスマイヤー61歳の誕生日に捧げるエッセイ集』 . Lecture Notes in Computer Science. Vol. 8106. Springer. pp. 168– 180. doi :10.1007/978-3-642-40355-2_12. ISBN 978-3-642-40354-5。

v t e アロンゾ・チャーチ
注目すべきアイデア	ラムダ計算単純な型付けのラムダ計算チャーチ＝チューリングのテーゼ教会のエンコーディングフレーゲ・教会の存在論チャーチ・ロッサー定理
学生	アラン・チューリング C. アンソニー・アンダーソンピーター・アンドリュースジョージ・アルフレッド・バーナードウィリアム・ブーンマーティン・デイビスウィリアム・イーストンアルフレッド・フォスターレオン・ヘンキンジョン・ジョージ・ケメニースティーブン・コール・クリーネサイモン・B・コッヘンモーリス・ラベゲイリー・R・マーマイケル・O・ラビンニコラス・レッシャーハートリー・ロジャース・ジュニア J. バークレーロッサーダナ・スコットノーマン・シャピロレイモンド・スマリヤン
機関	プリンストン大学カリフォルニア大学ロサンゼルス校
家族	アロンゾ・チャーチ（大学学長） ACクルーム