Reversible Computing for Developers: Understanding the Basics

There’s been a lot of talk about how AI is impacting software engineering, mostly focusing on the positive use cases for developers. But there is a mounting suspicion that the sheer amount of computing power needed to produce large language models is going to have an effect on how much more computing at this scale we can do. The sheer amount of electrical energy needed, in all those Nvidia chips, was already a problem when we overdosed on Crypto. But at least one of the main movers, Ethereum, moved their main algorithm from Proof of Work to Proof of Stake, thereby wasting much less energy.

This post is an attempt to shine some light on an area of hope that has been getting coverage recently: reversible computing. We’ll look at how reversible architecture might save energy and what it could mean for developers.

The Basic Physics of Ones and Zeroes

As the components in chips get smaller and closer together, excess heat becomes a serious problem. To stop wasting energy, we have to stop doing computational work that we can never recover. It turns out that the still far-off quantum computing also needs to consider these alternatives too.

Lesson for developers: stay aware of the principles of functional programming and try to imagine systems as moving between a number of fixed states.

But first of all, what on Earth is and isn’t reversible? We all know that a smashed vase never un-smashes itself, and this leads to the idea of entropy, which is the observation that, energy-wise, everything naturally gets more chaotic and falls apart. This is a one-way process, exemplified by the vase.

Let’s look at a logic gate. We know that these are the basics of circuits. The classic 2 input AND gate performs just the same bitwise operation we do in software. I do it in C# below:

We usually use bitwise arithmetic to create masks, for instance when manipulating images to get sprites to move on screen.

Now, in English, the AND gate is positive (with a binary output of 1 ) when inputs A and B are both 1. Fairly simple:

So, can I go in reverse? In other words, can I look at the output and deduce the inputs? Now, I can be sure that if the output is 1, then the inputs were also both1. That’s just the bottom row. Unfortunately, I can’t do that if the output is 0, as there are clearly 3 alternate routes to that output.

So the gate loses information; it loses energy every operation. By comparison, a simple NOT gate, which just reverses the bit, is indeed fully reversible. While the gate can lose energy by just flipping bits, we should strive to stop the information loss.

In the mechanical world, we are used to a degree of reversibility. If you have an old-school petrol car, you know that it uses a battery to start it. But once the engine is running, the alternator helps to recharge the battery. So first the energy goes from the battery to the motor, then from the motor back into the battery. We also allow mechanical processes to work in cycles in a similar way, like the four strokes of a combustion engine. Or even a pendulum.

So in order to allow for a reverse operation on a logic gate, we would have to somehow retain information on the right-hand side. This will probably be slower, but should allow for an energy saving reversible calculation. For a start, you’d imagine it would have the same number of inputs as outputs.

A lot of this is backed by recent theory. If you want a full-fat version of what is going on with the physics, this recent article goes into the relationship between energy and information.

Reversible Software

You might imagine that if we are spending time thinking about reversible computing, then there should be some reversible software — and perhaps a reversible software language. We can understand reversible code by assuming that it exists in fixed states and that you can go backward to previous states. Functional programming languages can sometimes achieve this. But in general, if you cannot deduce the inputs from a method output, you probably don’t have reversibility.

From another level, if you can consider running code as moving from one ‘state’ to another, like a state machine or a classic Turing Machine, then the idea of reversibility seems more straightforward. If you think about the way Git works, it looks at the progression of your code as nodes on a branch, with a past that you can jump back to. Git is reversible to a fault — indeed, anyone who has done a tricky merge will know that trying to get back to a past state while maintaining some choice bits of your present state isn’t fun.

There is a reversible high-level programming language called Janus. Purely as a taster, below is the Janus code for a  Fibonacci pair calculation where n = 4 in the sequence (which gives 5 and 8).

I don’t think any one organisation is dedicated to completing the reversible stack quite yet, but given the speed which LLMs are powering up, we will need to make sure we can keep feeding their insatiable energy appetite somehow.

What Does This Mean for Developers?

There was a major architecture redesign for transputers when parallel (or concurrent) computing was new. We needed to use RISC (reduced instruction) chips, not CISC (complex instruction) chips. Plus, there was a specialist concurrent language called OCCAM.

Over the years, underlying operating systems got a better hold of parallel operations, and the result was threading — which has always been a hard nut for even experienced developers to control reliably. Today, RISC architecture has made ARM the lead player in chips for smartphones.

The best way to keep ahead of architectural revolutions is to keep an eye on the community leading the charge. For reversible computing, if you stay aware of the principles of functional programming and try to imagine systems as moving between a number of fixed states, you should be able to keep abreast of any changes that this new paradigm might throw at you in the future.