License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITP.2023.8
URN: urn:nbn:de:0030-drops-183836
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18383/
Bosman, Roger ;
Karachalias, Georgios ;
Schrijvers, Tom
No Unification Variable Left Behind: Fully Grounding Type Inference for the HDM System
Abstract
The Hindley-Damas-Milner (HDM) system provides polymorphism, a key feature of functional programming languages such as Haskell and OCaml. It does so through a type inference algorithm, whose soundness and completeness have been well-studied and proven both manually (on paper) and mechanically (in a proof assistant). Earlier research has focused on the problem of inferring the type of a top-level expression. Yet, in practice, we also may wish to infer the type of subexpressions, either for the sake of elaboration into an explicitly-typed target language, or for reporting those types back to the programmer. One key difference between these two problems is the treatment of underconstrained types: in the former, unification variables that do not affect the overall type need not be instantiated. However, in the latter, instantiating all unification variables is essential, because unification variables are internal to the algorithm and should not leak into the output.
We present an algorithm for the HDM system that explicitly tracks the scope of all unification variables. In addition to solving the subexpression type reconstruction problem described above, it can be used as a basis for elaboration algorithms, including those that implement elaboration-based features such as type classes. The algorithm implements input and output contexts, as well as the novel concept of full contexts, which significantly simplifies the state-passing of traditional algorithms. The algorithm has been formalised and proven sound and complete using the Coq proof assistant.
BibTeX - Entry
@InProceedings{bosman_et_al:LIPIcs.ITP.2023.8,
author = {Bosman, Roger and Karachalias, Georgios and Schrijvers, Tom},
title = {{No Unification Variable Left Behind: Fully Grounding Type Inference for the HDM System}},
booktitle = {14th International Conference on Interactive Theorem Proving (ITP 2023)},
pages = {8:1--8:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-284-6},
ISSN = {1868-8969},
year = {2023},
volume = {268},
editor = {Naumowicz, Adam and Thiemann, Ren\'{e}},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18383},
URN = {urn:nbn:de:0030-drops-183836},
doi = {10.4230/LIPIcs.ITP.2023.8},
annote = {Keywords: type inference, mechanization, let-polymorphism}
}
