Typinferenz mit Überladung

Question

Ich arbeite an einem Typsystem, das Überlastung unterstützt.Ich habe eine ungefähre Vorstellung davon, wie Typinferenz normalerweise in einem solchen Szenario implementiert wird, aber ich frage mich, wie - nachdem die Typinferenz abgeschlossen ist - die korrekte Implementierung eines überladenen Operators ausgewählt werden kann.Oder mit anderen Worten, wie der abgeleitete Typ im Syntaxbaum an den Operator zurückgegeben werden kann.

Betrachten Sie für ein kleines Beispiel den Ausdruck (x + y) + 1 wo x :: N | S, y :: a, + :: (N -> N -> N) | (S -> S -> S), 1 :: N. :: steht für art der, und a | b steht für Typ a oder Art b.

Ich gehe davon aus, dass Typinferenz jetzt funktionieren würde, indem der Syntaxbaum durchlaufen und für jeden Knoten eine Typeinschränkung zurückgegeben wird:

(x + y) + 1 => ((N & (N[a=N] | S[a=S])), (N & N) -> N) | ((S & (N[a=N] | S[a=S])), (S & N) -> S) => N[a=N]
  1         => N
  +         => (N -> N -> N) | (S -> S -> S)
  x + y     => ((N & (N | S)), (N & a) -> N) | ((S & (N | S)), (S & a) -> S) => N[a=N] | S[a=S]
    x       => N | S
    y       => a
    +       => (N -> N -> N) | (S -> S -> S)

a & b in diesem Beispiel steht für einigende Art a und b, [a=T, b=U] ist eine Menge von Gleichheitsbeschränkungen für Typvariablen.

Wie erwartet wird der Rückgabetyp des angegebenen Ausdrucks wie folgt abgeleitet N[a=N], das ist N wobei die Typvariable a wird voraussichtlich sein N.

Daher sind von den beiden vorgesehenen Implementierungen für die + Betreiber (N -> N -> N, S -> S -> S), N -> N -> N sollte verwendet werden.Im angegebenen Beispiel wird der resultierende Typ abgeleitet, nicht jedoch der Typ des überladenen Operators.Meine Frage ist, ob es ein gemeinsames Muster gibt, das verwendet wird, um die + knoten im Syntaxbaum der verwendeten Implementierung.

Answer 1

Sie könnten die Typinferenz wie folgt organisieren.

Angenommen, Ihre Eingabesyntax hat den Typ Input.Ausgabesyntax definieren Output zu sein wie Input aber mit expliziten Typanmerkungen für alle Variablen.Die Typinferenz hätte Typ

infer : Input -> List (Output * Type)

Das heißt, einige Eingaben gegeben e, gibt eine Liste möglicher Antworten zurück.Jede Antwort ist ein Paar (e', t) wo e' is e mit Variablen, die nach Typen annotiert sind, und t ist der abgeleitete Typ von e.

Sie können dies als alles betrachten, was in der Nichtdeterminismus-Monade passiert.Wann immer Sie auf den Typ einer Variablen schließen müssen x, Sie sehen seine möglichen Typen nach S | T | ... und verzweige dich auf jeden von ihnen.Auf diese Weise müssen Sie keine Informationen an Unterausdrücke "zurückgeben".Stattdessen wird jeder Unterausdruck bereits auf alle möglichen Arten mit Anmerkungen versehen.