Specification and Verification of a Transient Stack
summary
Defines and machine-verified a scaled-down transient stack implemented as a list of fixed-capacity chunks with unique identifiers for ownership, copy‑on‑write when shared, and constant‑time conversions between ephemeral and persistent views. Uses CFML (Separation Logic with time credits) inside Coq to prove functional correctness and amortized costs, including iterator invalidation and a monotonic shared memory model. Implementation is ~250 LOC OCaml, with ~1,400 LOC of Coq specs and ~1,800 LOC of proofs; verification succeeds.
AI-written summary · about