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. 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). Christian -----Original Message----- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Russ Abbott Sent: Wednesday, October 26, 2005 7:43 PM To: Raphael Collet Cc: [EMAIL PROTECTED] Subject: Re: Implementing constraints On 10/26/05, Raphael Collet <[EMAIL PROTECTED]> wrote: Russ Abbott wrote: >> 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. Here is how to code that constraint in Oz if Xs is a list of integers: No dispute. If you can code stuff as integers and use FD, you get more leverage. > 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? There are two answers to that question. First, quite a few combinatorial problems can be easily "coded" with integers or integer sets. Second, noone has had the time to implement it yet :-( That was my question. Thanks for the answer. I would think that since the underlying mechanisms already exist, making them visible at the Oz level wouldn't take that much work--not that I'm volunteering to do it. Since Oz prides itself as being a platform for exploring issues in programming language design (and not just a language for writing FD constraint programs), exposing the mechanisms that make it possible to reason about range constraints in general would further that vision. I would urge that this be elevated to a higher priority. -- Russ _________________________________________________________________________________ mozart-users mailing list [email protected] http://www.mozart-oz.org/mailman/listinfo/mozart-users
