Geben Sie Inferenz mit Produkttypen ein

Question

Ich arbeite an einem Compiler für eine verkettende Sprache und möchte Typ -Inferenzunterstützung hinzufügen. Ich verstehe Hindley - Milner, aber ich habe die Typtheorie im Laufe dessen gelernt, also bin ich mir nicht sicher, wie ich sie anpassen kann. Ist das folgende System solide und leitbar abgeleitet?

Ein Begriff ist ein wörtlicher, eine Zusammensetzung von Begriffen, ein Zitat eines Begriffs oder ein primitives.

$$ e :: = x : big | : e : e : big | : [e] : big | : dots $$

Alle Begriffe bezeichnen Funktionen. Für zwei Funktionen $ e_1 $ und $ e_2 $, $ e_1 : e_2 = e_2 circ e_1 $, das heißt, das Nebeneinander bezeichnet eine umgekehrte Komposition. Literale bezeichnen niladische Funktionen.

Die anderen Begriffe als Komposition haben grundlegende Typregeln:

$$ dfrac {} {x: iota} text {[lit]} dfrac { gamma vdash e: sigma} { gamma vdash [e]: forall alpha. Alpha to sigma times alpha} text {[quot]}, alpha text {nicht frei in} gamma $$

Bemerkenswerterweise sind Regeln für die Anwendung, da verkettende Sprachen es fehlt.

Ein Typ ist entweder ein wörtlicher, eine Typvariable oder eine Funktion von Stapeln zu Stapeln, wobei ein Stapel als rechtsgebundenes Tupel definiert wird. Alle Funktionen sind implizit polymorph in Bezug auf den „Rest des Stapels“.

$$ begin {aligned} tau &: = iota : big | : alpha : big | : rho to rho rho &: = () : Big | : Tau Times rho sigma & :: = tau : big | : forall alpha. : sigma end {ausgerichtet} $$

Dies ist das erste, was verdächtig erscheint, aber ich weiß nicht genau, was daran los ist.

Um die Lesbarkeit zu unterstützen und Klammern zu verringern, gehe ich davon aus, dass $ a : b = b mal (a) $ in Typschemata. Ich werde auch einen Großbuchstaben für eine Variable verwenden, die einen Stapel und nicht einen einzelnen Wert bezeichnet.

Es gibt sechs Primitive. Die ersten fünf sind ziemlich harmlos. dup Nimmt den obersten Wert und produziert zwei Kopien davon. swap ändert die Reihenfolge der beiden obersten Werte. pop Verwaltet den Top -Wert. quote Nimmt einen Wert an und erzeugt ein Angebot (Funktion), das ihn zurückgibt. apply wendet ein Angebot auf den Stapel an.

$$ begin {aligned} mathtt {dUp} &: forall a b. : a : b to a : b : b mathtt {swap} &: forall a b c . : A : b : c to a : c : b mathtt {pop} & :: forall a b. : A : b to a mathtt {Quote} & :: forall a b. : a : b to a : ( forall C. c bis c : b) mathtt {anwenden} & :: forall a b. : a :( a bis B) bis B end {ausgerichtet} $$

Der letzte Kombinator, compose, sollten zwei Zitate nehmen und den Typ ihrer Verkettung zurückgeben, dh $ [e_1] : [e_2] : mathtt {kompose} = [e_1 : e_2] $. In der statisch getypten verkettenden Sprache Katze, die Art von compose ist sehr einfach.

$$ mathtt {compose} :: forall abc d. : a :( b bis c) :( C bis d) bis a :( b bis d) $$

Dieser Typ ist jedoch zu restriktiv: Es erfordert, dass die Produktion der ersten Funktion genau übereinstimmen der Verbrauch der zweiten. In Wirklichkeit müssen Sie unterschiedliche Typen annehmen und sie dann vereinen. Aber wie würden Sie diesen Typ schreiben?

acht

Wenn Sie $ setminus $ a Unterschied von zwei Typen, dann ich denken Sie können die Art von schreiben compose korrekt.

$$ mathtt {compose} :: forall abcd e. : a :( b bis c) :( d to e) to a : (d setminus c) : b to ((C setminus d) : e)) $$

Dies ist noch relativ einfach: compose Nimmt eine Funktion $ f_1: b bis c $ und eine $ f_2: d bis e $. Sein Ergebnis verbraucht $ B $ auf dem Verbrauch von $ f_2 $ nicht produziert von $ f_1 $ und produziert $ d $ bei der Produktion von $ f_1 $ nicht konsumiert von $ f_2 $. Dies gibt die Regel für die gewöhnliche Komposition.

$$ dfrac { gamma vdash e_1: forall a b. : a to b quad gamma vdash e_2: forall c d. c to d} { gamma vdash e_1 e_2: ((((((() C setminus b) : a to ((b setminus c) : d))} text {[comp]} $$

Ich weiß jedoch nicht, dass dieses hypothetische $ setminus $ tatsächlich irgendetwas entspricht, und ich habe es lange genug in Kreisen verfolgt, dass ich glaube, dass ich eine falsche Wendung genommen habe. Könnte es ein einfacher Unterschied von Tupeln sein?

$$ begin {align} forall A. () setminus a & = () forall A. a setminus () & = a forall abc D. ab setminus cd & = b setminus D textit {iff} a = c text {sonst} & = textit {undefined} end {align} $$

Gibt es etwas schrecklich gebrochenes daran, das ich nicht sehe, oder bin ich auf dem richtigen Weg? (Ich habe wahrscheinlich einige dieser Dinge falsch quantifiziert und würde auch die Korrekturen in diesem Bereich schätzen.)

Answer 1

Der folgende Rang-2-Typ $$ text {compose}: forall abc delta. delta ( forall alpha. alpha a to alpha b) ( forall beta. beta b to beta c) to delta ( forall gamma. gamma to delta ( forall gamma. A bis gamma c) $$ scheint ausreichend allgemein zu sein. Es ist viel polymorpher als der in der Frage vorgeschlagene Typ. Hier variable über zusammenhängende Stapelbrocken quantifizieren, die Multi-Argument-Funktionen erfassen.

Griechische Buchstaben werden nur für die rest-der-Stapel-Variablen verwendet.

Es drückt die Einschränkungen aus, dass der Ausgangsstapel des ersten Elements auf dem Stapel mit dem Eingangsstapel des zweiten Elements übereinstimmt. Angemessen, die Variable $ b $ für die beiden Argumente zu instanziieren, ist die Möglichkeit, die Einschränkungen ordnungsgemäß zu funktionieren, anstatt eine neue Operation zu definieren, wie Sie in der Frage vorschlagen.

Type Checking Rang-2-Typen sind im Allgemeinen unentscheidbar, obwohl einige Arbeiten durchgeführt wurden, die in der Praxis gute Ergebnisse liefern (für Haskell):

• Simon L. Peyton Jones, Dimitrios Vytiniotis, Stephanie Weirich, Mark Shields: Praktische Typinferenz für willkürliche Rangtypen. J. Funct. Programm. 17 (1): 1-82 (2007)

Die Typ -Regel für die Komposition lautet einfach:

$$ dfrac { gamma vdash e_1: forall alpha. alpha a to alpha b qquad gamma vdash e_1: forall alpha. alpha b to alpha c} { gamma vdash e_1 e_2: forall alpha. alpha a to alpha c} $$

Damit das Typsystem im Allgemeinen funktioniert, benötigen Sie die folgende Spezialisierungsregel:

$$ dfrac { gamma vdash e: forall alpha. alpha a to alpha b} { gamma vdash e: forall alpha.c a to alpha c b} $$