research-article

Open access

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

Authors:

Eric L. Seidel,

Kamalika Chaudhuri,

Westley Weimer,

Ranjit JhalaAuthors Info & Claims

Proceedings of the ACM on Programming Languages, Volume 1, Issue OOPSLA

Article No.: 60, Pages 1 - 27

https://doi.org/10.1145/3138818

Published: 12 October 2017 Publication History

Abstract

Localizing type errors is challenging in languages with global type inference, as the type checker must make assumptions about what the programmer intended to do. We introduce Nate, a data-driven approach to error localization based on supervised learning. Nate analyzes a large corpus of training data -- pairs of ill-typed programs and their "fixed" versions -- to automatically learn a model of where the error is most likely to be found. Given a new ill-typed program, Nate executes the model to generate a list of potential blame assignments ranked by likelihood. We evaluate Nate by comparing its precision to the state of the art on a set of over 5,000 ill-typed OCaml programs drawn from two instances of an introductory programming course. We show that when the top-ranked blame assignment is considered, Nate's data-driven model is able to correctly predict the exact sub-expression that should be changed 72% of the time, 28 points higher than OCaml and 16 points higher than the state-of-the-art SHErrLoc tool. Furthermore, Nate's accuracy surpasses 85% when we consider the top two locations and reaches 91% if we consider the top three.

Supplementary Material

Auxiliary Archive (oopsla17-oopsla37-aux.zip)

Download
129.25 MB

References

[1]

Rui Abreu, Peter Zoeteweij, and Arjan J C van Gemund. 2006. An Evaluation of Similarity Coefficients for Software Fault Localization. In 2006 12th Pacific Rim International Symposium on Dependable Computing (PRDC ’06). 39–46.

Digital Library

[2]

Rui Abreu, Peter Zoeteweij, and Arjan J C van Gemund. 2007. On the Accuracy of Spectrum-based Fault Localization. In Testing: Academic and Industrial Conference Practice and Research Techniques - MUTATION (TAICPART-MUTATION 2007). 89–98.

[3]

Mike Beaven and Ryan Stansifer. 1993. Explaining Type Errors in Polymorphic Languages. ACM Lett. Program. Lang. Syst. 2, 1-4 (March 1993), 17–30.

Digital Library

[4]

Karen L Bernstein and Eugene W Stark. 1995. Debugging Type Errors. Technical Report. State University of New York at Stony Brook.

[5]

Pavol Bielik, Veselin Raychev, and Martin Vechev. 2016. PHOG: Probabilistic Model for Code. In Proceedings of the 33rd International Conference on Machine Learning (ICML ’16).

[6]

Leo Breiman. 2001. Random Forests. Mach. Learn. 45, 1 (1 Oct. 2001), 5–32.

Digital Library

[7]

Leo Breiman, Jerome Friedman, Charles J Stone, and Richard A Olshen. 1984. Classification and regression trees. CRC press.

[8]

M Y Chen, E Kiciman, E Fratkin, A Fox, and E Brewer. 2002. Pinpoint: problem determination in large, dynamic Internet services. In Proceedings International Conference on Dependable Systems and Networks. 595–604.

[9]

Sheng Chen and Martin Erwig. 2014a. Counter-factual Typing for Debugging Type Errors. In Proceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’14). ACM, New York, NY, USA, 583–594.

Digital Library

[10]

Sheng Chen and Martin Erwig. 2014b. Guided Type Debugging. In Functional and Logic Programming, Michael Codish and Eijiro Sumii (Eds.). Springer International Publishing, 35–51.

[11]

Olaf Chitil. 2001. Compositional Explanation of Types and Algorithmic Debugging of Type Errors. In Proceedings of the Sixth ACM SIGPLAN International Conference on Functional Programming (ICFP ’01). ACM, New York, NY, USA, 193–204.

Digital Library

[12]

David Raymond Christiansen. 2014. Reflect on your mistakes! Lightweight domain-specific error messages. In Preproceedings of the 15th Symposium on Trends in Functional Programming.

[13]

P. Cousot and R. Cousot. 1977. Abstract interpretation: a unified lattice model for the static analysis of programs. In POPL 77. ACM, 238–252.

Digital Library

[14]

Dominic Duggan and Frederick Bent. 1996. Explaining type inference. Science of Computer Programming 27, 1 (July 1996), 37–83.

Digital Library

[15]

Cormac Flanagan, Matthew Flatt, Shriram Krishnamurthi, Stephanie Weirich, and Matthias Felleisen. 1996. Catching bugs in the web of program invariants. In Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation (PLDI ’96), Vol. 31. ACM, 23–32.

Digital Library

[16]

Joseph L Fleiss. 1971. Measuring nominal scale agreement among many raters. Psychol. Bull. 76, 5 (Nov. 1971), 378.

