--- tags: programming languages --- # Reversible Computing Reversible computing is growing research topic in computer science. It has roots in foundational questions of physics (What is the minimal amount of heat generated by a computing device?), but more recently also attracted attention from the programming language community, for example wrt [reversible debuggers](https://www.youtube.com/watch?v=l1YJTg_A914) .... On the physical foundations: - Bennett: [Demons, Engines and the Second Law](https://ecee.colorado.edu/~ecen4555/SourceMaterial/DemonsEnginesAndSecondLaw87.pdf). 1987. On the relevance to modern hardware: - IEEE Spectrum: [The Future of Computing Depends on Making It Reversible](https://spectrum.ieee.org/computing/hardware/the-future-of-computing-depends-on-making-it-reversible). 2017. On reversing concurrent computations, with applications to debugging: - Lanese and Tiezzi: [Causal-Consistent Reversibility](http://eatcs.org/beatcs/index.php/beatcs/article/download/305/287). 2014. I have not done research on reversible computing myself, but this is paper is close to my interests and to many topics in my courses on Programming Languages and Compiler Construction: - Abramsky: [A Structural Approach to Reversible Computation](https://arxiv.org/pdf/1111.7154.pdf). 2011. ## Talks Michael Frank: [Generalized Reversible Computing and the Unconventional Computing Landscape](https://www.youtube.com/watch?v=IQZ_bQbxSXk). 2017. "The future of computing is gonna hold, forever, unless we do reversible computing." This talk goes from hardware via physics to engineering. ## Further Recommended Reading A brief overview of work on reversibility up to 2014 is in Chapter 1.2 of Gile's thesis [An investigation of some theoretical aspects of reversible computing](https://pages.cpsc.ucalgary.ca/~robin/Theses/BrettGilesPhD.pdf). ## Projects One possible project would be to look at search and sorting algorithms. [Programming Techniques for Reversible Comparison Sorts](https://www.researchgate.net/publication/300131577_Programming_Techniques_for_Reversible_Comparison_Sorts) develops "developing a family of efficient reversible comparison sorts with asymptotically optimal (minimal) garbage, while also keeping the running times of the irreversible counterparts." See also [Analyzing Trade-offs in Reversible Linear and Binary Search Algorithms](https://arxiv.org/pdf/1910.10406.pdf). ## References Landauer: [Irreversibility and Heat Generation in the Computing Process](https://www.dropbox.com/s/bwmbx9og7kg3x7z/landauer%20Irreversibility%20and%20heat%20generation%20in%20the%20computing%20process%201961.pdf?dl=0). 1961. Workshops on [Reversible Computation](https://reversible-computation-2020.github.io/). The proceedings of [RC 2020](https://link.springer.com/book/10.1007/978-3-030-47361-7) contain survey articles on various topics related to reversible computing and the results of an [EU grant](http://www.revcomp.eu/). Scanning the list of titles and speakers at [previous editions](https://reversible-computation-2021.github.io/previous/) also gives a glimpse of relevant research topics. ## Acknowledgements Thanks to Jacob Anabi, Emilio Tuosto, Irek Ulidowski for some of the references.