Constraint-set Satisfiability for Overloading

摘要

This article discusses the problem of constraint-set satisfiability (CS-SAT) — that is, the problem of determining whether a given constraint-set is satisfiable in a given typing context — in the context of systems with support for overloading and parametric polymorphism. The paper reviews previous works on constraint-set satisfiability, showing that overloading policies used in order to guarantee decidability of CS-SAT have been generally too restrictive. An algorithm is proposed that does not impose a severe restriction on possible overloadings and decides CS-SAT in an expect-edly vast majority of cases of practical interest. In cases for which satisfiability cannot be decided, a configurable limit on the number of iterations is used in order to guarantee termination.