Performances of CLP(FD)

[Julio Di Egidio]

Hi all,

I have written two solutions to a little counting problem, one uses CLP(FD), the other is just a standard Prolog approach:

<https://gist.github.com/jp-diegidio/c3e2f6e25eba99f8297f>

As you will see, the CLP(FD) solution is *way* slower than the other.

The question is whether that is showing an intrinsic limit with CLP(FD) performances (and whether such limit is specific to SWI), or, on the contrary, it is just that I still cannot write decent CLP(FD) code.

Feedback appreciated,

Julio

[Jan Wielemaker]

If I read the code correctly, you are posing the clp(fd) version as
a simple search problem, while you specify an algorithm that solves
the problem without any search for comparison. Right?

You can't really expect clp(fd) to outperform your simple loop :)
Constraint programming is typically about specifying a search space
and asking for a solution (as you do), where you expect the constraint
system to traverse the search space a bit more elegantly than simply
enumerating it.

Cheers --- Jan

>
> Feedback appreciated,
>
> Julio
>
> --
> You received this message because you are subscribed to the Google
> Groups "SWI-Prolog" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to swi-prolog+...@googlegroups.com
> <mailto:swi-prolog+...@googlegroups.com>.
> Visit this group at http://groups.google.com/group/swi-prolog.
> For more options, visit https://groups.google.com/d/optout.

[Markus Triska]

Hi Eyal,

an important constraint in this puzzle is that the total number of candies be as small as possible.

In the CLP(FD) version, you get this for example with:

labeling([min(Sum)], Counts)

Notice that just using [min] only affects the variable selection strategy during labeling, and is not directly related to any optimisation.

As Jan already said, you are comparing here two entirely different approaches. If you want to measure exclusively the impact of CLP(FD) constraints, replace the low-level arithmetic predicates with constraints. I have posted a version of the code as a comment on github that shows such a version. You see that the performance difference is much lower.

Also, I strongly recommend you keep the kernel relation, which posts constraints, separate from the actual search for solutions via labeling/2.

This way, you can see if the model itself is deterministic, terminates etc.

For example, consider just:

 :- use_module(library(clpfd)).

candies(Ratings, Counts, Sum) :-
        same_length(Ratings, Counts),
        ratings(Ratings, Counts),
        sum(Counts, #=, Sum).

ratings([], []).
ratings([R|Rs], [C|Cs]) :- ratings_(Rs, Cs, R, C).

ratings_([], [], _, _).
ratings_([R|Rs], [C|Cs], R0, C0) :-
        R0 #< R #==> C0 #< C,
        R0 #> R #==> C0 #> C,
        ratings_(Rs, Cs, R, C).

And then you can query:

?- candies([2,3,4,4,4,2,1,3,4], Counts, Sum),
   Counts ins 1..10_000, labeling([min(Sum)], Counts).
Counts = [1, 2, 3, 1, 3, 2, 1, 2, 3],
Sum = 18 ;
Counts = [1, 2, 3, 1, 3, 2, 1, 2, 4],
Sum = 19 .

in this case, it is for example interesting that the solution with minimal sum is unique. This cannot be observed if you use once/1.

An additional comment: There really are two major use cases for CLP(FD) constraints. The first is declarative integer arithmetic. I recommend you simply use CLP(FD) constraints like #=/2 instead of is/2 etc. over integers, simply because they often make your predicates more general and are true relations that are easy to understand. library(clpfd) performs automatic rewriting at compilation time that keeps the overhead of using CLP(FD) constraints in this way as low as possible.

The second use case is for their propagation strength that often prunes large portions of the search space.

Of course, propagation is not free: It takes inferences to perform propagation. Yes, many toy programs will run many milliseconds longer because of this propagation. However, many hard combinatorial problems will run much faster due to this inference, because the search space becomes smaller. So, as a rule of thumb, the harder the problem, the more propagation will pay off, and for tiny problems, it typically does not really matter if they run more slowly. So yes, small search problems will often run inherently slower, because for small search problems, generate+test can be faster than constraint propagation, which involves the scheduling of propagators, reasoning about domains, selection of variables etc.

Very quickly though, propagation will vastly outperform generate+test, and that is why you often end up with much faster solutions if you use CLP(FD).

I hope this helps.

All the best!
Markus

[Julio Di Egidio]

On Friday, August 21, 2015 at 11:06:47 PM UTC+1, Markus Triska wrote:

> Hi Eyal,

Eyal?  :)  Markus, I am copying here the comment you had written on Gist, I'd have some questions/objections...

---/begin-message/----------------

Using CLP(FD) constraints instead of lower level arithmetic predicates:

    pc_3(Rtgs, Cnts, Sum) :-
            length(Rtgs, L),
            length(FCnts, L),
            length(Cnts, L),
            pc_3__prep(L),
            pc_3__loop(Rtgs, FCnts, Cnts, Sum).

    pc_3__prep(L) :-
            pc_sup(Sup),
            L #=< Sup.

    pc_3__loop([], [], [], 0).
    pc_3__loop([R1| RT], [FC1| FCT], Cnts, Sum) :-
            FC1 #= 1,
            pc_3__loop__i([R1| RT], [FC1| FCT], Cnts, Sum).

    pc_3__loop__i([], [], [], 0).
    pc_3__loop__i([_], [C1], [C1], C1) :- !.
    pc_3__loop__i([R1, R2| RT], [FC1, FC2| FCT], [C1, C2| CT], Sum) :-
            (       R1 #< R2
            ->      FC2 #= FC1 + 1
            ;       FC2 #= 1
            ),
            pc_3__loop__i([R2| RT], [FC2| FCT], [C2| CT], Sum0),
            (       R1 #> R2,
                    FC1 #=< C2
            ->      C1 #= C2 + 1
            ;       C1 #= FC1
            ),
            Sum #= Sum0 + C1.

