Very nice CLP(FD) article by m00nlight

[Markus Triska]

Hi all,

a few months ago, I came across a really nice article by m00nlight, using CLP(FD) to solve factorial and Fibonacci tasks:

http://m00nlight.github.io/constraint%20logic%20programming/2016/01/01/using-clpfd-to-solve-factorial-and-fibonacci-problems-reversely/

This is an example of a very well researched article, containing many very good links to further information.

It is unfortunate, though at the same time understandable, that the best contributors are always too modest to post about their own work on this list. They typically set too high a standard for themselves. I wish users like m00nlight would post more. It's a short article, but one can tell that a lot of work and care has been dedicated to it.

Thank you and all the best!
Markus

[Wouter Beek]

Hi Markus,

On Fri, Mar 25, 2016 at 6:49 PM, Markus Triska <tri...@logic.at> wrote:

This is an example of a very well researched article, containing many very good links to further information.

Thanks for sharing this.

It is unfortunate, though at the same time understandable, that the best contributors are always too modest to post about their own work on this list.

The impact something has is the multiplication of (a) the inherent quality of the thing itself and (b) the effectiveness with which the thing is shared with others.  (This is why universities combine both research and teaching.)  IIUC then ATM high-value contributions are getting lost because they are not spread effectively?  If true this would be a big problem!

They typically set too high a standard for themselves.

I do not understand this reasoning: the fact that someone places a high standard on the quality of a thing does not imply that the person is unwilling to share it in early stages.  I would reason the other way round: since the quality of a thing may improve under feedback from others, a person with high quality standards would share her work often.

I wish users like m00nlight would post more. It's a short article, but one can tell that a lot of work and care has been dedicated to it.

Good point!  What concrete steps can we take to make these high-quality contributions more visible?  I will give my 2cts below but I also want to hear your ideas on this.

