単純型付きラムダ計算

型理論の形式である単純に型付けされたラムダ計算 （λ→{\ displaystyle \ lambda ^ {\ to}}）は、1つの型コンストラクターのみを備えたラムダ計算の型付き解釈です：→{\ displaystyle \ to}関数タイプ。型付きラムダ計算の標準的で最も単純な例です。単純型付きラムダ計算は、1940年にアロンゾ教会によって、型なしラムダ計算の逆説的な使用を回避する試みとして導入され、多くの望ましい興味深い特性を示しています。

単純型という用語は、製品、連産体、自然数（System T）などの単純に型付けされたラムダ計算の拡張、または完全な再帰（PCFなど）を指す場合にも使用されます。対照的に、多相型（System Fなど）または依存型（Logical Frameworkなど）を導入するシステムは、 単純に型付けされたとは見なされません。完全再帰を除く前者は、→{\ displaystyle \ to}と適切な型変数のみを使用してそのような構造のチャーチエンコーディングを行うことができますが、多態性と依存関係はできないため、依然としてシンプルと見なされます。

構文

この記事では、σ{\ displaystyle \ sigma}およびτ{\ displaystyle \ tau}を使用して、型の範囲を広げます。非公式には、 関数タイプ σ→τ{\ displaystyle \ sigma \ to \ tau}は、タイプσ{\ displaystyle \ sigma}の入力が与えられると、タイプτ{\ displaystyle \ tauの出力を生成する関数のタイプを指します。 }。慣例により、→{\ displaystyle \ to}は右側に関連付けられます。σ→τ→ρ{\ displaystyle \ sigma \ to \ tau \ to \ rho}はσ→（τ→ρ）{\ displaystyle \ sigma \ to（\ tau \ to \ rho）}。

タイプを定義するために、 基本タイプのセットB {\ displaystyle B}を修正することから始めます。これらは、 アトミック型または型定数と呼ばれることもあります。これを修正すると、型の構文は次のようになります。

τ:: =τ→τ∣TwhereT∈B {\ displaystyle \ tau :: = \ tau \ to \ tau \ mid T \ quad \ mathrm {where} \ quad T \ in B}。

たとえば、B = {a、b} {\ displaystyle B = \ {a、b \}}は、a、b、{\ displaystyle a、b、} a→a、{\で始まる無限のタイプのセットを生成しますdisplaystyle a \ to a、} a→b、b→b、{\ displaystyle a \ to b、b \ to b、} b→a、{\ displaystyle b \ to a、} a→（a→a）、 …、{\ displaystyle a \ to（a \ to a）、\ ldots、}（b→a）→（a→b）、…{\ displaystyle（b \ to a）\ to（a \ to b）、 \ ldots}

また、基本型の一連の項定数も修正します。たとえば、基本型natを想定し、定数という用語は自然数である可能性があります。元のプレゼンテーションでは、Churchは2つの基本タイプのみを使用しました。o{\ displaystyle o}は「命題のタイプ」、ι{\ displaystyle \ iota}は「個人のタイプ」です。タイプo {\ displaystyle o}には項定数がありませんが、ι{\ displaystyle \ iota}には項定数が1つあります。多くの場合、基本型が1つだけの計算（通常はo {\ displaystyle o}）が考慮されます。

単純に型指定されたラムダ計算の構文は、本質的にラムダ計算自体の構文です。 x：τ{\ displaystyle x {\ mathbin {：}} \ tau}と書いて、変数x {\ displaystyle x}がτ{\ displaystyle \ tau}型であることを示します。 BNFの構文という用語は次のとおりです。

e :: = x∣λx：τ.e∣ee∣c {\ displaystyle e :: = x \ mid \ lambda x {\ mathbin {：}} \ tau .e \ mid e \、e \ mid c}

c {\ displaystyle c}は項定数です。

つまり、 変数参照 、 抽象化 、 アプリケーション 、および定数です。変数参照x {\ displaystyle x}は、抽象バインディングx {\ displaystyle x}内にある場合にバインドされます。バインドされていない変数がない場合、用語は閉じられます。

