Formal Verification of Algorithm W: The Monomorphic Case

Dieter Nazareth and Tobias Nipkow

A formal verification of the soundness and completeness of Milner's type inference algorithm W for simply typed lambda-terms is presented. Particular attention is paid to the notorious issue of ``new'' variables. The proofs are carried out in Isabelle/HOL, the HOL instantiation of the generic theorem prover Isabelle.



author={Dieter Nazareth and Tobias Nipkow},
title={Formal Verification of Algorithm {W}: The Monomorphic Case},
booktitle={Theorem Proving in Higher Order Logics (TPHOLs'96)},
editor={J. von Wright and J. Grundy and J. Harrison},
This work has been extended by Naraschewski and Nipkow to include let.