Lambda the Ultimate has an interesting post about the passage of time in computing systems. It's not talking about real-time systems. Rather, it deals with a fundamental limitation of most computing systems in that they deal with data transformations and not physical processes. This means that any data transformation can be problematic in a concurrent model when one process changes something that other processes are not expecting. Consider Prolog:
assert(male(frank)).
That adds the fact "frank is a male" to the database. Unfortunately, this is a destructive operation and survives backtracking (note that this state alteration doesn't require concurrency to be problematic). When this occurs, the programmer must be very careful to manually undo all changes upon failure. For large code bases, this is hard. Thus, asserting and retracting to/from the database should be used sparingly. The generally assumed solution is to create lists which maintain state and manipulate those lists since those manipulations are undone on backtracking. Unfortunately, when I read about this, programmers generally agree that this is painful.
That's interesting, though, because "state" is correlated with "time". At any given point in time, the state of a system is the state of the system. It doesn't change because change requires time. The solution, then, seems to be incorporating time into a system to ensure that for any given operation, the time is known. You could assert at will into the database and the assertions would be marked by time. Upon backtracking, the previous "time" of the system is restored and further unification would ignore facts and rules with a future time.
Still, I don't think that quite solves the problem if you assert a fact and your query fails, you probably want to retract that fact. There's a nifty blog post which describes a trivial way to get the correct behavior with standard Prolog. That's nifty and I'm tempted to make this the default behavior in AI::Logic. Since it's being built from the ground up and is not yet released, I'm free to do this. This solves the backtracking problem, but not the concurrency one. If you assert something and something else picks it up, whoops! I wish I could figure out time. I was thinking about "ticks" to artificially track time, but frankly, I doubt I'm smart or experienced enough to really figure this out.
Still, I don't think that quite solves the problem if you assert a fact and your query fails, you probably want to retract that fact.
This feels to me like you want an 'alternative futures' model of time: that is, when you backtrack, you not only go back to a previous 'time' but also arrange things so that when you go 'forward' again you are moving forward on a different timeline that diverges from the first at the point the backtrack went back to. If you change something and don't backtrack, subsequent computations stay on the same timeline so they keep any changes that were made.
Of course, this means that you end up storing every state that has been present in every hypothetical timeline your program has visited, which may be a problem. If there's no way to retrieve values from 'other' timelines, you could garbage-collect them at the point they become inaccessible.
Re:Alternative futures?
Ovid on 2009-06-05T14:26:34
I've no intention of simulating the many-worlds hypothesis in Prolog, thank you
;) I'll leave that to Damian.
Re:Alternative futures?
Aristotle on 2009-06-07T03:02:14
If git can do it so can you.
have been wrestling with these sort of concurrency issues for decades now (and of course you can view the DB as a set of assertions). With something like mvcc you're not even dealing with a single timeline any more.
There's been a recent discussion on the pgsql-hackers list wrt some issues of implementing true serializable transactions that might feed in to what you're interested in.
And of course, if you find a simple, efficient, easily understandable implementation then don't forget us little people once you get your Nobel
I was going to post some useful references coz I spent a large chunk of time with my undergraduate project implementing a temporal reasoning system based around a constraint propagation mechanism, intending it to form the backbone of a multi-agent planner.
Then I realised that was eighteen years ago and I cannot remember anything about the bugger - beyond the fact that it was annoyingly NP-complete and ran far too slowly to do anything useful.
Sorry!
