More Web Proxy on the site http://driver.im/

research-article

Open access

Getting into the Flow: Towards Better Type Error Messages for Constraint-Based Type Inference

Authors:

Lionel Parreaux,

Jonathan Immanuel BrachthäuserAuthors Info & Claims

Proceedings of the ACM on Programming Languages, Volume 7, Issue OOPSLA2

Article No.: 237, Pages 431 - 459

https://doi.org/10.1145/3622812

Published: 16 October 2023 Publication History

Abstract

Creating good type error messages for constraint-based type inference systems is difficult. Typical type error messages reflect implementation details of the underlying constraint-solving algorithms rather than the specific factors leading to type mismatches. We propose using subtyping constraints that capture data flow to classify and explain type errors. Our algorithm explains type errors as faulty data flows, which programmers are already used to reasoning about, and illustrates these data flows as sequences of relevant program locations. We show that our ideas and algorithm are not limited to languages with subtyping, as they can be readily integrated with Hindley-Milner type inference. In addition to these core contributions, we present the results of a user study to evaluate the quality of our messages compared to other implementations. While the quantitative evaluation does not show that flow-based messages improve the localization or understanding of the causes of type errors, the qualitative evaluation suggests a real need and demand for flow-based messages.

References

[1]

Brett A. Becker, Paul Denny, Raymond Pettit, Durell Bouchard, Dennis J. Bouvier, Brian Harrington, Amir Kamil, Amey Karkare, Chris McDonald, Peter-Michael Osera, Janice L. Pearce, and James Prather. 2019. Compiler Error Messages Considered Unhelpful: The Landscape of Text-Based Programming Error Message Research. In Proceedings of the Working Group Reports on Innovation and Technology in Computer Science Education (ITiCSE-WGR ’19). Association for Computing Machinery, New York, NY, USA. 177–210. isbn:9781450375672 https://doi.org/10.1145/3344429.3372508

Digital Library

[2]

Ishan Bhanuka, Lionel Parreaux, David Binder, and Jonathan Immanuel Brachthäuser. 2023. Getting Into The Flow: Towards Better Type Error Messages for Constraint-Based Type Inference. https://doi.org/10.5281/zenodo.8332129 Implementation of the system described in the paper.

Digital Library

[3]

Stephen Dolan. 2017. Algebraic Subtyping: Distinguished Dissertation 2017. BCS, Swindon, GBR. isbn:1780174152 https://dl.acm.org/doi/book/10.5555/3180976

[4]

Stephen Dolan and Alan Mycroft. 2017. Polymorphism, Subtyping, and Type Inference in MLsub. In Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages (POPL 2017). Association for Computing Machinery, New York, NY, USA. 60–72. isbn:9781450346603 https://doi.org/10.1145/3009837.3009882

Digital Library

[5]

Benedict du Boulay, Tim O’Shea, and John Monk. 1981. The black box inside the glass box: presenting computing concepts to novices. International Journal of Man-Machine Studies, 14, 3 (1981), 237–249. issn:0020-7373 https://doi.org/10.1016/S0020-7373(81)80056-9

[6]

Olive Jean Dunn. 1964. Multiple comparisons using rank sums. Technometrics, 6, 3 (1964), 241–252. https://doi.org/10.1080/00401706.1964.10490181

[7]

Janet Feigenspan, Christian Kästner, Jörg Liebig, Sven Apel, and Stefan Hanenberg. 2012. Measuring programming experience. In 2012 20th IEEE international conference on program comprehension (ICPC). 73–82. https://doi.org/10.1109/ICPC.2012.6240511

[8]

