Reversible programming language

A reversible programming language is designed to bridge the gap between the theoretical models of reversible computing and practical software development. They provide constructs that allow programmers to write code that is guaranteed, by the language's syntax and semantics, to be executable both forwards and backwards deterministically.

Core concepts and design principles

The fundamental goal of a reversible programming language is to support computation that is deterministic in both the forward and backward directions.This is typically achieved by ensuring that every primitive operation and composite statement within the language is locally invertible. Local invertibility means that each basic computational step has a well-defined inverse, and the inverse of a sequence of steps is the sequence of inverse steps performed in reverse order.

Key in the design of many reversible languages is cleanliness or garbage-free computation. This means avoiding the accumulation of auxiliary information (like computation histories or ancilla bits) that is generated solely for the purpose of enabling reversibility but is not part of the desired output. Clean reversible languages aim to perform computations and their reversals using only the specified input and output variables.

To achieve local invertibility and cleanliness, reversible languages typically incorporate several features:

• Reversible Updates: Standard assignment statements (x = expression) 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 +=, -=, ^= (bitwise XOR). An important restriction is that the variable being updated (e.g., x in x += e) must not appear in the expression on the right-hand side (e) to ensure the operation is bijective. The swap operation (x <=> y), which exchanges the values of two variables, is another fundamental reversible update.
• Reversible Control Flow: Conventional control flow structures like If-then-else and While loops merge computational paths, making them irreversible. Reversible languages introduce specialized constructs. Conditionals often require both a test condition (evaluated on entry) and an assertion (a predicate that must hold true on exit from one branch and false on exit from the other). Similarly, loops might require entry assertions and exit tests. 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. 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 call (forward execution) and uncall or rcall (backward execution).
• Data Structures: Early reversible languages often restricted data types to simple ones like integers and fixed-size arrays. 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 pop can perfectly reverse push. More recent research has explored reversible object-oriented features, including user-defined types, inheritance, and polymorphism.
• Computational Power: A common benchmark for the computational power of a reversible language is r-Turing completeness, which means the language can simulate any Reversible Turing Machine cleanly (without garbage accumulation).

Janus Language

Janus is widely recognized as the first structured, imperative programming language designed explicitly for reversible computation. Originally conceived by Christopher Lutz and Howard Derby at Caltech in the 1980s, it was later rediscovered, formalized, and extended, notably by Tetsuo Yokoyama and Robert Glück.

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.

Syntax and semantics

• Program Structure: A Janus program consists of global variable declarations followed by procedure declarations. The execution starts at a procedure named main, or the last procedure defined if main 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. Some versions include stacks. All variables and array elements are initialized to zero.
• Statements: Assignment: Reversible updates x op= e or x[e] op= e, where op is +, -, or ^ (bitwise XOR). The variable x must not appear in the expression e. Swap: x <=> y exchanges the values of x and y. Conditional: if e1 then s1 else s2 fi e2. The expression e1 is the test evaluated upon forward entry. The expression e2 is an assertion evaluated upon forward exit; it must be true if s1 was executed and false if s2 was executed. For backward execution (e.g., via uncall), e2 acts as the test to determine which inverse branch (s1−1 or s2−1) to take, and e1 becomes the assertion checked upon exiting backward. Loop: from e1 do s1 loop s2 until e2. Upon forward entry, assertion e1 must be true. s1 is executed. Then, test e2 is evaluated. If true, the loop terminates. If false, s2 is executed, after which assertion e1 must now be false for the loop to continue back to s1. In reverse, e2 is the entry assertion, s2−1 is executed, e1 is the test (loop continues if false, terminates if true), and s1−1 is executed if the loop continues. Stack Operations: push(x, stack) and pop(x, stack). Reversibility often relies on assumptions about the state of x (for example, x must be set to 0 after a call to push in order to be the perfect inverse of pop, which must restore x from 0 to the top value on the stack). Local Variables: local t x = e1 in s delocal t x = e2 This block introduces a local variable x of type t, initializes it reversibly using e1 and executes s. After executing s the value of x must be equal to the value of e2. The delocal-part of the statement stores the final value of x directly in the code. By storing the final value of x, it can be restored on a backwards run of the code. This in effect allows for the deletion of x after it leaves the scope. Procedure Call: call id executes procedure id forwards; uncall id executes procedure id backwards. Procedures operate via side effects on the global store. Skip: skip does nothing and is its own inverse. Sequence: s1; s2. The inverse is s2−1; s1−1.

Implementations and code examples

Several online interpreters for Janus exist. Janus has been used to implement various algorithms reversibly, including computing Fibonacci pairs and simulating RTMs, Fast Fourier Transform (FFT) and graph algorithms, and simulating the Schrödinger wave equation.

The following fibpair procedure in Janus calculates a pair of consecutive Fibonacci numbers. Given an input n, it sets x1 to F(n) and x2 to F(n+1), assuming x1 and x2 are initially 0:

For calling and uncalling the Fibonacci-pair procedure we use

R Language (MIT)

The R language (distinct from the statistical language R) was developed by Michael P. Frank at MIT in the late 1990s as part of the Reversible Computing project. It is an imperative, compiled language featuring an S-expression (Lisp-like) syntax. 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.

Syntax and semantics

