Höherrangiger Polymorphismus ohne explizite Anwendung oder Subtypisierung?

7

Daher kenne ich zwei Hauptstrategien für einen höherrangigen Polymorphismus in einer Sprache:

  • Polymorphismus im System-F-Stil, bei dem Funktionen explizit typisiert werden und die Instanziierung explizit über die Typanwendung erfolgt. Diese Systeme können beeindruckend sein.
  • Subtypisierungsbasierter Polymorphismus, wobei ein polymorpher Typ ein Subtyp aller seiner Instanziierungen ist. Um eine entscheidbare Subtypisierung zu haben, muss der Polymorphismus prädikativ sein. Dieses Dokument enthält ein Beispiel für ein solches System.

Einige Sprachen, wie Haskell, weisen jedoch einen unprädikativen höherrangigen Polymorphismus ohne explizite Typanwendungen auf.

Wie ist das möglich? Wie kann die Typprüfung "wissen", wann ein Typ ohne explizite Instanziierung oder Umwandlung und ohne den Begriff der Subtypisierung instanziiert werden muss?

Oder ist Typchecking in einem solchen System überhaupt entscheidbar? Ist dies ein Fall, in dem eine Sprache wie Haskell etwas Unentscheidbares implementiert, das für die Anwendungsfälle der meisten Menschen funktioniert?

BEARBEITEN:

Um es klar auszudrücken, ich interessiere mich für die Verwendung und nicht für Definitionen von polymorph typisierten Werten.

Nehmen wir zum Beispiel an, wir haben:

f : forall a . a -> a
g : (forall a . a -> a) -> Int
val = (g f, f True, f 'a')

Wie können wir wissen, dass wir instanziieren müssen, fwenn es angewendet wird, aber nicht, wenn es als Argument angegeben wird?

Oder um uns von Funktionstypen zu trennen:

f : forall a . a
g : (forall a . a) -> Int
val = (g f, f && True, f + 0)

Hier können wir nicht einmal zwischen der Verwendung fals Anwenden und Übergeben unterscheiden: Es wird instanziiert, wenn es als Argument an &&und übergeben wird +, aber nicht g.

Wie kann ein theoretisches System diese beiden Fälle ohne die magische Regel "Sie können jeden polymorphen Typ in seine Instanz konvertieren" unterscheiden? Oder können wir mit einer solchen Regel wissen, wann wir sie anwenden müssen, um die Entscheidbarkeit zu bewahren?

programming-languages type-theory functional-programming type-checking polymorphisms jmite
quelle
Haskell wird niemals einen Polytyp für eine Typvariable ableiten, es sei denn, er wird ausdrücklich vom Benutzer bereitgestellt. ZB \f -> (f True, f 'a')wird keine Typprüfung durchgeführt, auch wenn ihr der Typ zugewiesen werden kann(forall t. t->t) -> (Bool, Char)
Chi
@chi Ich interessiere mich für die Verwendung und nicht für Definitionen polymorpher Werte. In meiner Bearbeitung finden Sie ein Beispiel dafür, was ich meine. Entschuldigung, wenn dies zunächst nicht klar war.
Jmite
Es sollte ein Artikel von Simon Peyton-Jones geben, der den Inferenzalgorithmus erklärt (ich kann jedoch nicht zeigen, welcher). Aber wahrscheinlich kann die Inferenzmaschine sehen, gdass sie einen Polytyp erwartet und die Instanziierung von verhindert f.
Chi
@chi wahrscheinlich microsoft.com/en-us/research/publication/… und microsoft.com/en-us/research/publication/…
phadej

Antworten:

7

Die Einführung des Dunfield & Krishnaswami-Papiers bezieht sich auf die praktische Typinferenz für Typen mit beliebigem Rang

Wie zu sehen ist, lässt es sich gut auf Systeme vom fortgeschrittenen Typ skalieren. Darüber hinaus ist es einfach zu implementieren und liefert Fehlermeldungen von relativ hoher Qualität (Peyton Jones et al. 2007).

Beim System-F-ish-Ansatz gibt es auch eine "Subtypisierungs" -Relation. Siehe Abschnitt 3.3 Subsumtion.

Ich möchte auch betonen, dass Haskell keine aussagekräftigen Typen (oder Schlussfolgerungen für sie) hat. Hinweise finden Sie unter: https://mail.haskell.org/pipermail/ghc-devs/2016-September/012940.html .

  • Sie können einen Polytyp in ein sichtbares Typargument schreiben. z.B. f @ (für alle a. a-> a)

  • Sie können einen Polytyp als Argument eines Typs in eine Signatur schreiben, z. B. f :: [forall a. a-> a] -> Int

    Und das ist alles. Eine Vereinigungsvariable kann NOCH NICHT mit einem Polytyp vereinheitlicht werden. Die einzige Möglichkeit, eine polymorphe Funktion bei einem Polytyp aufzurufen, ist die Verwendung von Visible Type Application.

Kurz gesagt, wenn Sie eine Funktion bei einem Polytyp aufrufen, müssen Sie VTA verwenden. Einfach, leicht, vorhersehbar; und zweifellos nervig. Aber möglich.

Dh id idwird immer als ausgearbeitet

forall a. id @(a -> a) (id @a)

nicht

id @(forall a. a -> a) id

Letzteres können Sie jedoch explizit schreiben, wenn Sie es aktivieren ImpredicativeTypes.

Phadej
quelle
3

So überprüfen Sie die Anwendung einer Funktion wie g : (forall a. a -> a) -> Intzu f, müssen wir das überprüfen f : forall a. a -> a.

Anstatt Quantifizierer abzugleichen (was ziemlich spröde wäre), führen wir beispielsweise eine frische, starre (dh nicht unifizierbare) Variable ein a1, und wir müssen dies überprüfen f : a1 -> a1, und jetzt können wir wie gewohnt weitermachen und fbei a1(modulo Additional) instanziieren prüft, ob a1dies nicht dem Anwendungsbereich entgeht).

Der eigentliche Algorithmus ist in dem verknüpften Artikel phadej beschrieben.

Oder ist Typchecking in einem solchen System überhaupt entscheidbar? Ist dies ein Fall, in dem eine Sprache wie Haskell etwas Unentscheidbares implementiert, das für die Anwendungsfälle der meisten Menschen funktioniert?

Das allgemeine Problem der Typinferenz bei Vorhandensein eines höherrangigen Polymorphismus bleibt unentscheidbar. Bei vollständigen Typanmerkungen wird es jedoch zu einem (meistens?) Entscheidbaren Problem bei der Typprüfung . Der GHC-Algorithmus muss daher unvollständig sein, versucht jedoch, mit Hilfe einiger Anmerkungen vom spärlichen Typ so viel Boden wie möglich in der Mitte dieser beiden Situationen abzudecken.

Li-yao Xia
quelle