Hindley-Milner algorithm in Java

Question

I'm working on a simple dataflow based system (imagine it like a LabView editor/runtime) written in Java. The user can wire blocks together in an editor and I need type inference to ensure the dataflow graph is correct, however, most type inference examples are written in mathematical notations, ML, Scala, Perl, etc., which I don't "speak".

I read about the Hindley-Milner algorithm and found this document with a nice example I could implement. It works on a set of T1 = T2 like constraints. However, my dataflow graphs translate to T1 >= T2 like constraints (or T2 extends T1, or covariance, or T1 <: T2 as I saw it in various articles). No lambdas just type variables (used in generic functions like T merge(T in1, T in2)) and concrete types.

To recap the HM algorithm:

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

How can I change the original HM algorithm to work with these kind of relations instead of simple equality relations? Java-ish example or explanation would be much appreciated.

Hindley-Milner algorithm in Java

2 Answers