CLP(FD) examples and concepts

[Markus Triska]

Hi all,

I have uploaded a collection of CLP(FD) examples that illustrate the way I recommend to use the library:

https://github.com/triska/clpfd

The point and intention of this repository is to convey the underlying concepts and princples of using CLP(FD) constraints in order to benefit most from them.

In particular, the examples in the repository teach or at least touch:

• declarative integer arithmetic
• residual constraints and incompleteness
  
• core relations
  
• propagation strengths and consistency notions
• isomorphic solutions and symmetry breaking
  
• search strategies via labeling options and beyond
  
• global constraints and expressiveness.

I will extend these examples to illustrate other important concepts and techniques in the future.

Also included is a shortened version of the CLP(FD) manual, intended to be used as supplementary lecture material:

https://github.com/triska/clpfd/blob/master/clpfd.pdf

This PDF explains the most important concepts of library(clpfd) and contains a short description of common constraints. It is intended to be used as complementary lecture material for a one to two semester Prolog course at the undergraduate level.

I hope you find this useful.

To purity!

All the best,

Markus

[Julio Di Egidio]

On Wednesday, November 4, 2015 at 12:19:09 AM UTC, Markus Triska wrote:

To purity!

Markus, thanks for the fantastic job and for sharing: on the other hand, this campaign of yours for a declarative uber alles is simply insane.  So, while I am not interested in any more polemics with you, here is some basic counter-advice for readers and students:

- For those interested into where logic programming is going, look up computability logic.

- For those interested in software engineering (actual software production), of course declarative is just part of the picture --  questions should be asked in comp.software-eng.

HTH,

Julio

[Sam Neaves]

Thanks for this it is useful! 

--
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.
Visit this group at http://groups.google.com/group/swi-prolog.
For more options, visit https://groups.google.com/d/optout.

[Wouter Beek]

​Hi Julio, Markus,​ others,

Are there concrete use cases where the principles of Pure Prolog conflict with certain Software Engineering principles?  I don't see the mutual exclusivity.

- For those interested into where logic programming is going, look up computability logic.

​

​Computability Logic is cool.  Is it related to CLP(FD) though?​

​

- For those interested in software engineering (actual software production), of course declarative is just part of the picture --  questions should be asked in

​​

comp.software-eng.

​What's this?  A newsgroup of some kind probably, but what does it have to do with CLP(FD)?

I'm a bit confused about these last two remarks.​

 

​Cheers!,

Wouter.​

[Julio Di Egidio]

On Wednesday, November 4, 2015 at 12:18:53 PM UTC, Wouter Beek wrote:

​Hi Julio, Markus,​ others,

Hi Wouter,

 

Are there concrete use cases where the principles of Pure Prolog conflict with certain Software Engineering principles?  I don't see the mutual exclusivity.

Neither do I, that was the point.  But you have snipped Markus' claim I was replying to.

 

- For those interested into where logic programming is going, look up computability logic.

​

​Computability Logic is cool.  Is it related to CLP(FD) though?​

Computability logic claims to subsume *all* logical (and programming) paradigms.

​

- For those interested in software engineering (actual software production), of course declarative is just part of the picture --  questions should be asked in

​​

comp.software-eng.

​What's this?  A newsgroup of some kind probably, but what does it have to do with CLP(FD)?

It's the official newsgroup for software engineering discussion, but I could also have mentioned comp.theory, the newsgroup about computer science, for another side of the coin.  In either case, Markus' extremism, so to speak and in my opinion, is just untenable, inappropriate, and misguiding.  In any case, more detailed discussion is eventually off topic on the SWI list, which is why I was indicating more appropriate groups, at least for the technical part of the issues at stake.

 

I'm a bit confused about these last two remarks.​

 

I hope the above clarifies.  Indeed, I do not mean to get into polemics, he said something, to that I have replied, the discussion can safely end here as far as I am concerned... unless there are technical questions (but, again, I can hardly see any questions that could be directly relevant to SWI: at best a comp.lang.prolog group might be appropriate if the future of logic programming is really the point).

Julio

[Markus Triska]

Hi Wouter,

On Wednesday, November 4, 2015 at 1:18:53 PM UTC+1, Wouter Beek wrote:

Are there concrete use cases where the principles of Pure Prolog conflict with certain Software Engineering principles?

