Programming Reversible Computers

The theoretical study of the efficiency of reversible computing is certainly very interesting, but it's difficult to make progress on.

In contrast, the accompanying area, of how to apply the known theory to actually program reversible computers effectively, is ripe for advancement. My plan for my work in this area will involve the following steps, in approximately the following order:

1. Define a high-level programming language that leverages off of appropriate new reversible programming abstractions in order to make it easy to describe algorithms having arbitrary degrees of reversibility, up to and including full reversibility.
2. Demonstrate the expressiveness of the language by writing programs in it that implement the partially-to-fully reversible algorithms that will have already been studied in the theoretical work.
3. Write a compiler that can translate programs in the high-level language into instructions for a processor architecture that supports reversible computing, such as Pendulum or something like it.
4. Enable the compiler to optionally apply its own transformations for automatically reducing the thermodynamic complexity of the program as part of the compilation process. These transformations might include Bennett's technique, traditional data compression, or any new techniques that I might have discovered in my theoretical work. The user of the compiler should be able to specify how he wishes to trade off thermodynamic complexity versus space and time complexity.
5. Compile my various example programs using a variety of different automatic transformations for reducing thermodynamic complexity.
6. Execute the compiled programs on a simulated reversible processor. Check the correctness of the results to validate the compiler. Measure the actual time, space, and thermodynamic complexities of the executions to verify the theoretical predictions.
7. Compare the thermodynamic, time, and space efficiency of programs that are hand-designed to be highly reversible against that of nominally irreversible programs whose thermodynamic efficiency is optimized by the compiler using the general, automatic techniques.

I intend to spend approximately five months, from April through August of 1997, on this experimental work. If it seems to be moving too slowly, I can always limit the ambitiousness of the compiler, reduce the number of example programs being explored, or extend the period of research a few months. Since this experimental side of the research mainly consists of just software design and programming, as opposed to an all-or-nothing struggle to prove a possibly false theorem, I have high confidence in the success of the work, so there is less risk involved in extending the amount of time spent on it, if necessary. However, I would very much like to wrap it up by, at latest, the end of the year, if not in August as currently planned.