これを型付けされていないラムダ計算の構文と比較します。

e :: = x∣λx.e∣ee {\ displaystyle e :: = x \ mid \ lambda xe \ mid e \、e}

型付きラムダ計算では、すべての関数（ abstraction ）が引数の型を指定する必要があることがわかります。

入力規則

与えられた型のよく型付けされたラムダ項のセットを定義するために、項と型の間の型付け関係を定義します。最初に、 タイピングコンテキストまたはタイピング環境 Γ、Δ、…{\ displaystyle \ Gamma、\ Delta、\ dots}を紹介します 。これらは、タイピングの仮定のセットです。 タイピングの仮定の形式はx：σ{\ displaystyle x {\ mathbin {：}} \ sigma}です。つまり、x {\ displaystyle x}のタイプはσ{\ displaystyle \ sigma}です。

タイプ関係 Γ⊢e：σ{\ displaystyle \ Gamma \ vdash e {\ mathbin {：}} \ sigma}は、e {\ displaystyle e}がコンテキストΓ{のタイプσ{\ displaystyle \ sigma}の項であることを示します。 \ displaystyle \ Gamma}。この場合、e {\ displaystyle e}は適切に型付けされている （型σ{\ displaystyle \ sigma}を持つ）と言われます。タイプ関係のインスタンスは、タイプ判定と呼ばれます 。タイピング判定の妥当性は、タイピング規則を使用して構築されたタイピング派生を提供することで示されます（ラインの上の前提により、ラインの下の結論を導き出すことができます）。単純型付きラムダ計算では、次の規則を使用します。