Timing comparison:

    ?- time(pc_2([2,3,4,4,4,2,1,3,4], Cnts, Sum)).
    % 24 inferences, 0.000 CPU in 0.000 seconds (75% CPU, 666667 Lips)
    Cnts = [1, 2, 3, 1, 3, 2, 1, 2, 3],
    Sum = 18.

    ?- time(pc_3([2,3,4,4,4,2,1,3,4], Cnts, Sum)).
    % 139 inferences, 0.000 CPU in 0.000 seconds (81% CPU, 1759494 Lips)
    Cnts = [1, 2, 3, 1, 3, 2, 1, 2, 3],
    Sum = 18.

Even better, check out a pure version:

    :- use_module(library(clpfd)).

    candies(Ratings, Counts, Sum) :-
            same_length(Ratings, Counts),
            ratings(Ratings, Counts),
            sum(Counts, #=, Sum).

    ratings([], []).
    ratings([R|Rs], [C|Cs]) :- ratings_(Rs, Cs, R, C).

    ratings_([], [], _, _).
    ratings_([R|Rs], [C|Cs], R0, C0) :-
            R0 #< R #==> C0 #< C,
            R0 #> R #==> C0 #> C,
            ratings_(Rs, Cs, R, C).

You can use this version in *all* directions, also if ratings are not known initially!

I strongly recommend you stay within the pure monotonic subset of Prolog to make your solutions more general.

---/end-message/----------------

Julio

[Julio Di Egidio]

On Friday, August 21, 2015 at 4:53:26 PM UTC+1, Jan Wielemaker wrote:

You can't really expect clp(fd) to outperform your simple loop :) 

Constraint programming is typically about specifying a search space

OK, makes sense...

Thank you,

Julio

[Julio Di Egidio]

On Friday, August 21, 2015 at 11:06:47 PM UTC+1, Markus Triska wrote:

In the CLP(FD) version, you get this for example with:

labeling([min(Sum)], Counts)

Notice that just using [min] only affects the variable selection strategy during labeling, and is not directly related to any optimisation.

Thank you, I just now understand how to use min/max(Expr)...

I'd propose an example is added to the SWI documentation, maybe something like "11.7.0.5.bis Optimization"...

Julio

[Markus Triska]

Hi Julio,

good suggestion, I have added a new section on optimisation with CLP(FD), to appear at:

http://www.swi-prolog.org/pldoc/man?section=clpfd

starting with the next release. Please have a look at the git version until then.

Thank you and all the best!
Markus

[Markus Triska]

Hi Julio,

On Sunday, August 23, 2015 at 10:46:13 AM UTC+2, Julio Di Egidio wrote:

Eyal?  :)

I'm sorry Julio! I was used to all good recent CLP(FD) questions coming from Eyal :-)

All the best,
Markus

[Julio Di Egidio]

[Subject changed from "Performances of CLP(FD)" to "Using CLP(FD)".]

Hi Markus,

On Sunday, August 23, 2015 at 9:46:13 AM UTC+1, Julio Di Egidio wrote:

On Friday, August 21, 2015 at 11:06:47 PM UTC+1, Markus Triska wrote:

---/begin-message/----------------

You can use [the "pure"] version in *all* directions

I can grasp the general notion and the advantages, i.e. that CLP code directly expresses requirements as well as the fact of true relationships.  That is great, but the devil is in the detail, i.e. the difficulties...

Pretend this is a code review in some production office: you were given a problem statement and you have submitted a program that allegedly solves the problem.  --  I am framing it this way just to stress what an engineering approach looks like: in fact, I think the underlying issue is a disconnect between the worlds of theory and practice, so to speak.

Below you will find a run of tests against your program:

- The program as is goes short of solving the given problem (it does not pass most tests).  In particular:

  - Domains (or, at least, that counts are greater than zero)  are integral to the question (I have had to wrap the program);

  - Optimising (namely, the count of candies must be minimal) is integral to the question (most solutions are not valid);

  - Labelling must be done by the program, even for a true relationship (the teacher will not learn labelling, the program must do it);

  -  Besides, there are cases in which it goes into an infinite loop (strictly speaking, another error): either I am missing something or that seems to suggest limitations in the very implementation of CLP(FD).

Thoughts?  Can you see my point and the overall difficulty, a difficulty that I would venture most programmers encounter with CLP and Prolog in general, i.e. as soon as we get to actual production?  That the program does what requested is a capital point: would you be able to fix/complete the code so that it satisfies all requirements?

By all requirements I mean:

1) Solutions satisfy the problem statement (*);

2) (Optional) Implements a true relationship (all invocation patterns work).

(*)

- Minimise the number of candies the teacher needs,
  subject to the constraints that:
  - Every child gets at least 1 candy; and,
  - For any two adjacent children, if one's rating is higher than the
    other's, s/he must get more candies than the other.

1 ?- [user].
ct(Ratings, Counts, Sum) :-
 candies(Ratings, Counts, Sum),
 Ratings ins 1 .. 2,
 Counts ins 1 .. 10.

ctw(Ratings, Counts, Sum) :-
 ct(Ratings, Counts, Sum),
 append(Ratings, Counts, Vars),
 labeling([min(Sum)], Vars),
 format('~w -> ~w (~w)~n', [Ratings, Counts, Sum]).
true.

2 ?- set_prolog_flag(toplevel_print_anon, false).
true.

