Skip to main content
PRL Project

Some Normalization Properties of Martin-Lof's Type Theory and Applications

by David A. Basin, Douglas J. Howe

International Conference on Theoretical Aspects of Computer Software (TACS '91)

  • unofficial copies PDF, PS

For certain kinds of applications of type theories, the faithfulness of formalization in the theory depends on intensional, or structural, properties of objects constructed in the theory. For type theories such as LF, such properties can be established via an analysis of normal forms and types. In type theories such as Nuprl or Martin-Lof's polymorphic type theory, which are much more expressive than LF, the underlying programming language is essentially untyped, and terms proved to be in types do not necessarily have normal forms. Nevertheless, it is possible to show that for Martin-Lof's type theory, and a large class of extensions of it, a sufficient kind of normalization property does in fact hold in certain well-behaved subtheories. Applications of our results include the use of the type theory as a logical framework in the manner of LF, and an extension of the proofs-as-programs paradigm to the synthesis of verified computer hardware. For the latter application we point out some advantages to be gained by working in a more expressive type theory.

bibTex ref: BH91

cite link