Bidirectional Subroutines
by Brian Hayes
Published 14 February 2006
More on reversible computing.
If all it took to reverse a computation was stepping through a program backwards, there wouldn’t be much to say about the idea. In general, this kind of straightforward reversal doesn’t work. However, I have learned that a computer architecture outlined more than 40 years ago would have allowed such back-and-forth operation, at least for selected subroutines.
The scheme was proposed by Edwin D. Reilly, Jr., now retired from the State University of New York at Albany, and the late Francis D. Federighi. They presented their idea in the context of a machine called the MOHAC, or Mohawk-Hudson Automatic Computer, which they describe as a hypothetical computer designed for teaching programming in high schools. The MOHAC was never built, but Reilly and Federighi created a simulator that ran on the IBM 1620. By using (or abusing) certain unusual features of the MOHAC architecture, a program could be made to march either forward or backward through any sequence of contiguous instructions. Only in rare cases would such a subroutine produce meaningful results in both directions, but Reilly and Federighi suggested a further refinement that could have made the technique more broadly useful. When the direction of execution was reversed, they proposed, certain machine instructions would be replaced by their “conjugates.” Addition going forward would become subtraction on the backward phase; multiplication would become division; an instruction that reads data into a register would instead write the value of the register to a memory location. In this way many simple calculations could be made bidirectional.
Such two-way subroutines would do nothing to lower power consumption, which is now the main goal of reversible-computing research. But the dual-use instructions might have saved a few words of memory—a precious resource in 1965.
For the whole story see: Reilly, E. D. Jr., and F. D. Federighi. 1965. On reversible subroutines and computers that run backwards. Communications of the ACM 8:557–558. Reilly has made a PDF available on his web site.
Publication history
First publication: 14 February 2006
Converted to Eleventy framework: 22 April 2025
