EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Total Type Error Localization and Recovery with Holes

Eric Zhao, Raef Maroof, Anand Dukkipati, Andrew Blinn, Zhiyi Pan, Cyrus Omar

Proceedings of the ACM on Programming Languages · 02.01.2024 · 8 (POPL) · 2041-2068

DOI: 10.1145/3632910 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Programming Languages, online erschienen am 05.01.2024. Verfasst von Eric Zhao und 5 weiteren Autor:innen. Die Arbeit wurde bisher 15-mal zitiert (Crossref) und nennt 51 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Type systems typically only define the conditions under which an expression is well-typed, leaving ill-typed expressions formally meaningless. This approach is insufficient as the basis for language servers driving modern programming environments, which are expected to recover from simultaneously localized errors and continue to provide a variety of downstream semantic services. This paper addresses this problem, contributing the first comprehensive formal account of total type error localization and recovery: the marked lambda calculus. In particular, we define a gradual type system for expressions with marked errors, which operate as non-empty holes, together with a total procedure for marking arbitrary unmarked expressions. We mechanize the metatheory of the marked lambda calculus in Agda and implement it, scaled up, as the new basis for Hazel, a full-scale live functional programming environment with, uniquely, no meaningless editor states. The marked lambda calculus is bidirectionally typed, so localization decisions are systematically predictable based on a local flow of typing information. Constraint-based type inference can bring more distant information to bear in discovering inconsistencies but this notoriously complicates error localization. We approach this problem by deploying constraint solving as a type-hole-filling layer atop this gradual bidirectionally typed core. Errors arising from inconsistent unification constraints are localized exclusively to type and expression holes, i.e., the system identifies unfillable holes using a system of traced provenances, rather than localized in an ad hoc manner to particular expressions. The user can then interactively shift these errors to particular downstream expressions by selecting from suggested partially consistent type hole fillings, which returns control back to the bidirectional system. We implement this type hole inference system in Hazel.

Förderung

  • National Science Foundation

Zitieren

APA

Zhao, E., Maroof, R., Dukkipati, A., Blinn, A., Pan, Z., & Omar, C. (2024). Total Type Error Localization and Recovery with Holes. Proceedings of the ACM on Programming Languages, 8(POPL), 2041-2068. https://doi.org/10.1145/3632910

Vancouver

Zhao E, Maroof R, Dukkipati A, Blinn A, Pan Z, Omar C. Total Type Error Localization and Recovery with Holes. Proceedings of the ACM on Programming Languages. 2024;8(POPL):2041-2068. doi:10.1145/3632910

BibTeX
@article{Zhao2024,
  author = {Zhao, Eric and Maroof, Raef and Dukkipati, Anand and Blinn, Andrew and Pan, Zhiyi and Omar, Cyrus},
  title = {Total Type Error Localization and Recovery with Holes},
  journal = {Proceedings of the ACM on Programming Languages},
  year = {2024},
  volume = {8},
  number = {POPL},
  pages = {2041--2068},
  doi = {10.1145/3632910}
}
Kostenlos starten →