Specification and verification of a transient stack
Open Access
- 11 January 2022
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 82-99
Abstract
A transient data structure is a package of an ephemeral data structure, a persistent data structure, and fast conversions between them. We describe the specification and proof of a transient stack and its iterators. This data structure is a scaled-down version of the general-purpose transient sequence data structure implemented in the OCaml library Sek. Internally, it relies on fixed-capacity arrays, or chunks, which can be shared between several ephemeral and persistent stacks. Dynamic tests are used to determine whether a chunk can be updated in place or must be copied: a chunk can be updated if it is uniquely owned or if the update is monotonic. Using CFML, which implements Separation Logic with Time Credits inside Coq, we verify the functional correctness and the amortized time complexity of this data structure. Our verification effort covers iterators, which involve direct pointers to internal chunks. The specification of iterators describes what the operations on iterators do, how much they cost, and under what circumstances an iterator is invalidated.Keywords
This publication has 38 references indexed in Scilit:
- RRB vector: a practical general purpose immutable sequence2015
- Amortized Complexity Verified2015
- Machine-Checked Verification of the Correctness and Amortized Complexity of an Efficient Union-Find Implementation2015
- The KeY Platform for Verification and Analysis of Java Programs2014
- Rely-guarantee references for refinement types over aliased mutable data2013
- Mostly-automated verification of low-level programs in computational separation logicACM SIGPLAN Notices, 2011
- Infer: An Automatic Program Verifier for Memory Safety of C Programs2011
- Finger trees: a simple general-purpose data structureJournal of Functional Programming, 2005
- Making data structures persistentJournal of Computer and System Sciences, 1989
- Amortized Computational ComplexitySIAM Journal on Algebraic Discrete Methods, 1985