|
To achieve local invertibility and cleanliness, reversible languages typically incorporate several features:
* '''Reversible Updates:''' Standard assignment statements (<code>x = expression</code>) are inherently irreversible because they overwrite and erase the previous value of x. Reversible languages replace these with reversible updates, often denoted using operators like <code>+=</code>, <code>-=</code>, <code>^=</code> (bitwise XOR).<ref name="Yokoyama-71-81">{{cite conference
| last1 = Yokoyama
| first1 = Tetsuo
<!-- bibsource: dblp computer science bibliography, https://dblp.org -->
<!-- timestamp: Mon, 03 Mar 2025 21:37:52 +0100 -->
}}</ref> An important restriction is that the variable being updated (e.g., x in <code>x += e</code>) must not appear in the expression on the right-hand side (e) to ensure the operation is bijective.<ref name="Yokoyama-71-81"/> The swap operation (<code>x <=> y</code>), which exchanges the values of two variables, is another fundamental reversible update.<ref name="Choudhury">{{cite conferenceweb
| last1 = Yokoyama
| first1 = Tetsuo
| editor-last1 = Ulidowski
| editor-first1= Irek
| title = Reversible Computation and Reversible Programming Languages
| book-title = Proceedings of the Workshop on Reversible Computation, RC@ETAPS 2009, York, UK, March 22, 2009
| series = Electronic Notes in Theoretical Computer Science
| volume = 253
| issue = 6
| pages = 71–81
| publisher = Elsevier
| year = 2010
| url = https://doi.org/10.1016/j.entcs.2010.02.007
| doi = 10.1016/J.ENTCS.2010.02.007
| id = {{DBLP|journals/entcs/Yokoyama10}}
<!-- biburl: https://dblp.org/rec/journals/entcs/Yokoyama10.bib -->
<!-- bibsource: dblp computer science bibliography, https://dblp.org -->
<!-- timestamp: Mon, 03 Mar 2025 21:37:52 +0100 -->
}}</ref> The swap operation (<code>x <=> y</code>), which exchanges the values of two variables, is another fundamental reversible update.<ref name="Choudhury">{{cite web
| last1 = Choudhury
| first1 = Vikraman
<!-- timestamp: Wed, 19 Feb 2025 21:19:08 +0100 -->
| class = cs.PL
}}</ref> Similarly, loops might require entry assertions and exit tests.<ref name="Yokoyama-71-81"/> These additional predicates store the necessary information to determine the execution path uniquely during backward execution, where the roles of tests and assertions are typically swapped.<ref>{{cite conferencearXiv
| last1 = Yokoyama
| first1 = Tetsuo
| editor-last1 = Ulidowski
| editor-first1= Irek
| title = Reversible Computation and Reversible Programming Languages
| book-title = Proceedings of the Workshop on Reversible Computation, RC@ETAPS 2009, York, UK, March 22, 2009
| series = Electronic Notes in Theoretical Computer Science
| volume = 253
| issue = 6
| pages = 71–81
| publisher = Elsevier
| year = 2010
| url = https://doi.org/10.1016/j.entcs.2010.02.007
| doi = 10.1016/J.ENTCS.2010.02.007
| id = {{DBLP|journals/entcs/Yokoyama10}}
<!-- biburl: https://dblp.org/rec/journals/entcs/Yokoyama10.bib -->
<!-- bibsource: dblp computer science bibliography, https://dblp.org -->
<!-- timestamp: Mon, 03 Mar 2025 21:37:52 +0100 -->
}}</ref> These additional predicates store the necessary information to determine the execution path uniquely during backward execution, where the roles of tests and assertions are typically swapped.<ref>{{cite arXiv
| last1 = Palazzo
| first1 = Matteo
}}</ref> This explicit management of control flow information is a significant difference from conventional programming.
* '''Procedure Calls:''' Languages need mechanisms to invoke procedures both forwards and backwards. This is often achieved through paired commands like <code>call</code> (forward execution) and <code>uncall</code> or <code>rcall</code> (backward execution).<ref name="Choudhury"/>
* '''Data Structures:''' Early reversible languages often restricted data types to simple ones like integers and fixed-size arrays.<ref name="Yokoyama-71-81"/> Handling dynamic data structures like stacks requires careful semantic design to maintain reversibility, such as assuming variables are zero-cleared before being pushed onto a stack, ensuring <code>pop</code> can perfectly reverse <code>push</code>.<ref name="Choudhury"/> More recent research has explored reversible object-oriented features, including user-defined types, inheritance, and polymorphism.<ref>{{cite conference
| last1 = Yokoyama
| first1 = Tetsuo
| editor-last1 = Ulidowski
| editor-first1= Irek
| title = Reversible Computation and Reversible Programming Languages
| book-title = Proceedings of the Workshop on Reversible Computation, RC@ETAPS 2009, York, UK, March 22, 2009
| series = Electronic Notes in Theoretical Computer Science
| volume = 253
| issue = 6
| pages = 71–81
| publisher = Elsevier
| year = 2010
| url = https://doi.org/10.1016/j.entcs.2010.02.007
| doi = 10.1016/J.ENTCS.2010.02.007
| id = {{DBLP|journals/entcs/Yokoyama10}}
<!-- biburl: https://dblp.org/rec/journals/entcs/Yokoyama10.bib -->
<!-- bibsource: dblp computer science bibliography, https://dblp.org -->
<!-- timestamp: Mon, 03 Mar 2025 21:37:52 +0100 -->
}}</ref> Handling dynamic data structures like stacks requires careful semantic design to maintain reversibility, such as assuming variables are zero-cleared before being pushed onto a stack, ensuring <code>pop</code> can perfectly reverse <code>push</code>.<ref name="Choudhury"/> More recent research has explored reversible object-oriented features, including user-defined types, inheritance, and polymorphism.<ref>{{cite conference
| last1 = Haulund
| first1 = Tue
== Janus Language ==
[[Janus (time-reversible computing programming language)|Janus]] is widely recognized as the first structured, imperative programming language designed explicitly for reversible computation.<ref name="Yokoyama-71-81"/>{{cite conferenceOriginally conceived by Christopher Lutz and Howard Derby at [[Caltech]] in the 1980s,<ref name="Choudhury"/> it was later rediscovered, formalized, and extended, notably by Tetsuo Yokoyama and Robert Glück.<ref name="Choudhury"/>
| last1 = Yokoyama
| first1 = Tetsuo
| editor-last1 = Ulidowski
| editor-first1= Irek
| title = Reversible Computation and Reversible Programming Languages
| book-title = Proceedings of the Workshop on Reversible Computation, RC@ETAPS 2009, York, UK, March 22, 2009
| series = Electronic Notes in Theoretical Computer Science
| volume = 253
| issue = 6
| pages = 71–81
| publisher = Elsevier
| year = 2010
| url = https://doi.org/10.1016/j.entcs.2010.02.007
| doi = 10.1016/J.ENTCS.2010.02.007
| id = {{DBLP|journals/entcs/Yokoyama10}}
<!-- biburl: https://dblp.org/rec/journals/entcs/Yokoyama10.bib -->
<!-- bibsource: dblp computer science bibliography, https://dblp.org -->
<!-- timestamp: Mon, 03 Mar 2025 21:37:52 +0100 -->
}}</ref> Originally conceived by Christopher Lutz and Howard Derby at [[Caltech]] in the 1980s,<ref name="Choudhury"/> it was later rediscovered, formalized, and extended, notably by Tetsuo Yokoyama and Robert Glück.<ref name="Choudhury"/>
===Design philosophy===
===Syntax and semantics===
* ''Program Structure:'' A Janus program consists of global variable declarations followed by procedure declarations. The execution starts at a procedure named <code>main</code>, or the last procedure defined if <code>main</code> is absent.
* ''Data Types:'' Janus primarily uses 32-bit integers (interpreters may differ on signed vs. unsigned) and one-dimensional integer arrays of fixed size.<ref name="Yokoyama-71-81"/>{{cite conferenceSome versions include stacks.<ref name="Yokoyama-71-81"/> All variables and array elements are initialized to zero.<ref name="Yokoyama-71-81"/>
| last1 = Yokoyama
| first1 = Tetsuo
| editor-last1 = Ulidowski
| editor-first1= Irek
| title = Reversible Computation and Reversible Programming Languages
| book-title = Proceedings of the Workshop on Reversible Computation, RC@ETAPS 2009, York, UK, March 22, 2009
| series = Electronic Notes in Theoretical Computer Science
| volume = 253
| issue = 6
| pages = 71–81
| publisher = Elsevier
| year = 2010
| url = https://doi.org/10.1016/j.entcs.2010.02.007
| doi = 10.1016/J.ENTCS.2010.02.007
| id = {{DBLP|journals/entcs/Yokoyama10}}
<!-- biburl: https://dblp.org/rec/journals/entcs/Yokoyama10.bib -->
<!-- bibsource: dblp computer science bibliography, https://dblp.org -->
<!-- timestamp: Mon, 03 Mar 2025 21:37:52 +0100 -->
}}</ref> Some versions include stacks.<ref>{{cite conference
| last1 = Yokoyama
| first1 = Tetsuo
| editor-last1 = Ulidowski
| editor-first1= Irek
| title = Reversible Computation and Reversible Programming Languages
| book-title = Proceedings of the Workshop on Reversible Computation, RC@ETAPS 2009, York, UK, March 22, 2009
| series = Electronic Notes in Theoretical Computer Science
| volume = 253
| issue = 6
| pages = 71–81
| publisher = Elsevier
| year = 2010
| url = https://doi.org/10.1016/j.entcs.2010.02.007
| doi = 10.1016/J.ENTCS.2010.02.007
| id = {{DBLP|journals/entcs/Yokoyama10}}
<!-- biburl: https://dblp.org/rec/journals/entcs/Yokoyama10.bib -->
<!-- bibsource: dblp computer science bibliography, https://dblp.org -->
<!-- timestamp: Mon, 03 Mar 2025 21:37:52 +0100 -->
}}</ref> All variables and array elements are initialized to zero.<ref>{{cite conference
| last1 = Yokoyama
| first1 = Tetsuo
| editor-last1 = Ulidowski
| editor-first1= Irek
| title = Reversible Computation and Reversible Programming Languages
| book-title = Proceedings of the Workshop on Reversible Computation, RC@ETAPS 2009, York, UK, March 22, 2009
| series = Electronic Notes in Theoretical Computer Science
| volume = 253
| issue = 6
| pages = 71–81
| publisher = Elsevier
| year = 2010
| url = https://doi.org/10.1016/j.entcs.2010.02.007
| doi = 10.1016/J.ENTCS.2010.02.007
| id = {{DBLP|journals/entcs/Yokoyama10}}
<!-- biburl: https://dblp.org/rec/journals/entcs/Yokoyama10.bib -->
<!-- bibsource: dblp computer science bibliography, https://dblp.org -->
<!-- timestamp: Mon, 03 Mar 2025 21:37:52 +0100 -->
}}</ref>
* ''Statements:''
** '''Assignment:''' Reversible updates <code>x op= e</code> or <code>x[e] op= e</code>, where <code>op</code> is <code>+</code>, <code>-</code>, or <code>^</code> (bitwise XOR). The variable <code>x</code> must not appear in the expression <code>e</code>.<ref>{{cite conferencename="Yokoyama-71-81"/>
| last1 = Yokoyama
| first1 = Tetsuo
| editor-last1 = Ulidowski
| editor-first1= Irek
| title = Reversible Computation and Reversible Programming Languages
| book-title = Proceedings of the Workshop on Reversible Computation, RC@ETAPS 2009, York, UK, March 22, 2009
| series = Electronic Notes in Theoretical Computer Science
| volume = 253
| issue = 6
| pages = 71–81
| publisher = Elsevier
| year = 2010
| url = https://doi.org/10.1016/j.entcs.2010.02.007
| doi = 10.1016/J.ENTCS.2010.02.007
| id = {{DBLP|journals/entcs/Yokoyama10}}
<!-- biburl: https://dblp.org/rec/journals/entcs/Yokoyama10.bib -->
<!-- bibsource: dblp computer science bibliography, https://dblp.org -->
<!-- timestamp: Mon, 03 Mar 2025 21:37:52 +0100 -->
}}</ref>
** '''Swap:''' <code>x <=> y</code> exchanges the values of <code>x</code> and <code>y</code>.
** '''Conditional:''' <code>if e1 then s1 else s2 fi e2</code>. The expression <code>e1</code> is the test evaluated upon forward entry. The expression <code>e2</code> is an assertion evaluated upon forward exit; it must be true if <code>s1</code> was executed and false if <code>s2</code> was executed. For backward execution (e.g., via <code>uncall</code>), <code>e2</code> acts as the test to determine which inverse branch (s1<sup>−1</sup> or s2<sup>−1</sup>) to take, and <code>e1</code> becomes the assertion checked upon exiting backward.<ref>{{cite arXiv
| class = cs.PL
}}</ref>
** '''Loop:''' <code>from e1 do s1 loop s2 until e2</code>. Upon forward entry, assertion <code>e1</code> must be true. <code>s1</code> is executed. Then, test <code>e2</code> is evaluated. If true, the loop terminates. If false, <code>s2</code> is executed, after which assertion <code>e1</code> must now be false for the loop to continue back to <code>s1</code>. In reverse, <code>e2</code> is the entry assertion, s2<sup>−1</sup> is executed, <code>e1</code> is the test (loop continues if false, terminates if true), and s1<sup>−1</sup> is executed if the loop continues.<ref>{{cite conferencename="Yokoyama-71-81"/>
** '''Stack Operations:''' <code>push(x, stack)</code> and <code>pop(x, stack)</code>. Reversibility often relies on assumptions about the state of <code>x</code> (e.g., <code>x</code> must be 0 before <code>push</code> so <code>pop</code> can restore it).<ref name="Yokoyama-71-81"/>** '''Local Variables:''' <code>local t x = e in s delocal t x = e</code> This block introduces a local variable <code>x</code>, initializes it reversibly using <code>e</code>, executes <code>s</code>, and then uncomputes <code>x</code> back to its initial state (usually 0) using the inverse of <code>e</code> upon exit.<ref name="Yokoyama-71-81"/>
| last1 = Yokoyama
| first1 = Tetsuo
| editor-last1 = Ulidowski
| editor-first1= Irek
| title = Reversible Computation and Reversible Programming Languages
| book-title = Proceedings of the Workshop on Reversible Computation, RC@ETAPS 2009, York, UK, March 22, 2009
| series = Electronic Notes in Theoretical Computer Science
| volume = 253
| issue = 6
| pages = 71–81
| publisher = Elsevier
| year = 2010
| url = https://doi.org/10.1016/j.entcs.2010.02.007
| doi = 10.1016/J.ENTCS.2010.02.007
| id = {{DBLP|journals/entcs/Yokoyama10}}
<!-- biburl: https://dblp.org/rec/journals/entcs/Yokoyama10.bib -->
<!-- bibsource: dblp computer science bibliography, https://dblp.org -->
<!-- timestamp: Mon, 03 Mar 2025 21:37:52 +0100 -->
}}</ref>
** '''Stack Operations:''' <code>push(x, stack)</code> and <code>pop(x, stack)</code>. Reversibility often relies on assumptions about the state of <code>x</code> (e.g., <code>x</code> must be 0 before <code>push</code> so <code>pop</code> can restore it).<ref>{{cite conference
| last1 = Yokoyama
| first1 = Tetsuo
| editor-last1 = Ulidowski
| editor-first1= Irek
| title = Reversible Computation and Reversible Programming Languages
| book-title = Proceedings of the Workshop on Reversible Computation, RC@ETAPS 2009, York, UK, March 22, 2009
| series = Electronic Notes in Theoretical Computer Science
| volume = 253
| issue = 6
| pages = 71–81
| publisher = Elsevier
| year = 2010
| url = https://doi.org/10.1016/j.entcs.2010.02.007
| doi = 10.1016/J.ENTCS.2010.02.007
| id = {{DBLP|journals/entcs/Yokoyama10}}
<!-- biburl: https://dblp.org/rec/journals/entcs/Yokoyama10.bib -->
<!-- bibsource: dblp computer science bibliography, https://dblp.org -->
<!-- timestamp: Mon, 03 Mar 2025 21:37:52 +0100 -->
}}</ref>
** '''Local Variables:''' <code>local t x = e in s delocal t x = e</code> This block introduces a local variable <code>x</code>, initializes it reversibly using <code>e</code>, executes <code>s</code>, and then uncomputes <code>x</code> back to its initial state (usually 0) using the inverse of <code>e</code> upon exit.<ref>{{cite conference
| last1 = Yokoyama
| first1 = Tetsuo
| editor-last1 = Ulidowski
| editor-first1= Irek
| title = Reversible Computation and Reversible Programming Languages
| book-title = Proceedings of the Workshop on Reversible Computation, RC@ETAPS 2009, York, UK, March 22, 2009
| series = Electronic Notes in Theoretical Computer Science
| volume = 253
| issue = 6
| pages = 71–81
| publisher = Elsevier
| year = 2010
| url = https://doi.org/10.1016/j.entcs.2010.02.007
| doi = 10.1016/J.ENTCS.2010.02.007
| id = {{DBLP|journals/entcs/Yokoyama10}}
<!-- biburl: https://dblp.org/rec/journals/entcs/Yokoyama10.bib -->
<!-- bibsource: dblp computer science bibliography, https://dblp.org -->
<!-- timestamp: Mon, 03 Mar 2025 21:37:52 +0100 -->
}}</ref>
** '''Procedure Call:''' <code>call id</code> executes procedure <code>id</code> forwards; <code>uncall id</code> executes procedure <code>id</code> backwards.<ref name="Choudhury"/> Procedures operate via side effects on the global store.
** '''Skip:''' <code>skip</code> does nothing and is its own inverse.
===Implementations and code examples===
Several online interpreters for Janus exist.<ref>{{cite web |url=https://topps.diku.dk/pirc/?id=janus |title=Janus: a reversible imperative programming language |website=University of Copenhagen (DIKU) |access-date=April 9, 2025}}</ref> Janus has been used to implement various algorithms reversibly, including computing Fibonacci pairs,<ref name="Yokoyama-71-81"/> simulating RTMs,<ref name="Yokoyama-71-81"/> Fast Fourier Transform (FFT)<ref>{{cite web |url=https://cra.org/ccc/wp-content/uploads/sites/2/2020/11/Jayson-Lynch_ReversibleAlgorithmsTalk.pdf |title=Reversible Algorithms |website=Computing Research Association |access-date=April 9, 2025}}</ref>, graph algorithms <ref>{{cite web |url=https://cra.org/ccc/wp-content/uploads/sites/2/2020/11/Jayson-Lynch_ReversibleAlgorithmsTalk.pdf |title=Reversible Algorithms |website=Computing Research Association |access-date=April 9, 2025}}</ref>, and simulating the Schrödinger wave equation.<ref>{{cite conference
| last1 = Yokoyama
| first1 = Tetsuo
| editor-last1 = Ulidowski
| editor-first1= Irek
| title = Reversible Computation and Reversible Programming Languages
| book-title = Proceedings of the Workshop on Reversible Computation, RC@ETAPS 2009, York, UK, March 22, 2009
| series = Electronic Notes in Theoretical Computer Science
| volume = 253
| issue = 6
| pages = 71–81
| publisher = Elsevier
| year = 2010
| url = https://doi.org/10.1016/j.entcs.2010.02.007
| doi = 10.1016/J.ENTCS.2010.02.007
| id = {{DBLP|journals/entcs/Yokoyama10}}
<!-- biburl: https://dblp.org/rec/journals/entcs/Yokoyama10.bib -->
<!-- bibsource: dblp computer science bibliography, https://dblp.org -->
<!-- timestamp: Mon, 03 Mar 2025 21:37:52 +0100 -->
}}</ref>, simulating RTMs<ref>{{cite conference
| last1 = Yokoyama
| first1 = Tetsuo
| editor-last1 = Ulidowski
| editor-first1= Irek
| title = Reversible Computation and Reversible Programming Languages
| book-title = Proceedings of the Workshop on Reversible Computation, RC@ETAPS 2009, York, UK, March 22, 2009
| series = Electronic Notes in Theoretical Computer Science
| volume = 253
| issue = 6
| pages = 71–81
| publisher = Elsevier
| year = 2010
| url = https://doi.org/10.1016/j.entcs.2010.02.007
| doi = 10.1016/J.ENTCS.2010.02.007
| id = {{DBLP|journals/entcs/Yokoyama10}}
<!-- biburl: https://dblp.org/rec/journals/entcs/Yokoyama10.bib -->
<!-- bibsource: dblp computer science bibliography, https://dblp.org -->
<!-- timestamp: Mon, 03 Mar 2025 21:37:52 +0100 -->
}}</ref>, Fast Fourier Transform (FFT)<ref>{{cite web |url=https://cra.org/ccc/wp-content/uploads/sites/2/2020/11/Jayson-Lynch_ReversibleAlgorithmsTalk.pdf |title=Reversible Algorithms |website=Computing Research Association |access-date=April 9, 2025}}</ref>, graph algorithms <ref>{{cite web |url=https://cra.org/ccc/wp-content/uploads/sites/2/2020/11/Jayson-Lynch_ReversibleAlgorithmsTalk.pdf |title=Reversible Algorithms |website=Computing Research Association |access-date=April 9, 2025}}</ref>, and simulating the Schrödinger wave equation.<ref>{{cite conference
| last1 = Yokoyama
| first1 = Tetsuo
{| class="wikitable"
|+ Comparison of Reversible Programming Languages<ref name="Yokoyama-71-81"/><ref name="Choudhury"/><ref>{{cite conferencearXiv
| last1 = Yokoyama
| first1 = Tetsuo
| editor-last1 = Ulidowski
| editor-first1= Irek
| title = Reversible Computation and Reversible Programming Languages
| book-title = Proceedings of the Workshop on Reversible Computation, RC@ETAPS 2009, York, UK, March 22, 2009
| series = Electronic Notes in Theoretical Computer Science
| volume = 253
| issue = 6
| pages = 71–81
| publisher = Elsevier
| year = 2010
| url = https://doi.org/10.1016/j.entcs.2010.02.007
| doi = 10.1016/J.ENTCS.2010.02.007
| id = {{DBLP|journals/entcs/Yokoyama10}}
<!-- biburl: https://dblp.org/rec/journals/entcs/Yokoyama10.bib -->
<!-- bibsource: dblp computer science bibliography, https://dblp.org -->
<!-- timestamp: Mon, 03 Mar 2025 21:37:52 +0100 -->
}}</ref><ref name="Choudhury"/><ref>{{cite arXiv
| last1 = Haulund
| first1 = Tue
| 