We have already identified that improvements are needed in the following three areas:

  - Packs  It should be very easy to share Prolog code & documentation with others.  The current SWI Pack system is a good starting point but needs to be extended upon.  Based on community suggestions I've compiled a Wiki page about this.

  - Tutorials  Much of the Prolog wisdom of the present and past can be more successfully transmitted to the new generation.  Currently I see the work of Ulrich and other Pure Prologgers on StackOverflow as the best example of how this can be done effectively today.  (I include an example of what I mean for those that may not be aware of what's going on over at SO.  The example is randomly chosen, there are literally hundreds of high-quality posts like this.)  Since SO is question-based, it is not the best place to publish a more lengthy tutorial.  In the summer I want to write a Semantic Web tutorial in SWISH.  Since many existing tutorials are already Web-based we may be able to turn them into SWISH notebooks as well.  Since they can be edited, it should be easy for others to fix/extend them.

  - Online documentation  The SWI Web site can be further improved upon.  Annie, Jessica Chan, Jan and myself did a fair attempt 2 years ago.  There are concrete suggestions for improvements from Markus.

---

Cheers!,

Wouter.

[Markus Triska]

Hi Wouter,

On Saturday, March 26, 2016 at 9:18:33 AM UTC+1, Wouter Beek wrote:

It is unfortunate, though at the same time understandable, that the best contributors are always too modest to post about their own work on this list.

The impact something has is the multiplication of (a) the inherent quality of the thing itself and (b) the effectiveness with which the thing is shared with others.  (This is why universities combine both research and teaching.)  IIUC then ATM high-value contributions are getting lost because they are not spread effectively?  If true this would be a big problem!

This is definitely the case. The biggest asset currently in existence for teaching, learning and debugging Prolog (i.e., a teleteaching environment called GUPU) is not even publicly accessible! Ulrich has lost interest in porting this to SWI-Prolog due to its nonconformance to ISO. Even before that, the primitive reactions he often got when sharing his work were too much of a distraction from the work he is doing, so he simply stopped posting on the SWI mailing list.
 

I do not understand this reasoning: the fact that someone places a high standard on the quality of a thing does not imply that the person is unwilling to share it in early stages.  I would reason the other way round: since the quality of a thing may improve under feedback from others, a person with high quality standards would share her work often.

Definitely true, and m00nlight has also done this. Just not on this list. Why not, even though m00nlight has in fact previously posted, on this very list, a very good question while researching this same article? Of course only m00nlight can answer this, though maybe it is something worth thinking about regardless.

I wish users like m00nlight would post more. It's a short article, but one can tell that a lot of work and care has been dedicated to it.

Good point!  What concrete steps can we take to make these high-quality contributions more visible?  I will give my 2cts below but I also want to hear your ideas on this.

Many high-quality posters stopped participating when the SWI mailing list was moved to a Google group. I find this extremely unfortunate. In particular, we have lost one of the world's most famous and highly regarded Prolog programmers, Richard O'Keefe, certainly at least in part also due to this move. My first suggestion is therefore to move back to a mailing list that has a chance to attract such contributors again.

People are more willing to share high-quality material when at least a significant fraction of the community is actually capable of understanding and appreciating it, and then discusses it in a way that lives up to its quality.
 

We have already identified that improvements are needed in the following three areas:

  - Packs  It should be very easy to share Prolog code & documentation with others.  The current SWI Pack system is a good starting point but needs to be extended upon.  Based on community suggestions I've compiled a Wiki page about this.

One issue I noticed is that everyone calls this "packs", but the link on the homepage is still labeled (Downloads ->) "Add-ons". My first suggestion is to call the link Downloads->"Packs" or "Packs (add-ons)", or something in that direction.
 

  - Tutorials  Much of the Prolog wisdom of the present and past can be more successfully transmitted to the new generation.  Currently I see the work of Ulrich and other Pure Prologgers on StackOverflow as the best example of how this can be done effectively today.  (I include an example of what I mean for those that may not be aware of what's going on over at SO.  The example is randomly chosen, there are literally hundreds of high-quality posts like this.)  Since SO is question-based, it is not the best place to publish a more lengthy tutorial.  In the summer I want to write a Semantic Web tutorial in SWISH.  Since many existing tutorials are already Web-based we may be able to turn them into SWISH notebooks as well.  Since they can be edited, it should be easy for others to fix/extend them.

Definitely thumbs up! You are a great writer, and I am looking very much forward to reading your text.

There are a great many things I would also like to say about Prolog, regarding data structures, logical purity, declarative properties, naming, constraints etc., and I am looking forward to seeing how effective a SWISH tutorial can be for the material you will convey. Currently, I'm leaning towards the direction that an ordinary PDF could be even more effective for the things I would like to say, and seeing a good SWISH tutorial about the material that you will cover would therefore be very valuable.

All the best!
Markus

[Wouter Beek]

Hi Markus,

Even before that, the primitive reactions he often got when sharing his work were too much of a distraction from the work he is doing, so he simply stopped posting on the SWI mailing list.

Sorry to hear that.  My explanation would be that SWI attracts a more heterogeneous group of programmers than other Prologs.  Some users want to work on improving the declarative aspects of the language, while others want to build a cool Web site (and all usage scenario's in between these two extremes).

Users in the latter group may not always understand some of the stuff that is brought up by users in the former group.  This is not really a problem IMO, as long as people appreciate that many theoretic contributions are required in order to, for instance, build better Web sites.
 

Many high-quality posters stopped participating when the SWI mailing list was moved to a Google group. I find this extremely unfortunate. In particular, we have lost one of the world's most famous and highly regarded Prolog programmers, Richard O'Keefe, certainly at least in part also due to this move. My first suggestion is therefore to move back to a mailing list that has a chance to attract such contributors again.

I will pick up this point in a separate mail.

People are more willing to share high-quality material when at least a significant fraction of the community is actually capable of understanding and appreciating it, and then discusses it in a way that lives up to its quality.

Agreed.  But as I mention above, the fact that SWI positions itself WRT a very wide audience of programmers of different types and traits will inevitably be reflected in discussions on its mailinglist having varying level as well.

We have already identified that improvements are needed in the following three areas:

  - Packs  It should be very easy to share Prolog code & documentation with others.  The current SWI Pack system is a good starting point but needs to be extended upon.  Based on community suggestions I've compiled a Wiki page about this.

One issue I noticed is that everyone calls this "packs", but the link on the homepage is still labeled (Downloads ->) "Add-ons". My first suggestion is to call the link Downloads->"Packs" or "Packs (add-ons)", or something in that direction.

I will pick this one up in a separate mail as well.

---

Cheers!,

Wouter.

[Michael BEN YOSEF]

On Saturday, 26 March 2016 14:09:11 UTC+2, Wouter Beek wrote:

Hi Markus,

Even before that, the primitive reactions he often got when sharing his work were too much of a distraction from the work he is doing, so he simply stopped posting on the SWI mailing list.

Sorry to hear that.  My explanation would be that SWI attracts a more heterogeneous group of programmers than other Prologs.  Some users want to work on improving the declarative aspects of the language, while others want to build a cool Web site (and all usage scenario's in between these two extremes).

Users in the latter group may not always understand some of the stuff that is brought up by users in the former group.  This is not really a problem IMO, as long as people appreciate that many theoretic contributions are required in order to, for instance, build better Web sites.

I strongly agree with Wouter here. I thought I'd stay quiet, but since this is coming up now, I want to weigh in.

Markus, language such as the following is condescending and divisive:

Like little children, many Prolog users currently enjoy eating the raw dough.

My hope is that when they grow up, they will appreciate the finished pizza in the form of the fully baked pure Prolog constructs that we are making available.

 
There is no need to divide the Prolog community into "children" who shouldn't be allowed near impure constructs and "adults" such as you who are trying to save the "children" from themselves. If you think everyone who disagrees with you is automatically just a "child", then you have not finished "growing up" yourself.

Can we not please stop slinging mud at each other and instead foster a unified Prolog community? Just an idea.

Kind regards,

A "child"

[Julio Di Egidio]

+1, and the main reason why I am not anymore around here.

Not to mention, as a matter of fact, that declarative uber alles is *utterly wrong*: declarative is a proper subset of computation, not the other way round.

Julio

[Markus Triska]

Hi Michael,

On Saturday, March 26, 2016 at 3:47:27 PM UTC+1, Michael BEN YOSEF wrote:

 

Sorry to hear that.  My explanation would be that SWI attracts a more heterogeneous group of programmers than other Prologs.  Some users want to work on improving the declarative aspects of the language, while others want to build a cool Web site (and all usage scenario's in between these two extremes).

Users in the latter group may not always understand some of the stuff that is brought up by users in the former group.  This is not really a problem IMO, as long as people appreciate that many theoretic contributions are required in order to, for instance, build better Web sites.

I strongly agree with Wouter here. I thought I'd stay quiet, but since this is coming up now, I want to weigh in.

I also strongly agree with what Wouter has said. Like you, I thought I'd stay quiet, and also like you, I want to weigh in:

Users in the latter group [= wanting to build cool Web sites] may not always understand some of the stuff that is brought up by users in the former group [= wanting to work on improving the declarative aspects of the language]. This is not really a problem IMO, as long as people appreciate that many theoretic contributions are required in order to, for instance, build better Web sites.

I fall heavily in the latter and former group, and it is precisely my experience that many people in the latter group (= building cool Web sites) would benefit a lot from learning more about the declarative aspects and theoretic contributions that are required to build better Web sites. I hope that the CLP(FD) article I shared in my original post helps people in the latter group to understand such aspects better. m00nlight has done an excellent job explaining some of these features. Keep up the good work!

Regarding the tone on the mailing list, I am also fed up with it and will move to SICStus in the future, where the user base and discussions are much more civilized. Before that though, I have one major remaining thing I need to do in SWI: Improve library(simplex). If time permits, I will also port cTI to SWI, but only if verify_attributes/3 is available at the time I need it for CLP(Q).

All the best,
Markus

[Wouter Beek]

Hi Michael, Julio, Markus, others,

You say that you agree with me, but let me elaborate a bit on what I meant to say :-P

If you look at many of the other Prologs out there then you will likely encounter a different -- and in many ways better -- tone there, because the audience is oftentimes much more homogeneous.  If a community is homogeneous then it is no wonder why communication is effortless: the parties involved largely share the same set of competencies and values.

Compared to that, the SWI community is almost like the rough neighborhood in Prolog Town ;-)  It is used by commercial, hobbyist, and academic users alike, all with their own preconceptions and ways of expressing themselves.  As such, it is only natural that not all discussions are at the same level of proficiency.  At the same time, SWI is one of the most promising attempts to bring Logic Programming to a wider audience.  It offers CLP(FD), CHR etc. in combination with multi-threading, a HTTP server, JavaScript quasi-quoting, etc.  You can build large-scale applications that run as a Web Service, integrate with existing infrastructures and that have thousands of users, while benefiting from using declarative approaches.

The benefit of having a heterogeneous user base IMO is that it provides better opportunities to transfer knowledge about Logic Programming from one user group to another.  I think that this is what we should focus on in SWI.

---

Cheers!,

Wouter.

On Sat, Mar 26, 2016 at 6:19 PM, Markus Triska <tri...@logic.at> wrote:

Hi Michael,

On Saturday, March 26, 2016 at 3:47:27 PM UTC+1, Michael BEN YOSEF wrote:

 

Sorry to hear that.  My explanation would be that SWI attracts a more heterogeneous group of programmers than other Prologs.  Some users want to work on improving the declarative aspects of the language, while others want to build a cool Web site (and all usage scenario's in between these two extremes).

Users in the latter group may not always understand some of the stuff that is brought up by users in the former group.  This is not really a problem IMO, as long as people appreciate that many theoretic contributions are required in order to, for instance, build better Web sites.

I strongly agree with Wouter here. I thought I'd stay quiet, but since this is coming up now, I want to weigh in.

[Jan Burse]

Hi Julio Di Egidio, do you mean a challenge like this:

http://stackoverflow.com/questions/36264421/clpfd-ying-simultaneous-recursion-for-fibonacci-lukas-numbers-possible

[Julio Di Egidio]

On Monday, March 28, 2016 at 3:33:54 PM UTC+1, Jan Burse wrote:

Hi Julio Di Egidio, do you mean a challenge like this:

http://stackoverflow.com/questions/36264421/clpfd-ying-simultaneous-recursion-for-fibonacci-lukas-num/bers-possible

"declarative is a proper subset of computation"

Only an idiot and troll as you are would see a challenge there.

Julio

[Wouter Beek]

Hi Julio,

On Mon, Mar 28, 2016 at 6:22 PM, Julio Di Egidio <ju...@diegidio.name> wrote:

On Monday, March 28, 2016 at 3:33:54 PM UTC+1, Jan Burse wrote:

Hi Julio Di Egidio, do you mean a challenge like this:

http://stackoverflow.com/questions/36264421/clpfd-ying-simultaneous-recursion-for-fibonacci-lukas-num/bers-possible

I certainly think Jan's question on SO is challenging.  Why do you disagree?

Cheers,

Wouter.

[Julio Di Egidio]

Challenging what exactly?

Julio

[Julio Di Egidio]

On Saturday, March 26, 2016 at 7:19:26 PM UTC, Wouter Beek wrote:

Hi Michael, Julio, Markus, others,

You say that you agree with me, but let me elaborate a bit on what I meant to say :-P

If you look at many of the other Prologs out there then you will likely encounter a different -- and in many ways better -- tone there, because the audience is oftentimes much more homogeneous.  If a community is homogeneous then it is no wonder why communication is effortless: the parties involved largely share the same set of competencies and values.

Compared to that, the SWI community is almost like the rough neighborhood in Prolog Town ;-)  It is used by commercial, hobbyist, and academic users alike, all with their own preconceptions and ways of expressing themselves.  As such, it is only natural that not all discussions are at the same level of proficiency.  At the same time, SWI is one of the most promising attempts to bring Logic Programming to a wider audience.  It offers CLP(FD), CHR etc. in combination with multi-threading, a HTTP server, JavaScript quasi-quoting, etc.  You can build large-scale applications that run as a Web Service, integrate with existing infrastructures and that have thousands of users, while benefiting from using declarative approaches.

The benefit of having a heterogeneous user base IMO is that it provides better opportunities to transfer knowledge about Logic Programming from one user group to another.  I think that this is what we should focus on in SWI.

The general sentiment here is commendable, but you are not faithful to it: your emphasis remains on declarative, which is what has been criticised here (and not just by me).

Julio

[Wouter Beek]

On Mon, Mar 28, 2016 at 6:43 PM, Julio Di Egidio <ju...@diegidio.name> wrote:

Challenging what exactly?

Ah the SO page with the question on it is offline right now :-(  But since you were expressing a strong opinion on the topic I was assuming you would also have strong arguments to match that opinion.

Cheers!,

Wouter.

[Wouter Beek]

Hi Julio,

On Mon, Mar 28, 2016 at 6:49 PM, Julio Di Egidio <ju...@diegidio.name> wrote:

your emphasis remains on declarative

That is true.
 

, which is what has been criticised here (and not just by me).

Can you give a concrete argument for that?  I generally believe that the declarative nature of Prolog programs is a huge benefit, e.g. when building KR systems.

I do agree with a point you earlier raised in another thread that there is a point where declarative programming may no longer be considered beneficial to most programmers.  You mentioned Computability Logic in that context.  Similar things may hold for formal proof languages like Isabel and Coq.  However, I do not believe that this is generally the direction in which Pure Prolog is heading ATM (but I may be wrong in this?).

---

Cheers!,

Wouter.

[Julio Di Egidio]

On Saturday, March 26, 2016 at 7:19:26 PM UTC, Wouter Beek wrote:

> it is only natural that not all discussions are at the same level of proficiency.

And I take exception to that in particular, which is another side of the recurring presumption that has been denounced, that some disciplines are more knowledgeable than others.  For example, the difference between engineering and computer science has nothing to do with "levels of proficiency": different disciplines have different goals, principles, and practices, and rather interesting is to understand the distinctions as well as the interrelationships, and the interdisciplinarity.  I take you still think there are some who know better...

Julio

[Julio Di Egidio]

A "challenge" was introduced by Jan Burse: what is it, in snipping systematically what others say you cannot even keep track of yourself?

Try and be honest, that's the starting point.

Julio

[Julio Di Egidio]

Yes, look up Computability Logic (CL) and you'll get an actually complete picture (at the state of the art) of what Logic Programming (LP) entails: you'll find out not only that declarative is just part of computability, which itself should be pretty obvious, but also exactly why and how, as CL encompasses classical as well as intuitionistic and constructive logics and more.

There is also a paper at the frontier of theory and application that I'd like to mention, although it is not as directly related: "Out of the tar pit", about actual software construction and what matters for keeping complexity under control.

As for the future of Logic Programming, one thing is what I have just said, CL and what else is there, another is the resistance of the existing LP communities such as this one not to stay stuck into the mythology they have built for and around themselves...  Guess who'll win...

Good luck,

Julio

[Jan Burse]

Computer science (CS) would help to estimate the runtime, when running algorithms
backward via CLP(FD). In the present case we have a branching, if the CLP(FD)
cannot do its work.

Its a branching of either 2n->n or n+1->n. if the solver does not have n yet instantiated,
he must try both branches.

So what can we expect when we for example try to find n when Fn given and n=100?
There are now conflicting claims apperaing on the web.

Lurker claims:

?- time((fibluc(100, X, Y), fibluc(N, X, Z))).
% 11,337,988 inferences, 3.092 CPU in 3.100 seconds (100% CPU, 3666357 Lips)

I cannot reproduce this result neither for SWI 7.3.19, 7.2.3 and 6.5.2. What sense would it make
to fake a result on stack overlow? Maybe its a misunderstanding, and he was testing with a linear
algorithm, like in the original thread.

So far, its probably galactic time needed to compute the 100 problem. At least I get on my
fasted machine strangely a very low LISP, maybe some non-linear effects of the CLP(FD).
Was using the newest SWI 7.3.19:

?- time((fibluc(100, X, Y), fibluc(N, X, Z))).
Action (h for help) ? abort
% 247,887,134 inferences, 3070.989 CPU in 3072.519 seconds (100% CPU, 80719 Lips)
% Execution Aborted

But judignung from the number of inferences, we have indeed long passed the claimed 3 secs.

Bye

[Jan Burse]

> Its a branching of either 2n->n or n+1->n. if the solver does not have n yet instantiated,
> he must try both branches.

A further complication is of course the L, the lucas number is also not instantiated,
giving way to very large ranges of F or difficult number theoretic considerations.

So its basically an example designed to not work in backward CLP(FD) execution.

Bye

SWI-Prolog is currently the only candidate to run it.
In SICStus Prolog I get very quickly the following error:

| ?- fibluc(10, X, Y), fibluc(N, X, Z).
! Representation error in user:scalar_product/4
! CLPFD integer underflow
! goal:  scalar_product([1,5,-1],[_203,_207,_211],#=,0)

And the Jekejeke CLP(FD) will probably never run it as well,
since by design it has asymmetric interval propagation.

But I didn't do this design to prevent people doing fib, etc..
via CLP(FD), but it will have this effect in the future. LoL

[Carlo Capelli]

The whole issue is intriguing, and related to what I already experienced while testing CLP(FD) on some Project Euler questions.

FWIW, I can confirm Lurker experience.

Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 7.3.19-1-g61ad21b-DIRTY)...

Using his second version

?- time((fibluc(100, X, Y), fibluc(N, X, Z))).

% 10,070,701 inferences, 4.728 CPU in 4.738 seconds (100% CPU, 2130238 Lips)

X = 354224848179261915075,

Y = Z, Z = 792070839848372253127,

N = 100 ;

% 1,415,320 inferences, 0.615 CPU in 0.619 seconds (99% CPU, 2301332 Lips)

false.

The first version (with tail recursion) takes too long:

?- between(30,50,I), time((fibluc(I, X, Y), fibluc(N, X, Z))), writeln(I), fail.

% 3,555,184 inferences, 1.777 CPU in 1.782 seconds (100% CPU, 2000351 Lips)

30

% 4,159,367 inferences, 2.049 CPU in 2.073 seconds (99% CPU, 2029484 Lips)

% 900,317 inferences, 0.477 CPU in 0.482 seconds (99% CPU, 1889168 Lips)

31

% 20,585,667 inferences, 15.887 CPU in 15.934 seconds (100% CPU, 1295733 Lips)

...

% 59,988,012 inferences, 122.686 CPU in 123.458 seconds (99% CPU, 488955 Lips)

38

% 186,506,766 inferences, 411.913 CPU in 415.725 seconds (99% CPU, 452782 Lips)

% 1,408,922 inferences, 0.678 CPU in 0.681 seconds (100% CPU, 2076652 Lips)

39

... still running...

Al least for monotonic sequences, I would rather discourage newbies (ab)using of CLP(FD)...

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

[Markus Triska]

Hi Carlo,

Al least for monotonic sequences, I would rather discourage newbies (ab)using of CLP(FD)...

This conclusion is not warranted from the known premises. I have seen identical or similar fallacies many times on this list, and I would like to address them one more time. This is in no way meant as attacking you personally, and not meant to be condenscending in any way. In fact, I am mostly writing this because it is you who is posting. With other users, I would not even bother to read their posting, let alone reply to their nonsense. I am going into more details than would be necessary for you, because I have seen the fallacy from several posters, including some (like you) who I am holding in very high regard, and I can see how the fallacy is somewhat understandable because it involves things that are not taught in freely available teaching material.

In particular, the fallacy consists in erroneously concluding from the following true premises:

1. we have a fast program A involving (is)/2
2. we know that replacing (is)/2 by the CLP(FD) constraint (#=)/2 incurs at most a factor 2 of performance penalty
3. we have a slow program B involving (#=)/2

the obvisouly wrong statement (or something to this effect):

CLP(FD) constraints should not be used.

The fallacy here is typically that the slow program B was specifically not obtained by simply replacing (is)/2 by (#=)/2, but instead was often obtained by a more complex rewriting of A in the hope to make it much more general.

It is often not clear how to obtain a more general program from A, whether using CLP(FD) constraints or not (!), but one thing is clear:

If you simply replace (is)/2 by (#=)/2, then program A will still run acceptably fast in almost all cases, and certainly in all programs written by beginners.

This is the use of CLP(FD) constraints I'm primarily advocating for now: Simply use CLP(FD) constraints to replace lower-level arithmetic predicates over integers. You can only benefit from this. The community is currently not ready for more. In fact, it may regard already this observation as condenscending! My vision for CLP(FD) constraints goes much further than what is currently possible with the present SWI community, and I would like to proceed much faster than what we are doing currently. I have given it an honest attempt with SWI. I'm ready to try my luck with SICStus now, and let SWI catch up with what SICStus will do in that respect.

Future developments of library(clpfd) will take place with SICStus Prolog as the primary target.

All the best,
Markus

[Roberto Bagnara]

On 03/26/2016 06:19 PM, Markus Triska wrote:
> Regarding the tone on the mailing list, I am also fed up with it and
> will move to SICStus in the future, where the user base and
> discussions are much more civilized.

Hi there.

I am replying to this message, even though there have been many,
more disturbing messages in the mailing list.

I would like to encourage anyone to please stop all silly language
wars. SWI-Prolog supports different styles of programming and,
at the end of the day, anyone is entitled to choose a fragment
of the language and be happy with it. It is OK to gently point out
alternative solutions to specific problems and provide arguments
about their pros and cons. It is not OK to let such discussions
degenerate into religious battles and name calling. As far as
I know, the SWI-Prolog community is a very pragmatic one, and I would
be surprised if more than 1% of it is interested in the philosophy
of computing: people who are interested in such topics should
consider moving to another mailing list, especially if they
cannot resist the temptation of flaming.

Now, for Markus and all others who said they will move or they will
stop participating and so on: please don't.
As far as I know the mailing lists of all the other Prologs have more
civilized discussions only in the sense that they have no discussions.
Number of messages in 2016: Ciao: 1, GNU Prolog: 8, SICStus: 3,
SWI-Prolog: 273; XSB: 3; YAP: 17.
I have a debt of gratitude with respect to *all* these Prolog systems,
but this does not change reality; it is not just a matter of mailing
list traffic: SWI-Prolog is the only Prolog system that, today, can
be properly said to be alive and kicking (I wish the others will catch
up, but until then...).

So let us stop any behavior that might divide us and, to the contrary,
let us multiply efforts to unite the community.
Kind regards,

Roberto

--
Prof. Roberto Bagnara
Applied Formal Methods Laboratory
Department of Mathematics and Computer Science, University of Parma, Italy
http://www.cs.unipr.it/~bagnara/
mailto:bag...@cs.unipr.it

[Jan Burse]

The test case aka challenge is about changing
the mode of a predicate via CLP(FD).

The test case aka challenge is not about keeping the
mode of a predicate and replacing is/2 via CLP(FD).

What Julio has said in a rough tone and propably
only intuitively, is probably well known in CS.

You cannot so easily change the mode of a predicate.
Here is a simple proof:

     Take a predicate:
     % turing_step(+Integer, +Integer, -Integer)

     With the following spezification:
     turing_step(C, S, B):
     The predicate succeeds for the turing machine C excuting S
     steps and arriving at band B.

So far so good. You can code this with is/2. You can also code
this with CLP(FD) (#=)/2. But you can't certainly invert in certain
arguments with CLP(FD). If you invert it for example for the step
argument you get the HALTING PROBLEM:

       Its then the predicate:
       % turing_step(+Integer, -Integer, +Integer)

       This tries to find a setp S where the turing machine C
       arrives at band B.

This is just a rough sketch that changing the mode is far from
only beeing related to CLP(FD). So comming back to the test
case aka challenge. I have the feeling in Markus Triska answer
there was a total ingnorance of the problem of inversion. I find
not a single reference in his answer to this problem.

Most likely Markus Triska overlooked that the test case aka
challenge is posed in this direction by me. I have the feeling
Lurker who produced a solution grapsed the problem very
well. He wrote that he was posing a "compound" query.

But basically this "compound" query is just there to safe
typing, but what we pose is an inversion problem. Namely
we first go from n to Fn, and then ask the interpreter to go
back from Fn to n. Look see, the "compound" query is:

     ?- fibluc(100, X, Y), fibluc(N, X, Z).
                    n ---> Fn           n <-- Fn

So we arrive in X at a value Fn, and we call fibluc/3 again
to see whether the CLP(FD)-ification can determine n again,
in an inverse fashion. This is the core of the test case aka
challenge posed by me. Nothing else and nothing more. No
Obama Care Politics, no nothing.

Hope this helps. There is no intention what ever to sling mud
at anybody. This challenge is not ad hominen. Its about a reflection
what we are doing when we CLP(FD)-ing a predicate, and what
hopes are connected with such CLP(FD)-ing a predicate.

The original moonlight article shows a case where such CLP(FD)-ing
leads to a predicate that also shows seemingly some good behaviour
when used in another new mode which was not possible with is/2.
The new mode was made possible by simply using (#=)/2.

But the test case aka challenge is,
     What are the limits of this method?

There is only one answer so far on SO, and I think the answer shows that
for the given example CLP(FD)-ing fails. The problem is that the question
is not yet elaborated enough. There should be more answers. And
it will probably take 1-2 years until good answers will pop-up. Might
also try the same answer slightly re-wrapped in MO (Math Overflow)
and CS (Computer Science).

How such a harmless question could divide a community is a mistery
to me. Must be a very fragile community. I think the community should
take the chance to discuss such methodological issues early on, before
it has produce dozens of "pragmatic" blog posts, that give a totally wrong
picture of certain technologies.

It could be also the case that the ability of defining predicates via
CLP(FD) is only good enough for defining something along a kind
of macros. Like expanding a sum predicate or some such. The ability
to define predicates in CLP(FD) has certainly this application area. There
is no doubt that the combination of CLP(FD) and Prolog has this unique
benefit which other systems can hardly reach.

Everybody can make the test by himself. Checkout SAS Solver or MiniZinc
etc.. You have to learn a new language which is often a little bit strange.
By the genuis integration of CLP(FD) via attribute variables, one has to
learn little less new. We can all stick to our beloved Prolog. There are attempts
such as Picat, which really try to sell us that we are doing wrong sticking
to Prolog when integrating CLP(FD).

But still we should be very careful with our claims. I am not sure whether
SAS Solver or MiniZinc also aim at general inversion of predicates when
they provide integration. Maybe a more seasoned view would tells us,
well we could gain more if we would improve the array and CLP(FD) integration,
in contrast of speculating on general invertibility of predicates. There could
be a really quite big list of improvement suggestions coming!

Bye

[Jan Burse]

Anyway, don't worry, be happy:

NEW YORK - A public school teacher was arrested today at JFK
International Airport as he attempted to board a flight while in
possession of a ruler, a protractor, a set square, a slide rule and a
calculator.

At a morning press conference, Attorney General Gonzales said he
believes the man is a member of the notorious Al-gebra movement. He
did not identify the man, who has been charged by the FBI with carrying
weapons of math instruction. "Al-gebra is a problem for us," Ashcroft
said. "They desire solutions by means and extremes, and sometimes go
off on tangents in a search of absolute value.

They use secret code names like 'x' and 'y' and refer to themselves as
'unknowns', but we have determined they belong to a common
denominator of the axis of medieval with coordinates in every country.

As the Greek philanderer Isosceles used to say, 'There are three sides
to every triangle'." When asked to comment on the arrest, President Bush
said, "If God had wanted us to have better weapons of math instruction,
He would have given us more fingers and toes."

White House aides told reporters they could not recall a more
intelligent or profound statement by the president.

[Markus Triska]

Hi Jan,

The test case aka challenge is about changing
the mode of a predicate via CLP(FD).

Yours is a good test case and challenge, and I am confident that the Stackoverflow community will yield valuable inputs, if not immediately, then certainly in due time. The essence of your test case has not gone unnoticed by me. However, I assure you that what you are asking has a better chance to be resolved on Stackoverflow than on the SWI mailling list.

I find this somewhat ironic, given that often SWI-Prolog's CLP(FD) system is used in Stackoverflow answers, and a dedicated or complementary discussion on the SWI mailing list would have been very appropriate and useful for several questions. However, experience has repeatedly shown us that it is almost impossible to carry out a sensible discussion about CLP(FD) on the SWI mailing list. Please see the previous threads about CLP(FD) on this list.

Your test case is way beyond the level of exchange that is the norm here regarding constraints. In short, you are asking how to use CLP(FD) constraints so that a computation can be made more general. The discussion we are used to on this list is more like whether to even start using CLP(FD) constraints. This discrepancy is not surprising: Please take into account that you are yourself an implementor of a CLP(FD) system, talking here to many users who will likely remain far removed from constraints for the forseeable future.

The interesting question, to me, is: Which further CLP(FD) constraints, propagations and language constructs are necessary to make computations such as yours easy to express, general and efficient? I am currently looking for good places to discuss such issues. A few years ago, the SWI mailling list was a good place to do it. Now, Stackoverflow is good candidate.

All the best,
Markus

[Jan Burse]

The future is always difficult to predict, except if you invent it.
So try harder to make it accessible to everybody. Including usage
of the SWI-Prolog mailing list for this purpose.

Don't give up so quickly! Keep on the good work!

[Jan Burse]

Hi,

Today CAS (Computer Algebra Systems) are everywhere, in the
poket calculator, on the web, etc.. For example I was recently
cross checking via WolframAlpha some CLP(*) problems.

Here is what it is doing for f(0)=0, f(1)=2, f(n+1)=f(n)+f(n-1)
http://www.wolframalpha.com/input/?i=f%280%29%3D0,+f%281%29%3D2,+f%28n%2B1%29%3Df%28n%29%2Bf%28n-1%29

Quite amazing. In the future your children will know more about
CAS than you yourself when you were this young. The problem
is not the level of the others, the problem is the level of us and
keeping up with providing excellent tools!

Don't forget the world is always spinning.

Bye

[Jan Burse]

There is certainly a little overlap of CLP(*) and CAS. So over
the last days, I step on a lot of CATS.

What is a CATS? its a Computer Algebra Test Suite.
Here is an example:
http://axiom-developer.org/axiom-website/CATS/index.html

But not yet sure whether anything of this can be used for CLP(*).

[Jan Wielemaker]

Thanks Roberto,

Well spoken!

As of day one, the aim of SWI-Prolog was to have a Prolog implementation
that aims at practical usage, notably involving communication to humans
as well as other IT components. I think it was (one of the) first systems
to support Prolog -> C -> Prolog -> C ... calls and an extensive GUI
system. Right now, I think it is the Prolog implementation with the
richest interface to external resources (languages, data formats) and
the richest web infra structure. This has always been my primary focus.
In the meanwhile, others have stressed the `pure' aspects. I'm grateful
to that as it brought us notably constraints, which can be hugely useful
in some scenarios. The result is a system that is not particularly good
at anything but is, IMHO, pretty versatile.

All this has been made possible by many contributors. Think of JPL (Paul
and Fred), Pengines (Torbjorn), attributed variables (Tom and Bart),
cylic terms support (Bart, Ulrich), Safe and concurrent atom-GC (Keri),
CHR (Tom), CLP(Q,R) (Leslie), CLP(FD,B) (Markus), recent RDF 1.1
(Wouter), Quasi Quotations (Michael), web site, tutorials (Anne et al.),
CQL (Matt, Mike), SSL (Jan, Matt) stability issues (Ulrich), Logtalk,
yall (Paulo), Fast and correct term variance (Kuniaki) sponsored
developments (PlUnit, PlDoc, ODBC, unbounded arithmetic, avoid
C-recursion, dynamic stack management, safe concurrent reloading, ...),
etc. (sorry to all those I forgot).

I'm deeply grateful to all of these people who generously spent their
time to contribute or trusted me enough to sponsor a project. I've met
slightly over half of the prime contributors. I know many of these
people have a completely different opinion on the role of logic
programming in general and Prolog in particular. I think it is a big
virtue to have all these people united around one system. Please
remember there is no single truth and respect each other.

Sorry for the preach ...

Cheers --- Jan

[Jan Burse]

So besides the pathetic preaching of Jan. W. and given the fact that the
moonlight post and my challenge has a very narrow scope, namely
the title of the moonlight blog is indeed "Running program backward in
logic programming".

You wrote:

Am Dienstag, 29. März 2016 17:25:25 UTC+2 schrieb Markus Triska:

Your test case is way beyond the level of exchange that is the norm here regarding constraints.

In short, you are asking how to use CLP(FD) constraints so that a computation can be made

more general.

What do you mean by made more general? Do you think that more
general is the same as inverting a computation?

Do you think that SAS Constraint language and other constraint
languages use also the integration of constraints to make things
more general?

I mean I see that people have become hysteric in relation to the
SWI-Prolog mailing list, maybe because the sommertime switch and
not enough sleep.

But is killing a simple discussion midway for such pretentious
reasons a way to avoid to give a more thorough characteriszation
of the busines cases of CLP(FD) or the pros and cons of running
programs backward?

Why was carlo's vote killed. Thats not right. Either you post a
blog post on the SWI-Prolog mailing list and let the discussion flow
as long as it flows. Or you shut down the whole SWI-Prolog
mailing list forever.

[Jan Burse]

> What do you mean by made more general? Do you think that more
> general is the same as inverting a computation?

Generalizing can be often done inside existing mode bounds. Some
mode systems also allow expressing this. Think also of the ISO templates.

The typical means to do this: The Prolog variable. Think of steadfastness
of DCG, i.e. some "generalizing" the list output parameter.

Benefit of CLP(FD)? Who knows?

[Jan Burse]

CLP(FD) Benefit for Generalizing could be explained that we
don't need to go Peano Arithmetic.

Typically when we use Peano Arithmetic we get a lot of Generalizing
and also Invertibility for free. Here is a factorial example:

    add(n, X, X).
    add(s(X), Y, Z) :- add(X, s(Y), Z).

    mul(n, X, n).
    mul(s(X), Y, Z) :- mul(X, Y, H), add(Y, H, Z).

     fac(n, s(n)).
     fac(s(X), Y) :- fac(X, H), mul(s(X), H, Y).

For the mode fac(+,-), here is a specific call:

    ?- fac(s(s(s(n))), X).
    X = s(s(s(s(s(s(n)))))).


And the mode fac(-, -) also works, generalizing the
first argument:

     ?- fac(X, Y).
     X = n,
     Y = s(n) ;
     X = Y, Y = s(n) ;
     X = Y, Y = s(s(n)) ;
     X = s(s(s(n))),
     Y = s(s(s(s(s(s(n))))))  etc..

Invertibility would be a mode fac(-, +). Does this work?
Not really (so here invertibility is not given):

     ?- fac(X, s(s(s(s(s(s(n))))))).
     X = s(s(s(n))) ;
     ERROR: Out of global stack

     ?- fac(X, s(s(s(s(s(n)))))).
     ERROR: Out of global stack
 
So a lot of problem we might have with generalization and
invertibility we see already for Peano Arithmetic.

CLP(FD) is more or less another form of Peano Ariithmetic.
It does not only allow positive numbers n, s(n), s(s(n)), etc..
but also negative numbers and we can directly use the Prolog
integer atoms.

But CLP(FD) has of course much more to offer than only
add/3 and mul/3. But we can quickly arrive at a CLP(FD)
version of fac/2:

      :- use_module(library(clpfd)).
 
       fac(0, 1).
       fac(N, F) :- N #> 0, M #= N-1, fac(M, G), F #= N*G.

Now check mode fac(+, -):
 
        ?- fac(3, X).
        X = 6
        false.

Then the generalization mode fac(-, -):

     ?- fac(N, X).
     N = 0,
     X = 1
     N = X, X = 1
     N = X, X = 2
     N = 3,
     X = 6

Then the inversion mode fac(-, +):

     ?- fac(N, 6).
     N = 3 ;
      < hangs >

     ?- fac(N, 5).
     < hangs >

No additional benefit of CLP(FD). Only the number notation is
a benefit of CLP(FD) here, but it is still as stupid as Peano Arithmetic
if the code is not augmented!

I don't know whether the Peano Arithmetic and CLP(FD) version have
exactly the same reasons that they dont work for inversion, would need
to more close inspect the trace.

Augmentation of code as tne moonlight blog descirbes, to make a more
complete what concernes inversion, is this an art already documented some-
where? Just for curiousity can we also augment the Peano Arithmetic version?

What I wanted to prove here: Generalization != Inversion in my opinion.

Bye

[Julio Di Egidio]

On Wednesday, March 30, 2016 at 12:03:16 AM UTC+1, Jan Burse wrote:

 

I don't know whether the Peano Arithmetic and CLP(FD) version have
exactly the same reasons that they dont work for inversion, would need
to more close inspect the trace.

The usual approach and CLP are indeed sort of dual: essentially (as I get it), CLP works by discarding invalid solutions rather than by finding valid ones.

OTOH, I agree "invertibility" is the same for both, no difference there.  And here is some plain arithmetic that can be called with any input instantiation:

  <http://swish.swi-prolog.org/p/peano_ari.pl>

(I am also attaching here the file and the unit tests.)

The code clearly shows how the "invertibility" as well as the determinism are achieved, and how simply.

It would be interesting to see the corresponding solution in CLP.

Julio

[Julio Di Egidio]

On Wednesday, March 30, 2016 at 4:30:46 AM UTC+1, Julio Di Egidio wrote:

On Wednesday, March 30, 2016 at 12:03:16 AM UTC+1, Jan Burse wrote:

 

I don't know whether the Peano Arithmetic and CLP(FD) version have
exactly the same reasons that they dont work for inversion, would need
to more close inspect the trace.

The usual approach and CLP are indeed sort of dual: essentially (as I get it), CLP works by discarding invalid solutions rather than by finding valid ones.

OTOH, I agree "invertibility" is the same for both, no difference there.  And here is some plain arithmetic that can be called with any input instantiation:

  <http://swish.swi-prolog.org/p/peano_ari.pl>

(I am also attaching here the file and the unit tests.)

I have just realised that not all modes (of nat_add/3 in particular) actually work: I'll see if I can fix it and still keep it clean and simple...

Julio

[Jan Burse]

Hi,

Can you apply your nat_add to define a nat_mul, and then
also define a nat_fac(torial). What behaviour will the
nat_fact(torial) have?

Problem is that CLP(FD) provides a set of primities (#=)/2, etc.
which could be judged as already "invertible". But Herbrand
Unification (=)/2 is also "invertible". 

There is no reason to believe that an SMT solver (Herbrand or FD,
otra combination of both), when used in the definition of predicates,
automatically makes these predicates "inverrtible" as well.

The sum is more than its parts also works sometimes in the opposite
direction, the sum can be less than its parts. So although combining
"invertible" primitives in a predicate definition, doesn't mean the
predicate gets "invertible".

Bye

[Julio Di Egidio]

On Wednesday, March 30, 2016 at 5:36:00 AM UTC+1, Julio Di Egidio wrote:

On Wednesday, March 30, 2016 at 4:30:46 AM UTC+1, Julio Di Egidio wrote:

<snip>

And here is some plain arithmetic that can be called with any input instantiation:

  <http://swish.swi-prolog.org/p/peano_ari.pl>

(I am also attaching here the file and the unit tests.)

I have just realised that not all modes (of nat_add/3 in particular) actually work: I'll see if I can fix it and still keep it clean and simple...

I think I have fixed it.  Note that I have directly edited the attachment in the original post as well as the code on swish.

<http://swish.swi-prolog.org/p/peano_ari.pl>

<http://swish.swi-prolog.org/p/peano_ari.test.pl>

The code clearly shows how the "invertibility" as well as the determinism are achieved, and how simply.

It would be interesting to see the corresponding solution in CLP.

The code structure has 3 levels now: lowest is the basic logic; above that is determinism control depending on input instantiation; above that is input type checking.  After that, "Invertibility" sort of comes for free...

Julio

[Markus Triska]

Hi Jan,

But CLP(FD) has of course much more to offer than only
add/3 and mul/3. But we can quickly arrive at a CLP(FD)
version of fac/2:

      :- use_module(library(clpfd)).
 
       fac(0, 1).
       fac(N, F) :- N #> 0, M #= N-1, fac(M, G), F #= N*G.

Indeed!

 

Augmentation of code as tne moonlight blog descirbes, to make a more
complete what concernes inversion, is this an art already documented some-
where?

The art consists mostly in reasoning about termination properties:

Premise: Posting CLP(FD) constraints always terminates. This is guaranteed by library(clpfd)!

Conclusion: Calling CLP(FD) constraints before other goals can at most improve, never worsen termination properties.

In particular, in your case, you can simply exchange the last two goals (and also use a more relational name):

       n_factorial(0, 1).
       n_factorial(N, F) :- N #> 0, M #= N-1, F #= N*G, n_factorial(M, G).

and the cases you show now terminate:

?- n_factorial(_, 5).
false.

?- n_factorial(N, 6).
N = 3 ;
false.

Pretty straight-forward. There are many more declarative approaches that help you improve termination properties, automatically deduce (implied) constraints etc. These are the things I am interested in. They pop up when one seriously starts to think about CLP(FD) constraints and uses them in real-world tasks. They do not pop up if you quit using the library after the first time such a question develops in your mind.

Advantage of CLP(FD) constraints: Such an exchange of goals is possible. It is for example not possible with primitive integer arithmetic.

The Peano representation you show is an interesting and pure alternative to CLP(FD) constraints. Others have already impressively demonstrated that it is much harder to reason about termination properties with such a presentation though, and cumbersome to express more complex relations between integers with it. These are some of the reasons why it is justified to use CLP(FD) constraints right away, also when teaching Prolog to beginners. Personally, I have seen enough "instantiation-error" questions on Stackoverflow and other occasions by now to know that primitive arithmetic poses serious problems for beginners, and I would like to make Prolog easier to learn and teach by providing more general alternatives.

When teaching Prolog, this is only the starting point! All the interesting observations regarding termination etc. can be fully carried through, even more deeply, when employing CLP(FD) constraints. So, if you are teaching Prolog, you will still have enough to do.

All the best,
Markus

[Samer Abdallah]

Hi Julio,
You might be interested in this paper by Oleg Kiselyov:
http://okmij.org/ftp/Prolog/Prolog.html#pure-arithm

cheers,
Samer

> On 30 Mar 2016, at 10:53, Julio Di Egidio <ju...@diegidio.name> wrote:
>
> On Wednesday, March 30, 2016 at 5:36:00 AM UTC+1, Julio Di Egidio wrote:
> On Wednesday, March 30, 2016 at 4:30:46 AM UTC+1, Julio Di Egidio wrote:
> <snip>
> And here is some plain arithmetic that can be called with any input instantiation:
>
> <http://swish.swi-prolog.org/p/peano_ari.pl>
>
> (I am also attaching here the file and the unit tests.)
>
> I have just realised that not all modes (of nat_add/3 in particular) actually work: I'll see if I can fix it and still keep it clean and simple...
>
> I think I have fixed it. Note that I have directly edited the attachment in the original post as well as the code on swish.
>

> The code clearly shows how the "invertibility" as well as the determinism are achieved, and how simply.
>
> It would be interesting to see the corresponding solution in CLP.
>
> The code structure has 3 levels now: lowest is the basic logic; above that is determinism control depending on input instantiation; above that is input type checking. After that, "Invertibility" sort of comes for free...
>
> Julio
>
>

[Julio Di Egidio]

On Wednesday, March 30, 2016 at 11:26:11 AM UTC+1, Samer Abdallah wrote:

Hi Julio,
You might be interested in this paper by Oleg Kiselyov:
        http://okmij.org/ftp/Prolog/Prolog.html#pure-arithm

Hi Samer, IMHO:  It is similar to the code Jan was considering, i.e. it does not cover all real world scenarios: input might be of the wrong type, plus we want proper determinism (if there is one solution, the predicate shall succeed deterministically).  Markus's CPL code has those same limitations: as such, these solutions are not *production-level*, and in that gap again is the problem with how Prolog is conceived as well as taught...

[Julio Di Egidio]

On Wednesday, March 30, 2016 at 12:14:56 PM UTC+1, Julio Di Egidio wrote:

On Wednesday, March 30, 2016 at 11:26:11 AM UTC+1, Samer Abdallah wrote:

Hi Julio,
You might be interested in this paper by Oleg Kiselyov:
        http://okmij.org/ftp/Prolog/Prolog.html#pure-arithm

Hi Samer, IMHO:  It is similar to the code Jan was considering,

In fact, I have gone further in my implementation and have abstracted the underlying representation away, but if you reintroduce that directly inline, my nat_add__/3 is just equivalent to the add/3 Kiselyov defines at page 5...  except that I increment on the second argument while he decrements on the third, but otherwise the two solutions are exactly the same.  Rather, I add two further layers on top of that: as said, for proper determinism and input type checking.

Julio

[Jan Burse]

Hi,

Am Mittwoch, 30. März 2016 12:21:56 UTC+2 schrieb Markus Triska:

In particular, in your case, you can simply exchange the last two goals (and also use a more relational name):

       n_factorial(0, 1).
       n_factorial(N, F) :- N #> 0, M #= N-1, F #= N*G, n_factorial(M, G).

In the challenge I posted on SO, in the solution by Lurker, there is a comment by
Lurker, that when moving the recursive predicate to the end in the recursive clauses,
the recursive predicate will not produce anymore a solution for the 100 problem in
foreseeable time when using the current SWI-Prolog stable release.

He then goes on that when he keeps the position of the predicate call and doesn't
move it, on the other hand he also gets a solution for the 100 problem in what he
calls in favorable time. But this has probably to do with the fact that he limits the
solution parameter as well.

So this contradicts a little bit your recommendation. I don't know whether you have
read the solution of Lurker and noticed this contradiction?

Anyway, I don't believe that the given recipe works as such. It might work in
simple examples. But it doesn't work in the challenge I gave.

Again the challenge is to challenge the recipe. And it has many facets that
challenge the recipe.

- One challenge is that it has an additional branching,
  its not a simple recursion by one recursive clause.

- Another challenge is that it has not a simple one
  argument return value.

 Bye

[Jan Burse]

There is a further problem with Markus Triskas considerations,
he wrote the following:

> Conclusion: Calling CLP(FD) constraints before other goals can at most improve,
> never worsen termination properties.

I doubt that this is true as well. If you have a non-CLP(FD) solution that doesn't
terminate, it might improve the situation, but it might also leave the situation
untouched and still not terminate.

I am speaking here of the un-augmented code. I am speeking of code where only
the recursive predicate call in the recursive clause is moved to the end. This is
important since the moonlight blog post is refering to a totally differrent scenario:

- Possibly moving the recursive predicate call to the end.
- Possibly also inserting additional constraints.

In my opinion moving the recursive predicate call to the end doesn't guarantee
termination. Because you are using CLP(Z) and not CLP(N). So the parameter
you are seeking can still somehow infinitely decend even in terms of constraints.

On the otherhand when additional constraints are inserted, of course you can
limit the parameter that you are seeking. But since you start with an unknown
parameter that you are seeking there must be some interaction with the
given parameter.

The challenge I posted shows in my opinion that this interaction by CLP(FD)
is generally to weak to give a good solution. And it should be noted that
I am using an increasing number function example, which usally has very
simple traditional solution approachs such as bisection, upward search etc..

Bye

[Jan Burse]

Am Mittwoch, 30. März 2016 15:43:15 UTC+2 schrieb Jan Burse:

In my opinion moving the recursive predicate call to the end doesn't guarantee
termination. Because you are using CLP(Z) and not CLP(N). So the parameter
you are seeking can still somehow infinitely decend even in terms of constraints.

It will have some borders, from the recursive clause itself, such as N #> 0
in the factorial example. But since we are dealing with constraints, the constraint
store might nevertheless grow and grow.

Pitty I don't have not yet a command in Jekejeke to show the constraints in the
debugger when I am tracing a goal, otherwise I could show what is happening.
Maybe I should figure out whether SWI-Prolog has such a facility.

No time yet, everything is fresh... was experimenting with copy_term/3 inserting
into the code, but this flooded my screen.

Bye

[Jan Burse]

One last remark concerning:

> He then goes on that when he keeps the position of the predicate call and doesn't
> move it, on the other hand he also gets a solution for the 100 problem in what he
> calls in favorable time. But this has probably to do with the fact that he limits the
> solution parameter as well.

In hindsight Lurker suggested from the beginning in his solution to
combine the limiting of the seeked parameter by some iterative deepening
search.

The drawback of adding a fixed limit for the seeked parameter are obvious.
You can only invert the predicate for given parameters where the seeked
parameter is inside this limit.

If the seeked parameter is outside the limit, you could of course use
some additional methods that would gradually elarge the limit, until
a solution is found.

But such is Lurkers solution...

Bye

[Jan Burse]

Am Mittwoch, 30. März 2016 15:43:15 UTC+2 schrieb Jan Burse:

There is a further problem with Markus Triskas considerations,
he wrote the following:

> Conclusion: Calling CLP(FD) constraints before other goals can at most improve,
> never worsen termination properties.

I doubt that this is true as well. If you have a non-CLP(FD) solution that doesn't
terminate, it might improve the situation, but it might also leave the situation
untouched and still not terminate.

Oops, small correction. Its not as doubtful as it seems. Its possibly
true, but I am not 100% sure.

This is a new challenge to find a counter example here. I am just
dubious because recursion with incomplete strategies such as depth
first search is such a beast.

But its not helpful to the inversion challenge. What I want to say is
that  it doesn't give any guarantees that the reordering improves
termination.

[Julio Di Egidio]

On Wednesday, March 30, 2016 at 8:48:03 AM UTC+1, Jan Burse wrote:

Can you apply your nat_add to define a nat_mul, and then
also define a nat_fac(torial). What behaviour will the
nat_fact(torial) have?

Already writing a clean nat_mul with all desired properties is not trivial: I have tried for few

hours now but I am still struggling with it...  Maybe bounds on the input arguments (relative

to other input arguments) are indeed necessary, but I am not sure, still thinking about it:

whether it can be done "cleanly" at all, i.e. without separate cases for different instantiation

patterns, if not in some simple cases...  Because, even if it can be done (and in that case

most of it could be auto-generated!), there is still an issue of actual performance, i.e.

whether it is an approach feasible for real world solutions.

OTOH, it would still be interesting to understand how CLP does in that respect: same

considerations (questions) on cleanness and feasibility hold.

Julio

[Kuniaki Mukai]

Just a comment. Although Peano arithmetic is undecidable,
Presburger arithmetic, which drops multiplication from Peano,
is decidable, but whose complexity is doubly exponential.

https://en.wikipedia.org/wiki/Presburger_arithmetic

Long time ago, Masami Hagiya published a paper on "Lerning by examples"
based on the decidability of the Presburger arithmetic.

I am sorry if this comment is irrevant to the current thread.

Kuniaki Mukai