Cryptography Reference
In-Depth Information
every element in a list. Both are quite useful and easy to reverse
without conflicts.
Recursion
Recursion is a problem here. If procedures call them-
selves, then they are building a de facto loop and it may be dif-
ficult to identify a loop's starting position. For instance, here is
an example of a loop with an open beginning:
procedure Bob;
x=x+1;
if x<100 then Bob;
end;
This is just a while loop and it is impossible to back into it and
know the initial value of
x
when it began.
One solution is to ban recursion altogether. The standard loop
constructs will serve most purposes. This is, alas, theoreti-
cally problematic. Much of the theoretical intractability of pro-
grams comes from their ability to start recursing. While this
might make implementing reversible programs easier, it could
severely curtail their theoretical security.
Another solution is to save copies of all affected variables be-
fore they enter procedures. So, before the procedure Bob be-
gins, the reversible machine will save a copy of
x
.Thisversion
won't be destroyed, but it will become part of the waste bits that
must be conveyed along with the output.
In the end, the code for this system is quite close to the assembly
Ralph Merkle also notes
that most assembly code
is reversible and predicts
that in the future smart
compilers will rearrange
instructions to ensure
reversibility. This will
allow the chips to run
cooler once they're
designed to save the
energy from reversible
computations [Mer93].
code used for regular machines. The only difference is that there
is no complete overwriting of information. That would make the
system irreversible. Perhaps future machines will actually change
the programming systems to enhance reversibility. That may come
if reversible computers prove to be the best way to reduce power
consumption to an acceptable level.
8.3.3 The Reversible Grammar Machine
Although the structure will be very similar tomachine code, I've cho-
sen to create this implementation of the Reversible Grammar Ma-
chine (RGM) in LISP, one of the best experimental tools for creat-
ing new languages and playing around with their limits. It includes
many of the basic features for creating and modifying lists plus there
are many built-in pattern-matching functions. All of this makes it
