CLP(FD): what is necessary?

Wit Jakuczun wrote:
>    Good environment for developing software that
> is based on clp should provide its users with clean
> and robust interface. By clean I mean mainly
> clear syntax. Delay clauses
> (http://eclipse.crosscoreop.com/doc/...umsroot111.html)
> are good approach. In ECLiPSe there is also another
> mechanism based on suspensions (Internally both
> approaches are equivalent).

Yes, delay-clauses were invented first, but are now just
declarative syntactic sugar for the suspend/3 primitive:

delay p(X) if var(X).
p(X) :- writeln(just_instantiated(X)).

is implemented (via clause expansion) as

p(X) :- var(X), !, suspend(p(X), 0, X->inst).
p(X) :- writeln(just_instantiated(X)).

Delay clauses are nice for some simple cases, but not
general enough for most constraint applications.


>  The problem with
> ECLiPSe is that it each suspension can have a
> priority. This makes implementing constraints
> really painful and makes ECLiPSe not robust.

Hmm, priorities were introduced to _address_ problems with
constraint implementation, not to create them :-)

Having propagators wake up with different priority can be
quite important, so i think it is an important feature for
a constraint system.  Probably it is more relevant for a
system like ECLiPSe that aims at combining different solution
methods, than for a system that just wants to do FD.

I am not sure what you mean by "not robust" - do you refer to
the fact that higher priority propagators can interrupt lower
priority ones?  I guess this can be confusing when implementing
a low priority propagator, but you can always create "atomic regions"
by wrapping them in call_priority/2.

A real problem of priorities is however that they are hard to
implement without slowing down the whole waking mechanism.


-- Joachim

On 2008-03-13, Wit Jakuczun <wit@mefisto.hades> wrote:
> Dnia Thu, 13 Mar 2008 11:18:40 -0500 
> I support this suggestion! I wanted to talk about technical
> issues. Nothing more...

Ok.  Wit raised both a technical and an organizational issue.  I'm not
skilled enough in the details of CLP ...  The only remark I have is that,
especially in open projects, it is vital to define robust interfaces if
you want community contributions.

Cheers --- Jan

On Thu, 13 Mar 2008 13:50:47 +0000, Ulrich Neumerkel wrote:

> The achievements of Markus Triska's clpfd implementation in SWI
> so far have been to provide the basic constraints in a clean
> and robust fashion with highlights as:
>
> * Correctness: Similar to SICStus Prolog open domains are possible
>   thus extending CLP(FD) towards CLP(Z).

While I appreciate what you meant to write, I disagree with naming
this "correctness" - didn't I send a bug report to Markus recently
that pointed out something not quite correct in the SWI clpfd package,
and that was not caught by any of your testing ? It was unrelated to
the FD versus Z issue.
Please do not name something correct if it isn't [no blame is intended
towards Markus].


>   Note that other systems implicitly constrain all variables to
>   a small finite range. Failure in such systems means: No solution
>   within those limits. If a solution exists outside, you will not
>   find it.

That's fine as long as the user is aware of it, and as long as the system
makes an effort making her aware of it. Nobody expects 1 << 34 to give the
correct answer in C, and everybody knows that to get the correct answer,
there is price to pay, and a particular library to use.


> * Favourable termination properties: All predicates and
>   constraints in SWI's library(clpfd) terminate.

I would only name this favourable, if you have a proof that some
predicates or constraints in X's library(clpfd) don't - for any other X.


> Just defer is/2 and its archaic company to a more advanced level.

is/2 is certainly archaic, but also very useful. For me, the only archaic
thing about is/2 that really should be dumped, is the evaluation of source
level variables. Having eager arithmetic in a language is excellent.

Cheers

Bart Demoen

On Thu, 13 Mar 2008 16:23:17 GMT, ulrich@mips.complang.tuwien.ac.at
(Ulrich Neumerkel) wrote:

>A.L. <alewando@zanoza.com> writes: 
> 
>
>Monotonicity and similar properties to guarantee that your
>extention is a constraint at all.  It is a night mare to
>locate such bugs.  I cannot imagine that you never ran into
>those.  Just think of unifications that instantanously assign
>values to several variables, like (A-B=1-2).
>

Actually, no... I believe that it is enough to read manual carefully.
I have about 20 custom constraints... Of course, usual bugs happen...

>Guaranteed termination would be a bonus.

Agree, but can live without this...

A.L.

On Thu, 13 Mar 2008 20:38:21 +0100, bart demoen <bmd@cs.kuleuven.be>
wrote:

>On
>
>is/2 is certainly archaic, but also very useful. For me, the only archaic
>thing about is/2 that really should be dumped, is the evaluation of source
>level variables. Having eager arithmetic in a language is excellent.
>

Don't quite understand. Could you be more specific?...

A.L.

On Thu, 13 Mar 2008 15:15:54 -0500, A.L wrote:

> On Thu, 13 Mar 2008 20:38:21 +0100, bart demoen <bmd@cs.kuleuven.be>
> wrote:
> 
>
> Don't quite understand. Could you be more specific?...

Sorry to be so dense.
I meant:

