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


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
Publication date28. Jun 2022
ISBN (Print)978-3-031-09004-2
ISBN (Electronic)978-3-031-09005-9
Publication statusPublished - 28. Jun 2022
Externally publishedYes
Event14th International Conference on Reversible Computation - Urbino, Italy
Duration: 5. Jun 20226. Jun 2022


Conference14th International Conference on Reversible Computation
SeriesLecture Notes in Computer Science


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

Cite this