The core idea
A reversible language is one in which every execution step can be undone. If you know the state after a step and the program text, you can recover the state before it. Run the whole program from its end back to its start, and you get the original input back.
This is a strong restriction. Ordinary programming constantly destroys information. Writing x = 5 throws away whatever x held before, and the old value cannot be recovered from the new state. A reversible language forbids such steps, or requires that the information be kept somewhere.
Which operations are reversible
A step is reversible when different starting states always lead to different next states, so nothing is merged. Some everyday operations qualify.
- Adding in place. x += y can be undone by x -= y, as long as y is unchanged.
- Swapping. Exchanging two values can be undone by exchanging them again.
- Negation. Flipping the sign of a number undoes itself.
Others do not.
- Plain assignment. x = y loses the previous x.
- Multiplying by zero. Many inputs collapse to the same output.
- Most clearing operations. Setting a variable to zero forgets what it held.
A small worked example with a hypothetical state: let x be 3 and y be 4. After x += y, x is 7 and y is still 4. To undo, subtract y from x: 7 minus 4 is 3, which restores the original. By contrast, after x = y, x is 4 and the 3 is gone for good.
Control flow that goes both ways
Branches and loops need extra care. If a program takes one of two branches and then they rejoin, the reverse run must know which branch to retrace. Reversible languages handle this by attaching an assertion to the end of the branch: a condition that must hold if the first branch was taken and must fail otherwise. Likewise, a loop has an entry condition and an exit condition that make the iteration count recoverable.
A well-known research language in this style is Janus, whose programs are designed so that the inverse of any statement is another statement in the same language. Writing the inverse is mechanical: reverse the order of statements, and invert each one. Details differ between languages, so check a language’s definition before relying on any rule of thumb.
Why anyone cares
There are a few motivations.
- Physics and energy. A widely cited principle, associated with the physicist Rolf Landauer, links erasing a bit of information to a minimum amount of heat released. Reversible logic, in principle, avoids that cost. Whether this leads to practical savings depends on engineering, and the effect is far below what ordinary hardware dissipates for other reasons.
- Quantum computing. The operations on qubits are reversible, so ideas from reversible circuits carry over directly.
- Debugging. A debugger that can step backward is useful, and a reversible language can make that exact instead of relying on recorded history.
- Elegance. Having a program and its undo in a single text is attractive, and writing algorithms that preserve information is a good puzzle.
Reversible gates
At the circuit level, a classic example is the Toffoli gate, which has three inputs. It flips the third input only when both of the first two are 1, and leaves the first two unchanged. Applying it twice restores the original, so it is its own inverse. The gate is universal for reversible logic: you can build any reversible Boolean circuit from it, with extra helper bits as needed. Another well-known one, the Fredkin gate, swaps two inputs when a control bit is 1.
The price of reversibility is that you often need extra bits to hold information that an ordinary program would discard. These leftover bits are sometimes called garbage. A common trick is to compute a result, copy it out, and then run the computation backward to clean the garbage away.
Reversibility in esoteric languages
Esolang designers like reversibility because it forces fresh thinking. Some languages are reversible by construction. Others are only reversible in part, or include an instruction that flips the direction of execution. Grid languages offer a natural analogy: a pointer that moves along a path can in principle retrace it, though most do not guarantee that, since typical instructions discard values.
It is a good exercise to take an ordinary algorithm, such as computing a Fibonacci pair, and ask what extra state would make each step undoable. The answer often reveals how much a normal program silently throws away.
Is it as powerful
Reversible computing is not weaker in what it can compute. It is known that reversible Turing machines can simulate ordinary ones, usually at the cost of extra space or time. So a reversible language can be Turing complete, even though every step can be reversed.