A Minimalist's Reversible While Language

Robert GLÜCK; Tetsuo YOKOYAMA

doi:10.1587/transinf.2016EDP7274

A Minimalist's Reversible While Language

Robert GLÜCK, Tetsuo YOKOYAMA

Full Text Views

0

Cite this

Summary :

The paper presents a small reversible language R-CORE, a structured imperative programming language with symbolic tree-structured data (S-expressions). The language is reduced to the core of a reversible language, with a single command for reversibly updating the store, a single reversible control-flow operator, a limited number of variables, and data with a single atom and a single constructor. Despite its extreme simplicity, the language is reversibly universal, which means that it is as powerful as any reversible language can be, while it is linear-time self-interpretable, and it allows reversible programming with dynamic data structures. The four-line program inverter for R-CORE is among the shortest existing program inverters, which demonstrates the conciseness of the language. The translator to R-CORE, which is used to show the formal properties of the language, is clean and modular, and it may serve as a model for related reversible translation problems. The goal is to provide a language that is sufficiently concise for theoretical investigations. Owing to its simplicity, the language may also be used for educational purposes.

Publication: IEICE TRANSACTIONS on Information Vol.E100-D No.5 pp.1026-1034

Publication Date: 2017/05/01

Publicized: 2017/02/06

Online ISSN: 1745-1361

DOI: 10.1587/transinf.2016EDP7274

Type of Manuscript: PAPER

Category: Software System

Authors

Robert GLÜCK
University of Copenhagen
Tetsuo YOKOYAMA
Nanzan University

Keyword

reversible programming language, reversible self-interpreter, while language, translation, program inversion

Cite this

Copy

Robert GLÜCK, Tetsuo YOKOYAMA, "A Minimalist's Reversible While Language" in IEICE TRANSACTIONS on Information, vol. E100-D, no. 5, pp. 1026-1034, May 2017, doi: 10.1587/transinf.2016EDP7274.
Abstract: The paper presents a small reversible language R-CORE, a structured imperative programming language with symbolic tree-structured data (S-expressions). The language is reduced to the core of a reversible language, with a single command for reversibly updating the store, a single reversible control-flow operator, a limited number of variables, and data with a single atom and a single constructor. Despite its extreme simplicity, the language is reversibly universal, which means that it is as powerful as any reversible language can be, while it is linear-time self-interpretable, and it allows reversible programming with dynamic data structures. The four-line program inverter for R-CORE is among the shortest existing program inverters, which demonstrates the conciseness of the language. The translator to R-CORE, which is used to show the formal properties of the language, is clean and modular, and it may serve as a model for related reversible translation problems. The goal is to provide a language that is sufficiently concise for theoretical investigations. Owing to its simplicity, the language may also be used for educational purposes.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2016EDP7274/_p

Copy

@ARTICLE{e100-d_5_1026,
author={Robert GLÜCK, Tetsuo YOKOYAMA, },
journal={IEICE TRANSACTIONS on Information},
title={A Minimalist's Reversible While Language},
year={2017},
volume={E100-D},
number={5},
pages={1026-1034},
abstract={The paper presents a small reversible language R-CORE, a structured imperative programming language with symbolic tree-structured data (S-expressions). The language is reduced to the core of a reversible language, with a single command for reversibly updating the store, a single reversible control-flow operator, a limited number of variables, and data with a single atom and a single constructor. Despite its extreme simplicity, the language is reversibly universal, which means that it is as powerful as any reversible language can be, while it is linear-time self-interpretable, and it allows reversible programming with dynamic data structures. The four-line program inverter for R-CORE is among the shortest existing program inverters, which demonstrates the conciseness of the language. The translator to R-CORE, which is used to show the formal properties of the language, is clean and modular, and it may serve as a model for related reversible translation problems. The goal is to provide a language that is sufficiently concise for theoretical investigations. Owing to its simplicity, the language may also be used for educational purposes.},
keywords={},
doi={10.1587/transinf.2016EDP7274},
ISSN={1745-1361},
month={May},}

Copy

TY - JOUR
TI - A Minimalist's Reversible While Language
T2 - IEICE TRANSACTIONS on Information
SP - 1026
EP - 1034
AU - Robert GLÜCK
AU - Tetsuo YOKOYAMA
PY - 2017
DO - 10.1587/transinf.2016EDP7274
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E100-D
IS - 5
JA - IEICE TRANSACTIONS on Information
Y1 - May 2017
AB - The paper presents a small reversible language R-CORE, a structured imperative programming language with symbolic tree-structured data (S-expressions). The language is reduced to the core of a reversible language, with a single command for reversibly updating the store, a single reversible control-flow operator, a limited number of variables, and data with a single atom and a single constructor. Despite its extreme simplicity, the language is reversibly universal, which means that it is as powerful as any reversible language can be, while it is linear-time self-interpretable, and it allows reversible programming with dynamic data structures. The four-line program inverter for R-CORE is among the shortest existing program inverters, which demonstrates the conciseness of the language. The translator to R-CORE, which is used to show the formal properties of the language, is clean and modular, and it may serve as a model for related reversible translation problems. The goal is to provide a language that is sufficiently concise for theoretical investigations. Owing to its simplicity, the language may also be used for educational purposes.
ER -