x：σ∈ΓΓ⊢x：σ{\ displaystyle {\ frac {x {\ mathbin {：}} \ sigma \ in \ Gamma} {\ Gamma \ vdash x {\ mathbin {：}} \ sigma}}}（ 1）	cはタイプTΓ⊢c：T {\ displaystyle {\ frac {c {\ text {はタイプ}} T} {\ Gamma \ vdash c {\ mathbin {：}} T}}}の定数です（ 2）
Γ、x：σ⊢e：τΓ⊢（λx：σ。e）:(σ→τ）{\ displaystyle {\ frac {\ Gamma、x {\ mathbin {：}} \ sigma \ vdash e {\ mathbin { ：}} \ tau} {\ Gamma \ vdash（\ lambda x {\ mathbin {：}} \ sigma。〜e）{\ mathbin {：}}（\ sigma \ to \ tau）}}}（3）	Γ⊢e1：σ→τΓ⊢e2：σΓ⊢e1e2：τ{\ displaystyle {\ frac {\ Gamma \ vdash e_ {1} {\ mathbin {：}} \ sigma \ to \ tau \ quad \ Gamma \ vdash e_ {2} {\ mathbin {：}} \ sigma} {\ Gamma \ vdash e_ {1}〜e_ {2} {\ mathbin {：}} \ tau}}}（4）

言葉で、

1. コンテキストでx {\ displaystyle x}のタイプがσ{\ displaystyle \ sigma}である場合、x {\ displaystyle x}のタイプはσ{\ displaystyle \ sigma}であることがわかります。
2. 項定数には適切な基本型があります。
3. x {\ displaystyle x}がある特定のコンテキストでタイプσ{\ displaystyle \ sigma}を持っている場合、e {\ displaystyle e}のタイプはτ{\ displaystyle \ tau}であり、x {\ displaystyleのない同じコンテキストでx}、λx：σ。 e {\ displaystyle \ lambda x {\ mathbin {：}} \ sigma。〜e}のタイプはσ→τ{\ displaystyle \ sigma \ to \ tau}です。
4. 特定のコンテキストで、e1 {\ displaystyle e_ {1}}のタイプがσ→τ{\ displaystyle \ sigma \ to \ tau}であり、e2 {\ displaystyle e_ {2}}のタイプがσ{\ displaystyle \ sigma }、e1 e2 {\ displaystyle e_ {1}〜e_ {2}}のタイプはτ{\ displaystyle \ tau}です。

閉じた用語の例、 つまり空のコンテキストで入力可能な用語は次のとおりです。

• すべてのタイプτ{\ displaystyle \ tau}、項λx：τ.x：τ→τ{\ displaystyle \ lambda x {\ mathbin {：}} \ tau .x {\ mathbin {：}} \ tau \ to \ tau}（恒等関数/ Iコンビネータ）、
• タイプσ、τ{\ displaystyle \ sigma、\ tau}の場合、項λx：σ.λy：τ.x：σ→τ→σ{\ displaystyle \ lambda x {\ mathbin {：}} \ sigma。\ lambda y {\ mathbin {：}} \ tau .x {\ mathbin {：}} \ sigma \ to \ tau \ to \ sigma}（Kコンビネータ）、および
• タイプτ、τ ′、τ″ {\ displaystyle \ tau、\ tau'、\ tau ''}の場合、項λx：τ→τ ′→τ″.λy：τ→τ′.λz：τ.xz（ yz）:(τ→τ ′→τ″）→（τ→τ′）→τ→τ″ {\ displaystyle \ lambda x {\ mathbin {：}} \ tau \ to \ tau '\ to \ tau' ' 。\ lambda y {\ mathbin {：}} \ tau \ to \ tau '。\ lambda z {\ mathbin {：}} \ tau .xz（yz）：（\ tau \ to \ tau' \ to \ tau ' '）\ to（\ tau \ to \ tau'）\ to \ tau \ to \ tau ''}（Sコンビネータ）。

これらは、組み合わせ論理の基本的な組み合わせの型付きラムダ計算です。

各タイプτ{\ displaystyle \ tau}には、順序o（τ）{\ displaystyle o（\ tau）}が割り当てられます。基本型の場合、o（T）= 0 {\ displaystyle o（T）= 0};関数型の場合、o（σ→τ）= max（o（σ）+ 1、o（τ））{\ displaystyle o（\ sigma \ to \ tau）= {\ mbox {max}}（o（\ sigma ）+ 1、o（\ tau））}。つまり、型の順序は、最も左にネストされた矢印の深さを測定します。したがって：

o（ι→ι→ι）= 1 {\ displaystyle o（\ iota \ to \ iota \ to \ iota）= 1} o（（ι→ι）→ι）= 2 {\ displaystyle o（（\ iota \ to \ iota）\ to \ iota）= 2}

意味論

固有の解釈と外部の解釈

大まかに言って、単純に型付けされたラムダ計算に意味を割り当てる方法は2つあります。より一般的には、型付き言語については、 組み込み型と外部型 、またはチャーチスタイルとカリー スタイルと呼ばれることもあります。組み込み/教会スタイルのセマンティクスは、適切に型付けされた用語にのみ意味を割り当てます。より正確には、型付け派生に直接意味を割り当てます。これには、タイプ注釈によってのみ異なる用語に異なる意味を割り当てることができるという効果があります。たとえば、アイデンティティ用語λx：int。 x {\ displaystyle \ lambda x {\ mathbin {：}} {\ mathtt {int}}。〜x}整数および識別項λx：bool。ブール値のx {\ displaystyle \ lambda x {\ mathbin {：}} {\ mathtt {bool}}。〜x}は、意味が異なる場合があります。 （古典的な意図された解釈は、整数の単位関数とブール値の単位関数です。）対照的に、外部/カレースタイルのセマンティクスは、型付けされていない言語で解釈されるため、型付けに関係なく用語に意味を割り当てます。このビューでは、λx：int。 x {\ displaystyle \ lambda x {\ mathbin {：}} {\ mathtt {int}}。〜x}およびλx：bool。 x {\ displaystyle \ lambda x {\ mathbin {：}} {\ mathtt {bool}}。〜x}は同じことを意味します（ つまり 、λxと同じことです。x {\ displaystyle \ lambda x。〜x}） 。

組み込みセマンティクスと外部セマンティクスの区別は、ラムダ抽象化の注釈の有無に関連付けられることがありますが、厳密に言えばこの使用法は不正確です。それは種類が文脈から推定することができるとき、注釈のない条件で、教会風のセマンティクスを与えることができるように、単に（型消去を通じて、 すなわち ）の種類を無視して注釈を付け条件でカレー風の意味を定義することが可能である（ つまり、 、型推論を通じて）。内在的アプローチと外的アプローチの本質的な違いは、タイピングルールが言語を定義していると見なされるか、またはより原始的な基礎言語のプロパティを検証する形式主義と見なされるかだけです。以下で説明するさまざまなセマンティック解釈のほとんどは、教会またはカレーの視点から見ることができます。

等式理論

単純型付きラムダ計算には、型なしラムダ計算と同じβη等価の等式理論がありますが、型の制限があります。ベータ削減の方程式

（λx：σ。t）u =βt{\ displaystyle（\ lambda x {\ mathbin {：}} \ sigma。〜t）\、u = _ {\ beta} t}

コンテキストΓ{\ displaystyle \ Gamma}で、Γ、x：σ⊢t：τ{\ displaystyle \ Gamma、x {\ mathbin {：}} \ sigma \ vdash t {\ mathbin {：}} \ tau} Γ⊢u：σ{\ displaystyle \ Gamma \ vdash u {\ mathbin {：}} \ sigma}、イータ削減の方程式

λx：σ。 tx =η​​t{\ displaystyle \ lambda x {\ mathbin {：}} \ sigma。〜t \、x = _ {\ eta} t}

Γ⊢t：σ→τ{\ displaystyle \ Gamma \ vdash t \！：\ sigma \ to \ tau}であり、x {\ displaystyle x}がt {\ displaystyle t}に無料で表示されない場合は常に保持されます。

操作上のセマンティクス

同様に、名前による呼び出し、値による呼び出し、または他の評価戦略を使用して、単純型付きラムダ計算の操作上のセマンティクスを型なしラムダ計算に関して修正できます。型付き言語に関しては、型安全性はこれらすべての評価戦略の基本的な特性です。さらに、以下で説明する強力な正規化プロパティは、評価戦略が単純に入力されたすべての用語で終了することを意味します。

カテゴリーセマンティクス

単純に型付けされたラムダ計算（βη{\ displaystyle \ beta \ eta}と同等）は、Lambekが最初に観察したデカルト閉カテゴリー（CCC）の内部言語です。特定のCCCが与えられた場合、対応するラムダ計算の基本型は単なるオブジェクトであり、用語は射です。逆に、単純に型指定されたすべてのラムダ計算は、オブジェクトが型であり、射が用語の等価クラスであるCCCを提供します。

対応を明確にするために、通常、デカルト積の型コンストラクターが上記に追加されます。デカルト積のカテゴリ性を保持するために、 ペアリング 、 射影 、および単位項の型規則を追加します。 2つの用語s：σ{\ displaystyle s {\ mathbin {：}} \ sigma}およびt：τ{\ displaystyle t {\ mathbin {：}} \ tau}が与えられると、用語（s、t）{\ displaystyle（ s、t）}のタイプはσ×τ{\ displaystyle \ sigma \ times \ tau}です。同様に、項u：τ1×τ2{\ displaystyle u {\ mathbin {：}} \ tau _ {1} \ times \ tau _ {2}}がある場合、項π1（u）：τ1{があります。 \ displaystyle \ pi _ {1}（u）{\ mathbin {：}} \ tau _ {1}}およびπ2（u）：τ2{\ displaystyle \ pi _ {2}（u）{\ mathbin {：} } \ tau _ {2}}ここで、πi{\ displaystyle \ pi _ {i}}はデカルト積の射影に対応します。タイプ1の単位項は 、（）{\ displaystyle（）}と記述され、「nil」と発音されて、最終オブジェクトです。等式理論も同様に拡張されているため、

π1（s：σ、t：τ）= s：σ{\ displaystyle \ pi _ {1}（s {\ mathbin {：}} \ sigma、t {\ mathbin {：}} \ tau）= s {\ mathbin {：}} \ sigma}π2（s：σ、t：τ）= t：τ{\ displaystyle \ pi _ {2}（s {\ mathbin {：}} \ sigma、t {\ mathbin {：} } \ tau）= t {\ mathbin {：}} \ tau}（π1（u：σ×τ）、π2（u：σ×τ））= u：σ×τ{\ displaystyle（\ pi _ {1 }（u {\ mathbin {：}} \ sigma \ times \ tau）、\ pi _ {2}（u {\ mathbin {：}} \ sigma \ times \ tau））= u {\ mathbin {：}} \ sigma \ times \ tau} t：1 =（）{\ displaystyle t {\ mathbin {：}} 1 =（）}

この最後は、「 tの型が1の場合、nilになります 」と読みます。

次に、タイプをオブジェクトとして使用することにより、上記をカテゴリに変換できます。射影σ→τ{\ displaystyle \ sigma \ to \ tau}は、ペア（x：σ、t：τ）{\ displaystyle（x {\ mathbin {：}} \ sigma、t {\ mathbin {： }} \ tau）}ここで、 xは（タイプσ{\ displaystyle \ sigma}の）変数で、 tは（タイプτ{\ displaystyle \ tau}の）用語であり、（オプションで） x 。通常どおり、カレーとアプリケーションから閉鎖されます。

より正確には、デカルト閉カテゴリーのカテゴリーと単純型付きラムダ理論のカテゴリーの間にファンクターが存在します。

線形型システムを使用して、このケースを閉じた対称モノイドカテゴリに拡張するのが一般的です。これは、CCCが閉じた対称モノイドの特別なケースであり、通常はセットのカテゴリと見なされるためです。これは集合論の基礎を築くのに適していますが、より一般的なトポは優れた基礎を提供するようです。

証明論的セマンティクス

単純に型付けされたラムダ計算は、カリー-ハワード同型を介して命題直観主義的論理の含意的な断片、すなわち最小論理に密接に関連しています。

代替構文

上記のプレゼンテーションは、単純に型指定されたラムダ計算の構文を定義する唯一の方法ではありません。代替案の1つは、Hindley–Milner型推論による用語の適切な型付けを保証しながら、型注釈を完全に削除することです（構文は型付けされていないラムダ計算と同一です）。推論アルゴリズムは終了し、健全で、完全です。用語が入力可能になるたびに、アルゴリズムはそのタイプを計算します。より正確には、多くの場合、注釈のない用語（λx。x {\ displaystyle \ lambda x。〜x}など）には複数のタイプ（int→int {\ displaystyle {\ mathtt {int }} \ to {\ mathtt {int}}}、bool→bool {\ displaystyle {\ mathtt {bool}} \ to {\ mathtt {bool}}}など、すべてプリンシパルタイプα→のインスタンスα{\ displaystyle \ alpha \ to \ alpha}）。

単純に型付けされたラムダ計算の別の代替表現は、 双方向型チェックに基づいています。これは、Hindley–Milnerの推論よりも多くの型注釈を必要としますが、説明は簡単です。型システムは、 チェックと合成の両方を表す2つの判断に分割され、Γ⊢e⇐τ{\ displaystyle \ Gamma \ vdash e \ Leftarrow \ tau}とΓ⊢e⇒τ{\ displaystyle \ Gamma \ vdash e \ Rightarrowで記述されます。 \ tau}。操作上、三の成分Γ{\ displaystyle \ガンマ}、E {\ displaystyle電子}、及びτ{\ displaystyleの\タウは}チェック判定Γ⊢e⇐τ{\ displaystyle \ガンマ\ vdash E \ LEFTARROWへのすべての入力であります\ tau}、合成判定Γ⊢e⇒τ{\ displaystyle \ Gamma \ vdash e \ Rightarrow \ tau}は入力としてΓ{\ displaystyle \ Gamma}とe {\ displaystyle e}のみを取り、タイプτ{出力として\ displaystyle \ tau}。これらの判断は、次のルールを介して導出されます。

x：σ∈ΓΓ⊢x⇒σ{\ displaystyle {\ frac {x {\ mathbin {：}} \ sigma \ in \ Gamma} {\ Gamma \ vdash x \ Rightarrow \ sigma}}}	cはTΓ⊢c⇒T{\ displaystyle {\ frac {c {\ text {は型}} T} {\ Gamma \ vdash c \ Rightarrow T}}}の定数の定数です
Γ、x：σ⊢e⇐τΓ⊢λx。 e⇐σ→τ{\ displaystyle {\ frac {\ Gamma、x {\ mathbin {：}} \ sigma \ vdash e \ Leftarrow \ tau} {\ Gamma \ vdash \ lambda x。〜e \ Leftarrow \ sigma \ to \ tau}}}	Γ⊢e1⇒σ→τΓ⊢e2⇐σΓ⊢e1e2⇒τ{\ displaystyle {\ frac {\ Gamma \ vdash e_ {1} \ Rightarrow \ sigma \ to \ tau \ quad \ Gamma \ vdash e_ {2} \左矢印\ sigma} {\ Gamma \ vdash e_ {1}〜e_ {2} \ Rightarrow \ tau}}}
Γ⊢e⇒τΓ⊢e⇐τ{\ displaystyle {\ frac {\ Gamma \ vdash e \ Rightarrow \ tau} {\ Gamma \ vdash e \ Leftarrow \ tau}}}	Γ⊢e⇐τΓ⊢（e：τ）⇒τ{\ displaystyle {\ frac {\ Gamma \ vdash e \ Leftarrow \ tau} {\ Gamma \ vdash（e {\ mathbin {：}} \ tau）\ Rightarrow \タウ}}}

ルールに注意してください–チェックまたは合成の判断を慎重に選択することを除いて、上記のルール（1）〜（4）とほぼ同じです。これらの選択は次のように説明できます。

1. x：σ{\ displaystyle x {\ mathbin {：}} \ sigma}がコンテキストにある場合、x {\ displaystyle x}のタイプσ{\ displaystyle \ sigma}を合成できます。
2. 項定数のタイプは固定されており、合成できます。
3. そのλxを確認します。 e {\ displaystyle \ lambda x。〜e}のタイプはσ→τ{\ displaystyle \ sigma \ to \ tau}であり、コンテキストをx：σ{\ displaystyle x {\ mathbin {：}} \で拡張しますシグマ}とe {\ displaystyle e}のタイプがτ{\ displaystyle \ tau}であることを確認します。
4. e1 {\ displaystyle e_ {1}}がタイプσ→τ{\ displaystyle \ sigma \ to \ tau}を合成し、e2 {\ displaystyle e_ {2}}がタイプσ{\ displaystyle \ sigmaに対してチェックする場合}（同じコンテキストで）、e1 e2 {\ displaystyle e_ {1}〜e_ {2}}はタイプτ{\ displaystyle \ tau}を合成します。

合成のルールは上から下に読み、チェックのルールは下から上に読みます。特に、ruleのラムダ抽象化に関する注釈は必要ないことに注意してください。バインドされた変数の型は、関数をチェックする型から推測できるためです。最後に、ルールを次のように説明します。

1. e {\ displaystyle e}のタイプがτ{\ displaystyle \ tau}であることを確認するには、タイプτ{\ displaystyle \ tau}を合成すれば十分です。
2. e {\ displaystyle e}がτ{\ displaystyle \ tau}型に対してチェックする場合、明示的に注釈が付けられた用語（e：τ）{\ displaystyle（e {\ mathbin {：}} \ tau）}はτ{\ displaystyle \タウ}。

これらの最後の2つの規則は合成とチェックを強制するため、「十分な」タイプの注釈を挿入する限り、双方向システムで適切に型付けされているが注釈のない用語をチェックできることは容易にわかります。そして実際、注釈はβ-redexeでのみ必要です。

一般的な観察

標準的なセマンティクスを考えると、単純に型付けされたラムダ計算は強く正規化されます。つまり、型の適切な項は常に値、つまりλ{\ displaystyle \ lambda}抽象化に還元されます。これは、タイピング規則で再帰が許可されていないためです。固定小数点コンビネーターとループ項Ω=（λx。xx）（λx。xx）{\ displaystyle \ Omega =（\ lambda x。 〜x〜x）（\ lambda x。〜x〜x）}。言語に再帰を追加するには、特殊な演算子fixα{\ displaystyle {\ mathtt {fix}} _ {\ alpha}}のタイプ（α→α）→α{\ displaystyle（\ alpha \ to \ alpha）を修正します。 \ to \ alpha}または一般的な再帰型を追加しますが、どちらも強力な正規化を排除します。

それは強く正規化されているため、単純に型指定されたラムダ計算プログラムが停止するかどうかを決定できます。実際、 常に停止します。したがって、言語はチューリング完全ではないと結論付けることができます。

重要な結果

• Taitは1967年に、β{\ displaystyle \ beta} -reductionが強く正規化されることを示しました。当然の結果として、βη{\ displaystyle \ beta \ eta}-同等性は決定可能です。 1977年にStatmanは、正規化の問題は初等再帰ではなく、Mairson（1992）によって簡略化された証拠であることを示しました。 1991年にBergerとSchwichtenbergによって、純粋に意味論的な正規化の証明（評価による正規化を参照）が与えられました。
• βη{\ displaystyle \ beta \ eta}等価の統一問題は決定不能です。 Huetは1973年に3次の統一は決定不能であることを示し、1978年にBaxterによって、1981年にGoldfarbによって2次の統合がすでに決定不能であることを示すことで改善されました。高次マッチング（1つの用語のみに実存変数が含まれる統一）が決定可能であるという証明が2006年にColin Stirlingによって発表され、2009年に完全な証明が公開されました。
• タイプ（o→o）→（o→o）{\ displaystyle（o \ to o）\ to（o \ to o）}（教会の数字）の項で自然数をエンコードできます。 Schwichtenbergは1976年に、λ→{\ displaystyle \ lambda ^ {\ to}}で拡張多項式がチャーチ数の関数として正確に表現できることを示しました。これらはおおよそ、条件演算子の下で閉じられた多項式です。
• λ→{\ displaystyle \ lambda ^ {\ to}}の完全なモデルは、ベース型をセット理論関数空間によりセットおよび関数型として解釈することにより与えられます。フリードマンは、基本型が無限集合によって解釈される場合、この解釈がβη{\ displaystyle \ beta \ eta}-等値について完全であることを1975年に示しました。 Statmanは1983年に、βη{\ displaystyle \ beta \ eta}の等価性が、通常は曖昧である最大の等価性である 、つまり、型置換（ StatmanのTypical Ambiguity Theorem ） の下で閉じていることを示しました。これの帰結は、 有限モデルの特性が保持されることです。つまり、有限集合は、βη{\ displaystyle \ beta \ eta}-同等性によって識別されない用語を区別するのに十分です。
• Plotkinは1973年に、ラムダ項で定義可能なモデルの要素を特徴付ける論理関係を導入しました。 1993年に、JungとTiurynは、一般的な形式の論理関係（さまざまなアリティを持つKripke論理関係）がラムダ定義可能性を正確に特徴づけることを示しました。 PlotkinとStatmanは、有限集合から生成されたモデルの特定の要素がラムダ項で定義可能かどうかを決定できると推測しました（ Plotkin–Statman conjecture ）。推測は1993年にローダーによって偽であることが示されました。

ノート