License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TYPES.2022.12
URN: urn:nbn:de:0030-drops-184557
URL: https://drops.dagstuhl.de/opus/volltexte/2023/18455/
Ledein, Amélie ;
Blot, Valentin ;
Dubois, Catherine
A Semantics of 𝕂 into Dedukti
Abstract
𝕂 is a semantical framework for formally describing the semantics of programming languages thanks to a BNF grammar and rewriting rules on configurations. It is also an environment that offers various tools to help programming with the languages specified in the formalism. For example, it is possible to execute programs thanks to the generated interpreter, or to check their properties thanks to the provided automatic theorem prover called the KProver. 𝕂 is based on la Matching Logic, a first-order logic with an application and fixed-point operators, extended with symbols to encode equality, typing and rewriting. This specific la Matching Logic theory is called Kore.
Dedukti is a logical framework having for main goal the interoperability of proofs between different formal proof tools. Several translators to Dedukti exist or are under development, in order to automatically translate formalizations written, for instance, in Coq or PVS. Dedukti is based on the λΠ-calculus modulo theory, a λ-calculus with dependent types and extended with a primitive notion of computation defined by rewriting rules. The flexibility of this logical framework allows to encode many theories ranging from first-order logic to the Calculus of Constructions.
In this article, we present a paper formalization of the translation from 𝕂 into Kore, and a paper formalization and an automatic translation tool, called KaMeLo, from Kore to Dedukti in order to execute programs in Dedukti.
BibTeX - Entry
@InProceedings{ledein_et_al:LIPIcs.TYPES.2022.12,
author = {Ledein, Am\'{e}lie and Blot, Valentin and Dubois, Catherine},
title = {{A Semantics of \mathbb{K} into Dedukti}},
booktitle = {28th International Conference on Types for Proofs and Programs (TYPES 2022)},
pages = {12:1--12:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-285-3},
ISSN = {1868-8969},
year = {2023},
volume = {269},
editor = {Kesner, Delia and P\'{e}drot, Pierre-Marie},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18455},
URN = {urn:nbn:de:0030-drops-184557},
doi = {10.4230/LIPIcs.TYPES.2022.12},
annote = {Keywords: Programming language, Semantics, Rewriting, Logical framework, Type theory}
}