3 ?- Rs=[1,2,2], Cs=[1,2,1], CsX=[1,2,2], S=4, SX=5.
Rs = CsX, CsX = [1, 2, 2],
Cs = [1, 2, 1],
S = 4,
SX = 5.

4 ?- ctw($Rs, $Cs, $S).
[1,2,2] [1,2,1] (4)
true ;
false.

5 ?- ctw($Rs, $Cs, $SX).
false.

6 ?- ctw($Rs, $CsX, $S).
false.

7 ?- ctw($Rs, $CsX, $SX).
[1,2,2] [1,2,2] (5)
true ;
false.

8 ?- ctw($Rs, $Cs, _S).
[1,2,2] [1,2,1] (4)
true ;
false.

9 ?- ctw($Rs, $CsX, _S).
[1,2,2] [1,2,2] (5)
true ;
false.

10 ?- ctw($Rs, _Cs, $S).
[1,2,2] [1,2,1] (4)
true ;
false.

11 ?- ctw($Rs, _Cs, $SX).
[1,2,2] -> [1,2,2] (5)
true ;
[1,2,2] -> [1,3,1] (5)
true ;
false.

12 ?- ctw(_Rs, $Cs, $S).
[1,1,1] -> [1,2,1] (4)
true ;
[1,2,1] -> [1,2,1] (4)
true ;
[1,2,2] -> [1,2,1] (4)
true ;
[2,2,1] -> [1,2,1] (4)
true ;
[2,2,2] -> [1,2,1] (4)
true ;
false.

13 ?- ctw(_Rs, $Cs, $SX).
false.

14 ?- ctw(_Rs, $CsX, $S).
false.

15 ?- ctw(_Rs, $CsX, $SX).
[1,1,1] -> [1,2,2] (5)
true ;
[1,2,2] -> [1,2,2] (5)
true ;
[2,2,2] -> [1,2,2] (5)
true ;
false.

16 ?- ctw($Rs, _Cs, _S).
[1,2,2] -> [1,2,1] (4)
true ;
[1,2,2] -> [1,2,2] (5)
true ;
[1,2,2] -> [1,3,1] (5)
true ;
[1,2,2] -> [1,2,3] (6)
// ...
[1,2,2] -> [9,10,10] (29)
true ;
false.

17 ?- ctw(_Rs, _Cs, $S).
[1] -> [4] (4)
true ;
[2] -> [4] (4)
true ;
[1,1] -> [1,3] (4)
true ;
[1,1] -> [2,2] (4)
true ;
// ...
[1,1,1,1] -> [1,1,1,1] (4)
true ;
[2,2,2,2] -> [1,1,1,1] (4)
true ;
Action (h for help) ? abort
% Execution Aborted

18 ?- ctw(_Rs, $Cs, _S).
[1,1,1] -> [1,2,1] (4)
true ;
[1,2,1] -> [1,2,1] (4)
true ;
[1,2,2] -> [1,2,1] (4)
true ;
[2,2,1] -> [1,2,1] (4)
true ;
[2,2,2] -> [1,2,1] (4)
true ;
false.

19 ?- ctw(_Rs, _Cs, _S).
[] -> [] (0)
true ;
[1] -> [1] (1)
true ;
[2] -> [1] (1)
true ;
[1] -> [2] (2)
true ;
// ...
[1] -> [10] (10)
true ;
[2] -> [10] (10)
true ;
[1,1] -> [1,1] (2)
true ;
[2,2] -> [1,1] (2)
true ;
[1,1] -> [1,2] (3)
true ;
// ...

Julio

[Markus Triska]

Hi Julio,

it is good practice to keep the labeling part separate from posting constraints: This way, you can try different labeling strategies without recompiling the program.

Regarding the infinite loops: A logic program must not terminate if the solution set is infinite and there is no way to express all solutions finitely. Everything else would mean that the program is incomplete. In this case, solutions exist for all lists lengths, hence (for example) the most general query must not terminate.

To express the remaining constraints, you can for example add Counts ins 1..10_000, and obtain solutions in increasing number of total candies with labeling([min(Sum)], Counts), hence all minimal solutions will appear first. See my previous mail for the invocation example.

All the best!
Markus

[Julio Di Egidio]

On Sunday, August 23, 2015 at 6:02:55 PM UTC+1, Markus Triska wrote:

> Regarding the infinite loops: A logic program must not terminate if the solution set is infinite

I was talking of the resolution going into an infinite loop, i.e. the program *crashing* (look for "% Execution Aborted").

> minimal solutions will appear first

All solutions that are not minimal are *invalid*.

Markus, your program does not pass most of the tests...

Julio

[Markus Triska]

Hi Julio,

On Sunday, August 23, 2015 at 7:36:20 PM UTC+2, Julio Di Egidio wrote:

All solutions that are not minimal are *invalid*.

To truly constrain all solutions to the optimum value in a general way, there is a neat trick involving findall/3: Since findall/3 uses a failure-driven loop to collect all solutions, you can use it to collect the optimum without posting any additional constraints.

A simplified example will make this clearer: First, let us use min(Expr) to find solutions in increasing order of Expr:

?- Expr #= X*Y, [X,Y] ins 0..1, labeling([min(Expr)], [X,Y]).
Expr = X, X = Y, Y = 0 ;
Expr = X, X = 0, Y = 1 ;
Expr = Y, Y = 0, X = 1 ;
Expr = X, X = Y, Y = 1 ;
false.

Now, you truly want to constrain this to solutions that are actually minimum with respect to Expr. It is tempting to use once/1 and commit to the first solution, i.e.:

?- Expr #= X*Y, [X,Y] ins 0..1, once(labeling([min(Expr)], [X,Y])).
Expr = X, X = Y, Y = 0.