One reason why declarative Prolog constructs are still somewhat overshadowed by impure primitives certainly lies in their affiliation with some performance downsides that have previously been non-negligible. Luckily, the situation is becoming much better in that respect. For example, Ulrich Neumerkel and Stefan Kral have recently put a lot of work into improving the efficiency and usability of pure monotonic branching constructs.

A German version of their most recent work:

http://www.complang.tuwien.ac.at/ulrich/papers/PDF/2015-kps-3.pdf

It is clear that such large increases in expressiveness and declarative power cannot be immediately or fully understood by everyone, so I expect it will take several more iterations and variants of this paper and many more discussions on stackoverflow and other places to get the point across in a manner that more users can appreciate. Many people will never be able to follow where the pioneers are heading, and that's OK: Stefan and Ulrich are already doing unexpectedly well if they make these ideas accessible enough so that they are available to pick up and use for people who are interested in Prolog, to benefit from the increased expressiveness and comfort.

Other than performance concerns (which, as I said, are gradually becoming obsolete) and portability considerations (my take on this: the more you use these features, the more they will be ported to other systems too!), I see no reason to limit oneself to lower-level predicates when more general alternatives are readily available, certainly not from a software engineering point of view. In fact, quite the opposite: An important trend across several software platforms and systems is clearly into more and more declarative directions, eliminating or limiting side effects and large classes of errors via very controlled domain specific languages that are often very declarative.

From these developments, one point is clear to me: If Prolog programmers do not manage to hold themselves to high declarative standards, then someone else will eventually appear and hold them to that standard. The new directive that will then be issued by other powers is also clear: "Obey! Grind and obey." There is still time - enough time! - to further develop the ideas that are in reach nowadays, and to implement them efficiently and in such a way that they are accessible to the vast majority of Prolog programmers. One moment's silence for those we leave on the wayside impurely.

All the best!
Markus

[Julio Di Egidio]

Congrats, complete utter nonsense, not to mention the open mindedness.

I just hope you haven't written your code at those standards...

*Plonk*

Julio

[Boris Vassilev]

Hello Markus,

talking from my point of view only, it very useful to have easy access to example CLP(FD) solutions written by _you_ in particular.

As for the other topics discussed in this thread (with unnecessarily harsh language sometimes): I don't want to go into it myself, as I don't feel qualified to do so, but you might want to check out this interesting blog entry:

https://mkremins.github.io/blog/doors-headaches-intellectual-need/

It is admittedly just a blog of an undergrad student, but there are some interesting observation in it, and some even more interesting links, esp:

http://math.ucsd.edu/~jrabin/publications/ProblemFreeActivity.pdf

It is obviously about (US) high-school math teaching. My gut feeling is that it could have been written on any field of science, and the case studies could have been done at any level of education, and the results would have been quite similar.

Cheers,

Boris

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

--

[Wouter Beek]

​Hi Markus,
​

On Wed, Nov 4, 2015 at 10:37 PM, Markus Triska <tri...@logic.at> wrote:

One reason why declarative Prolog constructs are still somewhat overshadowed by impure primitives certainly lies in their affiliation with some performance downsides

​Yes, this is a /huge/ problem.  Not just for Pure Prolog but also for Prolog.​  From the academic perspective, evaluations are firstly about performance and only secondly about other properties (e.g., descriptiveness, understandability, maintainability).  It is great that (Pure) Prolog shines in the latter, but it needs to improve on the former considerably.

Let me illustrate this point with CHR which can run on a highly parallellized cluster /in theory/ but is lacking a threaded implementation that can actually do so /in practice/.

Luckily, the situation is becoming much better in that respect.

​Are there more data points you can share ​in order to substantiate your claim that this is indeed becoming 'much' better.  I only see a few scattered attempts in this area.

For example, Ulrich Neumerkel and Stefan Kral have recently put a lot of work into improving the efficiency and usability of pure monotonic branching constructs.

