On Repairing Ill-Typed Expressions

When developing code, a programmer typically knows the approximate structure of the desired expression. However, often the first attempt at writing it down results in an ill-typed code fragment. We propose an approach that automatically repairs code expressions based on the provided almost-correct code. Such a code repair can be applied in interactive scenarios like advanced code completion, as well as in automated repair in the compilation process. We formally define the problem of automatically repairing ill-typed expressions. For the certain class of problems we describe a polynomial time synthesis algorithm that returns the best well-typed expression corresponding to the given ill-typed expression. We also present a complete algorithm that takes as input an ill-typed expression and returns the desired number of type-correct expressions that are closest to the input expression. We simultaneously fix all the type errors in the expression.