However, in general, this will make the program incomplete, and I recommend to avoid this for this reason.

Instead, I recommend to wrap this into findall/3 just to collect the optimum, and then to use this information with the full power of unrestricted labeling/2 (or label/1)  to find all solutions that are optimal. For example:

?- Expr #= X * Y, [X,Y] ins 0..1,
   findall(Expr, once(labeling([min(Expr)],[X,Y])), [Expr]),
   label([X,Y]).
Expr = X, X = Y, Y = 0 ;
Expr = X, X = 0, Y = 1 ;
Expr = Y, Y = 0, X = 1.

Notice that two additional solutions are now found.

In many optimisation tasks, several different solutions are optimal, and - using this method - one can observe them and choose among optimum solutions by different criteria.

Your specific example may not need such a general technique, but I hope you find it useful in more complex cases.

All the best!
Markus

[Julio Di Egidio]

On Sunday, August 23, 2015 at 2:19:24 PM UTC+1, Julio Di Egidio wrote:

[Subject changed from "Performances of CLP(FD)" to "Using CLP(FD)".]

On Sunday, August 23, 2015 at 9:46:13 AM UTC+1, Julio Di Egidio wrote:

On Friday, August 21, 2015 at 11:06:47 PM UTC+1, Markus Triska wrote:

---/begin-message/----------------

You can use [the "pure"] version in *all* directions

The program as is goes short of solving the given problem (it does not pass most tests). 

<snip> 

 

[W]ould you be able to fix/complete the code so that it satisfies all requirements?

By all requirements I mean:

1) Solutions satisfy the problem statement (*);

2) (Optional) Implements a true relationship (all invocation patterns work).

(*)

- Minimise the number of candies the teacher needs,
  subject to the constraints that:
  - Every child gets at least 1 candy; and,
  - For any two adjacent children, if one's rating is higher than the
    other's, s/he must get more candies than the other.

After struggling with it for several hours, here is a version that is pure, fully relational, and passes all tests.

cc_max(r, 10_000).
cc_max(c, 10_000).

cc_3_t(Rs, Cs, S) :-
    cc_3(Rs, Cs, S, [2, 3]),
    format('~w => ~w (~w)', [Rs, Cs, S]).

cc_3(Rs, Cs, S) :-
    cc_max(r, R_max),
    cc_max(c, C_max),
    cc_3(Rs, Cs, S, [R_max, C_max]).

cc_3(Rs, Cs, S, [R_max, C_max]) :-
    cc_3__con(Rs, Cs, S, [Cs_r, S_r], [R_max, C_max]),
    cc_3__sol(Rs, Cs, S, [Cs_r, S_r]).

cc_3__con(Rs, Cs, S, [Cs_r, S_r], [R_max, C_max]) :-
    cc_3__set(Rs, Cs, S),
    cc_3__dom(Rs, Cs_r, S_r, [R_max, C_max]),
    cc_3__rel(Rs, Cs_r, S_r).

cc_3__sol(Rs, Cs, S, [Cs_r, S_r]) :-
    labeling([], Rs),
    once(labeling([min(S_r)], [S_r])),
    S = S_r,
    labeling([], Cs_r),
    Cs = Cs_r.

cc_3__set(Rs, Cs, S) :-
    same_length(Rs, Cs),
    (   var(S)            -> true
    ;   length(Rs, L),
        (   S < L         -> !, fail
        ;   S > (L+1)*L/2 -> fail
        ;   true
        )
    ).

cc_3__dom(Rs, Cs, _, [R_max, C_max]) :-
    same_length(Rs, Cs),
    Rs ins 0 .. R_max,
    Cs ins 1 .. C_max.

