Slash Boxes
NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

use Perl Log In

Log In

[ Create a new account ]

Ovid (2709)

  (email not shown publicly)
AOL IM: ovidperl (Add Buddy, Send Message)

Stuff with the Perl Foundation. A couple of patches in the Perl core. A few CPAN modules. That about sums it up.

Journal of Ovid (2709)

Friday June 05, 2009
07:02 AM

It's Time For Time In Computing

[ #39079 ]

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:


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.

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
More | Login | Reply
Loading... please wait.
  • 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 c

  • 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

  • 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.