A Type-Based Approach to Divide-and-Conquer Recursion in Coq

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, an...

Full description

Saved in:
Bibliographic Details
Published in:Proceedings of ACM on programming languages 2023-01, Vol.7 (POPL), p.61-90, Article 3
Main Authors: Abreu, Pedro, Delaware, Benjamin, Hubers, Alex, Jenkins, Christa, Morris, J. Garrett, Stump, Aaron
Format: Article
Language:English
Subjects:
Algebraic semantics
Functional languages
Recursion
Software and its engineering
Theory of computation
Type theory
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2475-1421
2475-1421
DOI:10.1145/3571196