Befreak is a purely reversible two-dimensional programming language (2003)

In general, one solution is to just keep the original inputs around as necessary. So instead of x -> x mod 4, take the function x -> (x, x mod 4); the inverse is just (x, y) -> x.

The actual % operator in this language is defined as (x, y) -> (y, x / y, x % y), acting as a divmod. The + and - operators are defined as (x, y) -> (x + y, y) and (x, y) -> (x - y, y). And so on, making sure enough inputs are left on the stack to reconstruct the others.

This just means that the language forces you to use more memory to make the computation reversible

Quantum computing suffer from the same problem. There you use the CNOT gate for example, because XOR is not reversible

Some pointers

https://en.wikipedia.org/wiki/Controlled_NOT_gate

https://en.wikipedia.org/wiki/Reversible_computing#Logical_r...

https://physics.stackexchange.com/questions/270266/why-do-qu...

In addition to the standard ways of dealing with this given by other commenters (keeping the original input around), perhaps more interesting is to imagine how befreak might compute 12 mod 4 using repeated subtraction.

I'm not clever enough to write the solution, but I imagine a loop using the branching operators (<, >, v, ^). Since each time through the loop pushes a bit onto the control stack, you have a built-in count for the number of times the loop was traversed.

In the example of 12 mod 4, the program would loop through 3 times and break once giving you 0001 (or 1110) on the control stack and something like 12, 8, 4, 0 on the stack. Then when reversing, control bits would be popped off and you'd end up going back 0, 4, 8, 12.

The proper way to think of reversible computing is that you just write everything down in a single-static-assignment ledger and never erase anything except for the tail end of the ledger. This can be accomplished with a multi-tape machine where writing down a value duplicates the current tape except the changed value. And once you're done with the computation, you can erase one tape at a time, starting with the most recent duplicate. So it can simulate a Turing machine. This implementation isn't as efficient as possible, but it's a good mental model for the absurdity required for reversibility.

Oh yeah, if that's what you're talking about you're just wrong. There are standard ways to deal with that in reversible computing, the most obvious is just to keep enough of the original data around that everything becomes invertible. E.g. instead of 12 mod 4 giving you zero it gives you (0,4,12) or something similar.