Cargando…

Reversible Computations in Logic Programming

In this work, we say that a computation is reversible if one can find a procedure to undo the steps of a standard (or forward) computation in a deterministic way. While logic programs are often invertible (e.g., one can use the same predicate for adding and for subtracting natural numbers), computat...

Descripción completa

Detalles Bibliográficos
Autor principal: Vidal, Germán
Formato: Online Artículo Texto
Lenguaje:English
Publicado: 2020
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7342172/
http://dx.doi.org/10.1007/978-3-030-52482-1_15
_version_ 1783555393310425088
author Vidal, Germán
author_facet Vidal, Germán
author_sort Vidal, Germán
collection PubMed
description In this work, we say that a computation is reversible if one can find a procedure to undo the steps of a standard (or forward) computation in a deterministic way. While logic programs are often invertible (e.g., one can use the same predicate for adding and for subtracting natural numbers), computations are not reversible in the above sense. In this paper, we present a so-called Landauer embedding for SLD resolution, the operational principle of logic programs, so that it becomes reversible. A proof-of-concept implementation of a reversible debugger for Prolog that follows the ideas in this paper has been developed and is publicly available.
format Online
Article
Text
id pubmed-7342172
institution National Center for Biotechnology Information
language English
publishDate 2020
record_format MEDLINE/PubMed
spelling pubmed-73421722020-07-09 Reversible Computations in Logic Programming Vidal, Germán Reversible Computation Article In this work, we say that a computation is reversible if one can find a procedure to undo the steps of a standard (or forward) computation in a deterministic way. While logic programs are often invertible (e.g., one can use the same predicate for adding and for subtracting natural numbers), computations are not reversible in the above sense. In this paper, we present a so-called Landauer embedding for SLD resolution, the operational principle of logic programs, so that it becomes reversible. A proof-of-concept implementation of a reversible debugger for Prolog that follows the ideas in this paper has been developed and is publicly available. 2020-06-17 /pmc/articles/PMC7342172/ http://dx.doi.org/10.1007/978-3-030-52482-1_15 Text en © Springer Nature Switzerland AG 2020 This article is made available via the PMC Open Access Subset for unrestricted research re-use and secondary analysis in any form or by any means with acknowledgement of the original source. These permissions are granted for the duration of the World Health Organization (WHO) declaration of COVID-19 as a global pandemic.
spellingShingle Article
Vidal, Germán
Reversible Computations in Logic Programming
title Reversible Computations in Logic Programming
title_full Reversible Computations in Logic Programming
title_fullStr Reversible Computations in Logic Programming
title_full_unstemmed Reversible Computations in Logic Programming
title_short Reversible Computations in Logic Programming
title_sort reversible computations in logic programming
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7342172/
http://dx.doi.org/10.1007/978-3-030-52482-1_15
work_keys_str_mv AT vidalgerman reversiblecomputationsinlogicprogramming