|
For Full-Text PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
|
A Minimalist's Reversible While Language
Robert GLÜCK Tetsuo YOKOYAMA
Publication
IEICE TRANSACTIONS on Information and Systems
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 Keyword: reversible programming language, reversible self-interpreter, while language, translation, program inversion,
Full Text: PDF(567.4KB)>>
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.
|
|
|