Type inference verified: Algorithm W in Isabelle/HOL

From MaRDI portal
Publication:4246952





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].





Describes a project that uses

Uses Software






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)