Holger Gast. 2005. Explaining ML Type Errors by Data Flows. In Implementation and Application of Functional Languages, Clemens Grelck, Frank Huch, Greg J. Michaelson, and Phil Trinder (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 72–89. isbn:978-3-540-32038-8 https://doi.org/10.1007/11431664_5

Digital Library

[9]

Chuqin Geng, Haolin Ye, Yixuan Li, Tianyu Han, Brigitte Pientka, and Xujie Si. 2022. Novice Type Error Diagnosis with Natural Language Models. In Programming Languages and Systems, Ilya Sergey (Ed.). Springer Nature Switzerland, 196–214. isbn:978-3-031-21037-2 https://doi.org/10.1007/978-3-031-21037-2_10

Digital Library

[10]

Bastiaan Heeren. 2005. Top quality type error messages. Ph. D. Dissertation. Utrecht University.

[11]

Bastiaan Heeren, Daan Leijen, and Arjan van IJzendoorn. 2003. Helium, for Learning Haskell. In Proceedings of the 2003 ACM SIGPLAN Workshop on Haskell (Haskell ’03). Association for Computing Machinery, New York, NY, USA. 62–71. isbn:1581137583 https://doi.org/10.1145/871895.871902

Digital Library

[12]

Felix Henninger, Yury Shevchenko, Ulf K Mertens, Pascal J Kieslich, and Benjamin E Hilbig. 2021. lab.js: A free, open, online study builder. Behavior Research Methods, 1–18. https://doi.org/10.3758/s13428-019-01283-5

[13]

Simon Peyton Jones, Dimitrios Vytiniotis, Stephanie Weirich, and Mark Shields. 2007. Practical type inference for arbitrary-rank types. Journal of Functional Programming, 17, 1 (2007), 1–82. https://doi.org/10.1017/S0956796806006034

Digital Library

[14]

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). Association for Computing Machinery, New York, NY, USA. 165–176. isbn:9781450343909 https://doi.org/10.1145/2931037.2931051

Digital Library

[15]

William H. Kruskal and W. Allen Wallis. 1952. Use of Ranks in One-Criterion Variance Analysis. J. Amer. Statist. Assoc., 47, 260 (1952), 583–621. https://doi.org/10.1080/01621459.1952.10483441

[16]

Didier Le Botlan and Didier Rémy. 2014. MLF: Raising ML to the Power of System F. SIGPLAN Not., 49, 4S (2014), jul, 52–63. issn:0362-1340 https://doi.org/10.1145/2641638.2641653

Digital Library

[17]

Calvin Loncaric, Satish Chandra, Cole Schlesinger, and Manu Sridharan. 2016. A Practical Framework for Type Inference Error Explanation. SIGPLAN Not., 51, 10 (2016), oct, 781–799. issn:0362-1340 https://doi.org/10.1145/3022671.2983994

Digital Library

[18]

Guillaume Marceau, Kathi Fisler, and Shriram Krishnamurthi. 2011. Measuring the Effectiveness of Error Messages Designed for Novice Programmers. In Proceedings of the 42nd ACM Technical Symposium on Computer Science Education (SIGCSE ’11). Association for Computing Machinery, New York, NY, USA. 499–504. isbn:9781450305006 https://doi.org/10.1145/1953163.1953308

Digital Library

[19]

Guillaume Marceau, Kathi Fisler, and Shriram Krishnamurthi. 2011. Mind Your Language: On Novices’ Interactions with Error Messages. Onward! 2011. Association for Computing Machinery, New York, NY, USA. 3–18. isbn:9781450309417 https://doi.org/10.1145/2048237.2048241

Digital Library

[20]

Matthias Neubauer and Peter Thiemann. 2003. Discriminative Sum Types Locate the Source of Type Errors. In Proceedings of the Eighth ACM SIGPLAN International Conference on Functional Programming (ICFP ’03). Association for Computing Machinery, New York, NY, USA. 15–26. isbn:1581137567 https://doi.org/10.1145/944705.944708

Digital Library

[21]

Lionel Parreaux. 2020. The Simple Essence of Algebraic Subtyping: Principal Type Inference with Subtyping Made Easy (Functional Pearl). Proc. ACM Program. Lang., 4, ICFP (2020), Article 124, Aug., 28 pages. https://doi.org/10.1145/3409006

Digital Library

[22]

Lionel Parreaux and Chun Yin Chau. 2022. MLstruct: Principal Type Inference in a Boolean Algebra of Structural Types. Proc. ACM Program. Lang., 6, OOPSLA2 (2022), Article 141, oct, 30 pages. https://doi.org/10.1145/3563304

Digital Library

[23]

Didier Rémy. 1992. Extension of ML type system with a sorted equation theory on types. INRIA. https://hal.inria.fr/inria-00077006 Projet FORMEL

[24]

