TY - GEN

T1 - A meta-programming approach to realizing dependently typed logic programming

AU - Snow, Zachary

AU - Baelde, David

AU - Nadathur, Gopalan

PY - 2010

Y1 - 2010

N2 - Dependently typed λ-calculi such as the Logical Framework (LF) can encode relationships between terms in types and can naturally capture correspondences between formulas and their proofs. Such calculi can also be given a logic programming interpretation: the Twelf system is based on such an interpretation of LF. We consider here whether a conventional logic programming language can provide the benefits of a Twelf-like system for encoding type and proof-and-formula dependencies. In particular, we present a simple mapping from LF specifications to a set of formulas in the higher-order hereditary Harrop (hohh) language, that relates derivations and proof-search between the two frameworks. We then show that this encoding can be improved by exploiting knowledge of the well-formedness of the original LF specifications to elide much redundant type-checking information. The resulting logic program has a structure that closely resembles the original specification, thereby allowing LF specifications to be viewed as hohh meta-programs. Using the Teyjus implementation of λProlog, we show that our translation provides an efficient means for executing LF specifications, complementing the ability that the Twelf system provides for reasoning about them.

AB - Dependently typed λ-calculi such as the Logical Framework (LF) can encode relationships between terms in types and can naturally capture correspondences between formulas and their proofs. Such calculi can also be given a logic programming interpretation: the Twelf system is based on such an interpretation of LF. We consider here whether a conventional logic programming language can provide the benefits of a Twelf-like system for encoding type and proof-and-formula dependencies. In particular, we present a simple mapping from LF specifications to a set of formulas in the higher-order hereditary Harrop (hohh) language, that relates derivations and proof-search between the two frameworks. We then show that this encoding can be improved by exploiting knowledge of the well-formedness of the original LF specifications to elide much redundant type-checking information. The resulting logic program has a structure that closely resembles the original specification, thereby allowing LF specifications to be viewed as hohh meta-programs. Using the Teyjus implementation of λProlog, we show that our translation provides an efficient means for executing LF specifications, complementing the ability that the Twelf system provides for reasoning about them.

KW - Dependently typed lambda calculi

KW - Higher-order logic programming

KW - Logical frameworks

KW - Translation

UR - http://www.scopus.com/inward/record.url?scp=77956234596&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77956234596&partnerID=8YFLogxK

U2 - 10.1145/1836089.1836113

DO - 10.1145/1836089.1836113

M3 - Conference contribution

AN - SCOPUS:77956234596

SN - 9781450301329

T3 - PPDP'10 - Proceedings of the 2010 Symposium on Principles and Practice of Declarative Programming

SP - 187

EP - 198

BT - PPDP'10 - Proceedings of the 2010 Symposium on Principles and Practice of Declarative Programming

T2 - 12th International ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming, PPDP 2010

Y2 - 26 July 2010 through 28 July 2010

ER -