Interpretation and programming of the reversible functional language RFUN

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

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.

OriginalsprogEngelsk
TitelProceedings of the 27th Symposium on the Implementation and Application of Functional Programming Languages, IFL 2015
Antal sider13
ForlagAssociation for Computing Machinery, Inc.
Publikationsdato14 sep. 2015
Artikelnummer8
ISBN (Elektronisk)9781450342735
DOI
StatusUdgivet - 14 sep. 2015
Begivenhed27th Symposium on the Implementation and Application of Functional Programming Languages, IFL 2015 - Koblenz, Tyskland
Varighed: 14 sep. 201516 sep. 2015

Konference

Konference27th Symposium on the Implementation and Application of Functional Programming Languages, IFL 2015
LandTyskland
ByKoblenz
Periode14/09/201516/09/2015
NavnACM International Conference Proceeding Series
Vol/bind14-16-September-2015

Bibliografisk note

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

ID: 359608372