Charakterisierung von Lambda-Termen mit Unionstypen

29

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

ΓM:T1ΓM:T2ΓM:T1T2(I)ΓM:(I)

Schnittpunkttypen haben interessante Eigenschaften in Bezug auf die Normalisierung:

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

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

ΓM:T1ΓM:T1T2(I1)ΓM:T2ΓM:T1T2(I2)

Hat die Lambda-Rechnung mit einfachen Typen, Untertypen und Vereinigungen eine interessante ähnliche Eigenschaft? Wie lassen sich die mit union typisierbaren Begriffe charakterisieren?

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:

11

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

Γ,x:T1M:SΓ,x:T1T2M:S(E1)Γ,x:T2M:SΓ,x:T1T2M:S(E2)

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:

Γ,x:T1M:SΓ,x:T2M:SΓ,x:T1T2M:S(E)Γ,x: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)Ω:AAE


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)MMNNδ
  • Ein λ-Term kann ohne die Regel eingegeben werden, wenn für alle stark normalisierenden stark normalisiert .MEMNN

Ü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.xx)(λ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
16

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:M2M1M2M1

(λx.Mxx)NMNN

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.MNNN

M:T1T2T3N:T1N:T2
M:T1T2T1T2T3N:T1T2
(λx.Mxx):T1T2T3N:T1T2
(λ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.(λx.xx)(λy.y)λx.xxS,T1,

x:T1T2Tnxx:S
ix:Tixx:SS

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

jmad
quelle