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 |
| Summary: | 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. |
|---|