Fundamentals of reversible flowchart languages
Fundamentals of reversible flowchart languages
复制标题
DOI：
10.1016/j.tcs.2015.07.046
复制
发表时间：
2016-01-18
影响因子：
1.1
通讯作者：
Gluck, Robert
中科院分区：
文献类型：
--
作者：
Yokoyama, Tetsuo;Axelsen, Holger Bock;Gluck, Robert
本文介绍可逆流程图的基本原理。可逆流程图旨在以简单的计算模型自然地表示可逆（命令式）编程语言的结构和控制流，与传统语言的经典流程图相同。虽然可逆的流程图是表面上类似于经典的流程图，有关键的区别：原子步骤仅限于本地可逆的操作，和连接点需要一个明确的正交条件expression.Despite这些限制，我们表明，可逆的流程图是既有表现力和强大的：可逆的流程图可以模拟不可逆的适应reversibilization技术的流程图模型。因此，可逆流程图是r-Turing-complete的，这意味着它们可以精确地计算所有的内射可计算函数。此外，结构化的可逆流程图的表达非结构化的，如经典的结构化程序Theorem.We的可逆版本所示可逆流程图可以具体化与两个示例编程语言，完成语法和语义：一个低级别的非结构化语言和一个高级别的结构化语言。我们介绍具体的工具，如程序逆变器和翻译器的两种语言，它遵循的结构所建议的流程图模型。为了进一步说明本文中的不同概念和工具，我们提出了两个主要的工作例子：一个可逆的置换到代码算法归因于Dijkstra，和可逆图灵机的模拟方案。通过展示广泛的用途，我们希望所提出的可逆流程图可以作为一个跳板，在可逆计算的进一步理论研究。(C)2015爱思唯尔B. V.保留所有权利。
This paper presents the fundamentals of reversible flowcharts. Reversible flowcharts are intended to naturally represent the structure and control flow of reversible (imperative) programming languages in a simple computation model in the same way classical flowcharts do for conventional languages. Although reversible flowcharts are superficially similar to classical flowcharts, there are crucial differences: atomic steps are limited to locally invertible operations, and join points require an explicit orthogonalizing conditional expression.Despite these constraints, we show that reversible flowcharts are both expressive and robust: reversible flowcharts can simulate irreversible ones by adapting reversibilization techniques to the flowchart model. Thus, reversible flowcharts are r-Turing-complete, meaning that they can compute exactly all injective computable functions. Furthermore, structured reversible flowcharts are as expressive as unstructured ones, as shown by a reversible version of the classic Structured Program Theorem.We illustrate how reversible flowcharts can be concretized with two example programming languages, complete with syntax and semantics: a low-level unstructured language and a high-level structured language. We introduce concrete tools such as program inverters and translators for both languages, which follow the structure suggested by the flowchart model. To further illustrate the different concepts and tools brought together in this paper, we present two major worked examples: a reversible permutation-to-code algorithm attributed to Dijkstra, and a simulation scheme for reversible Turing machines. By exhibiting a wide range of uses, we hope that the proposed reversible flowcharts can serve as a springboard for further theoretical research in reversible computing. (C) 2015 Elsevier B.V. All rights reserved.