[17]

Mark Gabel and Zhendong Su. 2010. A Study of the Uniqueness of Source Code. In Proceedings of the Eighteenth ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE ’10). ACM, New York, NY, USA, 147–156.

Digital Library

[18]

Holger Gast. 2004. Explaining ML Type Errors by Data Flows. In Implementation and Application of Functional Languages. Springer Berlin Heidelberg, 72–89.

Digital Library

[19]

Christian Haack and J B Wells. 2003. Type Error Slicing in Implicitly Typed Higher-Order Languages. In Programming Languages and Systems. Springer Berlin Heidelberg, 284–301.

[20]

Jurriaan Hage and Bastiaan Heeren. 2006. Heuristics for Type Error Discovery and Recovery. In Implementation and Application of Functional Languages. Springer Berlin Heidelberg, 199–216.

[21]

Alon Halevy, Peter Norvig, and Fernando Pereira. 2009. The unreasonable effectiveness of data. IEEE Intelligent Systems 24, 2 (2009), 8–12.

Digital Library

[22]

Trevor Hastie, Robert Tibshirani, and Jerome Friedman. 2009. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer New York.

[23]

Bastiaan Heeren, Jurriaan Hage, and S Doaitse Swierstra. 2003. Scripting the type inference process. In Proceedings of the eighth ACM SIGPLAN international conference on Functional programming, Vol. 38. ACM, 3–13.

Digital Library

[24]

Abram Hindle, Earl T. Barr, Zhendong Su, Mark Gabel, and Premkumar Devanbu. 2012a. On the Naturalness of Software. In Proceedings of the 34th International Conference on Software Engineering (ICSE ’12). IEEE Press, Piscataway, NJ, USA, 837–847. http://dl.acm.org/citation.cfm?id=2337223.2337322

[25]

Abram Hindle, Earl T Barr, Zhendong Su, Mark Gabel, and Premkumar Devanbu. 2012b. On the Naturalness of Software. In Proceedings of the 34th International Conference on Software Engineering (ICSE ’12). IEEE Press, Piscataway, NJ, USA, 837–847.

[26]

James A Jones, Mary Jean Harrold, and John Stasko. 2002. Visualization of Test Information to Assist Fault Localization. In Proceedings of the 24th International Conference on Software Engineering (ICSE ’02). ACM, New York, NY, USA, 467–477.

[27]

Stef Joosten, Klaas Van Den Berg, and Gerrit Van Der Hoeven. 1993. Teaching functional programming to first-year students. J. Funct. Programming 3, 01 (Jan. 1993), 49–65.

[28]

Manu Jose and Rupak Majumdar. 2011. Cause Clue Clauses: Error Localization Using Maximum Satisfiability. SIGPLAN Not. 46, 6 (June 2011), 437–446.

Digital Library

[29]

Diederik P Kingma and Jimmy Ba. 2014. Adam: A Method for Stochastic Optimization. (22 Dec. 2014). arXiv: 1412.6980

[30]

Pavneet Singh Kochhar, Xin Xia, David Lo, and Shanping Li. 2016. Practitioners’ Expectations on Automated Fault Localization. In Proceedings of the 25th International Symposium on Software Testing and Analysis (ISSTA 2016). ACM, New York, NY, USA, 165–176.

Digital Library

[31]

S B Kotsiantis. 2007. Supervised Machine Learning: A Review of Classification Techniques. Informatica 31, 3 (2007), 249–268.

[32]

Ted Kremenek and Dawson Engler. 2003. Z-Ranking: Using Statistical Analysis to Counter the Impact of Static Analysis Approximations. In Static Analysis, Radhia Cousot (Ed.). Lecture Notes in Computer Science, Vol. 2694. Springer Berlin Heidelberg, Berlin, Heidelberg, 295–315.

[33]

K Krippendorff. 2012. Content Analysis: An Introduction to Its Methodology. SAGE Publications.

[34]

J R Landis and G G Koch. 1977. The measurement of observer agreement for categorical data. Biometrics 33, 1 (March 1977), 159–174.

[35]

Oukseh Lee and Kwangkeun Yi. 1998. Proofs About a Folklore Let-polymorphic Type Inference Algorithm. ACM Trans. Program. Lang. Syst. 20, 4 (July 1998), 707–723.

Digital Library

[36]

Eelco Lempsink. 2009. Generic type-safe diff and patch for families of datatypes. Master’s thesis. Universiteit Utrecht.

[37]

Benjamin S Lerner, Matthew Flower, Dan Grossman, and Craig Chambers. 2007. Searching for Type-error Messages. In Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’07). ACM, New York, NY, USA, 425–434.

Digital Library

[38]

Calvin Loncaric, Satish Chandra, Cole Schlesinger, and Manu Sridharan. 2016. A practical framework for type inference error explanation. In Proceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications. ACM, 781–799.

