Ich arbeite an einer ausdrucksbasierten Sprache der ML-Genealogie, daher ist natürlich eine Typinferenz erforderlich> :)
Jetzt versuche ich, eine auf Einschränkungen basierende Lösung für das Problem der Ableitung von Typen zu erweitern, die auf einer einfachen Implementierung in EOPL (Friedman und Wand) basiert, aber sie sind elegant algebraische Datentypen.
Was ich bisher habe, funktioniert reibungslos; wenn ein Ausdruck eist a + b, e : Int, a : Intund b : Int. Wenn ees ein Match ist,
match n with
| 0 -> 1
| n' -> n' * fac(n - 1)`,
Ich kann mit Recht annehmen , dass die t(e) = t(the whole match expression), t(n) = t(0) = t(n'), t(match) = t(1) = t(n' * fac(n - 1)und so weiter ...
Bei algebraischen Datentypen bin ich mir jedoch sehr unsicher. Angenommen, eine Funktion wie filter:
let filter pred list =
match list with
| Empty -> Empty
| Cons(e, ls') when pred e -> Cons (e, filter ls')
| Cons(_, ls') -> filter
Damit der Listentyp polymorph bleibt, muss Cons vom Typ sein a * a list -> a list. Um diese Einschränkungen festzulegen, muss ich natürlich diese Typen meiner algebraischen Konstruktoren nachschlagen - das Problem, das ich jetzt habe, ist die "Kontextsensitivität" der mehrfachen Verwendung algebraischer Konstruktoren - wie drücke ich in meinen Einschränkungsgleichungen aus, dass die ain muss jeder Fall der gleiche sein?
Ich habe Probleme, eine allgemeine Lösung dafür zu finden, und ich kann nicht viel Literatur dazu finden. Immer wenn ich etwas Ähnliches finde - Ausdrucksbasierte Sprache mit Constraint-basierter Typinferenz - hören sie kurz vor algebraischen Datentypen und Polymorphismus auf.
Jede Eingabe wird sehr geschätzt!
Antworten:
Siehe: Mini ML Speziell im Abschnitt Typinferenz.
Dieser enthält Beispielcode in F # für einen vollständigen Parser einer einfachen Funktionssprache. Noch wichtiger ist, dass der Abschnitt Typinferenz den Hindley-Milner-Algorithmus implementiert, der in den meisten Typinferenzsystemen zu finden ist. Der Autor bietet auch Links zu zwei anderen wichtigen Dokumenten, um das Verständnis von Hindley-Milner zu erleichtern. Eine ist eine Art Einführung auf hoher Ebene und die andere ist ein Artikel, der die Implementierung des Algorithmus in Code beschreibt.
quelle