Program-ing finger trees in C oq
Author:
Open Access
- 1 October 2007
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 42 (9) , 13-24
Abstract
Finger Trees (Hinze & Paterson, 2006) are a general purpose persistent data structure with good performance. Their genericity permits developing a wealth of structures like ordered sequences or interval trees on top of a single implementation. However, the type systems used by current functional languages do not guarantee the coherent parameterization and specialization of Finger Trees, let alone the correctness of their implementation. We present a certified implementation of Finger Trees solving these problems using the Program extension of Coq. We not only implement the structure but also prove its invariants along the way, which permit building certified structures on top of Finger Trees in an elegant way.Keywords
This publication has 14 references indexed in Scilit:
- Concoqtion2007
- On the Strength of Proof-Irrelevant Type TheoriesLecture Notes in Computer Science, 2006
- Finger trees: a simple general-purpose data structureJournal of Functional Programming, 2005
- Inductive definitions in the system Coq rules and properties2005
- Languages of the futureACM SIGPLAN Notices, 2004
- The view from the leftJournal of Functional Programming, 2004
- Inductive Families Need Not Store Their Indices2004
- Functors for Proofs and Programs2004
- A New Extraction for Coq2003
- Synthesizing proofs from programs in the Calculus of Inductive ConstructionsLecture Notes in Computer Science, 1995