Constraint Satisfaction with Generic Functions

I think I’ve figured out how to solve a slightly different constraint satisfaction problem from the one I was working on Friday. I was thinking about GUI constraints, of the sort used in the Laszlo rich client platform. Laszlo uses constraints to implement lots of fancy operations with very little code. Basically, a Laszlo constraint is something like “my X position is equal to the mouse X position, if I’m currently being dragged”. So, constraints can be state-dependent.

With the current PyProtocols generic function implementation, it’s relatively easy to define a generic function to compute X given the current state. However, this doesn’t help in building a GUI because you don’t want to be continuously recomputing X all the time, only when something changes. In the dragging example, we want to recompute X only when the mouse position changes and the dragging state is active. (Or if some other state is active that causes X to change when the mouse position changes.)

What this means in practice is that we want there to be generic functions that get called when the mouse moves, keys get hit, and so on. And these generic functions would have rules like, “if the mouse X has changed and we are dragging an object of such-and-such type, then set that object’s X position to match.” In essence, we have taken a kind of “derivative” of the original rule, which stated “if dragging, object.X = mouse.X”.

Of course, that’s not all that has to happen. We also need a function that gets called whenever the drag state changes, so that we can set the initial X to match the mouse at that point in time. And there are other interesting complications, that I’ll get back to in a moment.

Anyway, it should be quite apparent that this is the basic complexity of event-driven programming. Your initial problem statement can be something quite simple like “while dragging, our X = mouse X”, but the actual implementation might require monitoring half a dozen events, each with its own idiosyncratic implementation requirements.

But what if we could handle this automatically? What if we had an object that could “read” and “understand” the constraint in its natural form, and automatically add cases to other generic functions or add callbacks to event sources for us? In the case of Laszlo, it has a specialized property system to handle this, and states have to be explicitly activated or deactivated, which greatly reduces the generality, because it means you still have to hook up events to change the states. If I understand correctly, you can’t just say something like “we’re dragging as long as the left mouse button is down and the cursor is over my drag handle”; instead, you still have to create event handlers to start and stop dragging.

Anyway, here’s my idea: suppose you had a generic function that took four parameters:

1. The criteria for selecting the objects to which this constraint applies
2. The conditions under which this particular constraint applies
3. The expression that the target attribute/method/etc. should be set to or passed
4. The target attribute/method/whatever to set/invoke

You could then add methods to it to actually perform the necessary subscriptions, by matching “meta criteria” against the arguments. For example, using parameters 1 and 2, you can set up event subscriptions to activate and deactivate the applicability of the constraint, and using parameters 3 and 4, you can figure out the event subscriptions that should be added or removed when the constraint is active, and what those event handlers should do.

For simplicity’s sake, let’s assume that whenever there’s a change to any expression tested by parameter 2, we should simply recompute the “activeness” of parameter 2 entirely. And, similarly, if any expression that’s part of parameter 3 changes, we just recompute the target expression and update the target. (We’ll assume that the target is responsible for not cascading needless events or doing expensive operations when there is no “real” change to it.)

Anyway, our hypothetical-four argument function – let’s call it “defConstraint” for the moment – can now set things up for us automatically, at least in principle. The implementation needs to be able to convert a given expression that’s part of parameter 2 or parameter 3, into an algorithm for subscribing to an event that indicates a change to that expression, given the criteria in parameter 1. Parameter 4 doesn’t really drive anything complex; for all practical purposes it’s probably just a callable that takes the target instance and the result of computing the constrained value.

This is where we get to the “interesting complications” part, which is that we don’t necessarily know what objects we’re hooking up to. There could be dozens of draggable objects, for example. At this point, we are ending up back in “forward-chaining rules” territory, wherein we need a kind of “working memory” in which we can store such information. For example, if our object selection criteria (parameter 1) specify “objects of type DraggableBox”, then we need some way to subscribe to the creation and disposal of objects of that type, in order to set up the second and third-level subscriptions. Interestingly, this also suggests that instead of a four-parameter constraint system, we might just have a system that allows N-level constraints, and can thus simplify the issue to just thinking about converting criteria into event monitors.

Of course, the next thing that occurs to me is that the structure I have in mind for such event monitors is almost exactly the same as… wait for it… a forward-chaining rule system’s Rete graph.

Sigh. So much for this idea simplifying things. The thing I dislike about Rete is that it’s data-driven, not object driven, which means that you have a sort of input-conversion step and an output-conversion step, which both add overhead and complexity. I’d prefer to make it so that the equivalent of a Rete network’s output nodes are simply direct event subscriptions that perform the needed behaviors, rather than stuff that feeds into a Rete “agenda” or “conflict set” to then be turned into something to invoke.

I think that maybe this is possible, though, it’s just going to take a little bit of thought to work out the details. For example, in Rete, there are “tuples” that represent partial matches of a rule. If we instead have “smart tuples” that manage event subscriptions to create dependent smart tuples or to directly enforce a constraint, and that keep links to their dependent tuples, then when such a tuple is deactivated, it can request its dependent tuples to deactivate themselves, and so on “all the way down”. This is roughly equivalent to how Rete “1/1” nodes work, except that here the nodes don’t exist as objects the way they do in a Rete network.

