Type Debugging with Counter-Factual Type Error Messages Using an Existing Type Checker

The cause of a type error can be very difficult to find for the Hindley-Milner type system. Consequently many solutions have been proposed, but they are hardly used in practice. Here we propose a new solution that provides counter-factual type error messages; these messages state what types specific subexpressions in a program should have (in contrast to the types they actually have) to remove a type error. Such messages are easy-to-understand, because programers are already familiar with them. Furthermore, our solution is easy-to-implement, because it reuses an existing type checker as a subroutine. We transform an ill-typed program into a well-typed program with additional λ-bound variables. The types of these λ-bound variables yield actual and counter-factual type information. That type information plus intended types added as type annotations direct the search of the type debugger.