Learning to blame: localizing novice type errors with data-driven diagnosis

Eric L. Seidel, Huma Sibghat, Kamalika Chaudhuri, Westley Weimer, Ranjit Jhala

TL;DR

NATE (Numeric Analysis of Type Errors) is a data-driven tool that uses supervised learning to pinpoint the root cause of type errors in OCaml programs. By training on thousands of real-world student mistakes and their subsequent fixes, NATE’s top prediction is correct 72% of the time—significantly outperforming both standard compilers and state-of-the-art constraint-based localization tools.

The "Blame Problem" in Type Inference

In languages with global type inference, such as OCaml or Haskell, the compiler automatically deduces types without requiring explicit annotations. While this improves productivity, it complicates error reporting. When a programmer makes a mistake, the compiler collects constraints until it finds a contradiction. It then "blames" the location where the contradiction was discovered, which is often far away from the actual source of the error. This is known as the blame problem.

Existing tools attempt to solve this using complex constraint-solving heuristics, such as finding the "minimum" set of changes to make a program type-check. However, these tools are often difficult to extend to new language features and fail to adapt to the specific patterns of mistakes made by human programmers, particularly novices.

Methods: NATE's Supervised Learning Workflow

The authors introduce NATE, which treats error localization as a supervised classification problem. The workflow involves several novel steps to transform raw code into a format suitable for machine learning.

Formalizing the Learning Task

To build a predictive model, the authors formalized the components of the type-checking and error-localization process. This includes defining how features are extracted from expressions and how the model eventually assigns "blame" to specific sub-expressions.

Formal definitions of the learning framework for error localization.

BOAT and Type Error Slicing

To feed programs into machine learning models, NATE represents them as vectors using a technique called BOAT (Bag-of-Abstracted-Terms). Each sub-expression is converted into a feature vector capturing local syntax, contextual syntax (parents and children), and partial typing information.

Crucially, NATE uses Type Error Slicing before classification. This standard PL technique discards any code that could not possibly be part of the error, drastically reducing the search space for the model. The table below illustrates how different expressions are mapped to these features and whether they are included in the slice.

Example of expression vectorization using BOAT features and type error slicing.

Datasets and Evaluation

The paper introduces a massive new benchmark for type error localization, consisting of over 5,000 labeled program pairs from 102 different students at UC San Diego (datasets SP14 & FA15). These programs cover a wide range of functional idioms, including higher-order functions and polymorphic algebraic data types.

Key Results

  • Accuracy: NATE's most advanced model (MLP-500) achieved 72% Top-1 accuracy. This is a massive improvement over the standard OCaml compiler (44%) and the previous state-of-the-art tool, SHErrLoc (56%).
  • Top-3 Performance: If the user considers the top three suggestions, NATE’s accuracy reaches 91%.
  • User Study: In an exam-based study, students provided with NATE’s blame assignments were more successful at explaining and fixing errors than those given SHErrLoc’s assignments.

Key Insights

  • Data Beats Algorithms: Sophisticated constraint-based solvers are outperformed by relatively simple ML models trained on actual human behavior.
  • Slicing is a Force Multiplier: ML models perform poorly on raw code, but when combined with Type Error Slicing to prune irrelevant code, even simple models like Logistic Regression become highly competitive.
  • Types are Better than Size: The authors found that the size of an expression was a poor predictor of error. Instead, the inferred types of the surrounding context provided the strongest signal for localization.

Limitations and Future Work

Currently, NATE uses a fixed set of features for built-in types and struggles to generalize to user-defined types (like a custom "Tree" type). Future work aims to use graphical models to make interdependent predictions (e.g., "if X is wrong, Y is likely correct") and to move beyond localization toward suggesting specific syntactic fixes.

Summary updated

BibTeX
@article{seidel2017learning,
  author = {Eric L. Seidel and Huma Sibghat and Kamalika Chaudhuri and Westley Weimer and Ranjit Jhala},
  title = {{Learning to blame: localizing novice type errors with data-driven diagnosis}},
  journal = {Proc. ACM Program. Lang.},
  year = {2017},
  doi = {10.1145/3138818},
}
Figure