Re: CLP(FD): Option list for labeling/2

Hi Fernando,

thank you for your insightful suggestions; my comments are embedded:

Fernando Sáenz Pérez <fernan@...> writes:

> labeling(+Vars). % For default options

This is good. Currently, there's label/1 with the same meaning;
labeling/2 should probably be kept for SICStus compatibility, but we can
thus use label/2, label/3 etc. for the other versions.

> specifying variable selection strategies. If a strategy is not
> specified (variable argument), it shoud be unified with the default.

Yes, and with other possible options on backtracking (otherwise it would
of course break monotonicity). Where there is no feasible way to
generate all possible options (like for optimisation expressions), it
must raise an instantiation error. However, I would even suggest
instantiation errors when the other options are not ground: Otherwise
labeling can take much longer and lead users to suspect performance
problems when in fact they only forgot to specify an option. This is one
reason why ins/2 creates an instantiation error instead of generating
all list lengths on backtracking if the first argument is not a list.

> labeling(?VariableSelectionStrategy,?BranchingStrategy,?SolutionOrders,+Vars)

This would indeed be good for the currently available set of options.
However, what about others or new ones, should we keep increasing
arities for them? For example, there are already (undocumented) options
in labeling/2 which are currently being discussed and will probably
become officially available soon. One example is upto_in/1:

   %?- [X,Y,Z] ins 0..100, 5*X #< Y, labeling([upto_in(S)], [X,Y,Z]).
   %@ X = 0, S = 10100, Y in 1..100, Z in 0..100 ;
   %@ X = 1, S = 9595, Y in 6..100, Z in 0..100 ;
   %@ X = 2, S = 9090, Y in 11..100, Z in 0..100 ; etc.

upto_in(S) labels variables until the remaining ones only have an in/2
constraint attached (which is trivially satisfiable), and S is unified
with the number of solutions that would arise if all variables were
labeled up to ground values. This allows to count solutions quickly.

Other sets of options are also conceivable for the future (backjumping,
learning, posting CLP(Q) constraints, verification etc.), and I've
therefore so far been reluctant to introduce higher arities for
different categories. But maybe it wouldn't be much of a problem?

> If several orders are allowed as in [min(Expr1),max(Expr2)], I'd
> understand them as a way to sort the solutions wrt., first, ascending
> values of Expr1, and for the same values of Expr1, show descending
> values of  Expr2. Then, if we have [min(X), max(X)], this only states:

I agree, and this is probably also what most users expect. I've already
seen a program where this was implicitly (and, so far, wrongly) assumed.
I've committed it in the "vienna" branch, which we use for experimental
changes in the CLP(FD) solver and related areas. You can try it with:

   $ git checkout -b vienna  --track origin/vienna

If it works as intended, I'll apply it to the master branch too.

> minimize(+Vars)

You mean a separate predicate for optimisation? That's an interesting
suggestion. We could have e.g.:

   optimisation(+MinMaxOpts, +LabelingOpts, +Vs)

This would separate the optimisation options (which can be several) from
the labeling options (where only one of each category is applicable).

> For instance, if one tries to minimize a function as F=X mod 3, there
> is as much solutions for X as 1/3 values in its domain. The system
> should report about all this solutions for it to be complete.

Absolutely; and indeed library(clpfd) is complete for all options, i.e.:

   ?- F #= X mod 3, X in 0..100, labeling([max(F)], [X]).
   %@ F = 2, X = 2 ;
   %@ F = 2, X = 5 ;
   %@ F = 2, X = 8 ;
   %@ F = 2, X = 11 ; etc.

One can use once/1 to get the incomplete behaviour of other systems.

> as a usual Prolog predicate. This, in addition, preserves the good
> properties of the provided labeling procedure.

Yes; one thing not considered so far is how options can be overridden if
we do away with the option list, i.e., labeling([ff,up|UserOptions], Vs).
Maybe this isn't a big problem? There probably aren't many programs that
use it that way, but it would be nice if it can still be supported.

Thank you and all the best,
Markus

------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...