Reasoning about higher-order relational specifications

Yuting Wang, Kaustuv Chaudhuri, Andrew Gacek, Gopalan Nadathur

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations

Abstract

The logic of hereditary Harrop formulas (HH) has proven useful for specifying a wide range of formal systems that are commonly presented via syntax-directed rules that make use of contexts and side-conditions. The two-level logic approach, as implemented in the Abella theorem prover, embeds the HH specification logic within a rich reasoning logic that supports inductive and co-inductive definitions, an equality predicate, and generic quantification. Properties of the encoded systems can then be proved through the embedding, with special benefit being extracted from the transparent correspondence between HH derivations and those in the encoded formal systems. The versatility of HH relies on the free use of nested implications, leading to dynamically changing assumption sets in derivations. Realizing an induction principle in this situation is nontrivial and the original Abella system uses only a subset of HH for this reason. We develop a method here for supporting inductive reasoning over all of HH. Our approach relies on the ability to characterize dynamically changing contexts through finite inductive definitions, and on a modified encoding of backchaining for HH that allows these finite characterizations to be used in inductive arguments. We demonstrate the effectiveness of our approach through examples of formal reasoning on specifications with nested implications in an extended version of Abella.

Original languageEnglish (US)
Title of host publicationProceedings of the 15th Symposium on Principles and Practice of Declarative Programming, PPDP 2013
Pages157-168
Number of pages12
DOIs
StatePublished - Oct 15 2013
Event15th Symposium on Principles and Practice of Declarative Programming, PPDP 2013 - Madrid, Spain
Duration: Sep 16 2013Sep 18 2013

Publication series

NameProceedings of the 15th Symposium on Principles and Practice of Declarative Programming, PPDP 2013

Other

Other15th Symposium on Principles and Practice of Declarative Programming, PPDP 2013
CountrySpain
CityMadrid
Period9/16/139/18/13

    Fingerprint

Keywords

  • formal specifications
  • higher-order abstract syntax
  • induction over higher-order specifications
  • meta-theoretic reasoning

Cite this

Wang, Y., Chaudhuri, K., Gacek, A., & Nadathur, G. (2013). Reasoning about higher-order relational specifications. In Proceedings of the 15th Symposium on Principles and Practice of Declarative Programming, PPDP 2013 (pp. 157-168). (Proceedings of the 15th Symposium on Principles and Practice of Declarative Programming, PPDP 2013). https://doi.org/10.1145/2505879.2505889