Type inference verified: Algorithm W in Isabelle/HOL
Most functional programming languages have a common core: the simply typed \(\lambda\)-calculus enriched with let-expressions, i.e. local definitions of polymorphic values. This language is called Mini-ML. The set of well-typed Mini-ML expressions is inductively defined by a set of inference rules. One of the key properties of Mini-ML is that every well-typed expression has a most general type. The computation of the most general type is called type inference. It was first studied by \textit{R. Hindley} [Trans. Am. Math. Soc. 146, 29-60 (1969; Zbl 0196.01501)] in the context of combinatory logic and later independently by \textit{R. Milner} [J. Comput. Syst. Sci. 17, 348-375 (1978; Zbl 0388.68003)] for Mini-ML. Milner's type inference algorithm is known as algorithm \({\mathcal W}\). L. Damas proved the completeness of \({\mathcal W}\). This paper presents the first machine-checked proof of correctness and completeness of \({\mathcal W}\). It is an extension of the work by \textit{D. Nazareth} and \textit{T. Nipkow} [Lect. Notes Comput. Sci. 1125, 331-346 (1996)], who treated the monomorphic case (no let-expressions). A partial verification of \({\mathcal W}\) in the proof checker Coq is reported by \textit{C. Dubois} and \textit{V. Ménissier-Morain} [in: J. von Wright et al. (eds.), Suppl. Proc. 9th Int. Conf. Theorem Proving in Higher-Order Logic, Turku Centre Comput. Sci., 15-30 (1996)]. Our paper provides the definition of (due to lack of space: almost) all concepts, the key lemmas, but almost no proofs. The complete development is accessible via \url{http://www4.in.tum.de/~nipkow/}. For the entire collection see [Zbl 0898.00024].
- Haskell overloading is DEXPTIME-complete
- Isabelle/HOL
- Proofs of a set of hybrid let-polymorphic type inference algorithms
- Type inference verified: Algorithm \(\mathcal W\) in Isabelle/H0L
- Certification of a type inference tool for ML: Damas-Milner within Coq
- Nominal verification of algorithm \(W\)
- A logical algorithm for ML type inference
- An experiment in type inference and verification by abstract interpretation
- HM(X) type inference is CLP(X) solving
- Formal verification of algorithm \(\mathcal{W}\): the monomorphic case
- Mini ML
This page was built for publication: Type inference verified: Algorithm \({\mathcal W}\) in Isabelle/HOL
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4246952)