Type inference verified: Algorithm \({\mathcal W}\) in Isabelle/HOL (Q4246952)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1301739
Language Label Description Also known as
default for all languages
No label defined
    English
    Type inference verified: Algorithm \({\mathcal W}\) in Isabelle/HOL
    scientific article; zbMATH DE number 1301739

      Statements

      0 references
      0 references
      13 December 1999
      0 references
      simply typed lambda calculus
      0 references
      Mini-ML
      0 references
      computation of the most general type
      0 references
      type inference algorithm
      0 references
      machine-checked proof of correctness and completeness
      0 references
      0 references
      0 references
      0 references
      Type inference verified: Algorithm \({\mathcal W}\) in Isabelle/HOL (English)
      0 references
      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].
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references