Algeo: An Algebraic Approach to Reversibility

Fritz Henglein, Robin Kaarsgaard, Mikkel Kragh Mathiesen*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

We present Algeo, a functional logic programming language based on the theory of infinite dimensional modules. Algeo is reversible in the sense that every function has a generalised inverse, an adjoint, which can be thought of as an inverse execution of the forward function. In particular, when the given function is invertible, the adjoint is guaranteed to coincide with the inverse.

Algeo generalises “ordinary” forward-backward deterministic reversible programming by permitting relational and probabilistic features. This allows functions to be defined in a multitude of ways, which we summarise by the motto that “all definitions are extensional characterisations; all extensional characterisations are definitions.”

We describe the syntax, type system, and the axiomatic semantics of Algeo, and showcase novel features of the language through examples.
Original languageEnglish
Title of host publicationReversible Computation
EditorsClaudio Antares Mezzina, Krzysztof Podlaski
PublisherSpringer
Publication date28. Jun 2022
Pages128-145
ISBN (Print)978-3-031-09004-2
ISBN (Electronic)978-3-031-09005-9
DOIs
Publication statusPublished - 28. Jun 2022
Externally publishedYes
Event14th International Conference on Reversible Computation - Urbino, Italy
Duration: 5. Jun 20226. Jun 2022

Conference

Conference14th International Conference on Reversible Computation
Country/TerritoryItaly
CityUrbino
Period05/06/202206/06/2022
SeriesLecture Notes in Computer Science
Volume13354
ISSN0302-9743

Fingerprint

Dive into the research topics of 'Algeo: An Algebraic Approach to Reversibility'. Together they form a unique fingerprint.

Cite this