I shared some thoughts about my personal definition of reversible computing over on Mastodon today. (Yeah, I slightly mangled the example of a surjective function — should have said nonnegative integers.)

Not to be a total nerd about this, but what you want sorta feels like a “homotopy equivalence”. f : X → Y and g : Y → X form a homotopy equivalence if g(f(x)) is “pretty much” like x and f(g(y)) is “pretty much” like y.* So it’s a weakening of the typical definition of inverse functions. A reason I don’t think this is a great metaphor for you: It actually says something pretty interesting about the relationship between X and Y for there to be any homotopy equivalence at all between them. (We call X and Y “homotopy equivalent” in this situation.) I think you want to be able to reverse functions between very dissimilar / arbitrary domains. So IDK. * It’s actually not that g(f(x)) is “pretty much” like x for every x; it’s that the function g ∘ f is, holistically, “pretty much” like the identity function. (Homotopic.)

You'll have to hold my hand a bit here — I'm way beyond my comfort zone wrt properties n shit — but I'm really interested here in terminology, theory, prior art, etc. How does this homotopy equivalence work if f and/or g are non-injective, non-surjective, partial, multivalued, etc.? In other words, how close to bijective do these functions need to be for this property of homotopy equivalence to hold? Do f and g both need to be equally "close" to bijective? Or can one of them be made, say, only injective, and the other made multivalued? (Hopefully I said that correctly, or at least that you can intuit my questions)

What makes this your favorite definition of reversible computing?

I'm looking for ways to make "reversible" versions of, basically, everything in JavaScript. So I'm trying to figure out what properties would enable the best-feeling version of this.

Yeah sounds like you’re interested so I’m happy to elaborate! All this homotopy equivalence stuff is coming from topology. Hopefully you know some of the basic topology spiel: we’re talking about squishy squashy spaces where we don’t care about exact shape, just sorta the way the spaces are connected. So a doughnut is the same as a coffee mug (with a handle). The classic example of a homotopy equivalence, as far as I’m concerned, is the equivalence between a circle C (like points in the plane distance 1 from the origin) and an annulus A (like points in the plane distance 0.9 to 1.1 from the origin). These two objects are topologically different! For instance: Removing a single point from C will “cut” it, producing something that you can unwrap to turn it into a little line segment. But removing a single point from A just gives you, like, an annulus with an extra tiny extra hole in it. But there’s a looser sense in which C and A have the same structure — they’re both things with a hole in them — and that sameness is captured by the fact that there’s a homotopy equivalence connecting them. Making a map f: C → A is easy — C is already a subset of A, so you just map it in there. This is an injective function. Making a map g: A → C is less obvious, but still pretty straightforward. For instance, you can map each point of the annulus to the point of the circle at the same angle. Which is also the closest point of the circle, FWIW. This is a surjective function. Interestingly, in this situation, f and g are inverses of each other in one of the two directions. If I start on the circle, do f, and then do g, I get back to my original point. But no way are they going to be inverses of each other the other way around. You lose information going from A to C. So if I start with a point a ∈ A, do g, and do f, I’m going to (generally speaking) end up at a different place in A. But it turns out (and this is where I’m gonna get very sketchy), that f ∘ g (the map that takes a to f(g(a))) is not that far off from the identity function. In particular, it’s “homotopic” to the identity: it can be continuously deformed to the identity. So that’s what makes f & g a special homotopy equivalence pair. Now that I’ve given you the whole spiel, let me look more carefully at what you wrote there…

I just lol’d working out how to sloppy-reverse

sin(x) > 0

evaluating to

true

. glhf, man, this is gonna be wild.

Yeah, that's a great example @alltom. I'd be perfectly happy if that produced, say,

1

when reversed — even if the original

x

was something totally different — because

1

gets you another

true

when you go forward again.

Does it matter to what you’re working on that

x

might be used in another expression that doesn’t have

1

in its domain? Is rocking forward after a rock backward going to be sloppy too?

Yes, potentially! In addition to non-injective, non-surjective, and multivalued, I'm also interested in a notion of "reversible function" that is loose enough to cover partial functions. But I don't have any strong examples yet to help me feel out sensibilities for how I'd like them to behave.

Can't you just use matrices? I think of a matrix as basically a couple of transform (functions) put into a neat grid. Inverting them is possible, albeit costly. So couldn't you use a really high order matrix and fit your function as close as possible. Than invert it. This coming from an armchair math expert. 🙂

I'm interested in functions on other data types too. Also, non-affine math functions. So matrices are a great example of a bijective function, but I can't see how they'd apply to, say, array.splice()

I'm working on a similar, more manual approach to the problem of reversing functions with my https://vezwork.github.io/polylab/dist/demo/bidirectionalParse/ bidirectional language project. My approach, up until this point, has been to manually write the reverses of JS functions, and pair them up to form isomorphisms/multidirectional functions. i.e. I manually write three cases for plus: c = a + b, a = c - b, b = c - a. I was going to continue this approach with other data types like array.splice etc. I like this approach because it is quite doable, and while the simple multidirectional functions themselves are not so expressive to use, once you start composing a bunch of them, you can pretty quickly build up some pretty interesting multidirectional functions, and you kind of get it for free because you can write code as if it were just normal functions, but then call them forward and sideways and backwards.

That idea of manually writing bidirectional versions of functions actually lines up with what I have in mind. Like, my plan is to start with the simplest / dumbest thing that'll work, then gradually (likely manually) add better behaviour where it's most useful. So for instance, the "automatic" reverse version of a math function could just return 0 (or 1, or NaN), for string functions return empty string, etc. Just return values that are likely to be a fixed point, even if it's totally wrong. It'll be a useful (and quick) enabler for what I want to explore. And then yeah, on top of that I can begin layering in different improvements. A little gradient descent here, maybe minikanren there, maybe sprinkle some GPT bullshit on top. Anything will be an improvement. The suggestions you have about nudging values and treating the error as a point on 2D space are appreciated, since that's the fuzzy frontier of my understanding for how to do a good job of this. Like, my gut says that making x + y = z reversible could be done nicely by creating a special pair of values for x and y that preserve the constraint that they must add to z. But exactly how to do that, I'm not sure yet.