Typinferenz auf Unifikationsproblem

stimmen
2

Hat jemand eine Idee, wie die Art Inferenzproblem

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 mögliche Hilfe würde wirklich geschätzt!

Veröffentlicht am 09/12/2008 um 14:58
quelle vom benutzer
In anderen Sprachen...                            


1 antworten

stimmen
3

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, wie etwas produziert:

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 Heere, Bastiaan. Top - Qualität Typ Fehlermeldungen. 2005 für ausführliche Details, warum Sie vielleicht eine oder andere Weise zu wählen. Dies wird wie in etwas zur Folge haben :

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ürde Nachteile des gleichen Typs . 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

Freuen Sie sich, Sie kennen jetzt die Art von jedem Unterausdruck in Ihrem ursprünglichen Ausdruck.

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

Beantwortet am 19/12/2008 um 21:33
quelle vom benutzer

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more