Sunday, August 18, 2013

Reversible binary operators

Given that a binary operation is a partial function $S \times S \to S$ a reversible binary operation is a bijection from a subset of $S \times S$ to another subset of S. The key reason that reversible binary operations are so interesting to me is that they can be used as a means of describing any irreversible computation in a reversible framework.

If we take the result of an irreversible computation and put it into the first slot of $S \times S$ and we put the information lost in the second slot then we will have a reversible decomposition of a structure into parts that are relevant and non-relevant to the current computation.

Every reversible binary operation has a complement in which the slots of $S \times S$ are reversed. The two slots of $S \times S$ induces two partitions of the output set that taken together cover it. Of particular interest to us are covering partitions that are independent and divisions.

The well known cons operation is a reversible binary operation because given any list like '(1 2 3) we can decompose it into first and rest parts '((1) (2 3)). We can clearly take the complement of the cons decomposition operation to get '((2 3) (1)).

The two parts first and rest of the operation are not only independent but divisions as well so we can for example use setf on the first and rest places to modify the value of a given list. We can define a special type of composition for reversible binary operations by taking the composition of the first parts and appending the trash parts together in the second part of the operation. This is a way of composing irreversible computations well also maintaining all the information we need to maintain reversibility.