Reversible Programming Language

A reversible programming language produces code that can be stopped at any point, reversed to any point and executed again. Every state change can be undone.

Is this really a function of the language, or is it more a function of the environment? Are there any examples?

It could be either. This page was started when someone asked about a proprietary language I worked on specifically created to generate reversible code. It had a keyword that indicated when reversal should stop.

It was a bad idea for several reasons. We ended up replacing it with a C++ library that let us achieve the same goals with normal C++ code.


There is a weird language named Kayak, which is reversible. Here it is


The Abundance language seems relatively non-weird, except ... "All Abundance programs can Jaunt -- run backward in time."

A quick Google led me to

"Abundance: A Data Base language that can run backward in time" by Roedy Green http://mindprod.com/article.html


Aren't all FunctionalProgrammingLanguages reversible in this sense?

Not really: after a BetaReduction? you don't know what formula the result was reduced from. That is, beta-reductions are deterministic into one direction only.

Do they save all of their state changes on stacks? Can you reverse execution direction and unwind the state changes to any previous state?

No, you can't. PrologLanguage can unwind to any state (which is required for backtracking), but these choice-points are not first level objects.

How closely coupled is this to hardware implementing ReversibleLogic? Does one imply/require the other, or not?

They are unrelated, but I first heard about ReversibleLogic when searching UseNet while trying to debug the reversible programming language.


With logging, there are some GoodDebuggers for Java that allow you to "step backwards" through a detailed history of your program's execution, to examine past state.

In theory, it wouldn't be hard to restore a system to a previous state and continue, but the listed Java debuggers don't have this feature.

(The SmalltalkLanguage, by contrast, has always had a "retry" operation on all the items you see on the stack. It isn't a strong "rollback to previous state," but it suffices for most common usage.)


Some research on reverse execution:

A research debugger that can execute Java code, both forward and backward: http://www.ingentaconnect.com/content/oup/cj/2002/00000045/00000006/art00608 (Full text, $25.48 plus tax)

JIVE Project: Interactive visualization (including reverse execution) http://www.acsu.buffalo.edu/~ahegde2/


See Also:


CategoryProgrammingLanguage


EditText of this page (last edited August 3, 2014) or FindPage with title or text search