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

 
You're quite right, Jan! I assumed it would be very advanced, being a PhD thesis, but looking at it for the first time now, I see that it's a highly accessible introduction to CLP(FD). Thank you, Markus!

Kind regards,

Michael

[Eyal Dechter]

Yes, I think it is also excellent. I wish there were more pointers to it online and in the documentation. 

--

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.

[Markus Triska]

Hi Martin,

On Wednesday, August 26, 2015 at 5:31:42 PM UTC+2, martin.riener wrote:

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

Many thanks for sharing this nice example!

Cases like this really benefit from declarative approaches like constraints. No doubt combinatorial search with labeling/2 is pretty cool too, however, the vast majority of CLP(FD) use cases are simply common integer expressions that become more general and more declarative with constraints, and essentially at no additional cost in many applications.

In this case, it is clear that an equality can never hold if it involves a division by zero. Therefore, we get:

?- X #= Y/0.
false.

This answer means: No matter what integer expressions X and Y stand for, the equality never holds.

Thank you and all the best!
Markus

[Jan Wielemaker]

On 08/26/2015 06:30 PM, Markus Triska wrote:
> Hi Martin,
>
> On Wednesday, August 26, 2015 at 5:31:42 PM UTC+2, martin.riener wrote:
>
>
> ?- 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.

Yet, they detect different issues. As E is ground, labeling plays no role.
Looking at http://swish.swi-prolog.org/p/JukCQScc.pl we see that the clpfd
version says:

Domain error: `clpfd_expression' expected, found `2/6'

In other words, it rejects a formula because it produces results outside
the domain of clp(fd), which is about integers.

The is/2 message is less precise. I'm afraid that is because ISO defined
exceptions do not provide more details. It also fails elsewhere. Where
is/0 is happy with 2/6, it is not happy with 2/(13-7-6). Using a catch/3
around either of them solves the problem.

Cheers --- Jan

> Many thanks for sharing this nice example!
>
> Cases like this really benefit from declarative approaches like
> constraints. No doubt combinatorial search with labeling/2 is pretty
> cool too, however, the vast majority of CLP(FD) use cases are simply
> common integer expressions that become more general and more declarative
> with constraints, and essentially at no additional cost in many
> applications.
>

> In this case, it is clear that an equality can /never/ hold if it

> involves a division by zero. Therefore, we get:
>
> ?- X #= Y/0.

> *false*.

>
> This answer means: No matter what integer expressions X and Y stand for,
> the equality never holds.
>
> Thank you and all the best!
> Markus
>

[Jan Wielemaker]

On 08/26/2015 07:27 PM, Jan Wielemaker wrote:

> Yet, they detect different issues. As E is ground, labeling plays no role.
> Looking at http://swish.swi-prolog.org/p/JukCQScc.pl

After adding `debug, expr([7,13,2,6],E), 71 is E.`, we nicely get:

Exception:71 is 2/(7+(6-13))

//2: Arithmetic: evaluation error: `zero_divisor'

Cheers --- Jan

[Markus Triska]

Hi Jan,

On Wednesday, August 26, 2015 at 7:27:48 PM UTC+2, Jan Wielemaker wrote:

        Domain error: `clpfd_expression' expected, found `2/6'

