Janus and reversible languages: run programs backwards, time-symmetric computation.
"Every computation can be undone. Time flows both ways."
Reversible computing ensures:
forward
Input ─────────────▶ Output
◀─────────────
backward
x = 5if without fi — conditionals must be invertibleprocedure swap(int x, int y)
x ^= y // x' = x ⊕ y
y ^= x // y' = y ⊕ (x ⊕ y) = x
x ^= y // x'' = (x ⊕ y) ⊕ x = y
// Running BACKWARDS automatically inverts!
// uncall swap(a, b) ← swaps back
// Forward: if-then-else-fi
if x = 0 then
x += 1
else
x += 2
fi x = 1 // <-- ASSERTION: must be true after forward
// Backward: uses fi-assertion to know which branch was taken
// Forward: from-do-loop-until
from x = 0 do
x += 1
loop
y += x
until x = 10
// Backward: runs until x = 0, undoing each iteration
How to make irreversible computation reversible:
1. Compute f(x) → y, keeping all intermediate garbage g
2. Copy y to output
3. UNCOMPUTE: run step 1 backwards to clean up g
┌─────────────────────────────────────┐
│ x ──▶ COMPUTE ──▶ (y,g) ──▶ COPY │
│ │ │ │
│ ▼ ▼ │
│ UNCOMPUTE y_out │
│ │ │
│ ▼ │
│ (x,0) │
└─────────────────────────────────────┘
Space: O(T) → O(T log T) with checkpointing
class ReversibleMachine:
def __init__(self):
self.tape = {} # variable → value
self.history = [] # for reversal
def xor_assign(self, var, value):
"""x ^= value (self-inverse!)"""
old = self.tape.get(var, 0)
self.tape[var] = old ^ value
self.history.append(('xor', var, value))
def add_assign(self, var, value):
"""x += value"""
old = self.tape.get(var, 0)
self.tape[var] = old + value
self.history.append(('add', var, value))
def sub_assign(self, var, value):
"""x -= value (inverse of add)"""
old = self.tape.get(var, 0)
self.tape[var] = old - value
self.history.append(('sub', var, value))
def reverse_step(self):
"""Undo last operation."""
if not self.history:
return False
op, var, value = self.history.pop()
if op == 'xor':
self.tape[var] ^= value # XOR is self-inverse
elif op == 'add':
self.tape[var] -= value
elif op == 'sub':
self.tape[var] += value
return True
def reverse_all(self):
"""Run entire program backwards."""
while self.reverse_step():
pass
Fredkin Gate (CSWAP): Toffoli Gate (CCNOT):
a ─────●───── a a ─────●───── a
│ │
b ───┬─┼─┬─── b' b ─────●───── b
│ │ │ │
c ───┴─●─┴─── c' c ─────⊕───── c ⊕ (a ∧ b)
If a=1: swap b,c If a=b=1: flip c
If a=0: pass through Otherwise: pass through
Both are universal for reversible classical computation.
# Reversible operations on GF(3)
# x ⊕₃ y = (x + y) mod 3 is reversible (inverse: x ⊖₃ y)
function gf3_add!(state, var, value)
state[var] = (state[var] + value) % 3
# Inverse: gf3_sub!(state, var, value)
end
function gf3_sub!(state, var, value)
state[var] = (state[var] - value + 3) % 3
end
# Trit-preserving swap
function trit_swap!(state, a, b)
# XOR doesn't work in GF(3), use:
state[a], state[b] = state[b], state[a]
# Self-inverse: swap is its own reverse
end
All quantum gates are unitary → reversible:
┌───┐
|ψ⟩ ────┤ U ├──── U|ψ⟩
└───┘
┌────┐
U|ψ⟩ ───┤ U† ├─── |ψ⟩ (U† = inverse)
└────┘
Irreversible measurement "collapses" superposition → information loss.
Irreversible: Erase 1 bit → kT ln(2) energy released as heat
≈ 2.8 × 10⁻²¹ J at room temperature
Reversible: No erasure → no theoretical minimum energy
(practical limits remain)
| Language | Description |
|---|---|
| Janus | First reversible imperative language |
| RFUN | Reversible functional |
| SyReC | Reversible circuit synthesis |
| Quipper | Quantum (inherently reversible) |
| Theseus | Type-safe reversible |
procedure fib(int n, int x1, int x2)
from x1 = 1 ∧ x2 = 0 do
x1 += x2
x1 <=> x2 // swap
n -= 1
until n = 0
// call fib(10, x1, x2) → x1 = 55, x2 = 89
// uncall fib(10, x1, x2) → x1 = 1, x2 = 0
quantum-computing - Unitary = reversiblethermodynamics - Landauer limitbidirectional-programming - Lensesinteraction-nets - Reduction is reversible