Mechanizing Logical Relations using Contextual Type Theory
Abstract. The logical framework LF supports elegant encodings of for-mal systems using higher-order abstract syntax, modelling binders in the object language as binders in the metalanguage. However, reasoning about formal systems in LF via logical relations has been challenging. Im-plementing such p...
Main Authors: | , |
---|---|
Other Authors: | |
Format: | Text |
Language: | English |
Subjects: | |
Online Access: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.673.3341 http://www.cs.mcgill.ca/%7Ebpientka/papers/logrel.pdf |
id |
ftciteseerx:oai:CiteSeerX.psu:10.1.1.673.3341 |
---|---|
record_format |
openpolar |
spelling |
ftciteseerx:oai:CiteSeerX.psu:10.1.1.673.3341 2023-05-15T15:41:37+02:00 Mechanizing Logical Relations using Contextual Type Theory Andrew Cave Brigitte Pientka The Pennsylvania State University CiteSeerX Archives application/pdf http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.673.3341 http://www.cs.mcgill.ca/%7Ebpientka/papers/logrel.pdf en eng http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.673.3341 http://www.cs.mcgill.ca/%7Ebpientka/papers/logrel.pdf Metadata may be used without restrictions as long as the oai identifier remains attached to it. http://www.cs.mcgill.ca/%7Ebpientka/papers/logrel.pdf logical relations logical frameworks Beluga text ftciteseerx 2016-01-08T17:28:39Z Abstract. The logical framework LF supports elegant encodings of for-mal systems using higher-order abstract syntax, modelling binders in the object language as binders in the metalanguage. However, reasoning about formal systems in LF via logical relations has been challenging. Im-plementing such proofs directly is beyond the logical strength of systems such as Twelf and Delphin. In this paper, we use the proof environment Beluga, which provides a dependently typed reasoning language on top of LF, to give a completeness proof of algorithmic equality. There are two key aspects of Beluga which we crucially rely upon: 1) we directly en-code the logical relation using recursive types and higher-order functions 2) we exploit Beluga’s support for contexts and the equational theory of substitutions. This leads to a direct and compact mechanization, demon-strating Beluga’s strength at formalizing logical relations proofs. Text Beluga Beluga* Unknown |
institution |
Open Polar |
collection |
Unknown |
op_collection_id |
ftciteseerx |
language |
English |
topic |
logical relations logical frameworks Beluga |
spellingShingle |
logical relations logical frameworks Beluga Andrew Cave Brigitte Pientka Mechanizing Logical Relations using Contextual Type Theory |
topic_facet |
logical relations logical frameworks Beluga |
description |
Abstract. The logical framework LF supports elegant encodings of for-mal systems using higher-order abstract syntax, modelling binders in the object language as binders in the metalanguage. However, reasoning about formal systems in LF via logical relations has been challenging. Im-plementing such proofs directly is beyond the logical strength of systems such as Twelf and Delphin. In this paper, we use the proof environment Beluga, which provides a dependently typed reasoning language on top of LF, to give a completeness proof of algorithmic equality. There are two key aspects of Beluga which we crucially rely upon: 1) we directly en-code the logical relation using recursive types and higher-order functions 2) we exploit Beluga’s support for contexts and the equational theory of substitutions. This leads to a direct and compact mechanization, demon-strating Beluga’s strength at formalizing logical relations proofs. |
author2 |
The Pennsylvania State University CiteSeerX Archives |
format |
Text |
author |
Andrew Cave Brigitte Pientka |
author_facet |
Andrew Cave Brigitte Pientka |
author_sort |
Andrew Cave |
title |
Mechanizing Logical Relations using Contextual Type Theory |
title_short |
Mechanizing Logical Relations using Contextual Type Theory |
title_full |
Mechanizing Logical Relations using Contextual Type Theory |
title_fullStr |
Mechanizing Logical Relations using Contextual Type Theory |
title_full_unstemmed |
Mechanizing Logical Relations using Contextual Type Theory |
title_sort |
mechanizing logical relations using contextual type theory |
url |
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.673.3341 http://www.cs.mcgill.ca/%7Ebpientka/papers/logrel.pdf |
genre |
Beluga Beluga* |
genre_facet |
Beluga Beluga* |
op_source |
http://www.cs.mcgill.ca/%7Ebpientka/papers/logrel.pdf |
op_relation |
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.673.3341 http://www.cs.mcgill.ca/%7Ebpientka/papers/logrel.pdf |
op_rights |
Metadata may be used without restrictions as long as the oai identifier remains attached to it. |
_version_ |
1766374514281676800 |