I take it that you intend to be controversial here ;-) Let me just take the first point again: the differnce is exponetial at least. Please reread my email (or indulge in some other writing on constraint programming). The point is really to prune without exponential backtracks. But actually this is not a matter of taste, it is just a matter of fact.
As it comes to the second point you are absolutely right. You want to have beauty, I want to have impact. Beauty is of course in the eye of the beholder. But there is no guarantee that beauty is relevant (not to mention that it is debatable that C++ defines ugliness). What I really want to stress (apart from the nasty stuff I said before): programming languages are not universal. They do serve a purpose. As it so happens, what you have to do to get a good propagator off the ground fits the C++ bill so much better than the Oz bill. Christian -----Original Message----- From: Russ Abbott [mailto:[EMAIL PROTECTED] Sent: Wednesday, October 26, 2005 10:06 PM To: [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] Subject: Re: Implementing constraints 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
