|
<!-- 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
| class = cs.PL
}}</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>{{cite webname="Choudhury"/>
| last1 = Choudhury
| first1 = Vikraman
| title = Reversible Programming Languages
| date = April 2018
| url=https://vikraman.org/files/reversible-languages.pdf
<!-- If it were accessible online, you'd add: |url=... |access-date=... -->
<!-- If it were for a specific institution, you could add: |institution=... -->
}}</ref>
* '''Data Structures:''' Early reversible languages often restricted data types to simple ones like integers and fixed-size arrays.<ref>{{cite conference
| last1 = Yokoyama
<!-- 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 webconference
| last1 = Choudhury
| first1 = Vikraman
| title = Reversible Programming Languages
| date = April 2018
| url=https://vikraman.org/files/reversible-languages.pdf
<!-- If it were accessible online, you'd add: |url=... |access-date=... -->
<!-- If it were for a specific institution, you could add: |institution=... -->
}}</ref> More recent research has explored reversible object-oriented features, including user-defined types, inheritance, and polymorphism.<ref>{{cite conference
| last1 = Haulund
| first1 = Tue
<!-- timestamp: Tue, 22 Oct 2019 15:21:14 +0200 -->
}}</ref>
* '''Computational Power:''' A common benchmark for the power of a reversible language is [[Turing completeness|r-Turing completeness]], which means the language can simulate any Reversible Turing Machine cleanly (without garbage accumulation).<ref>{{cite webname="Choudhury"/>
| last1 = Choudhury
| first1 = Vikraman
| title = Reversible Programming Languages
| date = April 2018
| url=https://vikraman.org/files/reversible-languages.pdf
<!-- If it were accessible online, you'd add: |url=... |access-date=... -->
<!-- If it were for a specific institution, you could add: |institution=... -->
}}</ref>
== Janus Language ==
<!-- 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"/>{{cite webit was later rediscovered, formalized, and extended, notably by Tetsuo Yokoyama and Robert Glück.<ref name="Choudhury"/>
| last1 = Choudhury
| first1 = Vikraman
| title = Reversible Programming Languages
| date = April 2018
| url=https://vikraman.org/files/reversible-languages.pdf
<!-- If it were accessible online, you'd add: |url=... |access-date=... -->
<!-- If it were for a specific institution, you could add: |institution=... -->
}}</ref>, it was later rediscovered, formalized, and extended, notably by Tetsuo Yokoyama and Robert Glück.<ref>{{cite web
| last1 = Choudhury
| first1 = Vikraman
| title = Reversible Programming Languages
| date = April 2018
| url=https://vikraman.org/files/reversible-languages.pdf
<!-- If it were accessible online, you'd add: |url=... |access-date=... -->
<!-- If it were for a specific institution, you could add: |institution=... -->
}}</ref>
===Design philosophy===
Janus embodies the principle of local invertibility. It operates on a global store of variables (no heap allocation or local procedure scope in early versions) and ensures that every statement has a unique inverse.<ref>{{cite webname="Choudhury"/>
| last1 = Choudhury
| first1 = Vikraman
| title = Reversible Programming Languages
| date = April 2018
| url=https://vikraman.org/files/reversible-languages.pdf
<!-- If it were accessible online, you'd add: |url=... |access-date=... -->
<!-- If it were for a specific institution, you could add: |institution=... -->
}}</ref>
===Syntax and semantics===
<!-- 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"/>{{cite webProcedures operate via side effects on the global store.
| last1 = Choudhury
| first1 = Vikraman
| title = Reversible Programming Languages
| date = April 2018
| url=https://vikraman.org/files/reversible-languages.pdf
<!-- If it were accessible online, you'd add: |url=... |access-date=... -->
<!-- If it were for a specific institution, you could add: |institution=... -->
}}</ref> Procedures operate via side effects on the global store.
** '''Skip:''' <code>skip</code> does nothing and is its own inverse.<ref>{{cite web |url=https://en.wikipedia.org/wiki/Janus_(time-reversible_computing_programming_language) |title=Janus (time-reversible computing programming language) |website=Wikipedia |access-date=April 9, 2025}}</ref>
** '''Sequence:''' <code>s1; s2</code>. The inverse is <code>s2<sup>−1</sup>; s1<sup>−1</sup></code>.<ref>{{cite web |url=https://en.wikipedia.org/wiki/Janus_(time-reversible_computing_programming_language) |title=Janus (time-reversible computing programming language) |website=Wikipedia |access-date=April 9, 2025}}</ref>
== R Language (MIT) ==
The R language (distinct from the [[R (programming language)|statistical language R]]) was developed by Michael P. Frank at [[MIT]] in the late 1990s as part of the Reversible Computing project.<ref name="Choudhury"/>{{cite webIt is an imperative, compiled language featuring an S-expression (Lisp-like) syntax.<ref name="Choudhury"/> A key aspect of R's design was its close integration with hardware development; it was designed to target the Pendulum reversible instruction set architecture (PISA), developed concurrently at MIT for an adiabatic CMOS processor.<ref name="Choudhury"/>
| last1 = Choudhury
| first1 = Vikraman
| title = Reversible Programming Languages
| date = April 2018
| url=https://vikraman.org/files/reversible-languages.pdf
<!-- If it were accessible online, you'd add: |url=... |access-date=... -->
<!-- If it were for a specific institution, you could add: |institution=... -->
}}</ref> It is an imperative, compiled language featuring an S-expression (Lisp-like) syntax.<ref>{{cite web
| last1 = Choudhury
| first1 = Vikraman
| title = Reversible Programming Languages
| date = April 2018
| url=https://vikraman.org/files/reversible-languages.pdf
<!-- If it were accessible online, you'd add: |url=... |access-date=... -->
<!-- If it were for a specific institution, you could add: |institution=... -->
}}</ref> A key aspect of R's design was its close integration with hardware development; it was designed to target the Pendulum reversible instruction set architecture (PISA), developed concurrently at MIT for an adiabatic CMOS processor.<ref>{{cite web
| last1 = Choudhury
| first1 = Vikraman
| title = Reversible Programming Languages
| date = April 2018
| url=https://vikraman.org/files/reversible-languages.pdf
<!-- If it were accessible online, you'd add: |url=... |access-date=... -->
<!-- If it were for a specific institution, you could add: |institution=... -->
}}</ref>
===Syntax and semantics===
* ''Program Structure:'' Programs are defined using <code>(defmain ...)</code> for the main routine and <code>(defsub ...)</code> for subroutines. Global variables and arrays are declared with <code>(defword ...)</code> and <code>(defarray ...)</code>.<ref>{{cite webname="Choudhury"/>
* ''Data Types:'' R primarily supports integers and integer arrays.<ref name="Choudhury"/>
| last1 = Choudhury
| first1 = Vikraman
| title = Reversible Programming Languages
| date = April 2018
| url=https://vikraman.org/files/reversible-languages.pdf
<!-- If it were accessible online, you'd add: |url=... |access-date=... -->
<!-- If it were for a specific institution, you could add: |institution=... -->
}}</ref>
* ''Data Types:'' R primarily supports integers and integer arrays.<ref>{{cite web
| last1 = Choudhury
| first1 = Vikraman
| title = Reversible Programming Languages
| date = April 2018
| url=https://vikraman.org/files/reversible-languages.pdf
<!-- If it were accessible online, you'd add: |url=... |access-date=... -->
<!-- If it were for a specific institution, you could add: |institution=... -->
}}</ref>
* ''Statements:''
** '''Assignment/Update:''' Includes increment (<code>loc ++</code>), negation (<code>- loc</code>), swap (<code>loc <-> loc</code>), and reversible updates (<code>loc op= e</code>) using operators like <code>+=</code>, <code>-=</code>, <code>^=</code>, and specialized comparison-updates (<code><=<</code>, <code>>=></code>).<ref name="Choudhury"/>{{cite webSimilar restrictions to Janus apply regarding variable dependencies.
** '''Conditional:''' <code>(if e then s*)</code>. To ensure reversibility, the language requires that the value of the conditional expression <code>e</code> must be the same before and after the execution of the <code>then</code> block (<code>s*</code>).<ref name="Choudhury"/> This acts as an implicit invariant assertion, similar in function to Janus's explicit exit assertion.
| last1 = Choudhury
** '''Loop:''' <code>(for name = e_start to e_end s*)</code>. Reversibility requires that the loop iteration variable (<code>name</code>) must have the same value before entering and after exiting the loop.<ref name="Choudhury"/>
| first1 = Vikraman
** '''Local Binding:''' <code>(let ((name <- e)) s*)</code>. Introduces a local variable <code>name</code> initialized with <code>e</code>. Reversibility is ensured by requiring the variable to be returned to a known state (e.g., zero-cleared) before the scope is exited, analogous to Janus's <code>local/delocal</code>.<ref name="Choudhury"/>
| title = Reversible Programming Languages
** '''Procedure Call:''' Explicit forward <code>(call subname e*)</code> and reverse <code>(rcall subname e*)</code> calls are provided.<ref name="Choudhury"/>
| date = April 2018
** '''Output:''' <code>(printword e)</code> and <code>(println)</code> are included for output.<ref name="Choudhury"/> These are inherently irreversible operations.
| url=https://vikraman.org/files/reversible-languages.pdf
<!-- If it were accessible online, you'd add: |url=... |access-date=... -->
<!-- If it were for a specific institution, you could add: |institution=... -->
}}</ref> Similar restrictions to Janus apply regarding variable dependencies.
** '''Conditional:''' <code>(if e then s*)</code>. To ensure reversibility, the language requires that the value of the conditional expression <code>e</code> must be the same before and after the execution of the <code>then</code> block (<code>s*</code>).<ref>{{cite web
| last1 = Choudhury
| first1 = Vikraman
| title = Reversible Programming Languages
| date = April 2018
| url=https://vikraman.org/files/reversible-languages.pdf
<!-- If it were accessible online, you'd add: |url=... |access-date=... -->
<!-- If it were for a specific institution, you could add: |institution=... -->
}}</ref> This acts as an implicit invariant assertion, similar in function to Janus's explicit exit assertion.
** '''Loop:''' <code>(for name = e_start to e_end s*)</code>. Reversibility requires that the loop iteration variable (<code>name</code>) must have the same value before entering and after exiting the loop.<ref>{{cite web
| last1 = Choudhury
| first1 = Vikraman
| title = Reversible Programming Languages
| date = April 2018
| url=https://vikraman.org/files/reversible-languages.pdf
<!-- If it were accessible online, you'd add: |url=... |access-date=... -->
<!-- If it were for a specific institution, you could add: |institution=... -->
}}</ref>
** '''Local Binding:''' <code>(let ((name <- e)) s*)</code>. Introduces a local variable <code>name</code> initialized with <code>e</code>. Reversibility is ensured by requiring the variable to be returned to a known state (e.g., zero-cleared) before the scope is exited, analogous to Janus's <code>local/delocal</code>.<ref>{{cite web
| last1 = Choudhury
| first1 = Vikraman
| title = Reversible Programming Languages
| date = April 2018
| url=https://vikraman.org/files/reversible-languages.pdf
<!-- If it were accessible online, you'd add: |url=... |access-date=... -->
<!-- If it were for a specific institution, you could add: |institution=... -->
}}</ref>
** '''Procedure Call:''' Explicit forward <code>(call subname e*)</code> and reverse <code>(rcall subname e*)</code> calls are provided.<ref>{{cite web
| last1 = Choudhury
| first1 = Vikraman
| title = Reversible Programming Languages
| date = April 2018
| url=https://vikraman.org/files/reversible-languages.pdf
<!-- If it were accessible online, you'd add: |url=... |access-date=... -->
<!-- If it were for a specific institution, you could add: |institution=... -->
}}</ref>
** '''Output:''' <code>(printword e)</code> and <code>(println)</code> are included for output.<ref>{{cite web
| last1 = Choudhury
| first1 = Vikraman
| title = Reversible Programming Languages
| date = April 2018
| url=https://vikraman.org/files/reversible-languages.pdf
<!-- If it were accessible online, you'd add: |url=... |access-date=... -->
<!-- If it were for a specific institution, you could add: |institution=... -->
}}</ref> These are inherently irreversible operations.
===Pendulum/PISA target architecture===
}}</ref>
* ''PISA Features:'' The instruction set includes several features tailored for reversibility:
** A Direction Bit (DIR) register tracks forward/backward execution mode.<ref>{{cite webname="Choudhury"/>
** A Branch Bit (BR) register assists with reversible control flow.<ref name="Choudhury"/>
| last1 = Choudhury
| first1 = Vikraman
| title = Reversible Programming Languages
| date = April 2018
| url=https://vikraman.org/files/reversible-languages.pdf
<!-- If it were accessible online, you'd add: |url=... |access-date=... -->
<!-- If it were for a specific institution, you could add: |institution=... -->
}}</ref>
** A Branch Bit (BR) register assists with reversible control flow.<ref>{{cite web
| last1 = Choudhury
| first1 = Vikraman
| title = Reversible Programming Languages
| date = April 2018
| url=https://vikraman.org/files/reversible-languages.pdf
<!-- If it were accessible online, you'd add: |url=... |access-date=... -->
<!-- If it were for a specific institution, you could add: |institution=... -->
}}</ref>
** Branch instructions (e.g., <code>BEZ</code>, <code>BLTZ</code>) are conditional and require careful pairing. Reverse branches (<code>RBEZ</code>, <code>RBLTZ</code>) also toggle the DIR bit.<ref>{{cite thesis
| last1 = Vieri
<!-- timestamp: Wed, 04 May 2022 12:58:32 +0200 -->
}}</ref>
** Memory access uses a reversible <code>EXCH</code> (exchange) instruction that swaps register and memory contents.<ref>{{cite webname="Choudhury"/>
** Arithmetic and logic instructions (e.g., <code>ADD</code>, <code>ANDX</code>, <code>XOR</code>, <code>SLLX</code>, <code>RL</code>) are designed to be reversible, with some operations' behavior (like addition/subtraction or rotation direction) dependent on the DIR bit.<ref name="Choudhury"/>
| last1 = Choudhury
| first1 = Vikraman
| title = Reversible Programming Languages
| date = April 2018
| url=https://vikraman.org/files/reversible-languages.pdf
<!-- If it were accessible online, you'd add: |url=... |access-date=... -->
<!-- If it were for a specific institution, you could add: |institution=... -->
}}</ref>
** Arithmetic and logic instructions (e.g., <code>ADD</code>, <code>ANDX</code>, <code>XOR</code>, <code>SLLX</code>, <code>RL</code>) are designed to be reversible, with some operations' behavior (like addition/subtraction or rotation direction) dependent on the DIR bit.<ref>{{cite web
| last1 = Choudhury
| first1 = Vikraman
| title = Reversible Programming Languages
| date = April 2018
| url=https://vikraman.org/files/reversible-languages.pdf
<!-- If it were accessible online, you'd add: |url=... |access-date=... -->
<!-- If it were for a specific institution, you could add: |institution=... -->
}}</ref>
===Code examples===
<!-- bibsource: dblp computer science bibliography, https://dblp.org -->
<!-- timestamp: Mon, 01 Apr 2024 11:15:35 +0200 -->
}}</ref>, Pi/Pi^o,<ref name="Choudhury"/> Inv <ref>{{cite webjournal
| last1 = Choudhury
| first1 = Vikraman
| title = Reversible Programming Languages
| date = April 2018
| url=https://vikraman.org/files/reversible-languages.pdf
<!-- If it were accessible online, you'd add: |url=... |access-date=... -->
<!-- If it were for a specific institution, you could add: |institution=... -->
}}</ref>, Inv <ref>{{cite journal
| last1 = Matsuda
| first1 = Kazutaka
<!-- bibsource: dblp computer science bibliography, https://dblp.org -->
<!-- timestamp: Mon, 03 Mar 2025 21:37:52 +0100 -->
}}</ref> <ref name="Choudhury"/><ref>{{cite webarXiv
| last1 = Choudhury
| first1 = Vikraman
| title = Reversible Programming Languages
| date = April 2018
| url=https://vikraman.org/files/reversible-languages.pdf
<!-- If it were accessible online, you'd add: |url=... |access-date=... -->
<!-- If it were for a specific institution, you could add: |institution=... -->
}}</ref> <ref>{{cite arXiv
| last1 = Haulund
| first1 = Tue
| 