Interpretation and programming of the reversible functional language RFUN
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Interpretation and programming of the reversible functional language RFUN. / Thomsen, Michael Kirkedal; Axelsen, Holger Bock.
Proceedings of the 27th Symposium on the Implementation and Application of Functional Programming Languages, IFL 2015. Association for Computing Machinery, Inc., 2015. 8 (ACM International Conference Proceeding Series, Vol. 14-16-September-2015).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
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 -
ID: 359608372