### 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 language | English (US) |
---|---|

Title of host publication | Proceedings of the 15th Symposium on Principles and Practice of Declarative Programming, PPDP 2013 |

Pages | 157-168 |

Number of pages | 12 |

DOIs | |

State | Published - Oct 15 2013 |

Event | 15th Symposium on Principles and Practice of Declarative Programming, PPDP 2013 - Madrid, Spain Duration: Sep 16 2013 → Sep 18 2013 |

### Publication series

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

### Other

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

Country | Spain |

City | Madrid |

Period | 9/16/13 → 9/18/13 |

### Fingerprint

### Keywords

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

### Cite this

*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