  Compilers for statically typed functional programming languages are notorious
for generating confusing type error messages. When the compiler detects a type
error, it typically reports the program location where the type checking failed
as the source of the error. Since other error sources are not even considered,
the actual root cause is often missed. A more adequate approach is to consider
all possible error sources and report the most useful one subject to some
usefulness criterion. In our previous work, we showed that this approach can be
formulated as an optimization problem related to satisfiability modulo theories
(SMT). This formulation cleanly separates the heuristic nature of usefulness
criteria from the underlying search problem. Unfortunately, algorithms that
search for an optimal error source cannot directly use principal types which
are crucial for dealing with the exponential-time complexity of the decision
problem of polymorphic type checking. In this paper, we present a new algorithm
that efficiently finds an optimal error source in a given ill-typed program.
Our algorithm uses an improved SMT encoding to cope with the high complexity of
polymorphic typing by iteratively expanding the typing constraints from which
principal types are derived. The algorithm preserves the clean separation
between the heuristics and the actual search. We have implemented our algorithm
for OCaml. In our experimental evaluation, we found that the algorithm reduces
the running times for optimal type error localization from minutes to seconds
and scales better than previous localization algorithms.
