Hindley-Milner-Algorithmus:Verwenden von Typen, um sicherzustellen, dass Bindungen angewendet werden

Question

Ich implementieren den Hindley-Milner-Typinferenzalgorithmus und folge den Tutorials von Mark Jones Und Oleg Kisseljow.Beide verfügen über einen Vorgang zum Anwenden von Bindungen mit einem Typ, der ungefähr der Form entspricht

applyBindings :: TyEnv -> Type -> Type

was gilt die tyvar -> ty Bindungen in TyEnv zum Gegebenen Type.Ich habe festgestellt, dass es ein häufiger Fehler in meinem Code ist, den Anruf zu vergessen applyBindings, und ich bekomme seitdem keine Hilfe vom Typsystem von Haskell ty hat den gleichen Typ wie applyBindings tyenv ty.Ich suche nach einer Möglichkeit, die folgende Invariante im Typsystem durchzusetzen:

Bei der Typinferenz müssen Bindungen angewendet werden, bevor ein „endgültiges“ Ergebnis zurückgegeben wird

Bei der Typinferenz für eine monomorphe Objektsprache gibt es eine natürliche Möglichkeit, dies zu erzwingen, wie sie in Thorntons Beispiel implementiert ist Unification-FD-Paket:Wir definieren zwei Datentypen für TypeS:

-- | Types not containing unification variables
type Type = ...          -- (Fix TypeF) in wren's package

-- | Types possibly containing unification variables
type MutType = ...       -- (MutTerm IntVar TypeF) in wren's package

und gebe applyBindings der Typ

-- | Apply all bindings, returning Nothing if there are still free variables
-- otherwise just
applyBindings :: TyEnv -> MutType -> Maybe Type

(Diese Funktion ist eigentlich freeze . applyBindings im Unification-FD).Dies erzwingt unsere Invariante – falls wir es vergessen applyBindings, dann erhalten wir einen Typfehler.

Dies ist die Art von Lösung, nach der ich suche, jedoch für Objektsprachen mit Polymorphismus.Der obige Ansatz ist in seiner jetzigen Form nicht anwendbar, da unsere Objektsprachentypen möglicherweise Typvariablen haben – tatsächlich möchten wir, wenn nach dem Anwenden von Bindungen Variablen frei sind, nicht zurückkehren Nothing, aber wir wollen diese Variablen verallgemeinern.

Gibt es eine Lösung in der von mir beschriebenen Richtung, d.h.einer, der gibt applyBindings ein anderer Typ als const id?Verwenden echte Compiler das gleiche Wortspiel (zwischen Vereinigungsvariablen und Objektsprachentypvariablen) wie die Tutorials von Mark und Oleg?

Answer 1

Ich tappe hier im Dunkeln, weil ich denke, dass es bei der von Ihnen vorgeschlagenen Lösung möglicherweise andere Probleme gibt, aber ich kann zumindest eine Schwierigkeit ansprechen:

• Ihr Typprüfer sollte dies haben anders Darstellungen für Variablen vom Typ Vereinigung Und Variablen vom Typ Objektsprache.

Diese Variante ist nicht schwer zu implementieren, und ich glaube tatsächlich, dass der GHC-Typprüfer zumindest einmal so funktioniert hat.Vielleicht möchten Sie das Papier überprüfen Praktische Typinferenz für Typen mit beliebigem Rang;Der Anhang enthält viele sehr hilfreiche Codes.