Алгоритм Хиндли-Милнера в Java

Я работаю над простой системой на основе потока данных (представьте ее как редактор / среда выполнения LabView), написанную на Java. Пользователь может соединять блоки вместе в редакторе, и мне нужен вывод типа, чтобы убедиться, что график потока данных правильный, однако большинство примеров вывода типов написано в математических обозначениях, ML, Scala, Perl и т. Д., О которых я не говорю ".

Я читал об алгоритме Хиндли-Милнера и нашел этот документ с хорошим примером, который я мог бы реализовать. Он работает с набором ограничений типа T1 = T2. Однако мои графики потоков данных переводятся в T1> = T2 как ограничения (или T2 расширяет T1, или ковариацию, или T1 <: t2> T merge (T in1, T in2) ) и конкретных типах.

Резюмируя алгоритм HM:

Type = {TypeVariable, ConcreteType}
TypeRelation = {LeftType, RightType}
Substitution = {OldType, NewType}
TypeRelations = set of TypeRelation
Substitutions = set of Substitution

1) Initialize TypeRelations to the constraints, Initialize Substitutions to empty
2) Take a TypeRelation
3) If LeftType and RightType are both TypeVariables or are concrete 
      types with LeftType <: RightType Then do nothing
4) If only LeftType is a TypeVariable Then
    replace all occurrences of RightType in TypeRelations and Substitutions
    put LeftType, RightType into Substitutions
5) If only RightType is a TypeVariable then
    replace all occurrences of LeftType in TypeRelations and Substitutions
    put RightType, LeftType into Substitutions
6) Else fail

Как я могу изменить исходный HM алгоритм работы с такими отношениями вместо простых отношений равенства? Будем очень признательны за пример или объяснение в стиле Java.

11
задан templatetypedef 21 July 2011 в 22:20
поделиться