Charakterisierung von Lambda-Termen mit Unionstypen

Viele Lehrbücher behandeln Schnittmengenarten in der Lambda-Rechnung. Die Typisierungsregeln für die Schnittmenge können wie folgt definiert werden (zusätzlich zur einfach getippten Lambda-Rechnung mit Subtypisierung):

\frac{Γ ⊢ M : T_{1} Γ ⊢ M : T_{2}}{Γ ⊢ M : T_{1} \land T_{2}} (\land I) \frac{}{Γ ⊢ M : ⊤} (⊤ I)

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

Schnittpunkttypen haben interessante Eigenschaften in Bezug auf die Normalisierung:

Ein Lambda-Ausdruck kann ohne die eingegeben werden rule iff es stark Normalisieren ist. $\top I$
Ein Lambda-Term lässt einen Typ zu, der nicht enthält, wenn er eine normale Form hat. $\top$

Was ist, wenn wir statt Kreuzungen Gewerkschaften hinzufügen?

\frac{Γ ⊢ M : T_{1}}{Γ ⊢ M : T_{1} \lor T_{2}} (\lor I_{1}) \frac{Γ ⊢ M : T_{2}}{Γ ⊢ M : T_{1} \lor T_{2}} (\lor I_{2})

$\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 die Lambda-Rechnung mit einfachen Typen, Untertypen und Vereinigungen eine interessante ähnliche Eigenschaft? Wie lassen sich die mit union typisierbaren Begriffe charakterisieren?

lambda-calculus type-theory logic Gilles 'SO - hör auf böse zu sein'
quelle

Interessante Frage. Könnten Sie sagen, dass Schnittstellen von OOP dem entsprechen?

Raphael

Vielleicht interessiert dich das cs.cmu.edu/~rwh/courses/refinements/papers/Barbaneraetal95/…

Fabio F.

Antworten:

Im ersten System, das Sie als Subtyping bezeichnen, gelten folgende zwei Regeln:

