Journal article
A Type-Based Approach to Divide-and-Conquer Recursion in Coq
Proceedings of ACM on programming languages, Vol.7(POPL), pp.61-90
01/09/2023
DOI: 10.1145/3571196
Abstract
This paper proposes a new approach to writing and verifying divide-and-conquer programs in Coq. Extending the rich line of previous work on algebraic approaches to recursion schemes, we present an algebraic approach to divide-and-conquer recursion: recursions are represented as a form of algebra, and from outer recursions, one may initiate inner recursions that can construct data upon which the outer recursions may legally recurse. Termination is enforced entirely by the typing discipline of our recursion schemes. Despite this, our approach requires little from the underlying type system, and can be implemented in System F ω plus a limited form of positive-recursive types. Our implementation of the method in Coq does not rely on structural recursion or on dependent types. The method is demonstrated on several examples, including mergesort, quicksort, Harper’s regular-expression matcher, and others. An indexed version is also derived, implementing a form of divide-and-conquer induction that can be used to reason about functions defined via our method.
Details
- Title: Subtitle
- A Type-Based Approach to Divide-and-Conquer Recursion in Coq
- Creators
- Pedro Abreu - Purdue University SystemBenjamin Delaware - Purdue University SystemAlex Hubers - University of IowaChrista Jenkins - University of IowaJ. Garrett Morris - University of IowaAaron Stump - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Proceedings of ACM on programming languages, Vol.7(POPL), pp.61-90
- DOI
- 10.1145/3571196
- ISSN
- 2475-1421
- eISSN
- 2475-1421
- Language
- English
- Date published
- 01/09/2023
- Academic Unit
- Computer Science
- Record Identifier
- 9984411076902771
Metrics
4 Record Views