\n
We provide a plugin extracting Coq functions of simple polymorphic types to the (untyped) call-by-value ?-calculus L. The plugin is implemented in the MetaCoq framework and entirely written in Coq. We provide Ltac tactics to automatically verify the extracted terms w.r.t a logical relation connecting Coq functions with correct extractions and time bounds, essentially performing a certifying translation and running time validation. We provide three case studies: A universal L-term obtained as extraction from the Coq definition of a step-indexed self-interpreter for \L, a many-reduction from solvability of Diophantine equations to the halting problem of L, and a polynomial-time simulation of Turing machines in L.
<a href="https://github.com/uds-psl/certifying-extraction-with-time-bounds">Link to Coq plugin and formalisation</a> - <a href="https://arxiv.org/abs/1904.11818">Also available at arXiv</a>