TY - GEN

T1 - Interpretation and programming of the reversible functional language RFUN

AU - Thomsen, Michael Kirkedal

AU - Axelsen, Holger Bock

N1 - 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).

PY - 2015/9/14

Y1 - 2015/9/14

N2 - 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.

AB - 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.

KW - Functional programming languages

KW - Program transformation

KW - Reversibilization

KW - Reversible computing

KW - Reversible functional programming

KW - Self-interpretation

UR - http://www.scopus.com/inward/record.url?scp=84983426568&partnerID=8YFLogxK

U2 - 10.1145/2897336.2897345

DO - 10.1145/2897336.2897345

M3 - Article in proceedings

AN - SCOPUS:84983426568

T3 - ACM International Conference Proceeding Series

BT - Proceedings of the 27th Symposium on the Implementation and Application of Functional Programming Languages, IFL 2015

PB - Association for Computing Machinery, Inc.

T2 - 27th Symposium on the Implementation and Application of Functional Programming Languages, IFL 2015

Y2 - 14 September 2015 through 16 September 2015

ER -