Eric L. Seidel, Huma Sibghat, Kamalika Chaudhuri, Westley Weimer, and Ranjit Jhala. 2017. Learning to Blame: Localizing Novice Type Errors with Data-Driven Diagnosis. Proc. ACM Program. Lang., 1, OOPSLA (2017), Article 60, oct, 27 pages. https://doi.org/10.1145/3138818

Digital Library

[25]

Yury Shevchenko. 2022. Open Lab: A web application for running and sharing online experiments. Behavior Research Methods, 54, 6 (2022), 3118–3125. https://doi.org/10.3758/s13428-021-01776-2

[26]

Dimitrios Vytiniotis, Simon Peyton Jones, and Tom Schrijvers. 2010. Let should not be generalized. In Proceedings of the 5th ACM SIGPLAN workshop on Types in language design and implementation. 39–50. https://doi.org/10.1145/1708016.1708023

Digital Library

[27]

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). Association for Computing Machinery, New York, NY, USA. 38–43. isbn:9781450373470 https://doi.org/10.1145/512644.512648

Digital Library

[28]

John Wrenn and Shriram Krishnamurthi. 2017. Error Messages Are Classifiers: A Process to Design and Evaluate Error Messages. Onward! 2017. Association for Computing Machinery, New York, NY, USA. 134–147. isbn:9781450355308 https://doi.org/10.1145/3133850.3133862

Digital Library

[29]

Danfeng Zhang and Andrew C. Myers. 2014. Toward General Diagnosis of Static Errors. SIGPLAN Not., 49, 1 (2014), jan, 569–581. issn:0362-1340 https://doi.org/10.1145/2578855.2535870

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
Parreaux LBoruch-Gruszecki AFan AChau C(2024)When Subtyping Constraints Liberate: A Novel Type Inference Approach for First-Class PolymorphismProceedings of the ACM on Programming Languages10.1145/36328908:POPL(1418-1450)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632890
Liu YHuang RYang JYang BWu S(2024)TLFL: Token-Level Fault Localization for Novice Programs via Graph Representation Learning2024 IEEE 35th International Symposium on Software Reliability Engineering Workshops (ISSREW)10.1109/ISSREW63542.2024.00068(135-142)Online publication date: 28-Oct-2024
https://doi.org/10.1109/ISSREW63542.2024.00068

Index Terms

Getting into the Flow: Towards Better Type Error Messages for Constraint-Based Type Inference

Recommendations

When Subtyping Constraints Liberate: A Novel Type Inference Approach for First-Class Polymorphism

Type inference in the presence of first-class or “impredicative” second-order polymorphism à la System F has been an active research area for several decades, with original works dating back to the end of the 80s. Yet, until now many basic problems ...
Polymorphism, subtyping, and type inference in MLsub
POPL '17

We present a type system combining subtyping and ML-style parametric polymorphism. Unlike previous work, our system supports type inference and has compact principal types. We demonstrate this system in the minimal language MLsub, which types a strict ...
Polymorphism, subtyping, and type inference in MLsub
POPL '17: Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages

We present a type system combining subtyping and ML-style parametric polymorphism. Unlike previous work, our system supports type inference and has compact principal types. We demonstrate this system in the minimal language MLsub, which types a strict ...

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 7, Issue OOPSLA2

October 2023

2250 pages

EISSN:2475-1421

DOI:10.1145/3554312

Editor:
Michael Hicks
Amazon, USA

Issue’s Table of Contents

Copyright © 2023 Owner/Author.

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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 October 2023

Published in PACMPL Volume 7, Issue OOPSLA2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
822
Total Downloads

Downloads (Last 12 months)616
Downloads (Last 6 weeks)110

Reflects downloads up to 03 Jan 2025

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
Parreaux LBoruch-Gruszecki AFan AChau C(2024)When Subtyping Constraints Liberate: A Novel Type Inference Approach for First-Class PolymorphismProceedings of the ACM on Programming Languages10.1145/36328908:POPL(1418-1450)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632890
Liu YHuang RYang JYang BWu S(2024)TLFL: Token-Level Fault Localization for Novice Programs via Graph Representation Learning2024 IEEE 35th International Symposium on Software Reliability Engineering Workshops (ISSREW)10.1109/ISSREW63542.2024.00068(135-142)Online publication date: 28-Oct-2024
https://doi.org/10.1109/ISSREW63542.2024.00068

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