Abstract for "Encoding Dependent Types in an Intuitionistic Logic"
Encoding Dependent Types in an Intuitionistic Logic
Amy Felty. In Gérard Huet and Gordon D. Plotkin, editors, Logical Frameworks, Cambridge University Press, 1991.

Abstract: Various languages have been proposed as specification languages for representing a wide variety of logics. The development of typed lambda-calculi has been one approach toward this goal. The logical framework (LF), a lambda-calculus with dependent types is one example of such a language. A small subset of intuitionistic logic with quantification over the simply typed lambda-calculus has also been proposed as a framework for specifying general logics. The logic of hereditary Harrop formulas with quantification at all non-predicate types, denoted here as hh-omega, is such a meta-logic. In this paper, we show how to translate specifications in LF into hh-omega specifications in a direct and natural way, so that correct typing in LF corresponds to intuitionistic provability in hh-omega. In addition, we demonstrate a direct correspondence between proofs in these two systems. The logic of hh-omega can be implemented using such logic programming techniques as providing operational interpretations to the connectives and implementing unification on lambda-terms. As a result, relating these two languages makes it possible to provide direct implementations of proof checkers and theorem provers for logics specified in LF.