A linear-time self-interpreter of a reversible imperative language

Robert Glück; Tetsuo Yokoyama

doi:10.11309/jssst.33.3_108

A linear-time self-interpreter of a reversible imperative language

Robert Glück, Tetsuo Yokoyama

Datalogisk Institut

14 Citationer (Scopus)

Abstract

A linear-time reversible self-interpreter in an r-Turing complete reversible imperative language is presented. The proposed imperative language has reversible structured control flow operators and symbolic tree-structured data (S-expressions). The latter data structures are dynamically allocated and enable reversible simulation of programs of arbitrary size and space consumption. As self-interpreters are used to show a number of fundamental properties in classic computability and complexity theory, the present study of an efficient reversible self-interpreter is intended as a basis for future work on reversible computability and complexity theory as well as programming language theory for reversible computing. Although the proposed reversible interpreter consumes superlinear space, the restriction of the number of variables in the source language leads to linear-time reversible simulation.

Originalsprog	Engelsk
Tidsskrift	Computer Software
Vol/bind	33
Udgave nummer	3
Sider (fra-til)	108-128
Antal sider	21
ISSN	0289-6540
DOI	https://doi.org/10.11309/jssst.33.3_108
Status	Udgivet - 2016

Adgang til dokumentet

10.11309/jssst.33.3_108

Citationsformater

@article{805691b5449a4a529007ecf59880765c,

title = "A linear-time self-interpreter of a reversible imperative language",

abstract = "A linear-time reversible self-interpreter in an r-Turing complete reversible imperative language is presented. The proposed imperative language has reversible structured control flow operators and symbolic tree-structured data (S-expressions). The latter data structures are dynamically allocated and enable reversible simulation of programs of arbitrary size and space consumption. As self-interpreters are used to show a number of fundamental properties in classic computability and complexity theory, the present study of an efficient reversible self-interpreter is intended as a basis for future work on reversible computability and complexity theory as well as programming language theory for reversible computing. Although the proposed reversible interpreter consumes superlinear space, the restriction of the number of variables in the source language leads to linear-time reversible simulation.",

author = "Robert Gl{\"u}ck and Tetsuo Yokoyama",

year = "2016",

doi = "10.11309/jssst.33.3_108",

language = "English",

volume = "33",

pages = "108--128",

journal = "Computer Software",

issn = "0289-6540",

publisher = "Japan Society for Software Science and Technology",

number = "3",

}

TY - JOUR

T1 - A linear-time self-interpreter of a reversible imperative language

AU - Glück, Robert

AU - Yokoyama, Tetsuo

PY - 2016

Y1 - 2016

N2 - A linear-time reversible self-interpreter in an r-Turing complete reversible imperative language is presented. The proposed imperative language has reversible structured control flow operators and symbolic tree-structured data (S-expressions). The latter data structures are dynamically allocated and enable reversible simulation of programs of arbitrary size and space consumption. As self-interpreters are used to show a number of fundamental properties in classic computability and complexity theory, the present study of an efficient reversible self-interpreter is intended as a basis for future work on reversible computability and complexity theory as well as programming language theory for reversible computing. Although the proposed reversible interpreter consumes superlinear space, the restriction of the number of variables in the source language leads to linear-time reversible simulation.

AB - A linear-time reversible self-interpreter in an r-Turing complete reversible imperative language is presented. The proposed imperative language has reversible structured control flow operators and symbolic tree-structured data (S-expressions). The latter data structures are dynamically allocated and enable reversible simulation of programs of arbitrary size and space consumption. As self-interpreters are used to show a number of fundamental properties in classic computability and complexity theory, the present study of an efficient reversible self-interpreter is intended as a basis for future work on reversible computability and complexity theory as well as programming language theory for reversible computing. Although the proposed reversible interpreter consumes superlinear space, the restriction of the number of variables in the source language leads to linear-time reversible simulation.

U2 - 10.11309/jssst.33.3_108

DO - 10.11309/jssst.33.3_108

M3 - Journal article

SN - 0289-6540

VL - 33

SP - 108

EP - 128

JO - Computer Software

JF - Computer Software

IS - 3

ER -

A linear-time self-interpreter of a reversible imperative language

Abstract

Adgang til dokumentet

Fingeraftryk

Citationsformater