TY - GEN

T1 - Reasoning about higher-order relational specifications

AU - Wang, Yuting

AU - Chaudhuri, Kaustuv

AU - Gacek, Andrew

AU - Nadathur, Gopalan

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - formal specifications

KW - higher-order abstract syntax

KW - induction over higher-order specifications

KW - meta-theoretic reasoning

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

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

U2 - 10.1145/2505879.2505889

DO - 10.1145/2505879.2505889

M3 - Conference contribution

AN - SCOPUS:84885229030

SN - 9781450321549

T3 - Proceedings of the 15th Symposium on Principles and Practice of Declarative Programming, PPDP 2013

SP - 157

EP - 168

BT - Proceedings of the 15th Symposium on Principles and Practice of Declarative Programming, PPDP 2013

T2 - 15th Symposium on Principles and Practice of Declarative Programming, PPDP 2013

Y2 - 16 September 2013 through 18 September 2013

ER -