Ordering Type Constraints: A Structured Approach

The separation between collecting, ordering, and solving constraints results in a flexible framework with fine-tuned control over the type inference process. We offer an abstraction which helps us deal with the process of the reordering of constraints in a generic way. As a result, our work generalizes various well-known algorithms such as M, W and G and also various real-life implementations. This opens the way for comparing the behaviors of these algorithms to each other and to other methods of type inferencing, such as those that consider more than one constraint at the time. The framework has been implemented, and used to build a real-life compiler called Helium. This compiler allows the programmer to choose between various strategies for solving his constraints, and in this way can control what is reported to him in the case of a type error.