Ole Ildsgaard Hougaard
February 1998
Many type inference problems are different instances of the same constraint satisfaction problem. That is, there is a class of constraints so that these type inference problems can be reduced to the problem of finding a solution to a set of constraints. Furthermore, there is an efficient constraint solving algorithm which can find this solution in polynomial time.
We have shown this by defining the appropriate constraint domain, devising an efficient constraint satisfaction algorithm, and designing a constraint logic programming language over the constraint domain. We have implemented an interpreter for the language and have thus produced a tool which is well-suited for type inference problems of different kinds.
Among the problems that can be reduced to our constraint domain are the following:
The programming language thus provides a very easy way of implementing a vast array of different type inference problems
Available as PostScript,
PDF.