Novice Type Error Diagnosis with Natural Language Models

Chuqin Geng, Haolin Ye, Yixuan Li, Tianyu Han, Brigitte Pientka, Xujie Si

TL;DR

This paper demonstrates that treating source code as natural language and applying Transformer-based models (like BERT) significantly improves type error localization for novice programmers. By reframing error diagnosis as a token classification task, the authors achieve a 62% accuracy rate—outperforming previous state-of-the-art tools by 11% while eliminating the need for tedious, language-specific feature engineering.

What Problem Does This Paper Address?

Novice programmers often struggle with strongly typed functional languages like OCaml. While these languages have powerful type systems that catch errors at compile-time, the resulting error messages are notoriously unhelpful. Standard compilers often point to the location where a type constraint is violated (the symptom), which can be far away from the actual code that needs fixing (the root cause).

Previous "data-driven" attempts to solve this, such as the tool NATE, relied heavily on manual feature engineering—experts had to hand-design hundreds of features to help the model understand code structure. Furthermore, these earlier models were evaluated using "loose" metrics that often overestimated their real-world utility. The authors of this paper sought an end-to-end approach that learns directly from raw code and a more rigorous way to measure success.

Methods

The researchers treated type error diagnosis as a token classification problem.

  1. Model Architecture: They utilized several variants of BERT (Bidirectional Encoder Representations from Transformers), ranging from "Small" to "Large," as well as CodeBERT (pre-trained on multiple programming languages) and a Bidirectional LSTM as a baseline.
  2. The Pipeline: An ill-typed program is split into a sequence of tokens. These tokens are fed into the model to generate embedding representations. A classification head then assigns a probability to each token, indicating whether it is likely part of the "root cause" of the type error.
  3. Pre-training & Fine-tuning: The models were pre-trained on large unlabeled OCaml datasets to learn the "grammar" of the language and then fine-tuned on a smaller labeled dataset of actual student errors.
  4. Structural Probes: To understand why Transformers work better than LSTMs, the authors used structural probes to test if the models' internal vector geometry implicitly captures the program's Abstract Syntax Tree (AST) without being explicitly programmed to do so.

Datasets

The study utilized four primary datasets:

  • GitHub-OCaml: ~350,000 programs collected from top GitHub repositories (used for pre-training).
  • Student-OCaml: ~20,000 homework submissions from McGill University students (used for pre-training).
  • NATE Dataset (SP14 & FA15): Approximately 5,000 labeled ill-typed programs with ground-truth fixes (used for fine-tuning and evaluation).

Key Insights and Ideas

  • The "Strict" Metric Matters: The authors identified that previous work used a loose metric where predicting any part of a large error-related subtree counted as 100% accuracy. They proposed a stricter Jaccard-like metric: $\text{Accuracy} = \frac{|P \cap L|}{|P \cup L|}$ (the intersection of predicted and labeled error tokens divided by their union). This provides a much more realistic view of model performance.
  • Bigger is Better (and doesn't overfit): In many NLP tasks, increasing model size leads to overfitting on small datasets. Here, the "Large" models consistently outperformed "Base" and "Small" models across all test setups, suggesting that the complexity of type inference requires the higher representational capacity of larger Transformers.
  • Implicit Structure: Even though the models view code as a flat sequence of text, the structural probes revealed that BERT models encode significantly more AST information than LSTMs. This explains their superior ability to generalize to unseen coding problems.
  • Domain Shift: Pre-training on student code (Student-OCaml) was more effective than pre-training on professional code (GitHub-OCaml), even though the GitHub dataset was much larger. This highlights the importance of matching the data distribution of the target "novice" audience.

Key Results

  • Top Performance: The best model, OCamlBERT Large, achieved 62% accuracy on the strict metric.
  • Comparison: This is 11 points higher than the state-of-the-art NATE tool and 24 points higher than SHErrLoc (a popular optimization-based tool).
  • Robustness: When tested on "unseen" program problems (training on one semester's homework and testing on another), BERT models maintained their performance much better than the Bi-LSTM, which saw accuracy drops of over 30%.
  • Confidence: BERT models were found to be more "confident" in their predictions; their accuracy remained stable even when the probability threshold for flagging an error was increased.

Limitations and Future Work

While the results are promising, the authors note a few areas for growth:

  • Interpretability: Although structural probes show that the models contain structural information, it is still not entirely clear how the model uses that information to arrive at a specific error diagnosis.
  • Language Scope: This study focused exclusively on OCaml. The authors plan to investigate if this approach transfers easily to other languages with complex type systems, such as Rust or Go.
  • Hybrid Systems: The paper suggests that the ultimate "type debugger" might combine the intuitive, data-driven strengths of language models with the formal, logic-based precision of constraint solvers.

Summary updated

Abstract

Strong static type systems help programmers eliminate many errors without much burden of supplying type annotations. However, this flexibility makes it highly non-trivial to diagnose ill-typed programs, especially for novice programmers. Compared to classic constraint solving and optimization-based approaches, the data-driven approach has shown great promise in identifying the root causes of type errors with higher accuracy. Instead of relying on hand-engineered features, this work explores natural language models for type error localization, which can be trained in an end-to-end fashion without requiring any features. We demonstrate that, for novice type error diagnosis, the language model-based approach significantly outperforms the previous state-of-the-art data-driven approach. Specifically, our model could predict type errors correctly 62% of the time, outperforming the state-of-the-art Nate's data-driven model by 11%, in a more rigorous accuracy metric. Furthermore, we also apply structural probes to explain the performance difference between different language models.
BibTeX
@inproceedings{geng2022novice,
  author = {Chuqin Geng and Haolin Ye and Yixuan Li and Tianyu Han and Brigitte Pientka and Xujie Si},
  title = {{Novice Type Error Diagnosis with Natural Language Models}},
  booktitle = {APLAS},
  year = {2022},
  doi = {10.1007/978-3-031-21037-2\_10},
}

Loading related content...

Figure