Hindsight: Reversible Computing 178
One of the more interesting tech pieces that came out this week has been Hindsight [PDF]. Hindsight is made by Virtutech and is billed as the "the first complete, general-purpose tool for reverse execution and debugging of arbitrary electronic systems." The demos were received extremely well and it just looks cool.
UI (Score:5, Interesting)
My question is how UI interactions are handled. If the execution between the checkpoint and current-1 instruction includes a UI interaction, it might be very confusing to the programmer to know what or how many UI interactions need to be carried out to accomplish the backstep.
"Last Technical Hurdles"? (Score:2, Interesting)
How in the world did they pull this off?
Re:UI (Score:1, Interesting)
But what about external events (Score:5, Interesting)
Re:That's just nutty... (Score:2, Interesting)
http://www.lambdacs.com/debugger/debugger.html [lambdacs.com] I'm sure a Hindsight sales person would (correctly) say this isn't a complete solution, but its the closest thing I've seen before this article.
Not by a decade. (Score:5, Interesting)
I read this usenet post [google.ca] every now and then when I'm trying to fix something, and it makes me want to cry every time I do.
Reverse Execution of Code? Haha! Oh wait... (Score:2, Interesting)
Hindsight seems to work based on a checkpoint mode when running backwards, it goes back to a checkpoint then runs forwards to the expected point. However how does it work with hardware?
Anybody tried this out for real?
OCaml anyone? (Score:4, Interesting)
And what about GUI and other side effects? Debugging a program in which such side-effects are deeply interleaved with algorithmics can be tricky indeed, although smart timestamping from the debugger will reduce glitches. But if you don't know better than randomly mixing algo and front-end in the first place, then you'd better fix the programmer than the program...
Re:hrmmm (Score:1, Interesting)
Any relation to ReVirt? (Score:5, Interesting)
ReVirt [umich.edu]:
Elephants never forget (Score:5, Interesting)
In this paper, he proposes the Elephant language [stanford.edu] that can refer to the past in computer programs.
Pretty cool stuff!
Is This Really New? (Score:3, Interesting)
Being able to trace backwards ware extraordinarily useful, and it's one thing I miss in modern compilers. I always assumed that this capability was taken out with the advent of event-driven (GUI) programming. That's when a lot of this kind of functionality seemed to disappear.
Re:UI (Score:3, Interesting)
Those bugs might be catched if the environment would record instructions one-by-one, but as is you may find a bug in your execution, roll back to the checkpoint and find that the bug is gone in the replay. Hey, that would be funny if it happened on a TV football game...
Obligotory jwz reversible gdb link (Score:1, Interesting)
(Actually someone has already posted [slashdot.org] the links jwz was talking about)
Re:Reverse Execution of Code? Haha! Oh wait... (Score:2, Interesting)
There is a way to do this, although it is a bit ugly. The reverse-runner forks the program into 3, one for each of the possibilities. It then continues this until values have been solved.
It would produce a decision tree, and the debugger could work backwards.
Of course, this is purely theoretical. If A and B were strings, the number of processes would be infinite, in which case heuristics would be required, and it wouldn't be perfect.
Re:But what about external events (Score:3, Interesting)
It's exactly an example of an external packet containing a wrong checksum.
If the system is in isolation, you would have to come up with the idea of sending a malformed packet yourself instead of just letting it run until it crashed. that doesn't seem a very likely thing to try.
Where do they store the entropy? (Score:3, Interesting)
more seriously, that would mean that there is no crypto on these machines since all encoding would be reversible.
Re:That's just nutty... (Score:4, Interesting)
At first I wasn't sure that your statement was true, but after thinking about it for 30 seconds or so, I realized it definitely was. Every instruction produces a deterministic calculation and can be reversed, right? If we have "ADD EAX, EBX", and know the current values of EAX and EBX, going backwards is easy, right?
Well, one really difficult case is jumps. How do you know what the previous instruction executed was? On X86 this would be pretty difficult since the encodings are non-regular, but even on an ISA with regular encodings it would be non-trivial because it would be difficult to figure whether you got to the instruction via a jump (which could be anywhere in memory), or from the previous instruction.
Add things such as Self-Modifying Code, and you have a real headache. Yes, you definitely need to track state as you go, though I'm not sure you'd need to save anything more than just the Instruction Pointer (which X86 does have a mechanism for). If you know what instructions were executed, it should be pretty easy to backtrack in time. I think.
Re:Damn misleading articles. (Score:2, Interesting)
I'm not trying to be an ass here, but isn't that why they call NOT a unary operation, because of one operand?
Re:That's just nutty... (Score:3, Interesting)
Try this UTM program:
Now, what UTM's could leave a machine in this state? Remember the states of the Universal Turing Machine are A, B, C, not what's written on the tape, i.e., the instructions.
The answer is, of course, a whole lot, but one simple subset of programs that can leave C in this state is any program like the above one, except the first instruction is Set A and B to values x0 and y0, where x0+y0=1+2=3, which is infinitely many, eg, 2+1=3,3+0=3,4+-1=3, etc. So that's infinitely many programs with the same form as the actual program, but with only a couple of constants changed.
(Note: true Turing Machines states aren't limited to a fixed set, like 0-255 etc, they use an encoding like 0100,1100,110100,111100, which can accomodate any size of number.)
That doesn't quite answer why it's generally complex to run a computer backwards, but you can put any number of instructions in between step 2 and 3, and as long as they don't touch A and B, once you've gone past that last instruction, you have no clue what states A and B were in until you go all the way back to the start of that program.
I guess a good checkpointing algorithm would be to save the states of any registers that are overwritten.
There are a few issues but... (Score:2, Interesting)
Replay with nondeterministic events (Score:2, Interesting)
The first language I know of that supported replay is the Abundance database language [mindprod.com], back in 1986. Also see http://c2.com/cgi/wiki?ReversibleProgrammingLangu
Re:UI (Score:2, Interesting)
The trick is to have a simulator fast enough so that you can do UI interactions, because the user isn't in the simulated world. As it happens Simics is fast enough and this is exactly how it works. I'm on the Simics product team, and one way we have of proving the point is to run operating systems and their applications backwards for which we cannot have the source code, eg Microsoft Windows. If someone still thinks we've inserted magic tricks after seeing CLOCK.EXE launched, run backwards and then unlaunch, well, there's not a lot more we can do. That also illustrates the point of the whole computer plus OS running backwards, not just a particular application.
You can get humorously stuck actually with UI interactions... if you run forward to a certain point going point click etc, and then have an animated discussion with somebody for five minutes having forgotten to pause the simulation... unless you do something clever when you engage the reverse gear you have to sit and wait for nothing to un-happen for five minutes until you see the UI get reversed!