Inspiration

The theme was time. One odd fact kept bugging us: a debugger can only step backwards if it wrote down everything your program did on the way forward, because normal computers throw away the old value every time they assign a new one. x = 5 and whatever x was is gone.

There's a branch of computing that avoids this, with machines that never discard anything. It goes back to Landauer and Bennett in the 60s and 70s. What we couldn't find was anyone saying what it costs in practice, compared with the obvious alternatives. So we built one and measured it.

What it does

Palindrome is a small computer where every instruction can be undone. Any program on it can run backwards, and the machine doesn't keep a log to make that work.

In the browser you can play Pong, lose, drag the timeline back and carry on with different keys. You can run a cipher, step back, and the same program decrypts. You can sort eight numbers and see the 19 yes/no answers the sort has to hold on to. And in the debugger you can ask "who last changed this variable?" and it rewinds until it finds out.

How we built it

We designed our own instruction set (ISA) of 19 instructions, all of them reversible, and built a virtual machine that runs it. We wrote the VM twice: one version keeps a full diary of what it did, and one keeps nothing and works out each undo as it goes. We compare the two after every step. It's C++ compiled to WebAssembly, so it runs in the page.

On top of that we made our own programming language, rev, and a compiler that turns it into our own assembly language. Our assembler then turns that into machine code for the VM. The compiler also reports what each line costs. Around all of it there's a debugger, a VS Code extension and the web app.

The language has no plain =, because assignment is a one-way street. You change values in place, with things like += and XOR (^=), and each of those can be undone: XOR the same value in a second time and you're back where you started.

To keep the comparison honest we also wrote ordinary versions of the sort and Pong, plus a tightly packed diary and a snapshot-and-replay scheme, and measured memory against all of them.

Challenges we ran into

Our first benchmark was wrong. We compared the reversible machine against our own wasteful diary and it won by miles, which meant nothing. We built stronger comparisons and reported the results, including the ones where we lose.

A bug in Pong took a while to find. A key press can arrive between any two instructions, and Pong read its input twice, so a key at the wrong moment left a register with the wrong value. We fixed it and wrote a test that presses a key at every point in a frame.

We also had a counter that briefly passes through zero while it's being updated, which broke frame stepping. And our first cipher barely scrambled anything, so we swapped it for the real one and checked it against the published test vector.

Accomplishments that we're proud of

It works end to end, from our own language through the compiler and assembler to the machine, and up to the browser, with about 430 automated tests. Stepping back is exact: text un-prints, the screen un-draws, and the machine isn't holding any history.

The cost table is real. For each frame of Pong, a naive diary keeps about 19,000 bytes, a tightly packed one keeps 126, and ours keeps 8, which is just the key presses. In return, our programs run about three times as many instructions.

What we learned

Going backwards isn't free. You pay in extra instructions and in leftovers the program can't erase. Anything from outside, like a key press, has to be recorded, because the machine can't work it out later. And testing against strong comparisons changed our results a lot.

What's next for Palindrome

Testing a program with a lot of memory, where we expect the reversible approach to look better. Getting the "who last changed this?" debugger into the browser. Cheaper printing and a leaner compiler. And a two-player game with rollback, since this is a natural fit.