Lambda the Ultimate

Well, it goes backwards, so that works for me. I think to have a 'true' reversible instruction set, either you have a very different language or you are just hiding the costs somewhere else.

Tailspin creates an ever increasing continuation for reversing, with each state change the new reverse continuation undoes the state change and calls the previous continuation. The cost is pretty minimal, but it probably has terrible memory performance.

I haven't explored the scalability of reversing, I think it will be fairly good as long as not having any memory freed ever is ok. The most computationally heavy visualization is the n-queens one http://will.thimbleby.net/algorithms/doku.php?id=n-queens and that works (although a little slow) on my old iPad.

Well, it goes backwards, so that works for me. I think to have a 'true' reversible instruction set, either you have a very different language or you are just hiding the costs somewhere else.

You are using a well-defined scientific term to mean something else, so don't be surprised if there is some confusion.

Your approach seems fine for teaching and some algorithm exploration, but I doubt it would scale to general programming.

Your approach seems fine for teaching and some algorithm exploration, but I doubt it would scale to general programming.

I would just like to add that the use of increasing continuations for the later reversal of an ongoing computation has been used for both general and specific programming since, at least, the late 1970s. See pretty much any implementation of Prolog based on Warren's PLM or WAM for the details.

According to that Wikipedia entry, a "reversible computation" is a computational process where the transition relation is injective, so Will's usage does not seem controversial.

A JavaScript execution is normally "open" (irreversible) in that it loses information to the environment. By capturing the lost information, this implementation effectively transforms an irreversible computation into a proper part of a reversible computation. (This paper is essential reading.)

> but I doubt it would scale to general programming

They said that about X, where X is any widely-used high-level programming feature you care to mention.

According to that Wikipedia entry, a "reversible computation" is a computational process where the transition relation is injective, so Will's usage does not seem controversial.

The article you are referring to is an orphan and mostly redundant with the more scientific and linked reversible computing article. But believe what you want. Here is a fixed link for the paper you are pointing out.

They said that about X, where X is any widely-used high-level programming feature you care to mention.

The technique of storing continuations after each instructions most definitely doesn't scale. This is not a new technique with unknown limitations. There are probably other ways of implementing the design that do scale, however (e.g. periodic delta-checkpoint + replay). We can argue about it in July if you want.

not having any memory freed ever

Have you thought about adapting this so you can start and stop recording in the middle of a program? I could see this being very useful in a step debugger. Often I'll know that a certain function call will cause a problem, but I choose to take baby steps through that function so I don't overlook the issue and have to restart. If I could get to the last known good state, press record, and then "step over" to the first known bad state, then I could scrub back and forth in a binary search for the problem.

This would be very possible, and very simple to implement. As a way to manage scalability, not recording an entire programs run would solve most of the issues. Perhaps only the last 100 or so operations could be kept, so any program error could be stepped back a certain amount.

For 'real' programming something like this would be well worth doing. Right now with the hugely powerful computers we have scalability is not an issue for me. There are lots of other ways to do 'real' programming, I'm interested in algorithm exploration, visualisation and opportunities for novel tools for learning.

java: silver bullet, chronon, et. al.
msft: intellitrace
ocaml: time travel
etc.

The cost is pretty minimal, but it probably has terrible memory performance.

Could you not garbage collect on a reverse? If so could you not have a reverse driven loop style of programming say:

/* POINT A */
get_some_input()
process_the_input()
force_a_reverse_back_to_point_a()

Reversing will free up memory, just running has the additional cost. The primary cost is that every JS object whose state is mutated is captured by the reverse continuations, a potential way to fix this would be to capture some path to the mutated object rather than the object itself. But I genuinely think that the performance / scalability is one of the least interesting things about Tailspin, if you are interested in those why would you be running in a meta-circular interpreter in the first place?

Exposing reversibility in the language would be really interesting. I could imagine a structure like call/cc or try{}catch-undo{}. Making a loop using reversing would need to have some non-reversed side-effect for the loop to do anything -- but this is possible as long as the side-effect doesn't impact the running of the program. For example in the IDE I initially made the console.log() functions reversible, until I realised it was actually counter-productive and that seeing previous logs was useful.

Actually, I was thinking about programmatic reversal and automatic memory collection together providing an opportunity for reactive computing in your language in a fashion similar to failure driven loops in Prolog.

That'd be really interesting. There's a lot of opportunity for interesting language extensions. It'd be an interesting trick to expose the reversibility in the language and also keep the same reversibility external to the interpreter, so that a user of a visualisation could scrub through the program execution whilst the program reverses.

I really am guessing here as I know nothing of your implementation or Javascript but language implementation details interest me greatly.

Since your implementation is meta-circular, would exposing a reverse function to your interpreter not expose it to the user as well, i.e., would the interface the interpreter uses internally, and the interface used by the user/GUI not be one in the same?

Yes, it wouldn't be possible to use the same reverse continuation for the UI and the program. Either there would have to be two reverse continuations (reverse-execution and reverse-time) or some sort of reverse and play forward system. Both of which sound fairly complex, but it'd be interesting to explore.

Most extant debuggers keep track of procedure arguments on the call stack, and some keep track of procedure arguments in recent history even if they're not on the call stack anymore.

If you add to that save the set of variables that a procedure closes over, you have repeatability of recently called procedures, starting from the beginning of each procedure.

Once you've got that, it's "trivial" to run the most recently called function (um, most recently called *before* the line requested was executed) from its start to the line whenever someone wants the state in which the program was last time it executed that line.

There is the matter of "externally visible" side effects such as printing, etc. Maybe those should only occur when the program is running forward.