The most straightforward approach to implementing control-flow instructions (such as branches) reversibly is to push the source address for the branch onto a special stack. Unfortunately this approach accumulates garbage whenever a branch is taken, garbage that cannot be disposed of under program control.
A potentially more space-efficient approach is to store the source address in a ``branch register'' which can be cleared under program control. However, the branch register approach seems clumsy and inelegant.
To solve these problems, we borrow from physics the concept of ``time-symmetry,'' which says that the same sorts of operations should apply whether time (or in this case, program execution) is run forwards or backwards. Inspired by this notion, we can design time-symmetric branching, looping, and procedure-calling instructions that can be used to greatly reduce, and in many cases eliminate, the garbage created by control-flow operations in structured programs, in a way that is simple and elegant and mirrors the time-symmetry of the underlying physics.
[Note: After this memo was written, I noticed that many of the same ideas were previously developed in a paper by Hall, published in 1994. Thus, the present memo needs to be rewritten to credit Hall's contributions, where appropriate.]
This paper is part of the M series of working memos produced by the MIT Reversible Computing Project.