組合タイプを持つラムダテルムの特性評価

Question

多くの教科書は、ラムダカルクルスの交差点をカバーしています。交差点のタイピングルールは、次のように定義できます（サブタイピングを使用して、単にタイプしたLambda-Calculusの上）：

$$ dfrac { gamma vdash m：t_1 quad gamma vdash m：t_2} { gamma vdash m：t_1 wedge t_2}（ wedge i） qquad qquad dfrac {} { gamma vdash m： top}（ top i）$$

交差タイプには、正規化に関して興味深い特性があります。

• Lambda-Termは、$ top i $ルールを使用することなく入力できます。
• Lambda-Termは、通常のフォームを持っている$ top $ iffを含む型を認めています。

交差点を追加する代わりに、組合を追加した場合はどうなりますか？

$$ dfrac { gamma vdash m：t_1} { gamma vdash m：t_1 vee t_2}（ vee i_1） qquad qquad dfrac { gamma vdash m：t_2} { gamma vdash M：T_1 vee t_2}（ vee i_2）$$

シンプルなタイプ、サブタイピング、および組合を備えたラムダカルクルスには、興味深い同様の特性がありますか？ユニオンで典型的な用語をどのように特徴づけることができますか？

Answer 1

最初のシステムでは、あなたがサブタイピングと呼ぶものは、これらの2つのルールです。

$$ dfrac {γ、x：t_1 vdash m：s} {γ、x：t_1∧t_2 vdash m：s}（∧e_1） quad dfrac {γ、x：t_2 vdash m：s} {γ、X：T_1

それらは、$∧$の排除ルールに対応しています。それらがなければ、接続$∧$は多かれ少なかれ役に立たない。

2番目のシステム（コネクティブ$∨$および$→$を使用して、$⊥$を追加することもできます）では、上記のサブタイピングルールは無関係であり、伴う添付のルールは次のとおりです。

$$ dfrac {γ、x：t_1 vdash m：s quadγ、x：t_2 vdash m：s} {γ、x：t_1∨t_2 vdash m：s}（∨e） quad dfrac {} {γ、x：{⊥} vdash m：s}（{⊥} e）$$

それが価値のあるものについては、このシステムでは、$（λx。i）ω：a→a $（$ {⊥} e $ルールを使用）と入力することができます。強く正常化していません。

---

ランダムな考え：（これはTCSで尋ねる価値があるかもしれません）

これにより、関連するプロパティは次のようなものであると推測することになります。

• λ-Term $ m $は、$⊥$ iff $ mn $を含む型を認めています。$ $ $ $は、通常のフォームを持つすべての$ n $に対して通常のフォームを持っています。 （$Δ$は両方のテストに失敗しますが、上記のλ項はそれらを渡します）
• λ-Term $ m $は、$ {⊥} e $ルールiff $ mn $を使用せずに入力できます。

エクササイズ： 私が間違っていることを証明してください。

また、それは退化したケースのようです、多分私たちは追加を検討する必要があります この男 写真に。覚えている限り、$ a∨（a→{⊥}）$を取得できますか？

Answer 2

他のタイプのシステムはできないのに対し、交差点タイプが正常化のクラス（強い、頭、または弱い）を特徴付けるのに適している理由を説明したいだけです。 （単純なタイプまたはシステムf）。

重要な違いは、「$ m_2 $と$ m_1→m_2 $を入力できれば、$ m_1 $を入力できます」と言わざるを得ません。この用語を複製できるため、これはしばしば非交差タイプでは当てはまりません。

$$（ lambda x.mxx）n→mnn $$

そして、$ MNN $を入力すると、$ N $の出来事を入力できるが、たとえば$$ M：T_1→T_2→T_3 QQUAD N：T_1 QQUAD N：T_2 $$を交差点タイプで入力できることを意味します。これを$$ M：T_1 WEDGE T_2→T_1 WEDGE T_2→T_3 QQUAD N：T_1 WEDGE T_2 $$に変換できます。 ：T_1 WEDGE T_2→T_3 QQQUAD N：T_1 WEDGE T_2 $$ SO $（ Lambda X.MXX）can can can by交差点型

ユニオンタイプについて次に：$（ lambda x.xx）（ lambda yy）$をいくつかのユニオンタイプで入力できるとします。$ lambda x.xx $を入力してから、いくつかのタイプ$ s、t_1を取得することもできます。 、 dots $ $$ x：t_1 vee t_2 vee dots Vee t_n $ s $はユニオンタイプです。

これが、組合タイプの正規化について簡単な特徴づけがあるとは思わない理由です。