[gecode-users] ND constructs in scripts

[Guido Tack]

Hi!

> One thing that I'm not sure about is non-deterministic programming
> constructs in scripts, like Oz's "choice". I see that C++ is not going
> to help here in terms of concurrency/blocking/etc. like Oz does, so I
> think that the expressive power of scripts in Gecode is probably weaker
> than in Mozart (am I right? no offence! :-)).

That's right, you cannot use Gecode as a general abstraction for
non-deterministic programming.

> To be more specific, from
> what I understand, such thing as "choice" could be done by cutting the
> script at the points of nondeterministic statements, putting the
> deterministic parts' bodies in the appropriate functions of some
> branchings... (posting a new branching should be done in commit(),
> right?). Is this correct?

I'm not sure we use the same terminology here ;-)  A branching is
something that is "installed" in a space, like a propagator, and which
will be queried after propagation has finished to a) determine how many
branches the space has and b) commit the space to one of these branches.

Just as with propagators, you can write your own Gecode branchings by
inheriting from the Branching class and implementing the necessary
interface.  As all branches will be explored during search, this is a way
of implementing non-determinism.

> So my question for now is - do you have a suggestion on how
> non-deterministic constructs could be done in scripts, if this can be
> done at all?

It really depends on what kind of non-determinism you want to implement. 
We use branchings only for search in the context of finite domain
constraint problems.  So if the non-determinism you have in mind is used
to split a constraint problem into two or more simpler problems, this is
the way to go.  I'm however not sure the abstractions we provide are the
best choice for other kinds of non-determinism.

Cheers,
   Guido

-- 
Guido Tack
http://www.ps.uni-sb.de/~tack