cc_3__rel([], [], 0).
cc_3__rel([R| Rs], [C| Cs], S) :-
    sum([C| Cs], #=, S),
    cc_3__rel__i(Rs, Cs, R, C).

cc_3__rel__i([], [], _, _).
cc_3__rel__i([R| Rs], [C| Cs], R0, C0) :-

    R0 #< R #==> C0 #< C,

    R0 #> R #==> C0 #> C,

    cc_3__rel__i(Rs, Cs, R, C).

/*

?- set_prolog_flag(toplevel_print_anon, false).
true.

?- Rs=[1,2,2], Cs=[1,2,1], CsX=[1,2,2], S=4, SX=5.
Rs = CsX, CsX = [1, 2, 2],
Cs = [1, 2, 1],
S = 4,
SX = 5.

?- cc_3_t($Rs, $Cs, $S).
[1,2,2] => [1,2,1] (4)
true.

?- cc_3_t($Rs, $Cs, $SX).
false.

?- cc_3_t($Rs, $CsX, $S).
false.

?- cc_3_t($Rs, $CsX, $SX).
false.

?- cc_3_t($Rs, $Cs, _S).
[1,2,2] => [1,2,1] (4)
true.

?- cc_3_t($Rs, $CsX, _S).
false.

?- cc_3_t($Rs, _Cs, $S).
[1,2,2] [1,2,1] (4)
true.

?- cc_3_t($Rs, _Cs, $SX).
false.

?- cc_3_t(_Rs, $Cs, $S).
[0,1,0] => [1,2,1] (4)
true ;
[0,1,1] => [1,2,1] (4)
true ;
[0,2,0] => [1,2,1] (4)
true ;
// ...
[1,2,2] => [1,2,1] (4)
true ;
[2,2,0] => [1,2,1] (4)
true ;
[2,2,1] => [1,2,1] (4)
true ;
false.

?- cc_3_t(_Rs, $Cs, $SX).
false.

?- cc_3_t(_Rs, $CsX, $S).
false.

?- cc_3_t(_Rs, $CsX, $SX).
false.

?- cc_3_t($Rs, _Cs, _S).
[1,2,2] => [1,2,1] (4)
true.

?- cc_3_t(_Rs, _Cs, $S).
[0,0,1] => [1,1,2] (4)
true ;
[0,0,2] => [1,1,2] (4)
true ;
[0,1,0] => [1,2,1] (4)
true ;
// ...
[2,2,1] => [1,2,1] (4)
true ;
[0,0,0,0] => [1,1,1,1] (4)
true ;
[1,1,1,1] => [1,1,1,1] (4)
true ;
[2,2,2,2] => [1,1,1,1] (4)
true ;
false.

?- cc_3_t(_Rs, $Cs, _S).
[0,1,0] => [1,2,1] (4)
true ;
[0,1,1] => [1,2,1] (4)
true ;
[0,2,0] => [1,2,1] (4)
true ;
// ...
[1,2,2] => [1,2,1] (4)
true ;
[2,2,0] => [1,2,1] (4)
true ;
[2,2,1] => [1,2,1] (4)
true ;
false.

?- cc_3_t(_Rs, $CsX, _S).
false.

?- cc_3_t(_Rs, _Cs, _S).
[] => [] (0)
true ;
[0] => [1] (1)
true ;
[1] => [1] (1)
true ;
[2] => [1] (1)
true ;
[0,0] => [1,1] (2)
true ;
[0,1] => [1,2] (3)
true ;
// ...

*/

Julio

[Julio Di Egidio]

On Sunday, August 23, 2015 at 10:41:57 PM UTC+1, Markus Triska wrote:

> Your specific example may not need such a general technique, but I hope you find it useful in more complex cases.

Markus, the OP is *more* complex than you are reading it: as I said, the devil is in the details, and you did not address any of the tough questions...

But definitely thanks for the food for thought, the tutorials, and the several tips, they were very useful regardless.

Cheers,

Julio

[Julio Di Egidio]

On Sunday, August 23, 2015 at 2:19:24 PM UTC+1, Julio Di Egidio wrote:

> After struggling with it for several hours, here is a version that is pure, fully relational, and passes all tests.

I have updated the code, there are significant improvements.

I wouldn't really guarantee about "pure": feedback still welcome.

<https://gist.github.com/jp-diegidio/c3e2f6e25eba99f8297f>

UPDATED 2015-08-25:
The original intent was that of comparing style and performances
between a plain Prolog solution and a solution based on CLP(FD).
Ensuing discussion noted that a clp-based solution can be meaningfully
compared to a plain Prolog solution only when the problem involves
browsing a search space.  Considering also the various hints and tips,
I have completely rewritten the two solutions while omitting all
performace comparisons.

TODO:
Write a fully relational solution 'mc_10' in plain Prolog.
Compare performances between 'mc_10' and 'mc_11'.

Julio

[Jan Wielemaker]

On 08/25/2015 03:21 PM, Julio Di Egidio wrote:
> On Sunday, August 23, 2015 at 2:19:24 PM UTC+1, Julio Di Egidio wrote:
>
>
> > After struggling with it for several hours, here is a version that is
> pure, fully relational, and passes all tests.
>
> I have updated the code, there are significant improvements.
>
> I wouldn't really guarantee about "pure": feedback still welcome.
>
> <https://gist.github.com/jp-diegidio/c3e2f6e25eba99f8297f>
>
> UPDATED 2015-08-25:
> The original intent was that of comparing style and performances
> between a plain Prolog solution and a solution based on CLP(FD).
> Ensuing discussion noted that a clp-based solution can be meaningfully
> compared to a plain Prolog solution only when the problem involves
> browsing a search space.

I wouldn't say that. Markus claims that clp(fd) is a meaningful
replacement for (integer) arithmetic. This justifies comparing A is B+C
with A #= B+C using instantiated B and C. Just, it is unfair to compare
an implementation that involves browsing a search space with another
that does not imply a search space.

I started a little comparison at the location below. I must admit
clpfd gives less overhead than I feared.

http://swish.swi-prolog.org/p/nPIbFzXI.swinb

> Considering also the various hints and tips,
> I have completely rewritten the two solutions while omitting all
> performace comparisons.
>
> TODO:
> Write a fully relational solution 'mc_10' in plain Prolog.
> Compare performances between 'mc_10' and 'mc_11'.

You may consider using http://swish.swi-prolog.org and create a
notebook for the comparison. That allows people to play.

Cheers --- Jan

[Julio Di Egidio]

On Tuesday, 25 August 2015 14:38:12 UTC+1, Jan Wielemaker wrote:

On 08/25/2015 03:21 PM, Julio Di Egidio wrote: 

<snip> 

 > The original intent was that of comparing style and performances
> between a plain Prolog solution and a solution based on CLP(FD).
> Ensuing discussion noted that a clp-based solution can be meaningfully
> compared to a plain Prolog solution only when the problem involves
> browsing a search space.

I wouldn't say that. Markus claims that clp(fd) is a meaningful
replacement for (integer) arithmetic.

But I do not agree on that point: I just preferred to leave it aside as other issues seemed quite more important.

I have immediate objections to that claim: to get from some code to a fully relational version is *not* trivial (and I say this partly in hindsight); OTOH, talking of pure functions, I do not see any advantage with that approach, so why pay the extra-price at all even if not dramatic?  Am I missing some scenarios?  I suppose a *significant* example, i.e. one where (just) replacing arithmetic with clp(fd) does make a significant difference, is in order...

Julio

[Jan Wielemaker]

I think I mostly agree with you on this point. In all my Prolog
programming I rarely came accross situations where I needed var/nonvar
tests to turn code using arithmetic into pure code. Most of the search
space exploration I do does not use arithmetic though. I assume that
clp(fd) does simplify search spaces that do include arithmetic.

Cheers --- Jan

[Markus Triska]

Hi all,

On Tuesday, August 25, 2015 at 3:38:12 PM UTC+2, Jan Wielemaker wrote:

Markus claims that clp(fd) is a meaningful replacement for (integer) arithmetic. 

This justifies comparing A is B+C with A #= B+C using instantiated B and C.

Indeed. I strongly recommend to simply use CLP(FD) constraints like (#=)/2 instead of is/2.

Thank you Jan for your benchmark. It shows that the overhead of using CLP(FD) constraints in this way is about a factor of 2 for extremely tight loops that consist exclusively of arithmetic. In very many applications, this overhead is completely acceptable or even entirely negligible, since (is)/2 is often not a bottleneck.

This raises the question: Why bother using (is)/2 at all for integer arithmetic? (is)/2 sure was fashionable in the 70s and 80s, but is it not time that we begin to use and teach more powerful and more declarative language elements that have since become available?

How many more "why does Prolog say 'uninstantiation error' with arithmetic?" questions do we want to see on stackoverflow.com? How many "I desperately need the functionality of constraints, but I want to avoid using constraints at all costs" types of questions? I think the time is near to end this nonsense by pointing users to more general solutions, which were not available or not as easily accessible in the past.

You can only win with CLP(FD) constraints: They are typically efficient enough, and can only lead to more general programs. They are easy to explain and use. They are available in many Prolog systems. They are also available in many free Prolog systems.

I have found CLP(FD) constraints to be vastly easier to explain and understand for beginners and leading to more general programs, nicer algebraic properties and enabling declarative debugging facilities (you can move around and comment out CLP(FD) constraints, and still retain an executable program).

You may say I am biased towards constraints, as the author of this specific library. I am. Though not because I am the author, but rather the other way around: The reason I built it is that I recognized the power and usefulness of this technology in SICStus Prolog, supported by a great teacher and a great teaching environment, and I want other users to freely benefit from this power too. Not all of us have been as lucky as I am. I know that many Prolog users are struggling with outdated books, incomplete tutorials, incompetent teachers, ridiculous online advice etc. Still, I recommend to look beyond all that and ask yourselves, from the bottom of your hearts, is it not time that we use and teach better alternatives as the basis for more declarative programs? And if not now, when?

All the best,
Markus

[Paulo Moura]

Hi Markus,

> On 25/08/2015, at 09:01, Markus Triska <tri...@logic.at> wrote:
>
> Hi all,
>
> On Tuesday, August 25, 2015 at 3:38:12 PM UTC+2, Jan Wielemaker wrote:
>
> Markus claims that clp(fd) is a meaningful replacement for (integer) arithmetic.
> This justifies comparing A is B+C with A #= B+C using instantiated B and C.
>
> Indeed. I strongly recommend to simply use CLP(FD) constraints like (#=)/2 instead of is/2.
>
> Thank you Jan for your benchmark. It shows that the overhead of using CLP(FD) constraints in this way is about a factor of 2 for extremely tight loops that consist exclusively of arithmetic. In very many applications, this overhead is completely acceptable or even entirely negligible, since (is)/2 is often not a bottleneck.
>
> This raises the question: Why bother using (is)/2 at all for integer arithmetic? (is)/2 sure was fashionable in the 70s and 80s, but is it not time that we begin to use and teach more powerful and more declarative language elements that have since become available?

Code portability.

> How many more "why does Prolog say 'uninstantiation error' with arithmetic?" questions do we want to see on stackoverflow.com? How many "I desperately need the functionality of constraints, but I want to avoid using constraints at all costs" types of questions? I think the time is near to end this nonsense by pointing users to more general solutions, which were not available or not as easily accessible in the past.

The current trend in SO is to post answers that only work in few systems at most, often forgetting to omit that little tiny detail. Also:

https://twitter.com/LogtalkDotOrg/status/605670287410102272

> You can only win with CLP(FD) constraints: They are typically efficient enough, and can only lead to more general programs. They are easy to explain and use. They are available in many Prolog systems. They are also available in many free Prolog systems.

many -> some

And there's also the question of feature parity among those systems that support finite domain solvers.

> I have found CLP(FD) constraints to be vastly easier to explain and understand for beginners and leading to more general programs, nicer algebraic properties and enabling declarative debugging facilities (you can move around and comment out CLP(FD) constraints, and still retain an executable program).
>
> You may say I am biased towards constraints, as the author of this specific library. I am. Though not because I am the author, but rather the other way around: The reason I built it is that I recognized the power and usefulness of this technology in SICStus Prolog, supported by a great teacher and a great teaching environment, and I want other users to freely benefit from this power too. Not all of us have been as lucky as I am. I know that many Prolog users are struggling with outdated books, incomplete tutorials, incompetent teachers, ridiculous online advice etc. Still, I recommend to look beyond all that and ask yourselves, from the bottom of your hearts, is it not time that we use and teach better alternatives as the basis for more declarative programs? And if not now, when?

I'm following and I'm enthusiastic about your improvements to the CLP(FD) library (thanks!) and I hope one day it would be universal enough (across Prolog systems) for me to consider using it on a regular basis. By universal, I mean not only available but also providing the same feature set. But currently, for writing portable code, is simply not an option. For users that don't care about portability, I would say, go for it!

Btw: where are the standard proposals for attributed variables and constraint systems?

Cheers,

Paulo

-----------------------------------------------------------------
Paulo Moura
Logtalk developer

Email: <mailto:pmo...@logtalk.org>
Web: <http://logtalk.org/>
-----------------------------------------------------------------

[Jan Wielemaker]

Hi Markus, Paulo,

I think Paulo has a point wrt. portability. Using #=/2 instead of is/2
requires the target Prolog to have clp(fd) (and constraints to start
with). I think I go with Markus to conclude that clp(fd) has a
reasonable support. If we have to wait for the last Prolog system we
will never get anywhere. But, many clp(fd) systems do not support
unbounded integers. This makes them a poor substitute.

More fundamentally, constraints combine poorly with pruning the search
space using -> or !, i.e., the classical Prolog way. These control
constructs just prune in the presence of pending constraints. In most
cases they should not, in some cases the pruning is nevertheless ok.

In my current opinion, using clp(fd) is great for setting up search
spaces that include arithmetic relations. In other applications I'm
not convinced.

Surely, constraints are a really valuable addition. I don't use them
often. Sometimes though, they provide an extremely elegant and short
solution to a problem that is really hard without them.

Cheers --- Jan

[Markus Triska]

Hi Paulo,

On Tuesday, August 25, 2015 at 6:36:43 PM UTC+2, Paulo Moura wrote:

 

Code portability.

Portability is one of the reasons why I am adamant to retain all parts of library(clpfd) in Prolog: I try to keep it as portable as possible, and it also runs on YAP already. Possibly with some extensions, I think I can port it to at least a few other systems too.

Come to think of it, maybe it would be best to start with a simple wrapper that uses only goal expansion to rewrite CLP(FD) constraints to built-in arithmetic, if that is possible, and throws an exception otherwise.

This would at least let us more uniformly use #=, #> etc. for integer arithmetic, with the option to later transparently elevate the support to more general, fully relational behaviour, across Prolog systems.

https://twitter.com/LogtalkDotOrg/status/605670287410102272

I've seen my share of the flip side:

1. teacher poses a problem that inherently has no fully relational solution
2. student amasses a hodgepodge of imperatively named predicates, barely useable in one direction at all
   
3. student walks away with the impression that Prolog is a trimmed down version of Pascal.

Most Prolog courses teach students to play with sand at the beach, while the ocean is in front of them, invisible to them. It is time to delve into the ocean: All libraries improve when they are being used. Support for them in other systems will inevitably improve too, as soon as there is sufficient user demand.

In the context of SWI, which is already incompatible with other systems in much more fundamental ways than just supporting a few predicates like (#>)/2 in more general ways (unbounded integers), the choice is clear.

 

I'm following and I'm enthusiastic about your improvements to the CLP(FD) library (thanks!) and I hope one day it would be universal enough (across Prolog systems) for me to consider using it on a regular basis. By universal, I mean not only available but also providing the same feature set. But currently, for writing portable code, is simply not an option. For users that don't care about portability, I would say, go for it!

Many thanks for this positive feedback, I really appreciate all encouragements. I think that the goal-expansion idea outlined above would help to get this started. This way, you would at least have a few universal predicates used for integer arithmetic (drop-in replacements of is/2 etc.), and extend them later with more generality.
 

Btw: where are the standard proposals for attributed variables and constraint systems?

Stay tuned :-) Currently, there is not much consensus: This will only come with increased use and after porting the libraries to different systems. Not much will come of this if people avoid using these features.


All the best!
Markus

[Michael BEN YOSEF]

Hi Markus!

This raises the question: Why bother using (is)/2 at all for integer arithmetic? (is)/2 sure was fashionable in the 70s and 80s, but is it not time that we begin to use and teach more powerful and more declarative language elements that have since become available?

For me, the essence of Prolog is Warren's "discovery" that it can be compiled to efficient imperative code. Prolog's strength is that it is an efficient procedural language and an "almost" sound and complete theorem prover at the same time. The well defined operational semantics are essential to Prolog. Why else do we put up with cut, unification without occurs check, incomplete search, unsound negation as failure, database modification and yes, (is)/2? They are operationally natural.
 
When we use CLP(FD), we give up our operational semantics and place it in your very capable hands. For me, that makes CLP(FD) a Prolog library - a very powerful one! - rather than a (partial) replacement for the Prolog language itself.

How many more "why does Prolog say 'uninstantiation error' with arithmetic?" questions do we want to see on stackoverflow.com? How many "I desperately need the functionality of constraints, but I want to avoid using constraints at all costs" types of questions? I think the time is near to end this nonsense by pointing users to more general solutions, which were not available or not as easily accessible in the past.

I am not a teacher of Prolog as you are, but I would say that the typical teaching order "declarative semantics->examples->operational semantics" is at fault here. Operational semantics should be introduced much earlier. Then students also won't wonder why their logically correct ancestor relation is going into an infinite loop. Even CLP(FD) can't help them with that. :-)

Personally, I would be immensely grateful if you wrote a book on how CLP(FD) works. Even one which expresses propagation in plain Prolog with explicit constraint stores rather than attributed variables. I think this would benefit us and your students tremendously.

Kind regards,

Michael

[Jan Wielemaker]

On 08/26/2015 07:15 AM, Michael BEN YOSEF wrote:
> Hi Markus!
>
> This raises the question: Why bother using (is)/2 at all for integer
> arithmetic? (is)/2 sure was fashionable in the 70s and 80s, but is it
> not time that we begin to use and teach more powerful and more
> declarative language elements that have since become available?
>
>
> For me, the essence of Prolog is Warren's "discovery" that it can be
> compiled to efficient imperative code. Prolog's strength is that it
> is an efficient procedural language and an "almost" sound and

> complete theorem prover /at the same time/. The well defined
> operational semantics are /essential/ to Prolog. Why else do we put

> up with cut, unification without occurs check, incomplete search,
> unsound negation as failure, database modification and yes, (is)/2?

> They are /operationally/ natural.

Agree!

> When we use CLP(FD), we give up our operational semantics and place
> it in your very capable hands. For me, that makes CLP(FD) a Prolog
> library - a very powerful one! - rather than a (partial) replacement
> for the Prolog language itself.
>
> How many more "why does Prolog say 'uninstantiation error' with
> arithmetic?" questions do we want to see on stackoverflow.com

> <http://stackoverflow.com>? How many "I desperately need the

> functionality of constraints, but I want to avoid using constraints
> at all costs" types of questions? I think the time is near to end
> this nonsense by pointing users to more general solutions, which were
> not available or not as easily accessible in the past.
>
>
> I am not a teacher of Prolog as you are, but I would say that the
> typical teaching order "declarative semantics->examples->operational
> semantics" is at fault here. Operational semantics should be
> introduced much earlier. Then students also won't wonder why their
> logically correct ancestor relation is going into an infinite loop.
> Even CLP(FD) can't help them with that. :-)

Kind of `get the magic out of Prolog'? Makes sense. If you want pure
declarative semantics, use a theorem prover. The power of Prolog is
(IMHO) indeed that it is both a theorem prover and a procedural
language. Of course, the counter argument is that is neither a good
theorem prover nor a good procedural language. I think that is valid in
itself. Many applications however need both and Prolog's procedural side
is capable of encapsulating more declarative islands (e.g., constraints,
tabling) naturally. It is also capable of encapsulating relational
subsystems much more naturally than pure procedural languages, a quite
important asset these days. And although you sometimes miss for-loops,
arrays, destructive assignment and functions, being able to handle
different cases in different clauses, having to use a proper (named)
recursive definitions rather than a three nested for-loop with 6 levels
if if-then-else and not having to worry about call-by-value vs.
call-by-reference or object identity also has its advantages. Prolog
tends to force you into simpler building blocks than the usual
OO/imperative suspects.

> Personally, I would be immensely grateful if you wrote a book on how

> CLP(FD) /works./ Even one which expresses propagation in plain

> Prolog with explicit constraint stores rather than attributed
> variables. I think this would benefit us and your students
> tremendously.

Markus did that. Just read his PhD thesis. It is a great document for
understanding (his) clpfd implementation as well as understanding how to
properly engineer non-trivial systems using Prolog. It explains how to
use pure code and retain efficiency, how to exploit code generation and
how to integrate testing (Markus, please extend if I forgot something
important). His clpfd implementation is a great engineering work and
indeed a valuable resource.

Cheers --- Jan

>
> Kind regards,
>
> Michael

[Julio Di Egidio]

On Wednesday, August 26, 2015 at 9:03:07 AM UTC+1, Jan Wielemaker wrote:

> Markus did that. Just read his PhD thesis.

You and Markus should get your head out of your ass...

> His clpfd implementation is a great engineering work

You and Markus don't even know what engineering is...

Julio

[Jan Wielemaker]

You make remarkably sharp observations :-) Really constructive
as well.

Thanks --- Jan

> Julio

[Julio Di Egidio]

On Wednesday, August 26, 2015 at 6:15:44 AM UTC+1, Michael BEN YOSEF wrote:

 

I would say that the typical teaching order "declarative semantics->examples->operational semantics" is at fault here.

I think you hit the nail in the head...

More generally, we know that the most difficult part of building any *real* product is *closing* the project: i.e. that there is an *abysmal* difference between bringing a project even up to 80% completion, and actually completing the project: it is a proverbial 80/20 in terms of effort.  Typical teaching and examples are simply useless unless in kindergarten, and even there I would think they are fundamentally the wrong way to go...

 

Julio

[Julio Di Egidio]

The unreasonability and the fallacy are all yours..  It is indeed nice that you guys are so nice to each other, until it becomes the real showstopper.

Julio

[Stephen Coda]

You just can't handle having your candy taken away.

[Julio Di Egidio]

On Wednesday, August 26, 2015 at 3:02:21 PM UTC+1, Stephen Coda wrote:

You just can't handle having your candy taken away.

More bulshitting?  FYI, I can handle everything, including calling things by their name...

That said, *stop CC'ing me in*: beside some intellectual honesty and the basics of rational discussion, learn some real etiquette, for a change.

EOD.

Julio

[Stephen Coda]

"You and Markus should get your head out of your ass... " You said that. 

Intellectual honesty is not a synonym for abuse, and what you said is certainly not "real etiquette."
I'm surprised someone of your intellectual status needs that pointed out.

These guys gave you a lot of screen time while simultaneously behaving like civilized human beings even though they disagreed with you, I think they deserve good manners at least.

[Martin]

Hi,

Coincidentally, i tried to solve a puzzle today where four given natural
numbers need to be recombined with the basic arithmetical operators
(+,-,*,/) to obtain a given result. I tried a generate and test approach
with a query like:

?- expr([7,13,2,6],E), 71 is E.
E = 6+13* (7-2) ;
E = 6+13* (7-2) ;
ERROR: //2: Arithmetic: evaluation error: `zero_divisor'

and after a few solutions, evaluated invalid expressions.
Using constraint propagation like:

?- expr([7,13,2,6],E), 71 #= E.

just detected the invalid expressions automatically. So even without
labeling, clp(fd) was pretty useful to me.

I attached the - admittedly amateurish - implementation, if you want to
play around with it.

cheers, Martin

[Michael BEN YOSEF]

Hi Jan,

> Personally, I would be immensely grateful if yo