Trifonov and Smith's Subtyping Constrained Types (1996) introduces constraint maps to represent consistent closed constraint sets (such maps providing sets of lower and upper bounds to each variable in their domain), and canonical constraint maps for which each variable has exactly one constructed upper and one constructed lower bound. They note that constraint maps and canonical constraint maps have potential as an implementation technique.

However, the work I am familiar with on algorithms for polymorphic type inference in the presence of constraints (essentially, Pottier and Rémy's The essence of ML type inference, and the range of research cited therein -- also see Simonet's Type inference with structural subtyping, and Odersky, Sulzmann and Wehr's Type inference with constrained types) does not appear to use the constraint map representation.

Have Trifonov and Smith's constraint maps been put to use in any published works (or actual implementations in the wild)? Were there any obstacles to doing so, or was this line of research simply not pursued?

  • $\begingroup$ have you checked here? (all papers that cite it) scholar.google.com/… $\endgroup$ Aug 30, 2010 at 19:03
  • $\begingroup$ Thanks for the link. I've looked at a fair amount of those, but certainly not all. The basic result of the paper is very well cited, but in what I've seen there's been no use of constraint maps. $\endgroup$
    – sclv
    Aug 30, 2010 at 19:11


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.