Interpretation and programming of the reversible functional language RFUN

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

RFUN is a small first-order reversible functional language introduced by Yokoyama et al. in 2012. The present paper aims to further the understanding of reversible functional programming (and RFUN in particular) by describing implementations in, and of, the RFUN language. After briefly summarizing RFUN in terms of syntax and semantics, we first (informally) describe a transformation from the simple irreversible first-order language FUN to RFUN. This highlights how irreversibility is avoided in RFUN, such as in the use of the so-called first-match policy. It also emphasizes the fact that RFUN is traceless, while also showing how the standard reversible (trace-full) embeddings of Landauer and Bennett can be implemented. Second, we outline (by examples) a number of the reversible functions that have been implemented in RFUN. The programming examples given here focus on Peano arithmetic and list functions, and are intended to show various useful programming techniques of the reversible functional programming paradigm. Finally, we discuss the implementation of RFUN. This is twofold as we relate a Haskell implementation of an RFUN interpreter, to an implementation of a self-interpreter, i.e., an RFUN interpreter implemented in RFUN. Although RFUN does not have the rich and expressive syntax of Haskell - which makes programming the selfinterpreter more cumbersome in some aspects - the built-in support for reverse execution greatly reduces the code base and makes the RFUN-based self-interpreter implementation follow the formal semantics of RFUN more directly than the Haskell-based interpreter.

Original languageEnglish
Title of host publicationProceedings of the 27th Symposium on the Implementation and Application of Functional Programming Languages, IFL 2015
Number of pages13
PublisherAssociation for Computing Machinery, Inc.
Publication date14 Sep 2015
Article number8
ISBN (Electronic)9781450342735
DOIs
Publication statusPublished - 14 Sep 2015
Event27th Symposium on the Implementation and Application of Functional Programming Languages, IFL 2015 - Koblenz, Germany
Duration: 14 Sep 201516 Sep 2015

Conference

Conference27th Symposium on the Implementation and Application of Functional Programming Languages, IFL 2015
LandGermany
ByKoblenz
Periode14/09/201516/09/2015
SeriesACM International Conference Proceeding Series
Volume14-16-September-2015

Bibliographical note

Funding Information:
This work was partly funded by the European Commission under the 7th Framework Programme and partly by the Danish Council for Independent Research. We also acknowledge the support given by COST Action IC1405.

Publisher Copyright:
© 2015 Copyright held by the owner/author(s).

    Research areas

  • Functional programming languages, Program transformation, Reversibilization, Reversible computing, Reversible functional programming, Self-interpretation

ID: 359608372