2026-07-21T14:16:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18396 2024-03-06T11:01:47Z ddc:004 open_access

Proof Pearl: Faithful Computation and Extraction of μ-Recursive Algorithms in Coq Larchey-Wendling, Dominique Monin, Jean-François Unbounded linear search μ-recursive functions computational contents Coq extraction OCaml Basing on an original Coq implementation of unbounded linear search for partially decidable predicates, we study the computational contents of μ-recursive functions via their syntactic representation, and a correct by construction Coq interpreter for this abstract syntax. When this interpreter is extracted, we claim the resulting OCaml code to be the natural combination of the implementation of the μ-recursive schemes of composition, primitive recursion and unbounded minimization of partial (i.e., possibly non-terminating) functions. At the level of the fully specified Coq terms, this implies the representation of higher-order functions of which some of the arguments are themselves partial functions. We handle this issue using some techniques coming from the Braga method. Hence we get a faithful embedding of μ-recursive algorithms into Coq preserving not only their extensional meaning but also their intended computational behavior. We put a strong focus on the quality of the Coq artifact which is both self contained and with a line of code count of less than 1k in total. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dominique Larchey-Wendling and Jean-François Monin 2023 Is Part Of LIPIcs, Volume 268, 14th International Conference on Interactive Theorem Proving (ITP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITP.2023.21 urn:nbn:de:0030-drops-183963 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2023.21 eng https://creativecommons.org/licenses/by/4.0/legalcode