Typinferenz auf Unifikationsproblem

Question

Hat jemand eine Idee, wie die Typinferenz Problem

E > hd (cons 1 nil) : α0

mit der Typisierung Umgebung

                E={
                   hd : list(α1 ) → α1 ,
                   cons : α2 → list(α2 ) → list(α2 ),
                   nil : list(α3 ),
                   1 : int
                }

kann in einem Unifikationsproblem übertragen werden?

Jede Hilfe wäre wirklich dankbar!

Answer 1

Zuerst Typ Variablen umbenennen, so dass keine der Variablen in Ihrem Ausdruck mit Variablen in der Typisierung Umgebung kollidieren. (In Ihrem Beispiel ist dies bereits seit der Ausdruck Referenzen getan {a0} und die Typisierung Umwelt Referenzen {a1, a2, a3}.

Zweitens neuen Typ Variablen, eine Art Variable in Ihrem Ausdruck für jeden Teilausdruck machen, etwas produzieren wie:

nil : a4
1 : a5
cons : a6
(cons 1 nil) : a7
hd : a8
hd (cons 1 nil) : a0 // already had a type variable

Drittens eine Reihe von Gleichungen unter Typvariablen erzeugen, die bereithalten müssen. Sie können dies tun, von unten nach oben, von oben nach unten, oder auf andere Weise. Siehe Heeren, Bastiaan. Top-Qualität Typ Fehlermeldungen. 2005 für ausführliche Details, warum Sie vielleicht eine oder andere Weise zu wählen. Dies wird in etwas ergeben wie:

a4 = list(a3) // = E(nil)
a5 = int // = E(1)
a6 = a2 -> list(a2) -> list(a2) // = E(cons)

// now it gets tricky, since we need to deal with application for the first time
a5 = a2 // first actual param of cons matches first formal param of cons
a4 = list(a2) // second actual param of cons matches type of second formal param of cons
a7 = list(a2) // result of (cons 1 nil) matches result type of cons with 2 params

a8 = list(a1) -> a1 // = E(hd)    

// now the application of hd
a7 = list(a1) // first actual param of hd matches type of first formal param of hd
a0 = a1 // result of hd (cons 1 nil) matches result type of hd with 1 param

Beachten Sie sorgfältig, dass, wenn die gleiche Funktion aus der Typ-Umgebung zweimal verwendet wurde, würden wir mehr neue Art Variablen müssen (in der zweiten Stufe, oben) mit vereinigen, damit wir nicht aus Versehen alle Anrufe machen würden Nachteile nutzen die gleiche Art. Ich bin mir nicht sicher, wie dieser Teil zu erklären deutlicher, sorry. Hier sind wir in dem einfachen Fall, da hd und Nachteile jeweils nur einmal verwendet werden.

Viertens vereinigen diese Gleichungen, die sich in so etwas wie (wenn ich nicht einen Fehler gemacht):

a4 = list(int)
a5 = int
a6 = int -> list(int) -> list(int)
a7 = list(int)
a8 = list(int) -> int
a0 = int

Rejoice, haben Sie jetzt die Art jedes subexpression in Ihrem ursprünglichen Ausdruck kennen.

(Eine Warnung, ich bin so etwas wie ein Amateur mich in diesen Dingen, und ich kann auch einen Tippfehler gemacht habe oder versehentlich irgendwo hier betrogen.)