​Thank you for sharing, this is great work!  (I'm still not onvinced that this is incicative of a trend though.)

A German version

​I happen to be able to read German but it would be beneficial for this text to (also) be available in English.​

It is clear that such large increases in expressiveness and declarative power cannot be immediately or fully understood by everyone

If programming in (Pure) Prolog would in fact pose significant benefits over less declarative languages without introducing too many resource burdens, then there would be a significant benefit that would warent the cost of learning.

Many people will never be able to follow where the pioneers are heading, and that's OK: Stefan and Ulrich

​I believe Stefan and Ulrich are particularly well equipped to ease the aforementioned educational hurde.  Their effort on Stackoverflow is significant.
​

and portability considerations

​I believe these to be secondary to the performance consideration as well.​

 

​Thanks for these explanations and for the literature pointer!​

---

​Cheers,

Wouter.

Email: w.g.j...@vu.nl

WWW: wouterbeek.com

Tel: +31647674624

[Jan Burse]

Hi,

Except that these pure monotonic branching constructs don't lead very far. It should
be well known that a simple interpretation for constructive negation would be the
Clark completion. So basically a set of Prolog clauses, where I am writing explicitly
Prolog clause and not clause, since I allow all kinds of stuff in the body B1,..,Bm:

      p(T11,..,T1n) :- B1.
      ..
      p(Tm1,..,Tmn) :- Bm.

Is logically equivalent to:

      p(X1,..,Xn) :- exists Y11..Y1k(X1=T11,..,Xn=T1n,B1).
      ..
      p(X1,..,Xn) :- exists Ym1..Ymk(X1=Tm1,..,Xn=Tmn,Bm).

Since the heads are now all the same we can combine this in a single
Prolog clause as follows:

      p(X1,..,Xn) :- exists Y11..Y1k(X1=T11,..,Xn=T1n,B1);
                         ...
                         exists Ym1..Ymk(X1=Tm1,..,Xn=Tmn,Bm).

So in the Clark completion the implication (:-)/2 is replaced by a bi-implication.
So that we have the following:

      p(X1,..,Xn) <-> exists Y11..Y1k(X1=T11,..,Xn=T1n,B1);
                         ...
                         exists Ym1..Ymk(X1=Tm1,..,Xn=Tmn,Bm).

Using the Clark completion is the minimum extension that is needed to
get negative information from Prolog programs. The problem is now
that these existence quantifiers exists Y11...Y1k work fine if a positive
query is issued. Prolog can simply proceed in ignoring such quantifiers.

But when negative information is required these existential quantifers
turn forall quantifers, eh voila one ends with the requirement that some
QUANTIFIER ELIMINATION methods are needed. And then things get
nasty if one tries to do it on top of ordinary Prolog.

I was recently making the tought experiment wherther maybe the member/2
predicate doesn't need a forall quantifier in its negation. Here is the completion
of member/2. First we have the normal definition of member/2:

     member(X, [X|_]).
     member(X, [_|Y]) :- member(X, Y).

Now lets make the first movement of the Clark completion, namely introducing
(=)/2 and makeing all heads the same. At the same time we must be also careful
about anonymous variables, and we will make the existential quantifier explicit:

     member(X, T) :-  exists H : (T = [X|H]).
     member(X, T) :-  exists J,Y : (T = [J|Y], member(X,Y)).

Now we can join the clauses together into a simple clause:

     member(X, T) :- exists H : (T = [X|H]);
                            exists J,Y : (T = [J|Y], member(X,Y)).

And now turn the following into a bi-implication:

     member(X, T) <-> exists H : (T = [X|H]);
                               exists J,Y : (T = [J|Y], member(X,Y)).

The fumbling of Stefan and Ulrich might only do something inbetween
T=[X|Y] and T=[J|Y] by introducing dif/2. This is already a progress. But
it wont capture the full logical content of member/2. In the future we might
for example require the availability of a constructive negation such that:

       ?- ~ member(X, [a,b,c]).
       dif(X, a),
       dif(X, b),
       dif(X, c).

Guess what, constructive negation is already a research goal since the 80's,
for example pioneered by David Chan. I am really happy to see some interested
in extending the declarativity of Prolog. But in my personal opinion, if the
QUANTIFIER ELIMINATION problem is not solved in some efficient way, the
results will be rather disappointing.

Bye

P.S.: An intermediate goal could be a general infrastructure for reification, for
example a (#\)/1 that works across different solvers. But this is only an idea that
came up the recent days on my side. We could also aim for weaker reification such
as allowing (#\)/1 for arguments that contain (,)/2 and (;)/2 instead of (#/\)/2 and
(#\/)/2. But in any case we will hurt our head on quantifiers sooner or later.

P.P.S.: Sometimes I have the impression the constructive negation problem
hasn't been solved so far, since it would kill jobs. No more papers about this
problem or indirectly addressing sub problems on it. But then when I take a look
by myself at it again, I still find so many technical traps, that I understand why it
hasn't become yet standard.

[Markus Triska]

Hi Boris,

many thanks for your posting, and for these links! They are interesting, and I have added some more material that is inspired by this content.

I value your opinion on the best didactic approach in particular, as I have seen you successfully getting important and non-trivial concepts across efficiently in difficult situations and various places.

Thank you and all the best,
Markus

[Markus Triska]

Hi Wouter,

On Thursday, November 5, 2015 at 3:10:36 PM UTC+1, Wouter Beek wrote:

​Are there more data points you can share ​in order to substantiate your claim that this is indeed becoming 'much' better.  I only see a few scattered attempts in this area.

Let us consider just the last decade, which - although a quite significant stretch in the life of an individual - is still the more recent past of logic programming and even SWI-Prolog itself.

~10 years ago, SWI-Prolog looked a bit like a logic-inspired version of Fortran when compared with what we have today: It had no rational numbers, no big integers, no copy_term/3, no pure residual goals, a toplevel and a version of time/1 that would silently cut away further solutions, no call_residue_vars/2, no library(pio), no CLP(B), no way to partially evaluate important and powerful meta-predicates (hence people tended to avoid them, using quite low-level coding styles over and over instead), no pure and robust timeout mechanism, no JIT indexing, a severely leaking freeze/2, and was lacking many other features that are intimately related to purity, declarative properties and at the same time efficiency.

Today, we are taking all these features for granted and some of us rely on them every day. The HTTP libraries and their beautiful and quite pure interface is also a good example where important functionality is implemented efficiently and at the same time largely bypassing and avoiding explicit side-effects. When I look at the past 10 years of SWI-Prolog development, I see a clear evolution of more and more declarative features, either implementing them in the first place, or changing existing features to become more declarative (like the toplevel, indexing, and attributed variables interface predicates), or making existing functionality more efficient so that declarative features can be added on top.

For example, there is a beautiful paper by Jan and Ulrich that explains in detail the features that a garbage collector must implement so that it deals correctly and efficiently with lazy data structures as used by phrase_from_file/2:

https://www.complang.tuwien.ac.at/ulrich/papers/PDF/2008-ciclops.pdf

In fact, the new declarative features have evolved so fast in SWI-Prolog that people are already having a hard time to catch up with them, and some of them are giving up when faced with so many unusual new things. On top of this, Ulrich and Stefan are now introducing and even publishing still more declarative approaches that appear on the horizon. You can imagine how tough such concepts are to accept for a community that was largely unaware of the call/N family of predicates until quite recently. Therefore, it is understandable that progress must be slow to give others a chance to catch up.
 

​I happen to be able to read German but it would be beneficial for this text to (also) be available in English.​

I also hope, for the sake of other readers, that this paper or improved and extended versions of it will soon become available also in English.

If programming in (Pure) Prolog would in fact pose significant benefits over less declarative languages without introducing too many resource burdens, then there would be a significant benefit that would warent the cost of learning.

​I believe Stefan and Ulrich are particularly well equipped to ease the aforementioned educational hurde.  Their effort on Stackoverflow is significant.

I agree completely on both accounts. I am convinced that the future will bring very nice and pure solutions to tough problems. Meanwhile, we can already prepare the way, and spread existing declarative solutions so that they become more widely accessible, understood and accepted.

All the best!
Markus

[Wouter Beek]

​​

​Hi Markus,​

On Thu, Nov 5, 2015 at 9:14 PM, Markus Triska <tri...@logic.at> wrote:

~10 years ago, SWI-Prolog looked a bit like a logic-inspired version of Fortran when compared with what we have today: It had no rational numbers, no big integers, no copy_term/3, no pure residual goals, a toplevel and a version of time/1 that would silently cut away further solutions, no call_residue_vars/2, no library(pio), no CLP(B), no way to partially evaluate important and powerful meta-predicates (hence people tended to avoid them, using quite low-level coding styles over and over instead), no pure and robust timeout mechanism, no JIT indexing, a severely leaking freeze/2, and was lacking many other features that are

​​

intimately related to purity, declarative properties and at the same time efficiency.

​You have mentioned quite a few data points!  This shows that you can clearly substantiate your earlier claim that Prolog is becoming more viable from a performance point of view over the last 10 years.

It is now also clear to me that you are talking about perfromance (and other) improvements in declerative programming today w.r.t. declarative programming in the past.​  I believe that the comparison gives a different outcome as soon as you start comparing declarative programming today to other programming paradigms today.

This need not be due to inherent limitations of the declarative paradigm b.t.w.: "computational complexity is a property of algorithms, not languages" (<-- I hope I'm quoting Jan correctly here!)  The lack of performant applications may also be due to the fact that the community of declarative programmers is not yet big enough.

I believe that the benefits of Prolog are by now very clearly demonstrated in terms of relatively small programs and solutions to many interesting isolated problems and puzzles: "4 understandable lines in Prolog <---> 10 confusing lines in Python!"

But when we move to big and scalable SotA applications these proven benefits do not always carry over.  E.g., constraint languages are awesome: they allow me to write a full-blown OWL reasoner in a few hours time.  A clear benefit over any other programming paradigm!  But the resultant reasoner cannot be expected to run reasonably over databases of >100K ground facts.  Nor is CHR able to identify independent entailments for me and calculate them in different threads (although theory states this can be done and this is one of the major claimed benefits of the language).

To be clear: I do think that CHR, CLP, Pure Prolog, etc. are extremely beneficial to software engineering.  But I do not think that we have sufficiently showed those benefits at the level of large-scale, visible, SotA software projects and services yet.  That's something we should do within the next 10 years ;-)

[Jan Burse]

Hi,

Am Donnerstag, 5. November 2015 15:13:25 UTC+1 schrieb Jan Burse:

Using the Clark completion is the minimum extension that is needed to
get negative information from Prolog programs. The problem is now
that these existence quantifiers exists Y11...Y1k work fine if a positive
query is issued. Prolog can simply proceed in ignoring such quantifiers

Since Prolog is ignoring quantifiers, and quantifiers are hardly expressed,
except for such special predicates such as bagof/3 and setof/3, the
Ulrich branching concepts might already bump their head.

I am not 100% sure, but I have deviced the following scenario, Assume
we cascade the branching constructs, i.e.

        A -> S
     ;  B -> T
     ;  R

Now if we don't want to use cut and instead some dif/2, lets denote
this by using some constructive negation (~)/2, so that the result would be:

        A, S
      ; ~A, (B, T
               ~B, R).

Now if A has a an existential quantifier, for example some innocently
looking goal p(X,Y), q(Y,Z) where Y is used to find a link between p and
q, than this might clash either with genuine variables in B or also some
variables in B that are used as existential quantifiers.

So there need to be some sanity side conditions between A and B,
and sooner or later, we will see that its all quantifier scopeing issues.

Bye

[Stefan Kral]

On Thursday, November 5, 2015 at 3:13:25 PM UTC+1, Jan Burse wrote:
> [...] But it wont capture the full logical content of member/2.

> In the future we might for example require the availability
> of a constructive negation such that:
>
>        ?- ~ member(X, [a,b,c]).
>        dif(X, a),
>        dif(X, b),
>        dif(X, c).

I cannot see how above use case is not covered by memberd_t/3. Consider:

?- memberd_t(X, [a,b,c], false).

cheers, Stefan.

[Jan Burse]

Yes, of course the intentin of a predicate XXd_t/n could be such that
constructive negation comes in as follows:

     XXd_t(A1, .., An, true) :- XX(A1, .., An).
     XXd_t(A1, .., An, false) :- ~ XX(A1, .., An).

So that XXd_t/n is kind of the truth function aka characteristic function
of the original predicate XX.

But in a constructive negation interpreter there wouldn't be much
effort for the end-user to invoke constructive negation. He would
just go with the usual definition:

      member(...) ...

And could then invoke the following:

      ?- ~ member(....)

The Prolog would automatically see the predicate member/2 in
the Clark completion. See some posts above what the Clark
completion is.

But I doubt that with XXd_t/m and call/n and dif/2, and without
some quantifier considerations, one could build constructive
negation.

But there might be syntactic fragments, predicates with a certain
shape, where XXd_t/m works. For example the whole Datalog
range restricted formulas work for constructive negation if the
constructive negation itself occurs also range restricted.

But it is more common in Datalog to already have an input
language that has quantifiers, at least I did it this way in my
Datalog interpreter ProQuel in 1993. So pushing Datalog into constructive
negation, would be easier than pushing Prolog into constructive
negation, as it doesn't have a quantifier notation.

So there could be code which falls out of this syntactic fragment,
or it might fall out of the sanity conditions I mention in a previous
post. So basically there is kind of a design space consisting of
enhancing the input language with quantifiers and then allowing
certain subsets of the input language.

I don't think there is much to disagree.

Bye

[Jan Burse]

I don't think there is much to disagree.

All papers that deal with constructive negation more or less
assume an input language that has quatifiers.

BTW: Here is a further situation where in normal Prolog
a quantifiers sneeks in, in ordinary negation as failure:

     ?- q(X), \+ p(X,_).

Can have the following logical reading:

     ?- q(X) & ~exists Y p(X,Y).

So if you translate XX/m to XXd_t/m+1 you would need
to analyze the variable flow. I don't see that this can be
done with call/n.

It could be done maybe with the new goal expansion
feature of SWI-Prolog, where you can ask about the status
of a variable. But I didn't find some usage of it so far.

So it could be that greater progress can be made with
goal expansion instead of call/n. Or both is needed.
But everything would be clearer if the end-user had an
input with quantifiers in the first place.

Bye

[Mauro DiNuzzo]

Hi, mine is just a desire and I really do not know exactly what you are talking about.

I always dreamt a "logic programming system" in which CLP completely replaces standard Prolog.

Importantly, this replacement should apply to every operator and the system should understand domain by context.

Since my first look at Prolog, I always wished that =/2 and is/2 had opposite meaning, i.e. is/2 performing unification.

Thus for example, I could write:

?- person(Name, Age) is person(mauro, _).

  Name is mauro 

and

? X = Y+1.  % or Y + 1 = X

and not the opposite.

If I were more inside these things (and less lazy and disorganized) I would develop such a system by myself.

Overall, I cannot understand the benefits of Prolog when we have CLP.

The issue in not about performance in any way, I believe. I use Prolog because it allows solving problems rapidly, so that I can spare time for the problem itself, not the solution strategy.

Best wishes,

M

[Carlo Capelli]

Hi Mauro

AFAIK, modelling a problem (like the 'escape from zurg', that can be solved efficiently in 10 lines of Prolog) can be a though process.

What I would like to see from CLP, would be some help/warning about which Prolog construct will interfere with contraints... but maybe this is a too difficult feature, not even feasible...

[Jan Wielemaker]

Hi Carlo,

On 11/16/2015 01:26 PM, Carlo Capelli wrote:
> AFAIK, modelling a problem (like the 'escape from zurg

> <http://stackoverflow.com/a/32981906/874024>', that can be solved

> efficiently in 10 lines of Prolog) can be a though process.
> What I would like to see from CLP, would be some help/warning about
> which Prolog construct will interfere with contraints... but maybe this
> is a too difficult feature, not even feasible...

The help is easy: you cannot combine delayed calls with pruning the
search space using ! or -> (which implies \+). In general you can also
not combine constraints with term copying, e.g., the all-solution
predicates findall/3, bagof/3 and setof/3.

There are exceptions to these rules. They typically require deep
understanding on how the delayed goal interact with copying or
committing.

For short, CLP only combines with pure Prolog. And yes, if you can get
your program specified in pure Prolog with constraints it is typically
easy to see that the program and solution are correct. One of the nice
things about Prolog is that you can write an *algorithm* as well as a
purely declarative description of the program. You can mix these two
fairly elegantly. You do need some understanding of both constraints
and plain Prolog execution though.

Automatic warnings are hard to generate ... AFAIK. I fear it is both
hard to define what is dangerous and to test this efficiently.

Cheers --- Jan

[Mauro DiNuzzo]

Could you give a simple example of an algorithm that can be written in pure Prolog but not in "pure" CLP?

Many thanks.

M

[Carlo Capelli]

What do you mean ? CLP(FD) is about integer (in?)finite domains, so isn't comparable to a general purpose language.
Even restricting to set of integers, we are left with list processing, and list processing algorithms are hard to express with CLP(FD).
Well, we have DCGs for that... Did I miss your point ?

[Mauro DiNuzzo]

Sorry, "pure CLP" was misleading. I am thinking about of a "hybrid" Prolog system, where standard arithmetic is *completely* replaced by CLP.

 

Such as system should understand the following goal:

?- X > 0.

as 

?- X #> 0. % for example in CLP(FD), which means X in 0..inf

and the following one:

?- X > 0.0.

as

?- {X > 0.0}. % for example in CLP(R) 

That is, depending on the context the system should be able to use the correct CLP, yet getting rid of the standard semantics, which now gives:

?- X > 0.

ERROR: >/2: Arguments are not sufficiently instantiated

Anyway, Jan argued that delayed calls would make difficult (or impossible, I do not know) the development of certain algorithms, so I asked for specific examples.

PS: It is equally possible that I am missing something, btw.

Best,

M

 

[Jan Wielemaker]

On 11/16/2015 04:47 PM, Carlo Capelli wrote:
> What do you mean ? CLP(FD) is about integer (in?)finite domains, so
> isn't comparable to a general purpose language. Even restricting to
> set of integers, we are left with list processing, and list
> processing algorithms are hard to express with CLP(FD). Well, we have
> DCGs for that... Did I miss your point ?

Well, if you can process integers, you can process anything :) The
question was also about CLP in general rather than CLP(FD). I can't make
much of the question either though. Basically, I think CLP gives you two
things

- multi-moded operation for a larger set of built-ins (notably
arithmetic, but e.g., [1]) extends this to other built-ins).
- domain dependent reasoning by considering multiple constraints
and do something smarter than enumerate and test. The typical
example is CLP(FD), which computes the new domain for a variable
that is constrained to two domains using intersection rather than
enumerate and test the domains (it does a lot more than just that).

This makes your program more declarative in the sense that the system
will reschedule (some) goals and faster because it exploits domain
knowledge. It also makes it a bit hard to predict what happens when or
how efficient something is. Another danger is that it isn't easy to
figure out whether/when all delayed goals are satisfied. There is
call_residue_vars/2 for that, but using this properly isn't that easy
either.

My $.001: if you want a theorem prover, use ASP. Prolog is a language to
write algorithms where, to a certain extend, the meaning can be derived
logically. CLP adds something in between. Very handy. It does require a
little understanding though.

Cheers --- Jan

[1] http://www.swi-prolog.org/pack/list?p=delay

>
> 2015-11-16 16:32 GMT+01:00 Mauro DiNuzzo
> <mauro....@neuroenergetics.org

> <mailto:mauro....@neuroenergetics.org>>:

[Jan Wielemaker]

On 11/16/2015 05:22 PM, Mauro DiNuzzo wrote:
> Anyway, Jan argued that delayed calls would make difficult (or
> impossible, I do not know) the development of certain algorithms, so I
> asked for specific examples.

Almost. Using delayed goals and domain-specific reasoning when
constraints are combined makes it less obvious what happens when. It is
nice to pose the problem completely declaratively and ask Prolog for an
answer. But, if the constraint system seems in a loop you have a problem.
Markus guarantees that his clp(fd) terminates, but doesn't garantee
you'll be patient enough to wait. You'll discover that sometimes it
helps to add additional (redundant) constraints or formulate the problem
differently. If you don't know the ins and outs of the constraint system
though you are mostly guessing.

This while you know an efficient algorithm to solve the problem :(
That is the time you wish you had Java/Python/... ... or Prolog! If
you use pure Prolog you know exactly what steps the system will take,
so you can write this:

?- member(X, ['I', love, 'Prolog']),
write(X), write(' '),
fail.

... and see "I love Prolog". This is dumb, but a pure logical language
will say "Hmmm. A conjunction ... I can prove it fails because one of
the conjunctives fails. --> "false". Not Prolog. It will obediently
walk the search tree depth-first, write the desired result and then say
"false".

More interesting, we can write things like merge sort, implement
balancing trees, etc. Constraints help you very little doing these jobs.
For most of these problems I prefer Prolog arithmetic that raises an
exception if I write X2 is X+1 if X is unbound as that typically
indicates a programming error. With clp(fd) I get a lot of pending
constraints and no answer. Isolated in a little program on the console
this is probably easy enough to figure out. Embedded in a larger
algorithm I may easily miss the residual goals and the unbound result
may trigger an error much later in the process.

IMHO, clp(fd) is great for combinatorial problems expressed as purely
logical relations that include integers. Once you leave this restricted
domain, the benefits are far less obvious to me.

I think I agree with Markus that using clp(fd) while introducing Prolog
has advantages as it all looks so elegant. I prefer avoiding arithmetic
for the first introduction though ...


Cheers --- Jan