Working Groups

Leader

Iain PHILLIPS, UK

Co-Leader

Michael Kirkendal THOMSEN, Germany

This Working Group is concerned with foundational issues in reversible computation. A variety of models will be considered. The computational and descriptional complexity of finite-state computing models will be investigated, as well as the properties of asynchronous cellular automata and finite-state machines with storage media in the reversible setting. Understanding the role that reversibility plays in natural systems, for example in cell biology, will help in the development of realistic formal models for concurrent and distributed systems. These models will be based mainly on process calculi, but also more abstract formalisms such as reversible event structures and modal logics. A topic of prime interest is what are the most suitable behavioural semantics for reversibility. Testing semantics offers the promise of sound foundations to commercial reversible testing and debugging software tools. Process calculi will also be applied to analysing descriptions of quantum protocols that are close to the level of real program code. We aim to develop general purpose languages (both imperative and functional) as the next step over the existing prototype languages. This includes high-level abstractions such as dynamic data types, polymorphic types and higher-order functions, and libraries of reversible algorithms. We will also develop novel compiler technology for cleanly translating reversible programming languages to reversible machine code.

Read State-of-the-art Report (pdf file)
Read Report of Grant Period 2 (pdf file)
Read Report of Grant Period 3 (pdf file)
Read Report of Grant Period 4 (pdf file)

Leader

Claudio Antares MEZZINA, Italy

Co-Leader

Rudolf SCHLATTE, Norway

Ad-hoc, limited reversibility is found in existing applications and languages, implementing robustness and user-visible features. Constructs in existing systems exhibiting aspects of reversibility include transactions, checkpoints, undo mechanisms and software transactional memory. The development of reliable applications beyond the current state of the art requires a considerable engineering effort. Aspects of mainstream languages that need to be considered for industrial-scale reversibility include dynamic data structures and error handling primitives such as try-catch; modularity aspects such as classes and objects; conventional and behavioural type systems; and concurrency and distribution. Additionally, enabling exploitation of reversibility features in software development requires the development of libraries for exploiting reversibility-based patterns and tools (debuggers, event-based simulators and software versioning systems, code analysis and optimization tools), so that they can be integrated in the existing software development process. A solid theoretical underpinning for existing reversibility patterns has the potential of providing linguistic abstractions, languages and tools to systematically develop safer and more reliable applications. The vision is to integrate the above mechanisms, ensure compositionality between them, and develop a unified theory and tools for reversibility that open the way to discovering completely new applications and expressions of reversibility.

Read State-of-the-art Report (pdf file)
Read Report of Grant Period 2 (pdf file)
Read Report of Grant Period 3 (pdf file)
Read Report of Grant Period 4 (pdf file)

Leader

Robert WILLE, Austria/Germany

Co-Leader

Pawel KERNTOPF, Poland

Albeit not established yet, reversible circuits enable several promising applications and, indeed, may superior conventional devices in many domains inlcuding e.g. dedicated low power circuit design, quantum computation, design of interconnect codings, or its exploitation in conventional design tasks such as verification and test. However, all that potential has not been unleashed yet. While the physicists and electrical engineers involved in the research towards these applications have received significant achievements in the recent past, there is still work to be done before this can be used for larger computing devices. However, this must not hinder research in efficiently designing reversible devices. Not to slow down the process, approaches to design at the reversible logic level must be ready when they are. A major open research question in this area is identifying the interface between the physical circuits and the logic designs. What is a sufficient and complete model that on one hand can be used to implement circuits and on the other can serve as a target of the logic designs? That this question has not yet been satisfactory addressed, can be attributed to the distance between the respective fields. A distance we seek to reduce in this work group.

Read State-of-the-art Report
Read Report of Grant Period 2 (pdf file)
Read Report of Grant Period 3 (pdf file)
Read Report of Grant Period 4 (pdf file)

Leader

Ulrik SCHULTZ, Denmark

Co-Leader

Carla FERREIRA, Portugal

The theories, techniques and support software tools delivered by Working Groups 1 to 3 will be validated, and their suitability for practical applications will be assessed in suitable case studies. The initial selection of appropriately challenging case studies was achieved during the preparation of the Action proposal, often in consultation with industrial partners, and is documented in the Memorandum of Understanding. One of the main activities in the first year of the Action is to discuss the proposed case studies, consider further case studies suggested by newly joined industrial partners, and agree a realistic timetable. The case studies will provide feedback on the effectiveness of the reversibility-inspired theories, techniques, and solutions, and will point to new applications and research questions.

Read State-of-the-art Report (pdf file)
Read Report of Grant Period 2 (pdf file)
Read Report of Grant Period 3 (pdf file)
Read Report of Grant Period 4 (pdf file)

Reversible Computation - Extending Horizons of Computing

Links

Memorandum of Understanding
COST rules and guidelines