• Program Structure: Programs are defined using (defmain ...) for the main routine and (defsub ...) for subroutines. Global variables and arrays are declared with (defword ...) and (defarray ...).
• Data Types: R primarily supports integers and integer arrays.
• Statements: Assignment/Update: Includes increment (loc ++), negation (- loc), swap (loc <-> loc), and reversible updates (loc op= e) using operators like +=, -=, ^=, and specialized comparison-updates (<=<, >=>). Similar restrictions to Janus apply regarding variable dependencies. Conditional: (if e then s*). To ensure reversibility, the language requires that the value of the conditional expression e must be the same before and after the execution of the then block (s*). This acts as an implicit invariant assertion, similar in function to Janus's explicit exit assertion. Loop: (for name = e_start to e_end s*). Reversibility requires that the loop iteration variable (name) must have the same value before entering and after exiting the loop. Local Binding: (let ((name <- e)) s*). Introduces a local variable name initialized with e. 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 local/delocal. Procedure Call: Explicit forward (call subname e*) and reverse (rcall subname e*) calls are provided. Output: (printword e) and (println) are included for output. These are inherently irreversible operations.

Pendulum/PISA target architecture

The R language was designed with a specific hardware target: the Pendulum processor.

• Architecture: Pendulum is a 12-bit, RISC-inspired, fully reversible microprocessor implemented in 0.5μm CMOS. It features general-purpose registers and fixed-length instructions.
• PISA Features: The instruction set includes several features tailored for reversibility: A Direction Bit (DIR) register tracks forward/backward execution mode. A Branch Bit (BR) register assists with reversible control flow. Branch instructions (e.g., BEZ, BLTZ) are conditional and require careful pairing. Reverse branches (RBEZ, RBLTZ) also toggle the DIR bit. Memory access uses a reversible EXCH (exchange) instruction that swaps register and memory contents. Arithmetic and logic instructions (e.g., ADD, ANDX, XOR, SLLX, RL) are designed to be reversible, with some operations' behavior (like addition/subtraction or rotation direction) dependent on the DIR bit.

Code examples

The following PISA assembly code simulates a free-falling object. It includes a main section to call and "uncall" (reverse) a subroutine named Fall, which contains the core simulation logic.

The R program defines global variables for height (h), end time (tend), velocity (v), and current time (t). The core logic is encapsulated in the Fall subroutine, which simulates the object's motion. The main routine initializes parameters, calls Fall to simulate forward motion, then modifies parameters and calls Fall in reverse (rcall Fall), mirroring the structure of the PISA example's "Call Fall" and "Uncall Fall" sections.

A key feature of R's if statement is that the conditional expression must evaluate to the same truth value before and after the execution of its then block. The Fall subroutine in PISA (lines 30-36) effectively has a loop that runs as long as t is not equal to tend, but this loop is only entered if an initial condition (implied by BGTZ t 5 meaning skip if t > 0, so run if t <= 0) is met. To translate this faithfully and handle R's if semantics, the R code for Fall uses a let binding to capture the state of the initial condition (t <= 0) before the loop. The if then operates on this captured, unchanging boolean value. The loop itself is represented by R's for construct, iterating tend times, which corresponds to the PISA loop structure (BNE t tend -5).

Overview of other reversible languages

Research has continued beyond Janus and R, exploring different paradigms and features:

• Eel (Energy-Efficient Language): Notable for supporting partially reversible computation. It allows mixing reversible operations with irreversible ones. To handle irreversible steps during reversal, Eel uses a "log stack" to save the necessary information (e.g., overwritten values), explicitly trading increased space complexity for the ability to reverse irreversible actions, while associating an energy cost with these actions based on Landauer's principle. It features advanced control logic constructs (protected/general conditionals and loops) offering different points on the energy-space trade-off spectrum. This makes Eel distinct from fully reversible languages like Janus, aiming for more flexibility in algorithm design.
• Rfun: A reversible functional programming language. Its semantics have been modeled using categorical structures like join inverse rig categories, highlighting the connection between functional programming and abstract algebraic models of reversibility.
• ROOPL: The first reversible object-oriented programming language. It extends the imperative reversible paradigm with features like user-defined data types (classes), inheritance, and subtype polymorphism. ROOPL demonstrates that higher-level object-oriented abstractions can be integrated into a reversible framework while maintaining local invertibility and r-Turing completeness. It was designed for garbage-free translation to the PISA assembly language.
• Reversible HDLs: To aid in the complex task of designing reversible logic circuits, specialized Hardware Description Languages have been developed. These are often functional in nature and may include features like linear types to manage resources and ensure garbage-free designs. They facilitate a design flow from high-level descriptions to gate-level implementations.
• Flowchart Languages: Languages like R-CORE, R-WHILE, and SRL provide structured representations of reversible control flow, often serving as intermediate languages or theoretical models. Their semantics can also be captured using categorical frameworks.
• Proposed Languages: A variety of other languages have been proposed, including Psi-Lisp, Pi/Pi^o, Inv, Yarel, SPARCL, Hermes (focused on cryptography), and Revs (compiling F# subset to circuits). Reversibility has also been studied in the context of existing languages like Erlang.

Comparison of reversible programming languages

The following table summarizes key characteristics of some prominent reversible programming languages discussed above:

This comparison highlights the different design choices made. Janus and R enforce full reversibility through language constructs, differing primarily in syntax (C-like vs S-expression) and target (interpretation vs PISA compilation). Eel introduces partial reversibility, allowing irreversible operations at the cost of using a log stack for reversal information and incurring a conceptual energy cost, aiming for greater flexibility. ROOPL extends the fully reversible imperative model with object-oriented features, demonstrating the applicability of higher-level abstractions.