Slashdot Mirror
Hindsight: Reversible Computing
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.
They say the way they accomplish this is running the program in some sort of sandbox and taking checkpoints every so often and then when you step back, it actually runs forward from the closest checkpoint and stops one instruction short.
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.
I've had enough abrasive sigs. Kittens are cute and fuzzy.
It's all very well to be able to run code backwards/forwards/slo-mo/etc, but how to handle non deterministic external events coming in from the network? Does this tool presume that all applications to which it will be applied live in isolation?
Rich people are eccentric. Poor people are strange. Me, I'd be happy with odd.
I read this usenet post every now and then when I'm trying to fix something, and it makes me want to cry every time I do.
Mike Hoye
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...
ReVirt:
Belief is the currency of delusion.
In this paper, he proposes the Elephant language that can refer to the past in computer programs.
Pretty cool stuff!
I remember that several of the older compilers like Borland's Turbo Pascal, Turbo C and Microsoft C and MASM could run reverse execution through the debugger. They also had the "animate" feature that let you step through the code automatically, but slowly so you could watch each line of code as it was executed. I remember setting my PC up with two video cards: a monochrome Hercules card and an EGA card. A lot of the compilers from those days supported mutiple graphics card output - the code would appear on the monochrome monitor and the running executable would appear on the color monitor.
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.
The only way to "back up" execution is to save your state as you go.
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.
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.
Damn, I already moderated this topic. Now I'll have to log in with my sock puppet to comment.