Wednesday, May 21, 2003

The Lie of Time

Returning to our theme of the mirrors of illusion that make programming suffering.

Another limitation of the Turing Machine is that it has a linear view of time. One step at a time, it crunches through the computation, reading, writing, moving the tape, and then (maybe) halting. Even non-deterministic Turing Machines only move through time in one direction. We only move through time in one direction too, so it's not unreasonable, but it's unimaginative.

There is an exception, which I mentioned a week or so ago. Undo. A tiny way for you to roll back your last operation, removing the effects of whatever dumb thing you did. Sometimes, you can keep undoing, sliding backwards in time, destroying your actions. (Commercial databases often have a much more sophisticated idea of rollback.)

But even Undo is linear, and the fact that it destroys your actions when you do something new is frustrating and limiting. Why can't we reach into an arbitrary point in the execution of a program, change an assumption or an action, and then stand back and see what would have happened? David Patterson at Berkeley applies something like this in search of reliable computing; he calls it "Rewind, Repair, Replay."

That's a step forward (backward?) but it's still a fundamentally linear view of time. Let's expand our minds just a little bit more. What if many simultaneous executions were happening at once? Each possible decision, resolution of ambiguity, or branch represents a fork into two possible futures. Why not do them all? Another ten doublings of Moore's Law will give us a thousand-fold improvement in performance; certainly we can spare a hundred-fold just to run multiple versions.

Mix that in with undo/redo, and you've got something like four-dimensional programming: moving back and forth through time, hopping from potential universe to potential universe, intervening, responding, and changing the assumptions at the beginning of time. Alfonso X said "If I was present at the creation, I would have given some useful hints for the better ordering of the universe." Programmers make mistakes; why shouldn't they have the capability that Alfonso wished for?