Jorge, Raph,
Your messages both suggest that I don't quite understand constraints. I believe I understand constraints reasonably well. I'm not sure you understand what I'm getting at with thread bombs.
In traditional logic programming, a constraint is implemented by generate and test: give the variables values and then test those values against the constraint. If one has lots of constraints, any one of which may or may not apply at any time, that's difficult to do and may lead of searches that are cut off later rather than earlier. The goal is to cut off a search as soon as possible.
The thread bomb approach generates a thread that is triggered when any of the variables it is watching gets a value. This does not eliminate generate and test, but since in effect all constraints are tested all the time it does cut off the search immediately whenever any constraint is violated.
The argument for direct constraint programming is that it skips the generate step. But when one's domain is a simple set the work done to eliminate the generate step is essentially the same as the work done to test the value once it is generated. The two are equivalent.
Expressing constraints in separate threads essentially guarantees that the constraint are checked as early as possible, which is the same as removing elements from the domain for domains that are sets.
Constraints save more work when one can cut out a number of possible values in one step. To do that, one needs a domain in which the values can be reasoned about, i.e., the domain is not just a set but perhaps a domain like the integers with lots more structure. Also, and more significantly, one needs a whole new level of mechanism to talk about and reason about domains. Apparently Oz doesn't support Oz-level definition of range constraints. One must write such constraints in C++, which is not desirable.
What I have been attempting to explore is what one can do without writing C++ code. (I thought I said that in a previous message.)
Does that clarify the issue?
So as far as I can see, thread bombs are as good as constraints when one's domains are simple sets. The next thing I want to look into is how to reason about more complex domains at the Oz level.
Consider the following example.
Suppose you have two variables X1 and X2. You want them both to come from some list Xs. Suppose that you want X1 to appear earlier in Xs than X2. But suppose that the program is not generating X1 and X2 directly from that specification. X1 and X2 are generated through other means, but they must satisfy that constraint.
In traditional logic programming one has three choices.
1. Generate all possible valid values for X1 and X2 from the start and run them all. That's terribly wasteful.
2. Test the constraint everywhere in the program that X1 and X2 are both known to be instantiated. That's usually not feasible. It's also not good programming.
3. Test the constraint somewhere down the line. That's bad because it may waste a lot of intermediate work.
The thread bomb approach tests the constraint as soon as X1 and X2 are both instantiated. It's a clean and feasible implementation of option 2.
A real constraint system would declare the ranges of X1 and X2 to be constrained to Xs and then modify those range constraint declarations whenever either becomes instantiated. The question is: how can one do that in Oz? How can one express range constraints and modifications to those range constraints at the Oz level? I imagine it can be done. But it will take a bit of work.
It seems to me that one needs three things.
1. A way to keep track of variable range constraints.
2. A way to allow those range constraints to be modified. The constraint threads (propagators) would do that modification when they are triggered.
3. A version of search that runs search-based unification through the range constraints.
I.e., disallow the use of straight unify for search. As in Oz, an intelligent search might (allow the user to specify that one should) select the variable with the smallest remaining range for the next search step.
These three features are not all that complex. But they are clearly a level of mechanism that must be built if one is to have constraints on domains that have more structured than simple sets.
A question that comes to my mind (and that I asked a few messages ago but not as fully) is why aren't these features already available at the Oz level. Oz must have much of this mechanism already built. Why must one write C++ code to get at it?
-- Russ
_________________________________________________________________________________ mozart-users mailing list [email protected] http://www.mozart-oz.org/mailman/listinfo/mozart-users
