Hi Christian,
I'm so happy to get your comments. But ... (see below).
On 10/26/05, Christian Schulte <[EMAIL PROTECTED]
> wrote:
Dear all,
I have been following this discussion with quite some interest, however I
was unably to throw in something. Here it comes.
The first point I would like to re-iterate on (Grégoire and Raphaël already
went there) is the tremedous difference between the essence of constraint
programming and generate and test. The very idea of constraint programming
is to open up variables so that they can specify what are values which still
can participate in a solution. By this, one describes (partially) a set of
solutions to the problem. With generate and test, one only describes a
single partial assignment. Why this matters: the inference you can do in
principle for generate and test is to find out that the current partial
assignment can not be extended to a solution. And if one finds out the only
thing is to backtrack! Now for constraint programming, inference (constraint
propagation, that is) can remove some assignments (as described by the
projections onto the involved variables) without being forced to backtrack.
The difference is typically at least exponential.
I don't see how you get any kind of improvement if the domains are simple sets of values with no structured relationships among the elements, i.e., no 'less-than' or other relationships other than equality. (One might get a constant speed-up in that it may be faster to remove an element from a domain than to generate a computation that uses that element and then kill it immediately.)
The other point I'd like to make is to discourage Russ to implement
propagators in Oz. Yes, one can do it. And yes, one can dig a hole with a
spoon. However, pick your tool well! Evidence has it that you are way better
of to implement a constraint as a propagator in C++ than in Oz. This is
partially due to efficiency concerns (these guys need to be really really
fast). But alos, as it comes to numerical and graph algorithms, C++ is just
the better pick. Of course, I am somehow biased as I abandoned Oz in favour
of my new pet: Gecode, a constraint programming environment entirely
developed in C++ (check www.gecode.org, we are going to release on Nov
24th).
I understand the desire for speed. But my preference is for beauty first. I'll admit that I don't solve real problems; I just like to think about elegant mechanisms that let other people solve them.
If Gecode is as it appears to be a C++ library, I regret to say that I probably won't spend the time to find out about it. There are lots of powerful libraries out there that I don't know about. I'll admit as well to another prejudice. I don't like C++. I much prefer Java. I know that at least half the programming world disagrees with me (and I don't want to start a C++ vs. Java discussion here), but probably at least 99% of the programming world has never even heard of either logic programming or constraint programming.
What attracted me to Oz in the first place and what has kept me interested in it is the possibility of exploring programming language paradigms in an integrated framework.
I know that this is not the same thing as wanting a light-speed constraint solver. I guess we each have our own priorities--and mine are not necessarily universally shared :-(
-- Russ
_________________________________________________________________________________ mozart-users mailing list [email protected] http://www.mozart-oz.org/mailman/listinfo/mozart-users