You need to replace (/)/2 by (//)/2 in the CLP(FD) version: As announced on this mailing list, support for (/)/2 is removed in the current git version and for the next 3 development releases, because I will re-introduce it with different semantics than previously. Please use (div)/2 or (//)/2 for truncated integer division.

It has nothing to do with the domain of the result: (/)/2 is currently not supported at all in CLP(FD).

All the best!
Markus

[Markus Triska]

Hi Michael,

On Wednesday, August 26, 2015 at 6:02:08 PM UTC+2, Michael BEN YOSEF wrote:

 

You're quite right, Jan! I assumed it would be very advanced, being a PhD thesis, but looking at it for the first time now, I see that it's a highly accessible introduction to CLP(FD). Thank you, Markus!

You are very welcome, I'm glad you find this useful. Also, thank you for your insightful earlier post! A didactic approach that emphasizes operational semantics is in my view completely compatible with teaching constraints: There is a well-defined operational semantics for constraints too.

However, I encourage a declarative (instead of operational) reading of programs because it answers typical student questions in a more straight-forward way. "Why does my predicate fail?" --> Because one of the goals is too specific; you can generalize away some goals to find out which. "Why does my predicate succeed unexpectedly?" --> Because it is too general; you can add constraints to rule out this case, etc. "Why does my predicate not terminate?" --> Because this minimal code fragment already does not terminate, so something must be changed in this fragment, etc. So, the declarative reading lets you focus on the "why" instead of the "how", and allows for better, more compact explanations and guidance.

A great didactic advantage when teaching Prolog, in comparison with almost all other languages, is that you can make modifications to a program and still make statements about properties of the resulting program. For example, removing a goal, or adding a clause, can at most make the program more general, and adding a goal can at most make the program more specific. This way, you can create nice explanations in the form of code fragments, which you can even create automatically. This approach works as long as you stay in the pure monotonic subset of Prolog. Extensions like constraints, library(pio) etc. make this subset also more practically useful all the time in addition to these advantages.

All the best!
Markus

[Jan Wielemaker]

You are right. I guess that makes the naive translation invalid, assuming
that the puzzle is about exact division. Writing your own evaluator
or using catch/3 is probably required.

Cheers --- Jan

[Boris Vassilev]

Hello Markus,

First, thank you for the work on CLP(FD), which has allowed me to write useful code (and this is what has mattered most to me).

As to teaching, I will share an observation coming from my admittedly limited experience:

There is no one good way to approach it, as people are different. To me it seems that it helps if students are exposed in parallel to as many different programming languages and styles (or paradigms if you will) as possible. Only as the practical experience grows is one able to appreciate certain approaches, and doing different things in parallel lets each individual take their own path forward.

It goes without saying, one teacher in one lecture can only concentrate on one thing. It is up to those who decide on the curriculum to make sure that there is enough variety.

Cheers,

Boris

Currently in the EET time zone: This is UTC +2:00 (and I sleep at night)
Save our in-boxes! http://emailcharter.org

--

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.

[Julio Di Egidio]

On Wednesday, August 26, 2015 at 12:33:50 PM UTC+1, Julio Di Egidio wrote:

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

The more I think of it, the more I think you hit the nail in the head...  Of course, the whole discussion was very useful, thanks everybody.

To (again) complement your point:  For engineering, the world (that can be automated) is "procedural over relation", where the procedural side is primary.  So to speak, the fact that we can *do* things with a system is primary, not just the things: and we are preliminary.  It seems to me, somehow similarly, the future of "programming in logic" rather goes in the direction of some computability logic than, say, some datalog, not to mention, in the direction of a convergence of computer programming and doing logic.  --  BTW, overall that is the reason why I would not to use any CLP in place of arithmetic unless for a reason: and use the right tool for the job at hand remains a best practice...

All the best,

Julio

[Markus Triska]

Hi Jan,

On Thursday, August 27, 2015 at 9:36:39 AM UTC+2, Jan Wielemaker wrote:

You are right.  I guess that makes the naive translation invalid, assuming
that the puzzle is about exact division.

I agree, with "exact" replaced by "rational". For declarative arithmetic over the rationals, I recommend CLP(Q) instead of CLP(FD). You can use CLP(FD) to some extent too, if you rewrite some expressions.

I will soon introduce (/)/2 in CLP(FD) to mean exact integer division, i.e., the constraint X #= Y/Z will hold if and only if (X*Z #= Y, Z #\= 0) holds, as one would algebraically expect.

For truncated integer division, I initially used (/)/2 for SICStus compatibility, and now also SICStus are making changes into the right direction: In the latest SICStus versions, we get:

| ?- X #= Y/Z.
Y//Z#=X,
etc.

i.e., (/)/2 is already replaced by (//)/2 at least in residual goals.

To avoid completely unexpected results in user code due to this transition, I have intermittently removed support of (/)/2 completely, so that users have a better chance to adapt: If there are users who are currently using this (undocumented) expression, then they will see a clear error message instead of silent failure or unexpected success, and should replace (/)2 by (//)/2.

All the best!
Markus

[Stefan Kral]

Hi Michael. Hi to everybody else, too!

I feel the same, so I really want to chime in on praising Markus' work---both his work on clp(FD) / clp(B) and equally, if not even more so, on his Ph.D. thesis!

Having seen quite a number of Ph.D. theses, it's easy for me to find the most impressive, the most remarkable one... what I find most outstanding about his thesis is that Markus made the issues at hand approachable to readers at all conceivable levels of expertise.

Makes me jealous I didn't write a thesis like this, honestly!
All the best!

Cordially,
Stefan.


On Wednesday, August 26, 2015 at 6:02:08 PM UTC+2, Mithael BEN YOSEF wrote:

Hi Jan,h

[Julio Di Egidio]

On Friday, August 28, 2015 at 9:48:16 PM UTC+1, Stefan Kral wrote:

Hi Michael. Hi to everybody else, too!

I feel the same

Troll alert.

 

We live in difficult, soon unrecoverable times...

Julio

[Anne Ogborn]

:: Annie is here, poking the nasty troll with a stick - poke, poke ::

:: She gives Markus and Jan cookies and milk and maybe they feel better about the nasty troll ::

:: Annie constrains the troll to a value #> 4 and #< 2 and he fails 8cD ::

:: Annie returns to playing "change the world" with Unca' Markus and Unca' Jan and her friends. They play nicely with Markus's new constraint library and sing the swipl song ::

8cP Phibbbbbbt!


8cD

[Markus Triska]

Hi Stefan,

On Friday, August 28, 2015 at 10:48:16 PM UTC+2, Stefan Kral wrote:

I feel the same, so I really want to chime in on praising Markus' work---both his work on clp(FD) / clp(B) and equally, if not even more so, on his Ph.D. thesis!

many thanks, I cannot express how much I appreciate this extremely positive feedback coming from you.

Also welcome to this list! I am very glad that you are resuming posting about Prolog-related subjects after a long hiatus.

All, just so that you know more: Stefan is one of the teachers who taught Prolog to me when I was a beginner. His work on optimizing compilers received numerous awards, including the Gordon Bell Prize in peak performance and outstanding dissertation award. In addition to his vast knowledge about Prolog use and implementation, he is a hardcore functional programmer too and extremely well-versed in OCaml and Haskell. He currently has a teaching position for Prolog and distributed systems.

I found the Prolog code of a peephole optimizer outlined in his Masters thesis so impressive that I still host this snippet on my homepage so that I can link to it when I need to refer to it:

http://metalevel.at/kral_optimizer.pdf

I once mentioned this snippet on a mailing list about compiler optimization, and to this day I see from the log files that people involved in this area regularly access this file. What I found particularly amazing was that this optimizer, written in Prolog only to concisely illustrate the principals underlying the actual optimizer, was still more elegant and clear than much actual production code and documentation I have seen.

None of my work would have been possible without Ulrich and Stefan, who built a teaching environment without rival and are also heavily personally involved in teaching Prolog.

What I find interesting is that people who are involved in functional programming generally tend to pick up the idea of constraints a lot more quickly and happily than Prolog programmers. This is surprising to some extent: The idea of thinking in relations should be natural to Prolog programmers, and one would expect them to quickly adopt more relational predicates for this reason, in particular if they come at acceptable cost.

Currently, there is a lot of good work going on in the functional programming community to incorporate constraints, and functional programmers often see the benefits of constraints more clearly and immediately than people familiar with Prolog. For example, I recently had a pleasant meeting with the author of Guile-log who, in an amazing feat of engineering, has single-handedly extended Guile to run SWI-Prolog's CLP(FD) and CLP(B) libraries. He needed to make many changes throughout Guile to make this possible, including deep changes to the garbage collector and attributed variable interfaces (all written in C), so he is very well-versed with procedural programming as well as functional programming. After getting familiar with constraints, his only remaining question was why CLP(FD) is a library in SWI-Prolog, and not available from the start for integer arithmetic. I could only reply that the Prolog community is not quite there yet, but to look at GNU Prolog and B Prolog to see constraints more readily available. At least we have dif/2 already as an autoloaded predicate!

[Julio Di Egidio]

Well, I make it a matter of planet survival, but you won't get it.  So be it, have it as you like it...

Julio