[gecode-users] Constraint store

[Mauricio Toro]

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_1UnaryWait.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>:

> 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>> 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/
>>
>>         Cheers
>>         Christian
>>
>>         --
>>         Christian Schulte, Professor of Computer Science, KTH,
>>         www.ict.kth.se/~cschulte/ <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>] On Behalf
>>         Of Pierre Talbot
>>         Sent: Tuesday, April 29, 2014 3:49 PM
>>         To: 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>
>>
>>         https://www.gecode.org/mailman/listinfo/gecode-users
>>
>>
>>
>>     _______________________________________________
>>     Gecode users mailing list
>>     users at gecode.org <mailto:users at gecode.org>
>>
>>     https://www.gecode.org/mailman/listinfo/gecode-users
>>
>>
>>
>>
>> --
>> Gustavo Gutierrez
>>
>
>
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
>



-- 
Mauricio
http://www.cs.ucy.ac.cy/~mtoro/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20140429/0368acfb/attachment-0001.html>