Novice Type Error Diagnosis with Natural Language Models

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

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.

Introduction

Strong static type systems in functional languages like OCaml offer significant benefits by catching errors at compile-time. However, for novice programmers, the resulting error messages are often cryptic and point to the symptom of a type violation rather than its root cause. Traditional approaches to error localization have relied on complex constraint solving or data-driven models requiring extensive manual feature engineering.

This research demonstrates that treating source code as natural language and applying Transformer-based models (like BERT) significantly improves type error localization. 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.

Methodology

The researchers treated type error diagnosis as a token classification problem, utilizing several variants of BERT (Bidirectional Encoder Representations from Transformers) and a Bidirectional LSTM as a baseline.

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.

The BERT-based pipeline for OCaml type error localization, showing the flow from raw code to token-level predictions.

Datasets

The study utilized four primary datasets for pre-training and fine-tuning:

  • GitHub-OCaml: ~350,000 programs collected from top GitHub repositories.
  • Student-OCaml: ~20,000 homework submissions from McGill University students.
  • NATE Dataset: Approximately 5,000 labeled ill-typed programs with ground-truth fixes used for evaluation.

Pre-training on student code (Student-OCaml) was found to be more effective than pre-training on professional code (GitHub-OCaml), highlighting the importance of matching the data distribution of the target novice audience.

Key Results and Analysis

The performance was evaluated using a new, "strict" Jaccard-based metric: $\text{Accuracy} = \frac{|P \cap L|}{|P \cup L|}$, where $P$ is the set of predicted tokens and $L$ is the set of labeled error tokens. This provides a much more realistic view of model performance than previous "loose" metrics.

  • Top Performance: The best model, OCamlBERT Large, achieved 62% accuracy on the strict metric, 11 points higher than the state-of-the-art NATE tool.
  • Robustness: BERT models maintained performance much better than the Bi-LSTM when tested on "unseen" program problems, where the Bi-LSTM saw accuracy drops of over 30%.

Implicit Structure and 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).

Structural probes demonstrate how BERT's high-dimensional embeddings (A) can be projected (B) to reconstruct the program's AST (C, D), explaining its superior performance.

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 and accurately localize errors based on the underlying logic of the code.

Conclusion

This work demonstrates that large-scale language models can effectively automate the diagnosis of type errors without manual feature engineering. While the results are promising, future work will focus on improving interpretability and extending the approach to other complex languages like Rust or Go. 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},
}
Figure