Skip to first unread message

Aug 21, 2015, 11:06:58 AM8/21/15

to SWI-Prolog

Hi all,

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

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

Aug 21, 2015, 11:53:26 AM8/21/15

to Julio Di Egidio, SWI-Prolog

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.

Aug 21, 2015, 6:06:47 PM8/21/15

to SWI-Prolog

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:

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:

And then you can query:

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

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).

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.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 .

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

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

Aug 23, 2015, 4:46:13 AM8/23/15

to swi-p...@googlegroups.com

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).

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_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([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.

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.

% 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.

% 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).

same_length(Ratings, Counts),

ratings(Ratings, Counts),

sum(Counts, #=, Sum).

ratings([], []).

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

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).

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

Aug 23, 2015, 4:57:46 AM8/23/15

to SWI-Prolog, ju...@diegidio.name

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

Aug 23, 2015, 5:06:51 AM8/23/15

to SWI-Prolog

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

Aug 23, 2015, 7:55:58 AM8/23/15

to SWI-Prolog

Hi Julio,

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

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

Thank you and all the best!

Markus

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

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

Thank you and all the best!

Markus

Aug 23, 2015, 7:58:35 AM8/23/15

to SWI-Prolog

Hi Julio,

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

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

All the best,

Markus

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

Aug 23, 2015, 9:19:24 AM8/23/15

to swi-p...@googlegroups.com

[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.

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

Aug 23, 2015, 1:02:55 PM8/23/15

to SWI-Prolog

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

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

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

Aug 23, 2015, 1:36:20 PM8/23/15

to SWI-Prolog

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

Aug 23, 2015, 5:41:57 PM8/23/15

to SWI-Prolog

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.

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 Expr = X, X = Y, Y = 0.

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

?- 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.label([X,Y]).

Expr = X, X = Y, Y = 0 ;

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

Markus

Aug 24, 2015, 5:16:36 PM8/24/15

to swi-p...@googlegroups.com

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

Aug 25, 2015, 9:12:40 AM8/25/15

to SWI-Prolog

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

Aug 25, 2015, 9:21:52 AM8/25/15

to SWI-Prolog

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.

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.

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'.

Write a fully relational solution 'mc_10' in plain Prolog.

Compare performances between 'mc_10' and 'mc_11'.

Julio

Aug 25, 2015, 9:38:12 AM8/25/15

to Julio Di Egidio, SWI-Prolog

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
> 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.

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'.

notebook for the comparison. That allows people to play.

Cheers --- Jan

Aug 25, 2015, 10:03:50 AM8/25/15

to SWI-Prolog

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

Aug 25, 2015, 10:19:45 AM8/25/15

to Julio Di Egidio, SWI-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

Aug 25, 2015, 12:01:38 PM8/25/15

to SWI-Prolog

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

Aug 25, 2015, 12:36:43 PM8/25/15

to Markus Triska, SWI-Prolog

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/>

-----------------------------------------------------------------

> 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?

> 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.

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.

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?

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/>

-----------------------------------------------------------------

Aug 25, 2015, 1:45:55 PM8/25/15

to Paulo Moura, Markus Triska, SWI-Prolog

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

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

Aug 25, 2015, 7:27:02 PM8/25/15

to SWI-Prolog

Hi Paulo,

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

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.

I've seen my share of the flip side:

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:

- teacher poses a problem that inherently has no fully relational solution
- student amasses a hodgepodge of imperatively named predicates, barely useable in one direction at all
- 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

Aug 26, 2015, 1:15:44 AM8/26/15

to SWI-Prolog

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

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)

Kind regards,

Michael

Aug 26, 2015, 4:03:07 AM8/26/15

to Michael BEN YOSEF, SWI-Prolog

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
> 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

> 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.
> unsound negation as failure, database modification and yes, (is)/2?

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

> 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
> 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. :-)

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

> 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
> variables. I think this would benefit us and your students

> tremendously.

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

Aug 26, 2015, 7:15:27 AM8/26/15

to SWI-Prolog

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

Aug 26, 2015, 7:26:25 AM8/26/15

to Julio Di Egidio, SWI-Prolog

as well.

Thanks --- Jan

> Julio

Aug 26, 2015, 7:33:50 AM8/26/15

to SWI-Prolog

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

Aug 26, 2015, 7:36:08 AM8/26/15

to SWI-Prolog, ju...@diegidio.name

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

Aug 26, 2015, 10:02:21 AM8/26/15

to SWI-Prolog, ju...@diegidio.name

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

Aug 26, 2015, 10:18:33 AM8/26/15

to SWI-Prolog

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

Aug 26, 2015, 10:31:32 AM8/26/15

to swi-p...@googlegroups.com

"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.

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.

Aug 26, 2015, 11:31:42 AM8/26/15

to swi-p...@googlegroups.com

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

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

Aug 26, 2015, 12:02:08 PM8/26/15