I think the model I’ve described so far can handle anything but rules that use cartesian products, so all the objects that participate in rules have to be reachable from some known starting point(s). This avoids the need for a true “working memory”, but we do have to know where the root “subscriber” is, so we don’t create more than one. Actually, though, it’s probably extensible to the full equivalent of a working memory, and even cartesian products. It just gets a little too complicated to think about all at once, at least for me. And, I’m finding it hard to think of a GUI constraint situation where you need cartesian products or re-orderable joins, even though it’s easy to think of domain-model situations where you need them.

I suppose, however, if you think of the simple model as a special case of cartesian products involving only one “table”, then things make a lot more sense. Hm. I think it’s all coming together now…

Okay, so there’s a WorkingMemory, which knows about FactTypes and Facts. It has methods to add, remove, and locate facts; these methods are generic functions, so you can extend them to do indexing, but also to do triggers. So, for example, if you have a fact type “Dragging(ob)” you could add a method to the “addFact” generic function that would set up the mouse event subscription whenever a “Dragging” fact was added, and remove it when the fact was withdrawn. In practice, I think some of these operations need a way to store state in the working memory, like the event handler that was subscribed when the fact was added.

For facts derived from more than one other fact, you could subscribe to the adding of any of the relevant facts, and then search for corresponding facts from the working memory, in order to then assert the corresponding derived fact.

Interesting. There are lots of ways to incrementally optimize this, too. For example, the add and remove functions can have methods added to update indexes, and the lookup function can have methods added to use those indexes when applicable. Further, the “defConstraint” function can have methods that either use dedicated fact types, or that automatically generate fact types for arbitrary expressions. One of the peculiarities of non-OO Rete variants is that they create nodes (fact types, effectively) for each filtering condition, but here we can avoid creating unnecessary fact types by tuning the mapping functions that convert constraint expressions to fact types.

At this point, the overall design is still horrendously complex to think about. But, I think that the “working memory” part is now simple enough to possibly prototype and play around with. It seems to me that I could actually just use tuples to represent facts, with the zero-th element of the tuple being an arbitrary hashable object indicating the type. The working memory would then consist of two dictionaries, where the first dictionary maps active facts to dictionaries containing working states (for fact monitors that need a state).

The second dictionary would map keys to sets of matching facts. Then, the methods would be things like add, remove, find, __contains__, and keysFor(), where the latter is a generic function that lists the keys a fact should be indexed under. (By default, they’d be indexed only under their type.) The add, remove, and find methods would all just call keysFor() to get the keys they should add, remove, or look in, so ‘find’ doesn’t really even need to be a generic function, only add and remove, and those only because they’ll be used to create dependent/derived facts.

Interestingly, this means you can easily create a nicely tunable forward-chaining rules engine using just three generic functions, as methods on a relatively simple class. Of course, the real complexity here is in defining the fact types and derivations. But, if this base part is implemented and well-understood, then it should be possible to prototype various approaches to generate the fact types and relationships automatically. I think I’ll go ahead and whip up a dispatch.factbase module sometime later this week, implementing a simple forward-chaining “working memory”. Then, I can experiment with some different ways to manually implement derivations, joins, and so forth, before trying to automate them.

The end result, though, should be a kind of “nervous system” to which you can link inputs and outputs. The inputs operate by event handlers calling “addFact” or “removeFact”, and the outputs operate by methods on addFact and removeFact invoking operations on the “real” system whose “nervous system” the fact base is. Of course, some of those outputs will actually just directly subscribe an input event to a necessary action, so that events needing low latency (like mouse dragging) don’t have to pass through the “nervous system”. Instead, only events that change the current mode or “wiring” should pass through the fact base.

Another interesting thought is that a fact base need not be restricted to an in-memory implementation. In principle, a database can also be a fact base, with fact type indicating a table, and the other items in the fact tuple representing columns. Indeed, given the nature of the implementation of the basic fact base using generic functions, you could in theory represent some fact types in memory, and others in one or more databases, according to your whims. I think this will actually need me to distinguish in some sense between an “addFact” command and a “factAdded” event, since the latter may need to trigger lots of things, but the former needs to manage storage issues like indexing and checking whether the fact is already present. This is true even in the simple, in-memory case, except that “addFact” doesn’t need to be a generic function in the memory-only implementation. But a more sophisticated fact base could override addFact and replace it with a generic function too.

What’s rather exciting about “mixed-mode” fact bases is the potential to use them for various kinds of real-time business analysis including trend detection and “exception reporting” (where the system “notices” that some value has moved outside its “normal” range). These concepts are also useful for system administration tools that need to project the rate of disk space consumption, or notice load spikes that suggest problems.

On the implementation side, it’s important to note that rules responding to add/remove operations can be defined in different subclasses of FactBase, and then merged using multiple inheritance. (This is a useful property of how PyProtocols’ generic functions work.) So, you can have one set of classes that define the “reasoning”, and another set of classes that define the storage, then mix them into a concrete implementation.

Wow. Too bad I don’t have time to work on this right now, or I’d be doctest-ing away already. This mechanism will become an important complement to generic functions, as it will form a basis for implementing complete rule-driven programming systems.