Digital Library

[39]

H B Mann and D R Whitney. 1947. On a Test of Whether one of Two Random Variables is Stochastically Larger than the Other. Ann. Math. Stat. 18, 1 (March 1947), 50–60.

[40]

Bruce J McAdam. 1998. On the Unification of Substitutions in Type Inference. In Implementation of Functional Languages (Lecture Notes in Computer Science), Kevin Hammond, Tony Davie, and Chris Clack (Eds.). Springer Berlin Heidelberg, 137–152.

[41]

Vinod Nair and Geoffrey E Hinton. 2010. Rectified linear units improve restricted boltzmann machines. In Proceedings of the 27th international conference on machine learning (ICML-10). 807–814.

Digital Library

[42]

Greg Nelson and Derek C Oppen. 1979. Simplification by Cooperating Decision Procedures. ACM Trans. Program. Lang. Syst. 1, 2 (Oct. 1979), 245–257.

Digital Library

[43]

Michael A Nielsen. 2015. Neural Networks and Deep Learning. Determination Press.

[44]

Zvonimir Pavlinovic, Tim King, and Thomas Wies. 2014. Finding Minimum Type Error Sources. In Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications (OOPSLA ’14). ACM, New York, NY, USA, 525–542.

Digital Library

[45]

John Ross Quinlan. 1993. C4.5: Programs for Machine Learning. Morgan Kaufmann.

[46]

Vincent Rahli, J B Wells, and Fairouz Kamareddine. 2010. A constraint system for a SML type error slicer. Technical Report HW-MACS-TR-0079. Herriot Watt University.

[47]

Veselin Raychev, Martin Vechev, and Andreas Krause. 2015. Predicting Program Properties from “Big Code”. In Proceedings of the 42Nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’15). ACM, New York, NY, USA, 111–124.

Digital Library

[48]

Veselin Raychev, Martin Vechev, and Eran Yahav. 2014. Code Completion with Statistical Language Models. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’14). ACM, New York, NY, USA, 419–428.

Digital Library

[49]

Thomas Schilling. 2011. Constraint-Free Type Error Slicing. In Trends in Functional Programming. Springer Berlin Heidelberg, 1–16.

Digital Library

[50]

Eric L Seidel and Ranjit Jhala. 2017. A Collection of Novice Interactions with the OCaml Top-Level System. (June 2017).

[51]

Eric L Seidel, Ranjit Jhala, and Westley Weimer. 2016. Dynamic Witnesses for Static Type Errors (or, Ill-typed Programs Usually Go Wrong). In Proceedings of the 21st ACM SIGPLAN International Conference on Functional Programming (ICFP 2016). ACM, New York, NY, USA, 228–242.

Digital Library

[52]

Eric L. Seidel, Huma Sibghat, Kamalika Chaudhuri, Westley Weimer, and Ranjit Jhala. 2017. Learning to Blame: Localizing Novice Type Errors with Data-Driven Diagnosis. (Aug. 2017). arXiv: 1708.07583

[53]

Alejandro Serrano and Jurriaan Hage. 2016. Type Error Diagnosis for Embedded DSLs by Two-Stage Specialized Type Rules. In Programming Languages and Systems. Springer Berlin Heidelberg, 672–698.

[54]

F Tip and T B Dinesh. 2001. A Slicing-based Approach for Locating Type Errors. ACM Trans. Softw. Eng. Methodol. 10, 1 (Jan. 2001), 5–55.

Digital Library

[55]

Mitchell Wand. 1986. Finding the Source of Type Errors. In Proceedings of the 13th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL ’86). ACM, New York, NY, USA, 38–43.

Digital Library

[56]

W Eric Wong and Vidroha Debroy. 2009. A survey of software fault localization. Technical Report UTDCS-45-09. University of Texas at Dallas.

[57]

Jun Yang. 1999. Explaining Type Errors by Finding the Source of a Type Conflict. In Selected Papers from the 1st Scottish Functional Programming Workshop (SFP ’99). Intellect Books, Exeter, UK, 59–67.

[58]

Shin Yoo, Mark Harman, and David Clark. 2013. Fault Localization Prioritization: Comparing Information-theoretic and Coverage-based Approaches. ACM Trans. Softw. Eng. Methodol. 22, 3 (July 2013), 19:1–19:29.

Digital Library

[59]

Danfeng Zhang and Andrew C Myers. 2014. Toward General Diagnosis of Static Errors. In Proceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’14). ACM, New York, NY, USA, 569–581.

Digital Library

Cited By