?- X = 1+2, Y is X*3.
should give an error
instead of 9.

Source level variables to the right of is/2 (or in < =:= ...)
should be numbers, and not be evaluated.

Prolog could also have the ability to evaluate source level variables,
but it should be a separate built-in - and if Prolog would have only one
predicate, it should be the one that does not evaluate source level vars.

Hope I was more clear this time.

Cheers

Bart Demoen

bart demoen wrote:
>
> Sorry to be so dense.
> I meant:
>
> 	?- X = 1+2, Y is X*3.
> should give an error
> instead of 9.
>
> Source level variables to the right of is/2 (or in < =:= ...)
> should be numbers, and not be evaluated.

That's what ECLiPSe does, though it hasn't been popular and I
had to defend that decision many times...

>
> Prolog could also have the ability to evaluate source level variables,
> but it should be a separate built-in - and if Prolog would have only one
> predicate, it should be the one that does not evaluate source level vars.

You can do it simply with a function, in ECLiPSe called eval/1
(implemented by predicate eval/2):

?- X = 1+2, Y is eval(X)*3.

This is type-clean and makes the intention clear.


-- Joachim

A.L. wrote:
> On Thu, 13 Mar 2008 17:50:54 +0000, Joachim Schimpf
> <jschimpf@cisco.com> wrote:
> 
>
> OK, I am bot familiar with current version of ECLIPSE... Are
> priorities defined for each constraint separately, or across teh
> system?

It's a simple scheme of a small number (12) of priorities
across the system.


> And what happens if I am using 2 custom constraints, each with
> its own priorities numbered from 1 to 5?...

We've had endless discussions about an improved priority scheme
within the ECLiPSe team and with users, but never arrived at a
satisfactory proposal.  We considered float-priorities, partially
ordered ones, priority vectors, you name it...
There is some risk of trying to do things via priorities that are
better done via data-driven dependencies or localised computations.

The current, simple system allows you to assign priorities roughly
according to propagator complexity or effectiveness, to give debugging
and visualisation goals high priority, and a few other tricks.
A principle is that priority choice should not affect correctness,
only efficiency.


-- Joachim

Wit Jakuczun wrote:
...
> - It is not clear if there is any policy for
>   priorities. It would be much better to have
>   priorities defined like this:
>
> Debugging:
>
>   suspend(
> 	   Goal,
>            debug,
>            Conditions
>          )
>
> CLP(FD):
>    suspend(
>             Goal,
>             fd,
>             Conditions
>           )
>
> and so on
>
> Of course internally this could be solved
> using priority system you have. But such
> interface could help users to create
> constraints with consistent priorities.

That's a good suggestion, thanks.


>
> For example, I do not understand why
> priorities for global constraints
> form (ic_global) are different then
> for other constraints (ic)?

The main point is that you want to execute "cheaper" propagators
before more expensive ones, e.g. constant time ones like X #= Y+3,
before linear ones like LongLinearExpression #> 0, before quadratic
or cubic time ones like some of the global constraints. Some of
your propagators may run a whole simplex algorithm for example.
Of course this is only a heuristic, the system of propagators
still needs to compute a fixpoint, and that should be the same
regardless of priorities.


... 
> I know ;) (I used it). But still it is not something that
> makes is easier.

One idea I had to make this simpler was to separate waking-priority
from run-priority.  Run-priority would by default be very high, so
that propagators are atomic by default, independent of the priority
with which they are woken.


> 
> What was the main reason for introducing priorities?
> Neither SWI, nor SICStus or B-Prolog have
> priorities. You just declare constraint and off you go ;).

Hopefully answered above.  You will also see that the new G12
constraint platform being developed in Melbourne has opted for
having priorities.


-- Joachim

Dnia Fri, 14 Mar 2008 11:33:59 +0000
Joachim Schimpf <jschimpf@cisco.com> napisa=C5=82(a):
 
>=20
> The main point is that you want to execute "cheaper" propagators
> before more expensive ones, e.g. constant time ones like X #=3D Y+3,
> before linear ones like LongLinearExpression #> 0, before quadratic
> or cubic time ones like some of the global constraints. Some of
> your propagators may run a whole simplex algorithm for example.
I understand.

> Of course this is only a heuristic, the system of propagators
> still needs to compute a fixpoint, and that should be the same
> regardless of priorities.
>=20
Correct but with atomic propagators it would be much easier
to maintain.

>=20
> ... 
>=20
> One idea I had to make this simpler was to separate waking-priority
> from run-priority.  Run-priority would by default be very high, so
> that propagators are atomic by default, independent of the priority
> with which they are woken.
>=20
I think that would be a VERY good idea. That would make priorities
more useful. One could use call_priority for this but it would
be much better to do it by default.
 
>=20
> Hopefully answered above.  You will also see that the new G12
> constraint platform being developed in Melbourne has opted for
> having priorities.
>=20
Goals seems impressive.=20


Best regards
--=20
[ Wit Jakuczun    <W.Jakuczun [at] wlogsolutions.com> ]
[ WLOG Solutions  http://www.wlogsolutions.com ]