\frac{Γ, x : T_{1} ⊢ M : S}{Γ, x : T_{1} \land T_{2} ⊢ M : S} (\land E_{1}) \frac{Γ, x : T_{2} ⊢ M : S}{Γ, x : T_{1} \land T_{2} ⊢ M : S} (\land E_{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 ∧ T_2 \vdash M:S}(∧E_2)$

Sie entsprechen den Eliminierungsregeln für ; ohne dass sie die Binde ist mehr oder weniger nutzlos. $∧$ $∧$

Im zweiten System (mit den Konnektiven und , zu denen wir auch ein hinzufügen ) sind die oben genannten Subtypisierungsregeln irrelevant, und ich denke, dass die begleitenden Regeln, an die Sie gedacht haben, die folgenden sind: $∨$ $→$ $⊥$

\frac{Γ, x : T_{1} ⊢ M : S Γ, x : T_{2} ⊢ M : S}{Γ, x : T_{1} \lor T_{2} ⊢ M : S} (\lor E) \frac{}{Γ, x : ⊥ ⊢ M : S} (⊥ E)

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

Dieses System erlaubt es, (unter Verwendung der Regel) zu , was nicht nur mit einfachen Typen möglich ist, die eine normale Form haben, aber nicht stark normalisieren . $(λx. I)Ω:A→A$ ${⊥}E$

Zufällige Gedanken: (Vielleicht lohnt es sich, bei TCS nachzufragen)

Dies lässt mich vermuten, dass die verwandten Eigenschaften etwa so sind:

ein λ-Term einen Typ zu, der nicht wenn eine Normalform für alle hat, die eine Normalform haben. ( beide Tests nicht, aber der obige λ-Term besteht sie) $M$ $⊥$ $MN$ $N$ $δ$
Ein λ-Term kann ohne die Regel eingegeben werden, wenn für alle stark normalisierenden stark normalisiert . $M$ ${⊥}E$ $MN$ $N$

Übung: Beweise, dass ich falsch liege.

Es scheint auch ein degenerierter Fall zu sein, vielleicht sollten wir darüber nachdenken, diesen Typen in das Bild aufzunehmen. So weit ich mich erinnere, würde es erlauben, ? $A ∨ (A → {⊥})$

Stéphane Gimenez
quelle

Ein guter Punkt zu den Subtypisierungsregeln: Sie zeigen, dass Vereinigungstypen nicht annähernd so natürlich sind wie Schnittpunkte (die orthogonal zu Pfeilen geschrieben werden). Über den zweiten Teil muss ich noch etwas nachdenken.

Gilles 'SO - hör auf böse zu sein'

Ich denke, beantwortet die Übung, wenn Sie über Gewerkschaftstypen sprechen.

M = (λ x . x x) (λ y . y)

$M=(\lambda x.xx)(\lambda y.y)$

Jmad

Über call / cc: Es braucht mehr als nur Lambda-Terme (wie Lambda-Mu-Terme oder ein anderes Framework), aber Typsysteme sind komplexere logische Systeme, in denen Unionstypen irrelevant sein können.

jmad

@jmad: In der Tat werden Kreuzungstypen benötigt, um diesen Begriff einzugeben :-( Vielleicht wäre es interessant, Gewerkschaften und Kreuzungen zusammen zu betrachten?

Stéphane Gimenez

Ich wäre an einem λ-Term interessiert, den man mit Vereinigungstypen (rs. Mit Kreuzungstypen), aber nicht mit einfachen Typen (rs. Mit Kreuzungstypen) schreiben kann.

jmad

Ich möchte nur erklären, warum Schnittpunkttypen gut zur Charakterisierung von Normalisierungsklassen (stark, kopf oder schwach) geeignet sind, während andere Typsysteme dies nicht können. (einfach eingegeben oder System F).

Der Hauptunterschied besteht darin, dass Sie sagen müssen: "Wenn ich und dann kann ich ". Dies gilt häufig nicht für Nicht-Schnittmenge-Typen, da ein Begriff dupliziert werden kann: $M_2$ $M_1→M_2$ $M_1$

(λ x . M x x) N \to M N N

$(\lambda x.Mxx)N → MNN$

und dann die Eingabe bedeutet , dass Sie beide Vorkommen geben können , aber nicht mit der gleichen Art, zum Beispiel Mit Kreuzungstypen , die Sie dies in umwandeln können: und dann ist der entscheidende Schritt jetzt ganz einfach: also kann mit Schnittpunkttypen eingegeben werden. $MNN$ $N$

M : T_{1} \to T_{2} \to T_{3} N : T_{1} N : T_{2}

$M:T_1→T_2→T_3 \qquad N:T_1 \qquad N:T_2$

M : T_{1} \land T_{2} \to T_{1} \land T_{2} \to T_{3} N : T_{1} \land T_{2}

$M:T_1\wedge T_2→T_1\wedge T_2→T_3 \qquad N:T_1\wedge T_2$

(λ x . M x x) : T_{1} \land T_{2} \to T_{3} N : T_{1} \land T_{2}

$(\lambda x.Mxx):T_1\wedge T_2→T_3 \qquad N:T_1\wedge T_2$

(λ x . M x x) N

$(\lambda x.Mxx)N$

Nun zu Vereinigungstypen: Angenommen, Sie können mit einem Vereinigungstyp , dann können Sie auch und dann für einige Typen Aber Sie immer noch , dass für jeden zu beweisen , haben , , die sogar unmöglich scheint , ist ein Union - Typ ist. $(\lambda x.xx)(\lambda y.y)$ $\lambda x.xx$ $S, T_1, \dots$

x : T_{1} \lor T_{2} \lor \dots \lor T_{n} ⊢ x x : S

$x : T_1\vee T_2 \vee \dots \vee T_n ⊢xx:S$

i

$i$

x : T_{i} ⊢ x x : S

$x:T_i⊢xx:S$

S

$S$

Aus diesem Grund glaube ich nicht, dass es eine einfache Charakterisierung der Normalisierung für Unionstypen gibt.

jmad
quelle