Towards a reversible functional language

Tetsuo Yokoyama, Holger Bock Axelsen, Robert Glück

32 Citations (Scopus)

Abstract

We identify concepts of reversibility for a functional language by means of a set of semantic rules with specific properties. These properties include injectivity along with local backward determinism, an important operational property for an efficient reversible language. We define a concise reversible first-order functional language in which access to the backward semantics is provided to the programmer by inverse function calls. Reversibility guarantees that in this language a backward run (inverse interpretation) is as fast as the corresponding forward run itself. By adopting a symmetric first-match policy for case expressions, we can write overlapping patterns in case branches, as is customary in ordinary functional languages, and also in leaf expressions, unlike existing inverse interpreter methods, which enables concise programs. In patterns, the use of a duplication/equality operator also simplifies inverse computation and program inversion. We discuss the advantages of a reversible functional language using example programs, including run-length encoding. Program inversion is seen to be as lightweight as for imperative reversible languages and realized by recursive descent. Finally, we show that the proposed language is r-Turing complete.
Original languageEnglish
Title of host publicationReversible Computation : Third International Workshop, RC 2011, Gent, Belgium, July 4-5, 2011. Revised Papers
EditorsAlexis De Vos, Robert Wille
Number of pages16
PublisherSpringer
Publication date2012
Pages14-29
ISBN (Print)978-3-642-29516-4
ISBN (Electronic)978-3-642-29517-1
DOIs
Publication statusPublished - 2012
Event3rd International Workshop on Reversible Computation - Gent, Belgium
Duration: 4 Jul 20115 Jul 2011
Conference number: 3

Conference

Conference3rd International Workshop on Reversible Computation
Number3
Country/TerritoryBelgium
CityGent
Period04/07/201105/07/2011
SeriesLecture notes in computer science
Volume 7165
ISSN0302-9743

Fingerprint

Dive into the research topics of 'Towards a reversible functional language'. Together they form a unique fingerprint.

Cite this