Charakterisierung von lambda-Begriffe, die union-Typen

Question

Viele Lehrbücher decken Kreuzung Typen in der lambda-Kalkül.Die Eingabe von Regeln für die Kreuzung kann wie folgt definiert werden (auf der Oberseite des einfach typisierten lambda-Kalkül mit subtypisierung):

$$ \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 : op} (\oben I) $$

Kreuzung Arten haben interessante Eigenschaften in Bezug auf die Normalisierung:

• Ein lambda-Ausdruck geschrieben werden kann, ohne mit der $ op I$ Regel iff ist es dringend zu normalisieren.
• Ein lambda-Ausdruck, gesteht ein Typ nicht mit $ op$ iff es hat eine normale form.

Was ist, wenn anstelle der Zugabe von Kreuzungen, fügen wir Gewerkschaften?

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

Hat der lambda-Kalkül mit einfachen Typen, subtypisierung und Gewerkschaften haben Sie interessante ähnliche Eigenschaft?Wie können die Bedingungen typable mit union charakterisiert werden?

Answer 1

Im ersten system, wie du es nennst, subtypisierung sind diese zwei Regeln:

$$\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 ∧ T_2 \vdash M:S}(∧E_2)$$

Sie entsprechen Beseitigung Regeln für $∧$;ohne Sie, die Binde $∧$ ist mehr oder weniger nutzlos.

In dem zweiten system (mit Verknüpfungen, $ ∨ $ und $→$, auf welche wir könnten auch ein $ δ$), die über subtypisierung Regeln sind irrelevant, und ich denke, dass die dazugehörigen Regeln, die Sie im Sinn hatte, sind die folgenden:

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

Für was es Wert ist, dieses system ermöglicht type $(λx.I)Ω:A→A$ (der ${⊥}E$ rule), die nicht eingegeben werden, mit nur einfache Typen, die eine normale form, aber nicht stark normalisierend.

---

Zufällige Gedanken:(vielleicht ist das eine Frage Wert, auf TCS)

Das führt mich zu der Vermutung, dass der Verwandte Eigenschaften sind so etwas wie:

• ein λ-term $M$ räumt ein Typ nicht mit $ δ$ iff $MN$ hat eine normale form für alle $N$, die hat eine normale form.($δ$ fehlschlägt beide tests, aber die oben genannten λ-Ausdruck übergeben)
• ein λ-term $M$ geschrieben werden kann, ohne mit der ${⊥}E$ rule iff $MN$ ist stark Normalisierung für alle stark normalisierend $N$.

Übung: beweisen Sie mich falsch.

Auch scheint es sich um ein degenerierter Fall ist, sollten wir vielleicht überlegen, dieser Kerl in die Bild.Soweit ich mich erinnere, würde es ermöglichen, erhalten Sie $A ∨ (A → {⊥})$?

Answer 2

Ich möchte nur erklären, warum Schnitttypen gut geeignet sind, um Normalisierungsklassen (stark, Kopf oder schwach) zu charakterisieren, während andere Typsysteme dies nicht können. (Einfach-typed oder System f).

Der Hauptunterschied besteht darin, dass Sie sagen müssen: "Wenn ich $ M_2 $ und $ M_1 → M_2 $ eingeben kann, kann ich $ M_1 $ eingeben." Dies gilt oft nicht bei Nicht-Interpretationstypen, da ein Begriff dupliziert werden kann:

$$ ( lambda x.mxx) n → mnn $$

Und dann eingeben $ mnn $ bedeutet, dass Sie beide Vorkommen von $ n $, aber nicht mit demselben Typ eingeben können, z. Sie können dies in: $$ M: t_1 Wedge T_2 → T_1 Wedge T_2 → T_3 qquad n: t_1 Wedge t_2 $$ verwandeln, und dann ist der entscheidende Schritt jetzt wirklich einfach: $$ ( lambda x.mxx) : T_1 keil t_2 → t_3 qquad n: t_1 wedge t_2 $$ so $ ( lambda x.mxx) n $ kann durch getippte Kreuzungsarten typisiert.

Nun zu Gewerkschaftstypen: Angenommen, Sie können $ ( lambda x.xx) ( lambda yy) $ mit einem Gewerkschaftstyp eingeben, dann können Sie auch $ lambda x.xx $ eingeben und dann für einige Typen $ s, t_1 erhalten , dots $ $$ x: t_1 vee t_2 vee dots vee t_n ⊢xx: s $$, aber Sie müssen immer noch beweisen Sogar Is $ S $ ist ein Gewerkschaftstyp.

Aus diesem Grund glaube ich nicht, dass die Normalisierung für Gewerkschaftstypen eine einfache Charakterisierung gibt.