Pasar al contenido principal

Resultados relacionados

Resultados totales (Incluyendo duplicados): 3
Encontrada(s) 1 página(s)

RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

A theory of reversibility for Erlang

  • Lanese, Ivan
  • Nishida, Naoki
  • Palacios, Adrián
  • Vidal, Germán|||0000-0002-1857-6951
[EN] In a reversible language, any forward computation can be undone by a finite sequence of backward steps. Reversible computing has been studied in the context of different programming languages and formalisms, where it has been used for testing and verification, among others. In this paper, we consider a subset of Erlang, a functional and concurrent programming language based on the actor model. We present a formal semantics for reversible computation in this language and prove its main properties, including its causal consistency. We also build on top of it a rollback operator that can be used to undo the actions of a process up to a given checkpoint. (C) 2018 Elsevier Inc. All rights reserved., This work has been partially supported by MINECO/AEI/FEDER (EU) under grants TIN2013-44742-C4-1-R and TIN2016-76843-C4-1-R, by the Generalitat Valenciana under grant PROMETEO-II/2015/013 (SmartLogic), by the COST Action IC1405 on Reversible Computation-extending horizons of computing, and by JSPS KAKENHI Grant Number JP17H01722. Adrian Palacios was partially supported by the EU (FEDER) and the Spanish Ayudas para contratos predoctorales para la formacian de doctores and Ayudas a la movilidad predoctoral para la realtzacion de estancias breves en centros de I+D, MINECO (SEIDI), under FPI grants BES-2014-069749 and EEBB-I-16-11469. Ivan Lanese was partially supported by INdAM as a member of GNCS (Gruppo Nazionale per il Calcolo Scientifico). Part of this research was done while the third and fourth authors were visiting Nagoya and Bologna Universities; they gratefully acknowledge their hospitality. Finally, we thank Salvador Tamarit and the anonymous reviewers for their helpful suggestions and comments.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Reversible computation in term rewriting

  • Nishida, Naoki
  • Palacios, Adrián
  • Vidal, Germán
[EN] Essentially, in a reversible programming language, for each forward computation from state S to state S', there exists a constructive method to go backwards from state S' to state S. Besides its theoretical interest, reversible computation is a fundamental concept which is relevant in many different areas like cellular automata, bidirectional program transformation, or quantum computing, to name a few. In this work, we focus on term rewriting, a computation model that underlies most rule-based programming languages. In general, term rewriting is not reversible, even for injective functions; namely, given a rewrite step t(1) -> t(2), we do not always have a decidable method to get t(1) from t(2). Here, we introduce a conservative extension of term rewriting that becomes reversible. Furthermore, we also define two transformations, injectivization and inversion, to make a rewrite system reversible using standard term rewriting. We illustrate the usefulness of our transformations in the context of bidirectional program transformation. (C) 2017 Elsevier Inc. All rights reserved., This work has been partially supported by the EU (FEDER) and the Spanish Ministerio de Economia y Competitividad (MINECO) under grants TIN2013-44742-C4-1-R and TIN2016-76843-C4-1-R, by the Generalitat Valenciana under grant PROMETE0-II/2015/013 (SmartLogic), and by the COST Action IC1405 on Reversible Computation extending horizons of computing. Adrian Palacios was partially supported by the EU (FEDER) and the Spanish Ayudas para contratos predoctorales para la formacian de doctores and Ayudas a la movilidad predoctoral para la realizacion de estancias breves en centros de I+D, MINECO (SEIDI), under FPI grants BES-2014-069749 and EEBB-I-16-11469. Part of this research was done while the second and third authors were visiting Nagoya University; they gratefully acknowledge their hospitality.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Contribución de congreso (ConferenceOutput)

Reversible Term Rewriting

  • Nishida, Naoki
  • Palacios Corella, Adrián
  • Nishida
  • Vidal, Germán|||0000-0002-1857-6951
Essentially, in a reversible programming language, for each forward computation step from state S to state S', there exists a constructive and deterministic method to go backwards from state S' to state S. Besides its theoretical interest, reversible computation is a fundamental concept which is relevant in many different areas like cellular automata, bidirectional program transformation, or quantum computing, to name a few. In this paper, we focus on term rewriting, a computation model that underlies most rule-based programming languages. In general, term rewriting is not reversible, even for injective functions; namely, given a rewrite step t1 -> t2, we do not always have a decidable and deterministic method to get t1 from t2. Here, we introduce a conservative extension of term rewriting that becomes reversible. Furthermore, we also define a transformation to make a rewrite system reversible using standard term rewriting., This work has been partially supported by the EU (FEDER) and the Spanish Ministerio de Economía y Competitividad (MINECO) under grant TIN2013-44742-C4-1-R, by the Generalitat Valenciana under grant PROMETEO-II/2015/013 (SmartLogic) and by the COST Action IC 1405 on Reversible Computation. A. Palacios was partially supported by the the EU (FEDER) and the Spanish Ayudas para contratos predoctorales para la formación de doctores de la Sec. Estado de Investigación, Desarrollo e Innovación del MINECO under FPI grant BES-2014-069749. Part of this research was done while the second and third authors were visiting Nagoya University; they gratefully acknowledge their hospitality.