Proof Pearl: Faithful Computation and Extraction of μ-Recursive Algorithms in Coq ...
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023
Konferenz
Zugriff:
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 ... : LIPIcs, Vol. 268, 14th International Conference on Interactive Theorem Proving (ITP 2023), pages 21:1-21:17 ...
Titel: |
Proof Pearl: Faithful Computation and Extraction of μ-Recursive Algorithms in Coq ...
|
---|---|
Autor/in / Beteiligte Person: | Larchey-Wendling, Dominique ; Monin, Jean-François |
Link: |
|
Veröffentlichung: | Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023 |
Medientyp: | Konferenz |
DOI: | 10.4230/lipics.itp.2023.21 |
Schlagwort: |
|
Sonstiges: |
|