Zhao EMaroof RDukkipati ABlinn APan ZOmar C(2024)Total Type Error Localization and Recovery with HolesProceedings of the ACM on Programming Languages10.1145/36329108:POPL(2041-2068)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632910
Bhanuka IParreaux LBinder DBrachthäuser J(2023)Getting into the Flow: Towards Better Type Error Messages for Constraint-Based Type InferenceProceedings of the ACM on Programming Languages10.1145/36228127:OOPSLA2(431-459)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622812
Ye HVasconcelos V(2023)An Optimal Structure-Aware Code Difference Framework with MaxSAT-SolverCompanion Proceedings of the 2023 ACM SIGPLAN International Conference on Systems, Programming, Languages, and Applications: Software for Humanity10.1145/3618305.3623601(43-45)Online publication date: 22-Oct-2023
https://dl.acm.org/doi/10.1145/3618305.3623601
Show More Cited By

Index Terms

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

Recommendations

Discriminative sum types locate the source of type errors

We propose a type system for locating the source of type errors in an applied lambda calculus with ML-style polymorphism. The system is based on discriminative sum types---known from work on soft typing---with annotation subtyping and recursive types. ...
Discriminative sum types locate the source of type errors
ICFP '03: Proceedings of the eighth ACM SIGPLAN international conference on Functional programming

We propose a type system for locating the source of type errors in an applied lambda calculus with ML-style polymorphism. The system is based on discriminative sum types---known from work on soft typing---with annotation subtyping and recursive types. ...
Explaining type errors in polymorphic languages

Strongly-typed languages present programmers with compile-time feedback about the type correctness of programs. Errors during polymorphic type checking take the form of a unification failure for two types. Finding the source of the type error in the code ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the ACM on Programming Languages

Proceedings of the ACM on Programming Languages Volume 1, Issue OOPSLA

October 2017

1786 pages

EISSN:2475-1421

DOI:10.1145/3152284

Issue’s Table of Contents

Copyright © 2017 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 October 2017

Published in PACMPL Volume 1, Issue OOPSLA

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
660
Total Downloads

Downloads (Last 12 months)123
Downloads (Last 6 weeks)19

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhao EMaroof RDukkipati ABlinn APan ZOmar C(2024)Total Type Error Localization and Recovery with HolesProceedings of the ACM on Programming Languages10.1145/36329108:POPL(2041-2068)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632910
Bhanuka IParreaux LBinder DBrachthäuser J(2023)Getting into the Flow: Towards Better Type Error Messages for Constraint-Based Type InferenceProceedings of the ACM on Programming Languages10.1145/36228127:OOPSLA2(431-459)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622812
Ye HVasconcelos V(2023)An Optimal Structure-Aware Code Difference Framework with MaxSAT-SolverCompanion Proceedings of the 2023 ACM SIGPLAN International Conference on Systems, Programming, Languages, and Applications: Software for Humanity10.1145/3618305.3623601(43-45)Online publication date: 22-Oct-2023
https://dl.acm.org/doi/10.1145/3618305.3623601
Peng YXie JYang QGuo HLi QXue JYuan MChandra SBlincoe KTonella P(2023)Statistical Type Inference for Incomplete ProgramsProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3616283(720-732)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3611643.3616283
Milovančević DKunčak V(2023)Proving and Disproving Equivalence of Functional Programming AssignmentsProceedings of the ACM on Programming Languages10.1145/35912587:PLDI(928-951)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591258
Ye HGu JMartinez MDurieux TMonperrus M(2022)Automated Classification of Overfitting Patches With Statically Extracted Code FeaturesIEEE Transactions on Software Engineering10.1109/TSE.2021.307175048:8(2920-2938)Online publication date: 1-Aug-2022
https://doi.org/10.1109/TSE.2021.3071750
Li RChen BZhang FSun CPeng X(2022)Detecting Runtime Exceptions by Deep Code Representation Learning with Attention-Based Graph Neural Networks2022 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER)10.1109/SANER53432.2022.00053(373-384)Online publication date: Mar-2022
https://doi.org/10.1109/SANER53432.2022.00053
Geng CYe HLi YHan TPientka BSi X(2022)Novice Type Error Diagnosis with Natural Language ModelsProgramming Languages and Systems10.1007/978-3-031-21037-2_10(196-214)Online publication date: 25-Nov-2022
https://doi.org/10.1007/978-3-031-21037-2_10
Zhang FChen BLi RPeng X(2021)A hybrid code representation learning approach for predicting method namesJournal of Systems and Software10.1016/j.jss.2021.111011(111011)Online publication date: May-2021
https://doi.org/10.1016/j.jss.2021.111011
Polikarpova NStefan DYang JItzhaky SHance TSolar-Lezama A(2020)Liquid information flow controlProceedings of the ACM on Programming Languages10.1145/34089874:ICFP(1-30)Online publication date: 2-Aug-2020
https://doi.org/10.1145/3408987
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents