[gecode-users] Constraint store
Christian Schulte
cschulte at kth.se
Wed Apr 30 10:56:11 CEST 2014
Please, let's not discuss Oz here. There are better places. Thanks Christian
--
Christian Schulte, Professor of Computer Science, KTH,
www.ict.kth.se/~cschulte/
-----Original Message-----
From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Max Ostrowski
Sent: Wednesday, April 30, 2014 10:53 AM
To: gecode list
Subject: Re: [gecode-users] Constraint store
Hi everybody,
i actually did something similar using Gecode, using it as a theory solver
for an SMT system.
The approach is the same as from Mauricio, except that my ask method is
allowed to return Maybe, and postpone the request. (if propagation is strong
enough to tell me if the constraint is entailed, this is fine, otherwise i
need to do more tell operations)
I just tried to read the Dissertation of Christian (at least the part from
Chapter 2 - 4) to try to figure out why Oz would be more suitable for this.
I think the tell operation is clear and simple for both systems, adding a
constraint.
For the "ask" task, in Oz you could use the equality test or the domain
Reflection ? Is this right?
What is the difference of Gecode and Oz in the behavior.
Both seem to use some kind of reification.
Can Oz answer the "ask" task without doing search?
Best,
Max
On 04/30/2014 01:10 AM, Mauricio Toro wrote:
> Hi Pierre,
>
> I implemented long time ago an interpreter for ntcc using Gecode. Here
> is the implementation http://ntccrt.sourceforge.net/ and this is a
> conference article about the implementation and some applications
> http://www.cs.ucy.ac.cy/~mtoro/traa09.pdf
>
> I agree with Christian that Oz is more appropriate to implement ntcc,
> but, although it has some limitations, using Gecode proved to be more
efficient.
> I also agree with Gustavo that Christian's dissertation is crucial.
>
> My approach was the following:
>
> tell(c) : I add 'c' to the Space
> ask (c) do P: I add 'c <--> b', a reified constraint for the
> constraint 'c'. I also add a propagator 'wait (b) do P'.
>
> http://www.gecode.org/doc-latest/reference/classGecode_1_1Kernel_1_1Un
> aryWait.html
>
> That approach make the execution of ntcc very efficient, but it some
> disadvantages, one of them is that the 'ask' is limited by the
> constraints you can deduce using propagation and it is, therefore, not
> complete. Another disadvantage is that it limits the constraints in
> the guard of ask to those that can be reified.
>
> Cheers,
> Mauricio
>
>
> 2014-04-29 14:50 GMT-05:00 Pierre Talbot <ptalbot at hyc.io
> <mailto:ptalbot at hyc.io>>:
>
> Hi,
>
> Thanks to both of you, I'll carefully read this dissertation.
>
> Regards,
> Pierre
>
>
> On 04/29/2014 09:33 PM, Gustavo Gutierrez wrote:
>
> Hi Pierre,
>
> Oz does use the store concept, that is for sure :). You can have
> a look at Christian's dissertation "Programming constraint
> Services". Start by chapter 2 and you will find the terminology
> you seem to be looking for.
>
> Regards,
> Gustavo
>
>
> On Tue, Apr 29, 2014 at 9:44 AM, Pierre Talbot <ptalbot at hyc.io
> <mailto:ptalbot at hyc.io> <mailto:ptalbot at hyc.io
> <mailto:ptalbot at hyc.io>>> wrote:
>
> I'm very new to constraint programming and Oz but I read that
> there are plans to use Gecode in Mozart. On the other hand, I
> don't think Oz is using the store concept, correct me if I'm
> wrong. Anyways, thanks for the infos, I'll definitely look
> into Oz
> and AKL.
>
> Do you think it's feasible to use Gecode to avoid
reimplementing
> the basis of a constraint system? Or is Gecode have little
> chances
> to help us?
>
> Regards,
> Pierre Talbot
>
> Le 29/04/2014 15:54, Christian Schulte a écrit :
>
> Hi,
>
> Gecode is a terrible choice for a cc-inspired language.
> Please
> go back to
> predecessors of Gecode such as Oz and AKL, there you
> will find
> how you can
> implement ask and tell efficiently. A (somewhat dated
> starting
> point) is:
> http://mozart.github.io/__publications/
> <http://mozart.github.io/publications/>
>
> Cheers
> Christian
>
> --
> Christian Schulte, Professor of Computer Science, KTH,
> www.ict.kth.se/~cschulte/
> <http://www.ict.kth.se/~cschulte/>
> <http://www.ict.kth.se/%__7Ecschulte/
> <http://www.ict.kth.se/%7Ecschulte/>>
>
>
>
> -----Original Message-----
> From: users-bounces at gecode.org
> <mailto:users-bounces at gecode.org>
> <mailto:users-bounces at gecode.__org
> <mailto:users-bounces at gecode.org>>
> [mailto:users-bounces at gecode.__org
> <mailto:users-bounces at gecode.org>
> <mailto:users-bounces at gecode.__org
> <mailto:users-bounces at gecode.org>>] On Behalf
> Of Pierre Talbot
> Sent: Tuesday, April 29, 2014 3:49 PM
> To: users at gecode.org <mailto:users at gecode.org>
> <mailto:users at gecode.org <mailto:users at gecode.org>>
> Subject: [gecode-users] Constraint store
>
> Hi,
>
> I develop a compiler for a formal concurrent language
called
> 'ntcc'.
> This language introduces a constraint store that we can
> manipulate with two
> operations:
>
> * Ask(c): ask the store d if c is entailed by d.
> * Tell(c): Entail the constraint c in the store.
>
> I'd like to use Gecode to implement it but I didn't find
> anything related to
> the notion of store. A technique, probably inefficient,
> would
> be to copy the
> store each time we want to ask something, add the
constraint
> in and search
> for the first solution (if it exists). Also, we are not
> interested by the
> solution but only by the existence of a solution.
>
> If you have any leads on previous works or
> implementations of
> such a store
> using (or implemented in) Gecode, I'd be grateful.
>
> Regards,
> Pierre Talbot (IRCAM)
>
> _________________________________________________
> Gecode users mailing list
> users at gecode.org <mailto:users at gecode.org>
> <mailto:users at gecode.org <mailto:users at gecode.org>>
>
> https://www.gecode.org/__mailman/listinfo/gecode-users
> <https://www.gecode.org/mailman/listinfo/gecode-users>
>
>
>
> _________________________________________________
> Gecode users mailing list
> users at gecode.org <mailto:users at gecode.org>
> <mailto:users at gecode.org <mailto:users at gecode.org>>
>
> https://www.gecode.org/__mailman/listinfo/gecode-users
> <https://www.gecode.org/mailman/listinfo/gecode-users>
>
>
>
>
> --
> Gustavo Gutierrez
>
>
>
> _________________________________________________
> Gecode users mailing list
> users at gecode.org <mailto:users at gecode.org>
> https://www.gecode.org/__mailman/listinfo/gecode-users
> <https://www.gecode.org/mailman/listinfo/gecode-users>
>
>
>
>
> --
> Mauricio
> http://www.cs.ucy.ac.cy/~mtoro/
>
>
>
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
>
_______________________________________________
Gecode users mailing list
users at gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users
More information about the users
mailing list