Reversible programming | Hacker News Reader

Reversible programming

stanford.edu

76 pointsjackowayed18 comments

Wasn't it a consequence of Maxwell's Demon like that as soon a you revert any operation theoretically there will be no energy consumed? Because cleaning up memory is the only costly operation.

There are people working on reversible computing hardware for that very reason. You still have to consume energy to output information, but that's relatively insignificant.

Kurzweil talks about it in The Singularity Is Near, when he examines just how far Moore's Law can go. If we can figure out reversible computing, the upper bound is quite a bit further out, since heat dissipation issues go away. Ask a reversible computer a yes-no question that takes enormous computation, and it will consume no more energy than a rock, until at last you have to pay for your one bit of output.

Have you any information published by the folks who are working on this task?

No, sorry. Aside from Kurzweil, I read an article a year or two ago about someone who'd made a bit of a breakthrough, figuring out how to break a large computation into a lot of smaller reversible chunks. But I don't have the link.

Edit: I seemed to remember that IBM had done some work on it, and found this paper: http://www.research.ibm.com/people/b/bennetc/bennettc19734c5...

Then I remembered the name Fredkin, and found this: http://www.aicit.org/jdcta/ppl/18.%20JDCTA4-440054.pdf

Fredkin invented the Fredkin Gate: http://en.wikipedia.org/wiki/Fredkin_gate

And quantum computation must be reversible too, except for the final measurement process.

boomerang[1] is a whole programming language for writing bidirectional trasformations (for text formats) using combinators and bidirectional primitives. It seems quite alien but also really interesting.

[1] http://www.seas.upenn.edu/~harmony/

A beautiful model of reversible computing is the billiard ball model, summarized here:

http://en.wikipedia.org/wiki/Billiard-ball_computer

The punchline is that (idealized, friction free) billiard balls + billiard ball "mirrors" (for the balls to bounce off) are enough to do universal computation! To reverse the computation, just reverse all the billiard balls.

I wonder what would happen if you did (undo (discrete-log y g))

or tried to undo some other trap-door function. In cryptography, a trap door function has linear complexity in one direction, but in the other direction it is either exponential or NP, unless you know some additional information in which case it drops back down to linear.

Given the fact that the entire call/uncall mechanism is based on keeping the original parameters that are required to undo the calculation - it will work fine, but you won't be able to call the undo on the result you got from any other source (i.e. not through the call/uncall mechanism)

read the source for p-divmod (one of the most useful functions in cryptography). You need to pass the original y to get back the original x in the reverse

If you're wondering if there's a real-world use for this:

http://lambda-the-ultimate.org/node/4191

One of the coolest papers I've seen recently.

Also, out recently: https://github.com/MedeaMelana/JsonGrammar

I fiddled with a similar idea for XML a long time ago, but I lacked the skills to pull it off. Also it's harder in Python, several-years-more-experienced-me thinks you really want a combinator approach for this as JsonGrammar takes, and while that can be done in not-Haskell, it's certainly a lot easier in Haskell for a number of reasons.

What happens if a function is not bijective?

Good question. Obviously only bijections are invertible. Perhaps only bijections are allowed, or perhaps the reversed version of a non-bijective function uses a subset of the original function's codomain as its domain.

It would seem that you would have to be explicit about the domain and codomain of a function to even be able to programmatically figure out an inverse function. Given the author's example of strings to integers, clearly the inverse function will be from integers to strings—but obviously the codomain can't be all strings, but rather ones that are string representations of integers. The validation logic for which strings represent integers (which is essentially the definition of the codomain of the integers->strings function) would certainly have to be explicit somewhere.

Interesting; Factor has a neat library for inverting functions:

http://docs.factorcode.org/content/article-inverse%2Cintro.h...

I'd like to take this opportunity to point out that this was done by Lisp, and is another example of Lisp and "out of the box" thinking linked.

Stuff like this always reinforces my thought that Lisp and strange thinking work well together.

/me 2c

Do you have an example?

Well -

* Qi and Loom are pretty nifty and IMO radical projects.

* Hot-patchable servers are trivially doable.

* There are some really trippy things over on Lambda the Ultimate done in Lisp (Schemes to be precise).

I don't try to canvass projects and figure out which ones are done in Lisp for net arguments.

I have trouble seeing how Qi is interesting except for sequent calculus and that in and of itself has disturbing practical implications. I'd personally like to see an example of a practical programming problem which is more easily implemented and integrated in Qi than in, say, Racket.

Also, Lambda the Ultimate is a weblog for functional programming, not Lisp specifically.

Reply on news.ycombinator.com