Friday, December 24, 2004

Generic Functions == Backward Chaining, Constraint Maintenance = Forward Chaining

I've been thinking a lot lately about the design of a constraint management system for peak.schema. Among other things, I want the system to be able to check constraints immediately, at transaction commit time, or upon request. Further, it should be able to distinguish between warnings and errors, and it should be possible to iterate over all the errors for a given input, so that batch-oriented (e.g. web) forms can display more useful feedback. Also, it should be possible to trigger notifications or other actions to be taken, based on failure to meet some constraint.

It just occurred to me that this is precisely the same thing as a forward-chaining rule system. I mean, it's exactly the same thing. D'oh! This also helps explain why my attempts to make generic functions handle everything were having limited success, as generic functions are a backward-chaining rule system.

The difference is that in a backward-chaining system, you ask the system a question about something, and it consults the rules and the current state of things, and says, "here's the answer". In a forward-chaining system, you just tell the system lots of things, and it tells you things it "notices".

Of course, there is a certain overlap area between the two, in that if you can cram all the relevant data into the arguments of a generic function, then you can effectively ask the question, "what's interesting about this?", and get the same answers you would from the forward-chaining system.

So, for many kinds of constraint validation, you could get by with predicate-dispatched generic functions. Really, almost any constraint that only deals with a single object could be handled nicely. But in real business systems, often the really interesting constraints cross over between lots of objects, or depend on the changes that have been made, rather than the current state of an object. That's where forward-chaining systems can be a bit handier: when you make a change, you could just dump in the old value and the new value as "raw facts", and let the system draw the conclusions for you. If a value changes more than once, withdraw the current-value fact and replace it with a new one.

Anyway, the point of this post was just that it occurred to me that what I'm actually trying to make is effectively a forward-chaining rule system. This recognition is good because now I can either 1) review the literature and open source rule engines for ideas to steal, or 2) figure out what parts of the ideal design I should discard in order to implement something simpler. :)

Update: Hot diggity! A little bit of research on the Rete algorithm, and I noticed something interesting. The so-called "1/1" nodes of a Rete graph don't do anything that a generic function can't do; i.e. select targets for a match of an argument tuple. It's the "2/1" nodes of a Rete graph that do the bit that generic functions don't. However, if you represent those nodes as collections of currently-matching tuples, then you can include join conditions in the predicates so as to select an action that triggers the corresponding join rule. Thus, the mapping to a forward chaining system consists simply (okay, so it's not that simple) of having a generic function per fact type, with storage locations corresponding to the "1/1" Rete nodes. I'm not sure if it makes sense to bother with "2/1" nodes or just conduct all joins in an N-way fashion. I'll have to think about it some more. But it looks like I could definitely reuse generic functions for most of the logic.