a silly question about concurrent propagators

[Aurélien Campéas]

On Sat, Feb 24, 2007 at 10:58:10AM +0100, Raphael Collet wrote:
> Aurélien Campéas wrote:
> >While we are doing some 'final touches' (read : last-minute debugging
> >of vital functionality) to a dumbed-down (non-nestable) version of the
> >computation space concept for inclusion in PyPy (see the pypy project
> >at : http://codespeak.net/pypy/) I also have to polish the technical
> >report that explains what we did, and why, and I have a hard time
> >remembering the rationale behind constraint propagators running in
> >their own threads. (I'am quite sure I asked Raphael at some point but
> >I didn't record reliably his answer, whatever it was)
> 
> I remember we discussed a lot about this design issue, but I do not 
> remember whether we reached a definitive answer to the question...  

I think we didn't :)

> Here are a few elements that may help.
> 
> If you're interested in "pure" constraint programming, then you don't 
> need threads.  All you need is something (read: an object) that executes 
> the propagators until they reach a fixpoint.  In Gecode, this task is 
> done by the object that implements the computation space.

Right.

> 
> Now, if you want to run preemptive (Python) code inside a space, it's a 
> different story.  You need something like that if you want to use spaces 
> for logic programming.  The logic program inside the space should stop 
> when a nondeterministic choice has to be made, and let the search engine 
> (outside the space) decide what to do.  

That is the ask/choose/commit protocol, which indeed ensures proper
synchronized communication between the distributor thread of the space
(the only thread that should be allowed to 'choose' if I understood it
well) and the 'outer space' search engine (running in another thread
of course).

I believe this still doesn't tell me why I should make my propagators
concurrent ... (at this point, I can always ensure that full revision
of domains happen in a traditional fashion between calls to choose in
the distributor thread).

> Or the logic program could be encoded as a data structure that is
> fed to a solver, possibly written in Python (and single-threaded).
> 
> If you want to use logic variables for dataflow synchronization (inside 
> computation spaces or in the main program), then you need explicit 
> threads, IMO.  Being able to run arbitrary Oz code inside spaces is what 
> led the designers of Oz to this general concept of computation spaces.
> 
> 
> Don't hesitate to ask for more if it's not enough ;-)

My vision of an oz-ish constraint script is quite restricted to what
is to be found in CTM (... I hope, at least that I didn't miss some
important bits) : a definition of a problem (written in Pyhton in my
case) which terminates by the invocation of a distributor doing the
main grunt work of the search, driven by a 'search script'.

Maybe I need to hear more about 'impure' constraint programming ;-)

Regards,
Aurélien.