java library that handles clp(fd)

[LoreForProlog]

Hello,
I'm looking for a java library that implements the clp(fd) module.
If there isn't any java library that achieves this task, could be the ECLiPSe Constraint Programming System the most similar solution in java to resolve CSP problems?

Best Regards,
Lorenzo

[Markus Triska]

Hi Lorenzo,

the CLP(FD) module in SWI-Prolog is designed and implemented as a declarative, modern replacement for all integer arithmetic. This means for example that there are no artificial bounds on domains. This falls outside the primary scope of many other CLP(FD) systems even in SWI's own area of Prolog-based constraint systems. Only a few other Prolog systems like SICStus and Jekejeke also support this, to various extents.

To the best of my knowledge, no Java library is available that implements such declarative integer arithmetic with Java-based CLP(FD) constraints, even though Java does provide arbitrary precision integers and could be made to handle such arithmetic with built-in mechanisms (and many thousands of linesInvolvingUnreadableNames).

If your use cases are all limited to comparatively small, finite domains, then the Java Constraint Solver JaCoP may be useful:

http://jacop.osolpro.com/

Note that the finite domain components of the ECLiPSe constraint programming system are not written in Java either, but in a mixture of Prolog (with ECLiPSe's extensions) and C.

The general question arises: Why do you even want this? There are many ways to make Java and (SWI-)Prolog communicate, and you can keep the CLP(FD) part entirely in Prolog, with several important advantages. For example, you do not have to use Java so much this way.

All the best,

Markus

[Julio Di Egidio]

On Monday, June 13, 2016 at 6:52:28 PM UTC+2, Markus Triska wrote:

> the CLP(FD) module in SWI-Prolog is designed and implemented as a declarative, modern replacement for all integer arithmetic.

You keep insisting with your fundamentalism, just adamant to any objection, in particular that your declarative uber alles is not even wrong...

In the meantime, if you like, try and fix this:

8 ?- between(1,inf,X).
X = 1 ;
X = 2 ;
X = 3 .

9 ?- X #>= 1, label([X]).
ERROR: Arguments are not sufficiently instantiated

Julio

[Julio Di Egidio]

On Monday, June 13, 2016 at 6:52:28 PM UTC+2, Markus Triska wrote:

> There are many ways to make Java and (SWI-)Prolog communicate, and you can

> keep the CLP(FD) part entirely in Prolog, with several important advantages.

+1

> For example, you do not have to use Java so much this way.

That is again just nonsense.

Julio

[Markus Triska]

Hi Julio,

On Monday, June 13, 2016 at 8:38:14 PM UTC+2, Julio Di Egidio wrote:

 

In the meantime, if you like, try and fix this:

8 ?- between(1,inf,X).
X = 1 ;
X = 2 ;
X = 3 .

OK. I strongly recommend you use instead:

?- length([_|_], X).

X = 1 ;

X = 2 ;

X = 3 .

It is much more portable!

All the best,

Markus

[Julio Di Egidio]

On Monday, June 13, 2016 at 9:30:32 PM UTC+2, Markus Triska wrote:

Hi Julio,

On Monday, June 13, 2016 at 8:38:14 PM UTC+2, Julio Di Egidio wrote:

 

In the meantime, if you like, try and fix this:

8 ?- between(1,inf,X).
X = 1 ;
X = 2 ;
X = 3 .

OK. I strongly recommend you use instead:

That misrepresents my point: at least try and be honest.

?- length([_|_], X).

X = 1 ;

X = 2 ;

X = 3 .

It is much more portable!

Sure, keep going...

*Plonk*

Julio

[Markus Triska]

Hi Julio,

On Monday, June 13, 2016 at 9:59:15 PM UTC+2, Julio Di Egidio wrote:

*Plonk*

Thank you!

All the best,

Markus

[Jan Burse]

The following works already in Jekejeke Prolog 1.1.3:

   ?- X #>= 1, label([X]).

You can enumerate any domain finite or infinite.
Source code at the end of this post.

Among the infinite you can enumerate those which are
only one sided infinite, i.e. L \/ H..sup or inf..L \/ H.

You can also enumerate the two sided infinite, i.e.
inf..sup and inf..L \/ M \/ H..sup.

Problem is to enumate an infinite ensemble with multiple
variables. It begins already with this simple example
of pythagorean tripples:

?- X*X + Y*Y #= Z*Z, label([X,Y,Z]).
/* this should do something */

For the enumeration of infinite ensemble of multiple variables
I have investigated the fair disjunction and fair conjunction
recently. These operators are one route to enumerate multiple
variables with infinite domain.

For the fair disjunction and fair conjunction I have created
today a new module shuffel. But integration with CLP(FD)
is still missing.

I somehow believe a true CLP(Z) is only one that can help
in overcoming enumeration limitations of depth first Prolog.
Its for example not so easy to do label([X,Y,Z]) with depth
first Prolog.

But I am not a fundamentalist on CLP(Z) or something. I
rather see it as an exercise on building and integrating
such enumerations in CLP(FD) to use them later also in
other domains.

I feel a little bit intimitated in using integers to solve
my problems. There are much more domains around.

Bye

(*)
Enumerating infinite domains:
http://www.jekejeke.ch/idatab/doclet/blog/en/docs/15_min/02_reference/finite/enum.html?hash=sys_mem_set/2

(**)
New shuffle library:
http://www.jekejeke.ch/idatab/doclet/blog/en/docs/15_min/02_reference/term/shuffle.html?hash=%3E%3E-/2

[Jan Burse]

The module "shuffle" is agnostic to what domain it
is applied. It works on the level of backtracking.

It can be also used to enumerate trees in a fair
way, means completely. Here is an example of
an enumeration of a binary tree.

:- use_module(library(term/shuffel)).
is_tree(leaf).
is_tree(node(X,Y)) ;- >>-(is_tree(X), is_tree(Y)).

When I use this definition I currently get the following
result so far:

?- is_tree(X).
X = leaf ;
X = node(leaf,leaf) ;
X = node(node(leaf,leaf),leaf) ;
X = node(leaf,node(leaf,leaf)) ;
X = node(node(node(leaf,leaf),leaf),leaf) ;
X = node(leaf,node(node(leaf,leaf),leaf)) ;
X = node(node(node(leaf,leaf),leaf),node(leaf,leaf)) ;
X = node(leaf,node(leaf,node(leaf,leaf)))
Erc..

As can be seen, there is no more preference to only
enumerate a subset of the binary trees, like the list
like forms of binary trees or something similar.

But the module "shuffel" is only one possible approach.
SWI-Prolog has already a module "tor", which helps
in enumerating Prolog programs.

Integrating it with CLP(FD), to broaden the domain search,
doesn't seem to be extremly compicated, but somebody
has to do the work. Puh.

Bye

[Jan Burse]

Sorry for the interlude.

i found this web site helpful in checking the many constraint solvers
written in Java. If you allow Scala to be viewed also as a JVM language
the choice is even bigger:
https://en.wikipedia.org/wiki/Constraint_programming#Constraint_programming_libraries_for_imperative_programming_languages

Unfortunately (Prolog) ECLiPSe is not related to the (Java) Eclipse IDE.

One might chose a Prolog based CLP(FD) library because of big nums.
But I think using Prolog is also apealing because it so easy to define
predicates that make use of CLP(FD).

That most of these Java solvers dont support big nums is a shame.

Bye

[Jan Burse]

The fundamentalist program is layed out here:

Features of good Prolog code? [closed]

http://stackoverflow.com/a/15710541/502187

I have the following problems with these program:
- Ambiguity of the adjective "pure": In functionaly programming
   pure only means no side effect. We might ask whether this
   weaker notion already helps archive (A,B) = (B,A).
- Ambiguity of the adjective "montonic": The term usually describes
   how the volume of a predicate changes when some dependent
   facts change their volume. Here I guess it means something else
   namely some form of steadfastness.

Further there seems to be no real promis in the program:
- It literally says "In pure, monotonic code, ( A, B ) and
 ( B, A ) describe the same relation. The only differences
   may lie in different termination behavior and the sequence
   how answers appear."
- If this fine print isn't read, deciples might go around in the
  world and promis much more than what the fundamentalist
  program aims at.

Bye

Am Montag, 13. Juni 2016 20:38:14 UTC+2 schrieb Julio Di Egidio:

[Jan Wielemaker]

On 06/14/2016 10:33 AM, Jan Burse wrote:
> The fundamentalist program is layed out here:

I would be happier if we could leave this battle behind us. (SWI-)Prolog
supports programming from nearly declarative (surely when tabling is
included) to purely imperative (but a bit clumsy) using cuts all over
the place and destructive assignment. Be happy.

The purists have some tricks to avoid cuts and make code multi-moded,
sometimes without much effort. Learn from it and use it where
applicable. Do note that constraints, which are often part of making
code multi-moded, combine poorly with pruning (->, !), term copying and
side effects.

In many applications, the required mode is completely obvious, so why
spent brain and/or CPU cycles trying to support more modes? If you need
to process lots of data and need performance, avoiding choicepoints is
simple necessary. A couple of tactically placed cuts typically do the
trick. Carefully choosing the data representation and some intermediate
predicates can often avoid the need for these cuts. Whether it is worth
the trouble? That is your judgement.

Learn the different styles to have them all in your toolbox. Apply
them where applicable. Prolog makes it easy to combine both in one
application and it is often a good idea to do so.

Don't worry, be happy

--- Jan

> Features of good Prolog code? [closed]

> <http://stackoverflow.com/questions/15709808/features-of-good-prolog-code>

>
> http://stackoverflow.com/a/15710541/502187
>
> I have the following problems with these program:
> - Ambiguity of the adjective "pure": In functionaly programming
> pure only means no side effect. We might ask whether this
> weaker notion already helps archive (A,B) = (B,A).
> - Ambiguity of the adjective "montonic": The term usually describes
> how the volume of a predicate changes when some dependent
> facts change their volume. Here I guess it means something else
> namely some form of steadfastness.
>
> Further there seems to be no real promis in the program:
> - It literally says "In pure, monotonic code, |( A, B )| and |

> ( B, A )| describe the same relation. *The only differences
> may lie in different termination behavior *and the sequence
> how answers appear."
> - If this _*fine print *_isn't read, deciples might go around in the

> world and promis much more than what the fundamentalist
> program aims at.
>
> Bye
>
> Am Montag, 13. Juni 2016 20:38:14 UTC+2 schrieb Julio Di Egidio:
>
> On Monday, June 13, 2016 at 6:52:28 PM UTC+2, Markus Triska wrote:
>
>
> > the CLP(FD) module in SWI-Prolog is designed and implemented as a

> declarative, modern replacement for /all integer arithmetic/.

>
> You keep insisting with your fundamentalism, just adamant to any

> objection, in particular that your /declarative uber alles/ is not

> even wrong...
>
> In the meantime, if you like, try and fix this:
>
> 8 ?- between(1,inf,X).
> X = 1 ;
> X = 2 ;
> X = 3 .
>
> 9 ?- X #>= 1, label([X]).
> ERROR: Arguments are not sufficiently instantiated
>
> Julio
>

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

[Jan Burse]

You shouldn't kill the quest by simply calling it an unhappy battle.
I think its an interesting quest. For example we have already a coding
guideline for Prolog, which has a volume of 39 pages:

Coding Guidelines for Prolog, Michael A. Covington et al., 2011

https://arxiv.org/abs/0911.2899

There might be a need for a further guideline. A guideline that doesn't
work on the formatting level of Prolog code, but gives some advice
concerning on a semantic level.

The above guideline isn't free of semantic considerations. We find
for example the following requirement:

    5.1 Predicates must be steadfast.
    Any decent predicate must be “steadfast,” i.e., must work correctly if its output
    variable already happens to be instantiated to the output value (O’Keefe 1990).

    That is,
        ?- foo(X), X = x.
    and
        ?- foo(x).

    must succeed under exactly the same conditions and have the same side
    effects. Failure to do so is only tolerable for auxiliary predicates whose call
    patterns are strongly constrained by the main predicates.

This is a much more practical requirement than pure+montonic. But unfortunately
the above requirement is not possible. See the recent AST discussion on
comp.lang.prolog. We cannot have:

      ?- is_json(X), X=<json>.

      -- same as --

      ?- is_json(<json>).

But we find the sarcastic comment in the Guideline:

     3.14 Do not blindly import styles from other languages.
     For instance, do not blindly follow the Java tradition by calling everything in sight
     is_xxx or get_yyy. It is fine to name is_tree/1 a checker, that is, a predicate
     that will only succeed, without leaving choice-points, on well-formed, structurally
     complete trees. This will help the user to distinguish it from the generator —
     whether its existence in the program is real or only conceivable— called tree/1.

So what is going wrong here? BTW: Tabling doesn't help either. So I guess
an additional more semantically oriented Guideline is surely demanded. This
Guideline would take care:

- New developments such as CLP(FD).
- New developments such as tabling
- New developments such as module system (asked here recently)
- Maybe even object oriented extensions
- What else?
- Would be better elaborated concerning its claims.
- Would use established subclasses of Prolog programs.
- Would maybe also elaborate on CWA.
- What else?

Problem is such a Guideline Nr. II will sure have also a big volume. Most
likely it is not possible to fit everything on one page as for example the
stackoverflow fundamentalist post tries to do.

Maybe you get some funding from somewhere to do this, plus the fame
of doing this in subsequent generation of logic programmers. Assuming
they survive also in the future after the Haskell comet incident.

Best Regards

[Jan Burse]

Am Dienstag, 14. Juni 2016 12:15:17 UTC+2 schrieb Jan Burse:

- New developments such as CLP(FD).
- New developments such as tabling
- New developments such as module system (asked here recently)
- Maybe even object oriented extensions
- What else?
- Would be better elaborated concerning its claims.
- Would use established subclasses of Prolog programs.
- Would maybe also elaborate on CWA.
- What else?

Add to the list:
- DCG not only for parsing/unparsing, i.e. state/goal generation/etc..
- New developments such as tor.
 

[LoreForProlog]

Hi Markus,
Thank you for answering me.

Actually I have not yet found any open source java API that mangaes the module clp(fd).
For example I've tried to use open source solutions like jpl (http://www.swi-prolog.org/packages/jpl/java_api/) or prolog development tool PDT (https://sewiki.iai.uni-bonn.de/research/pdt/docs/start), but neither of them are able to handle in java the result of the clp(fd) module.
However it's quite good for me just handling the result of a constraint logic progrmming problem, I don't need a java implementation.
Therefore even though jacop-solver could be the best open source java solution to constraint programming, I think EclipSe is better for me, because it provides the java API (http://eclipseclp.org/doc/javadoc/JavaEclipseInterface/index.html) as well as interfaces with other languages.

Lorenzo

[Jan Burse]

I guess using something along call_residue_vars/2 might solve
your problem. I am not sure whether it will differ much in other
Prolog APIs, that you need such helpers.

After all, a Prolog API only returns the variable bindings, but
not the constraint store. So if you query:

    ?- X+Y #= 100.

You get just a result set with a single solution, which is the
empty tuple, or a tuple X=X and Y=Y. But if you call:

    ?-  call_residue_vars(X+Y #= 100, L).
    L = [Y, X],
    X +Y#=100.

Oops, its not working. I guess its only working for freeze/2
or some such, or its broken. For CLP(FD) you need to use copy_term/3.

    ?- X+Y #= 100, copy_term([X,Y], [X,Y], L).
    L = [clpfd: (X+Y#=100)].

So in a result set, via the variable L, you can also receive constraints.

Bye

[Jan Burse]

Documentation says:

http://www.swi-prolog.org/pldoc/doc_for?object=copy_term/3
This building block is used by the top level to report
pending attributes in a portable and understandable fashion.
 This predicate is the preferred way to reason about and
communicate terms with constraints.

[Markus Triska]

Hi Lorenzo,

Actually I have not yet found any open source java API that mangaes the module clp(fd).
For example I've tried to use open source solutions like jpl (http://www.swi-prolog.org/packages/jpl/java_api/) or prolog development tool PDT (https://sewiki.iai.uni-bonn.de/research/pdt/docs/start), but neither of them are able to handle in java the result of the clp(fd) module.
However it's quite good for me just handling the result of a constraint logic progrmming problem, I don't need a java implementation.
Therefore even though jacop-solver could be the best open source java solution to constraint programming, I think EclipSe is better for me, because it provides the java API (http://eclipseclp.org/doc/javadoc/JavaEclipseInterface/index.html) as well as interfaces with other languages.

It is as Jan has said: You can use copy_term/3 to explicitly reason about residual constraints; that is, you can make them available as a list of Prolog terms in this way, and the various bindings of SWI-Prolog should make it possible to pass around such lists of goals. The CLP(FD) documentation also shows examples of this:

http://eu.swi-prolog.org/pldoc/man?section=clpfd-residual-goals

Note also that SWI ships with powerful web libraries, and I recommend using them for communication between different processes.

ECLiPSe is much more powerful and much faster than SWI-Prolog in many aspects of CLP(FD) constraint solving, and it is definitely a great choice if that is your primary focus.

All the best,
Markus

[Jan Burse]

The agenda definitely needs also the following topics:
- Cyclic terms, what are they, how to use/not to use them.
- Freeze/when predicates, how to use them for declarativity.

Here is a nice example making a predicate steadfast:

   flip(V, W) :- var(V), var(W), !,
                 when((nonvar(V);nonvar(W)), flip(V, W)).
   flip(red, black).
   flip(black, red).
   flip(node(X,Y), node(Z,T)) :- flip(X,Z), flip(Y,T).

This is not on Ulrich Neumerkels agenda. Also its not yet
working perfectly, for example I get a choice point here:

   ?- flip(X,Y), Y=node(black,red).
   X = node(red, black),
   Y = node(black, red) ;
   false.

But since SWI-Prolog has multi-argument indexing, I don't
see why a choice point is needed here.

Bye
  

[Markus Triska]

Hi Jan,

The agenda definitely needs also the following topics:

Please include set_prolog_flag(double_quotes, chars)!

It makes working with double-quoted strings so convenient and easy!

All the best,
Markus

[LoreForProlog]

Hi,
I've used the predicate copy_term/3 in PDT and it works.

Given a query like this one: ?- X #\= 20.
 I wrote it in PDT using the following LOC:
String query1 = QueryUtils.bT("#\\=", "X","20");
String query2= QueryUtils.bT("copy_term", "[X]","[X]","Gs");
List<Map<String, Object>> result = prologProcess.queryAll(query1,query2);
System.out.println(result);

It prints me the following result:
[{X=_G1041, Gs=[:(clpfd,in(_G1041,\/(..(inf,19),..(21,sup))))]}]

Since I have not particular performance issues, there's no point in using ECLiPSe for now, therefore I'll continue to use CLP(FD).

Thanks everyone,
Lorenzo

[Markus Triska]

Hi Jan,

One might chose a Prolog based CLP(FD) library because of big nums.
But I think using Prolog is also apealing because it so easy to define
predicates that make use of CLP(FD).

Yes, that's one of the reasons. To me, among the important reasons to keep the implementation entirely in Prolog were also:

1) The prospect of the library's portability to different Prolog systems. (It is successfully ported to YAP, for example.)
2) Keep the code short enough to make also extensive changes doable.
3) Gather experience about how fast a completely Prolog-based system can run.
4) Find the right set of general low-level primitives that make the Prolog-based code run faster.
5) Popularize Prolog as an implementation language; show what can be done purely in Prolog. Very important reason!
6) Avoid getting lost in intricacies of more primitive languages and their interfacing with Prolog. Also a very important reason!

That most of these Java solvers dont support big nums is a shame.

That's nothing in comparison to how much more tragic reality could be. For example, imagine a situation where an implementor provides a Java-based CLP(FD) system that does support bignums in order to entirely replace low-level integer arithmetic by more general functionality, and users then actively discourage its use in precisely the intended application domain, or continue to argue with the designer about the motivation and goals of the system. It would be very unfortunate to see such a development, and I hope it is unlikely to happen.

All the best,
Markus

[Jan Burse]

You can also do constraint solving in Ruby, using

McCarthy's Ambiguous Operator statement.

http://www.randomhacks.net/2005/10/11/amb-operator/

At least this would cover some of the labeling, how
you would do the rest, i.e. the constraint store etc.. I
don't kow, since I don't know anything about Ruby

[Jan Burse]

Hi,

At least they have something like a reset/shift in Ruby,
maybe also adopting the SWI-Prolog tabling:
http://ruby-doc.org/core-2.2.0/Continuation.html

Then suddently there is a range type, which
can be used with blocks i.e. closures etc..
http://ruby-doc.org/core-2.2.0/Range.html

But all this stuff smells like sooner or later running
into stack overflows etc.. In prolog you can do heavy
search also when CLP(FD) is involved.

Thats why the fundamentalistic agenda is not extremly
wrong in one respect. When it says replace is/2 by
CLP(FD), then it is indeed the case that not a lot
of things can be brocken,

tail recursion optimization etc.. still works. At least
I guess this is the case for SWI-Prolog, since even
unreachable attribute variables seem to be reclaimed.
But you guys should publish more about all that.

Bye

[Jan Burse]

Current problem with the fundamentalist agenda:

   Features of good Prolog code? [closed]

   http://stackoverflow.com/a/15710541/502187

On this agenda we find the following item:

    Use clpfd for arithmetics. Don't use (is)/2, it makes your code much too moded.

For me, at the moment, its not clear whether this is a good advice. Especially

when is/2 is used inside heavy search. I know about a study that shows that

attribute variables used in freeze/2 are automatically reclaimed, when unreachable.

The study even only holds for SWI-Prolog in some simple cases, other systems have

more problems.

Whether this also holds for attribute variables occuring in CLP(FD) I don't know

at the moment. I am not aware of some studies on this topic. The problem is

easily shown in the tree test/generate example. We will have a predicate:

       tree(X) :- var(X), !, freeze(X, tree(X)).

       tree(...) :- rest of tree code

The freeze X is a cyclic structure, since the frozen goal contains X again. Very

difficult for example for Jekejeke Prolog to reclaim such stuff (*). Usually if a variable

is instantiated with a constant or another variable GC is much easier.

Bye

(*)
One idea I had was using closures in freeze, so we would do:

       tree(X) :- var(X), !, freeze_closure(X, tree).

In CLP(FD) I don't know exactly whats underneath, i.e. some propagator
queues, etc.. Would be interested in empirical data, how intermediate
variables can be dealt by the system in practical problems.

Typical test example:

     sum([], 0).
     sum([X|Y], S) :- sum(Y, T), S #= T+X.

How many constraints will this generate?

[Markus Triska]

Hi Jan,

Typical test example:

     sum([], 0).
     sum([X|Y], S) :- sum(Y, T), S #= T+X.

How many constraints will this generate?

Very good question, and I applaud you for actually inquiring this. To my knowledge, it is the first time that such a question is asked on this mailing list.

The answer is: When CLP(FD) arithmetic constraints are used in modes that can also be handled by built-in arithmetic, zero pending constraints are generated. That is not a typo. No pending constraints at all are generated when (#=)/2 is used in modes that can also be handled by (is)/2 and (=:=)/2. You can look at the listing with ?- listing(sum/2), and see that only lower level predicates are used in such cases.

In a very real sense, the only thing that users have to change to pave at least a small path for more general programs while retaining everything they like about their existing code (including acceptable performance) is a textual replacement of (is)/2, (>)/2, ... by (#=)/2, (#>)/2 etc. All existing properties (except for the limited generality, which increases) are preserved, and you can discuss and teach all features like accumulators, tail calls etc. also and equally well with (#=)/2.

The fallacy I often see on this list is that users change more than that, and then complain that the resulting program has quite different performance characteristics than before. It's true, you cannot in general expect that exchanging the order of goals has no impact on performance. This is an entirely different aspect, and we can tackle it as soon as we have collected more experience with tinier changes (is/2 --> #=/2). I'm prepared for this and ready to discuss this as soon as declarative integer arithmetic is more widely adopted. Before that, there will simply be too many misunderstandings to efficiently discuss more subtle aspects.

All the best,
Markus

[Jan Burse]

This is obvious that no extra constraints are generated when one
argument is a ground expression in (#=)/2 and the other is a variable.

That this boils down into is/2 is part of the attribute variable and
forward checking logic of CLP(FD).

But still:
   - For this mode, (#=)/2 will it compete in space and
              time efficiency with is/2? (do some heavy search
                 examples still run, i.e. do they not consume
                 much more time or stack?)
   - For this mode, (#=)/2 will it cover the same funs as
             the good old is/2? (what about sin/1 etc..)
   - For other modes, makes it sense at all to use (#=)/2?

For example I get the following blow-up of constraints in this
trivial example:

?- sum([1,2,3,4,A,B],S).

B+A#=_G472,

_G472+4#=_G484,

_G484+3#=_G496,

_G496+2#=_G508,

_G508+1#=S.

This is the projection problem of constraints. I have already posted
on comp.lang.prolog and here about that. There are even CLP-WAM,
indeed a CWAM proposals that try to improve the situation.

All in all, I doubt that the fundamentalist agenda makes any sense
without thorough research and studies. You might have some early
adopters, which will be your focus group.

But I don't think you would make anybody happy with suddently
switching (is)/2 to something else. Its still in its fancy.

Bye

[Jan Burse]

Sometimes the blow up can be avoided by rephrasing the problem
slightly. But then we are in the realm of reordering goals, and not
in the more simpler is/2 --> #=/2.

You also observed that, that this are two different issues. Bud
sadly, as long as the projection problem persist, there is a
dependency.

Maybe the world is even that dark, that you will need mode
casing, so instead of is/2 --> #=/2, the said truth is that
you will need code:

p(...) :- var(X), !, /* mode 1 */
      /* goals ordered this way */
p(...) :- var(Y), !, /* mode 2 */
      /* goals ordered that way */

The declarative dream going up in smoke...

[Markus Triska]

Hi Jan,

For example I get the following blow-up of constraints in this
trivial example:

This is a non-trivial example! It cannot be handled by lower-level arithmetic at all.

Please, let us first focus on cases where the issue is simply replacing low-level arithmetic by more declarative constraints. This is possible already today, and can at most improve the generality of your programs.

All the best,
Markus

[Jan Burse]

I did nothing else.

Code before:

     sum([], 0).
     sum([X|Y], S) :- sum(Y, T), S is T+X.

Code after:

     sum([], 0).
     sum([X|Y], S) :- sum(Y, T), S #= T+X.

The code is conservative for ground input lists. Works the
same as before. But I didn't do some time/space measurents,
might be slower.

On the other hand, if the input list is not ground:

- It might hang if the tail of the list is a variable, the is/2 -> #=/2
  replacement doesn't deal with this issue.

vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
- The fundamentalist agenda v0.1 blends out freeze/2 and when/2.
   Subsequently gives no advice how to combine them with
   #=/2. If the tail of the list is a variable, we might solve the
   problem with freeze/2.
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
- For invidiual elements of the list, that are non-ground,
  we see this constraint blow up. Which might be a good or
   bad thing. Not yet sure.

Bye

[Julio Di Egidio]

On Thursday, June 16, 2016 at 2:12:02 PM UTC+2, Markus Triska wrote:

Hi Jan,

Typical test example:

     sum([], 0).
     sum([X|Y], S) :- sum(Y, T), S #= T+X.

How many constraints will this generate?

Very good question, and I applaud you for actually inquiring this. To my knowledge, it is the first time that such a question is asked on this mailing list.

The answer is: When CLP(FD) arithmetic constraints are used in modes that can also be handled by built-in arithmetic, zero pending constraints are generated. That is not a typo. No pending constraints at all are generated when (#=)/2 is used in modes that can also be handled by (is)/2 and (=:=)/2. You can look at the listing with ?- listing(sum/2), and see that only lower level predicates are used in such cases.

In a very real sense, the only thing that users have to change to pave at least a small path for more general programs while retaining everything they like about their existing code (including acceptable performance) is a textual replacement of (is)/2, (>)/2, ... by (#=)/2, (#>)/2 etc. All existing properties (except for the limited generality, which increases) are preserved, and you can discuss and teach all features like accumulators, tail calls etc. also and equally well with (#=)/2.

Not all arithmetic is covered, so it is not as simple as a text replacement.  For example:

?- X #= 1.2, Y #= sin(X).
ERROR: Domain error: `clpfd_expression' expected, found `1.2'

The fallacy I often see on this list is that users change more than that,

But, besides the caution expressed above, what is the point of changing that stuff at all?  Indeed, what would be the "path to more general programs"?

Julio

[Julio Di Egidio]

On Thursday, June 16, 2016 at 4:24:31 PM UTC+2, Jan Burse wrote:

I did nothing else.

Code before:

     sum([], 0).
     sum([X|Y], S) :- sum(Y, T), S is T+X.

Code after:

     sum([], 0).
     sum([X|Y], S) :- sum(Y, T), S #= T+X.

The code is conservative for ground input lists. Works the
same as before. But I didn't do some time/space measurents,
might be slower.

:- use_module(library(clpfd)).

sum_0([], 0).
sum_0([X|Y], S) :- sum_0(Y, T), S is T+X.

sum_1([], 0).
sum_1([X|Y], S) :- sum_1(Y, T), S #= T+X.

?- time((N=100000,between(1,N,_),sum_0([1,2,3,4,5,6,7,8,9,10],S),fail)).
% 2,200,002 inferences, 0.296 CPU in 0.296 seconds (100% CPU, 7422361 Lips)
false.

?- time((N=100000,between(1,N,_),sum_1([1,2,3,4,5,6,7,8,9,10],S),fail)).
% 6,200,002 inferences, 0.655 CPU in 0.655 seconds (100% CPU, 9462702 Lips)
false.

Julio

[Martin]

On 06/16/2016 04:30 PM, Julio Di Egidio wrote:
> But, besides the caution expressed above, what is the point of changing
> that stuff at all? Indeed, what would be the "path to more general
> programs"?
>
> Julio

Have a fish for the sin herring: ><((((*>

For everyone else: Markus already ansered that multiple times. Replace
integer reasoning by clpfd, since it has the same behaviour on the modes
supported by is. Already now, clpfd is more general than is, improving
it will introduce more generality.

Martin

[Julio Di Egidio]

On Thursday, June 16, 2016 at 5:36:42 PM UTC+2, martin.riener wrote:

On 06/16/2016 04:30 PM, Julio Di Egidio wrote:
> But, besides the caution expressed above, what is the point of changing
> that stuff at all?  Indeed, what would be the "path to more general
> programs"?

Have a fish for the sin herring: ><((((*>

For everyone else: Markus already ansered that multiple times. Replace
integer reasoning by clpfd, since it has the same behaviour on the modes
supported by is. Already now, clpfd is more general than is, improving
it will introduce more generality.

That is a promise, not an answer.

HTH...

Julio

[Jan Burse]

It seems that the ECLiPSe system can do it. Didn't know
about it, but it seems so.

I find the following example:

?- model(X), labeling([X]).

X = 58      More? (;)

X = 118     More? (;)

X = 178     More? (;)

See here, slide Nr. 17:
http://eclipseclp.org/reports/Workshop/interval.ppt

But don't have yet hands-on.

[Jan Wielemaker]

Simplified story IMO:

- You can replace classical Prolog arithmetic with clp(fd), provided
you only deal with integers and (most) integer arithmetic. The
semantics will remain the same. You'll loose some performance,
in particular when compared to using -O on tight arithmetic loops.
- You don't really gain anything, unless your multi-moded operation
is a clear win and you don't use any choice commitment (->, or !).

Is using clp(fd) a good idea? It depends. If your program is about
search in integer domains, probably yes. But, you need to reorder your
program. If your program now runs using clasical Prolog arithmetic,
replacing this with clp(fd) probably only makes it slower. You need to
move arithmetic to the front as much as possible to make the constraint
reasoning do its intelligent pruning of the search space.

If your program is just simply single moded computation, clp(fd) will
only make it slower. If generalising to multiple modes makes sense,
you have to carefully examine your code after replacing the traditional
arithmetic with clp(fd). E.g.,

( X =:= 0
-> ...
; ...
)

is something very different from this. Actually, the below is almost
surely errornous unless X is ground, in which case it behaves as the
above.

( X =#= 0
-> ...
; ...
)

In other words, the style of clp(fd) programs is different from traditional
programs. Clp(fd) says this:

- Define domains
- Define constraints
- Label

Traditional programs do

- Generate candidates
- Select candidates

In theory, in the clp(fd) case the exact constraints and the order in
which you state them should not be relevant. In practice this matters,
but usually not as much as in the traditional setting. In the
traditional setting you are in control and you typically need a clever
interleaved mixture of generating and testing to solve a realistic
combinatorial problem.

Cheers --- Jan

On 06/16/2016 01:19 PM, Jan Burse wrote:
> Current problem with the fundamentalist agenda:
>
>
> Features of good Prolog code? [closed]

> <http://stackoverflow.com/questions/15709808/features-of-good-prolog-code>

>
>
> http://stackoverflow.com/a/15710541/502187
>
>
> On this agenda we find the following item:
>
>

> Use clpfd <http://stackoverflow.com/questions/tagged/clpfd> for
> arithmetics. Don't use |(is)/2|, it makes your code much too moded.

[Jan Burse]

Yes, thats of course the text book definition of CLP(FD) and also
a part of the Operations Research (OR) thinking. Operations
Research might sound strange, but these are the guys that deal
with advanced decision making:

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

But I guess the fundamental agenda of Ulrich Neumerkel says
something else, he wants to blend the traditional Prolog programming
with CLP(FD). To begin with its not clear whether his programs will
be OR programs or web applications or compilers or whatever.

It just says features of good Prolog code:
http://stackoverflow.com/questions/15709808/features-of-good-prolog-code

If you write a compiler with Prolog you might be less in need of
generate and test, and do more stuff like pipeing results via lists
etc.. from predicate to predicate modelling the various stages
of a compiler. For example a parse, is just a predicate:

     parser(+ListOfTokens, -AST)

The backend is then:

     codegen(+AST, +ListOfInstructions)

And so on etc.. Maybe do pattern matching along lists, etc..
Similar to integers, lists are infinite structures. Not sure whether
the fundamentalist agenda is also meant to be useful there.
The sum/2 predicate is a mixture of integer and lists.

Still puzzled!

[Markus Triska]

Hi Jan,

On Thursday, June 16, 2016 at 9:11:18 PM UTC+2, Jan Wielemaker wrote:

Simplified story IMO:

   - You can replace classical Prolog arithmetic with clp(fd), provided
     you only deal with integers and (most) integer arithmetic.  The
     semantics will remain the same.  You'll loose some performance,
     in particular when compared to using -O on tight arithmetic loops.
   - You don't really gain anything, unless your multi-moded operation
     is a clear win and you don't use any choice commitment (->, or !).

I would like to add 2 points to this list: Most importantly, using CLP(FD) constraints from the start saves a lot of time when teaching Prolog. Please see the instantiation-error tag on stackoverflow, which is frequently associated with low-level arithmetic, and see how much time it would save to get rid of such errors. This is time that can be spent on more important topics in Prolog courses. Without (#=)/2, you will need to introduce at least (is)/2, and in many cases also (=:=)/2, both in tandem with procedural limitations that are extremely hard to grasp for beginners. Please note that this list and several people worldwide that participate in the occasional discussions about didactic approaches when teaching Prolog are not representative for beginners.

I sympathize with the opinion expressed by Boris in a different thread, to lead students to more declarative approaches in smaller doses by first struggling with more limitations. However, in this particular case, the struggle is not worthwhile in my view, for the following reason:

In any serious Prolog course, you will have to introduce CLP(FD) constraints in any case at some point, so doing it sooner is in this case better because it allows you to do away completely with other predicates that are only harder to understand for beginners without providing any benefit, and which I (for example) already regard as superseded.

For comparison, let us take a look at how CLP(FD) constraints themselves are nowadays introduced: Contrast the CLP(FD) constraints we have now with earlier approaches to integrate them in Prolog systems, and in particular also their different syntax variants. For example, in some early systems, you could not simply use a predicate like (in)/2 to state domains, but needed to declare isolated facts using a special syntax. Nowadays, CLP(FD) constraints blend in completely naturally as normal Prolog goals in programs. Yet, when introducing CLP(FD) constraints nowadays, we do not teach students the entire history of syntax development and also errands that led to their current form. In analogy to this approach, we now have the opportunity to simply omit lower-level predicates that are entirely superseded. In my view, we should seize this opportunity and use the time to teach more important aspects of the language.

This is similar to how Haskell's way to do I/O is now introduced: Only monads are presented typically, and earlier approaches or previously suggested alternatives to do I/O in Haskell are simply omitted because they are now considered superseded. The often painful and lengthy controversies surrounding these topics are stated in more advanced courses, but not when introducing the current state of the art to beginners.

My recommendation is therefore to use (#=)/2 when introducing integer arithmetic to beginners.

The second point is more subtle and regards strategic opportunities for improvements to SWI-Prolog itself, made possible by collecting empirical evidence supplied by more experienced Prolog programmers: For example, as the benchmark shown in this thread illustrates, using CLP(FD) constraints instead of lower-level predicates may slow down tight arithmetic loops by a factor of ~2. This is due to some tests that are dynamically performed in the case of constraints. The point is that there are certainly ways to compile such checks more efficiently, and thus to improve all parts of Prolog programs that perform such checks. In this regard, I also view CLP(FD) constraints as an opportunity to detect and implement possible improvements in the underlying system. This is completely analogous to how using the declarative library(pio) in real programs has led to excellent improvements to SWI-Prolog's garbage collector.

For this reason, I recommend using (#=)/2 for integer arithmetic in all programs.

All the best!
Markus

[Jan Burse]

But currently (#=)/2 has a much smaller scope than (is)/2. For
example bitwise operations are not supported. I get the
following error:

   ?- X #= 12 \/ 14.
   ERROR: Domain error: `clpfd_expression' expected, found `12\/14'

But you find tons of Prolog code that uses bitwise operations. I
see people on purpose for efficiency using 0 =:= N /\ 1 to check for
an even number or M is N>>1 to divide by two. (Old and new Prolog code)

Further a lot of (is)/2 operations are across float and integers. For
example min/2 can work on both integer and float. You also find tons
of Prolog code that needs this.

   ?- X #= min(1, 1.2).

   ERROR: Domain error: `clpfd_expression' expected, found `1.2'

Finally a lot of operations inside (#=)/2 are indeed working similar
to (is)/2. Except for a few operations that have integer arguments but
sometimes float results. Here is an example (also SWI-Prolog):

    ?- X #= (-7)^(-5).
    false.
    ?- X is (-7)^(-5).
    X = -5.949901826619859e-5.
    (BTW: Violating the ISO standard: 9.3.10.3 Errors, e)
     https://www.complang.tuwien.ac.at/ulrich/iso-prolog/dtc2#pow)

So you can only replace is/2 by #=/2 when it is an arithmetic integer
operation, in a very narrow sense of arithmetic, i.e.:
- Not a bitwise operation
- Not an operation that can mix integer and float arguments
- Not an operation that can return float

Etc..

[Jan Burse]

Further a speciality of SWI-Prolog the (**)/2 operator returns
integer instead of float. But not supported by (#=)/2:

   ?- X is (-7)**5.
   X = -16807.
   ?- X #= (-7)**5.
   ERROR: Domain error: `clpfd_expression' expected, found `-7**5'

[Jan Burse]

Lets also not forget that CLP(FD) adopts another philosophy concerning
function arguments that are outside of the domian of a function. CLP(FD)
fails in such situations, since it wants to continue its labeling.

But is/2 on the other is required to throw an exception by the ISO
standard. So we find the following two different behaviours:

   ?- X #= 12 div 0.
   false.

   ?- X is 12 div 0.
   ERROR: div/2: Arithmetic: evaluation error: `zero_divisor'

Means if you change (is)/2 to (#=)/2 you might quickly run into
the situation that the code has, possibly spurious, fails, instead
of exceptions.

(Have to revise my agreement that (is)/2 can be replaced by
(#=)/2 for ground arguments, there are some differences...)

[Markus Triska]

Hi Jan,

On Saturday, June 18, 2016 at 8:12:21 PM UTC+2, Jan Burse wrote:

But currently (#=)/2 has a much smaller scope than (is)/2.

But currently the scope of (#=)/2 is larger than it was when you wrote this, because I have treated your post like every other feature request I have received so far: I have added the requested functionality for free. Of course, I value feature requests that start with something like "Dear Markus, would you please be so kind as to add feature X because I need it for Y..." much more highly, and in the past such requests were, fortunately, also a lot more common than the kind of requests I get nowadays (which are mostly along the lines of "CLP(FD) is terrible because it doesn't support X.").

 

For example bitwise operations are not supported. I get the
following error:

   ?- X #= 12 \/ 14.
   ERROR: Domain error: `clpfd_expression' expected, found `12\/14'

With the latest git version, I get instead:

?- X #= 12 \/ 14.

X = 14.

 

But you find tons of Prolog code that uses bitwise operations.

That's great. Simply use the arithmetic CLP(FD) constraints  to reason about integer expressions that may also involve >>, <<, \, \/, /\ and xor.
 

I see people on purpose for efficiency using 0 =:= N /\ 1 to check for
an even number or M is N>>1 to divide by two. (Old and new Prolog code)

And even newer Prolog code will, I hope, soon use for example:

?- 0 #= 3 /\ 1.
false.

?- N #= 3 /\ 1.
N = 1.

?- N #= 2^100 >> 1.
N = 633825300114114700748351602688.

 

Further a lot of (is)/2 operations are across float and integers. For
example min/2 can work on both integer and float. You also find tons
of Prolog code that needs this.

Overall, we will comparatively soon move away from floats altogether. You may fight and struggle against this for a few more years or even decades, but the future belongs to rational numbers, unums, and other formats with more declarative and more desirable properties. Floats were good and, in many cases, also tragically bad for a few decades, and I hope we can soon leave them behind entirely. I know that just as with (is)/2 --> (#=)/2, the transition away from floats will appear, at first, unusual and will invoke strong feelings from current users, researchers, hardware manufacturers etc. and will probably be delayed due to some resistance. I consider both transitions inevitable in the long run and will not invest any time in issues involving floats. My remaining large task in SWI is enhancing library(simplex), and for this I will use rational numbers exclusively.

All the best!
Markus

[Wouter Beek]

Hi Markus, others,

Thank you for adding bitwise operators to CLP(FD), and thank you Jan for pointing out some of the issues involved when switching from `is/2` to `#=/2` that were not obvious to me at first.

Further a lot of (is)/2 operations are across float and integers. For
example min/2 can work on both integer and float. You also find tons
of Prolog code that needs this.

Overall, we will comparatively soon move away from floats altogether.

This is a very interesting prospect.  Would rationals work in all/most cases where floats are currently used?

Another area where we want to use rationals is for values of RDF datatype `xsd:decimal` in module `semweb/rdf11`.

I notice that GMP, which is currently used for rational support, is licensed under the GPL and cannot be compiled with the rest of the, now MIT licensed, SWI stack for commercial purposes.

---

Cheers,

Wouter.

[Jan Wielemaker]

Hi Wouter,

On 06/19/2016 10:07 AM, Wouter Beek wrote:
> Hi Markus, others,
>
> Thank you for adding bitwise operators to CLP(FD), and thank you Jan for
> pointing out some of the issues involved when switching from `is/2` to
> `#=/2` that were not obvious to me at first.
>
> Further a lot of (is)/2 operations are across float and
> integers. For
> example min/2 can work on both integer and float. You also find tons
> of Prolog code that needs this.
>
> Overall, we will comparatively soon move away from floats altogether.
>
> This is a very interesting prospect. Would rationals work in all/most
> cases where floats are currently used?

No. Rationals represent $Q$ and provide an exact representation as long
as you limit your arithmetic functions to $Q -> Q$ functions. As soon as
you include functions that have values in $R$, rationals only give you
an expensive false feeling of correctness. In other words, pi/0, sin/1,
etc. require floats. Even for operations within $Q$, moving to floats
may be desirable if exact results are not required due to the much lower
costs of floating point representations and the hardware supported
computations.

That said, it would be a good idea if 1/3 would return a rational rather
than a float, i.e., the system should use rationals as long as these
represent exact results. That might happen some day.

> Another area where we want to use rationals is for values of RDF
> datatype `xsd:decimal` in module `semweb/rdf11`.

Supporting decimals would be a good idea too, probably on top of
rationals.

> I notice that GMP, which is currently used for rational support, is
> licensed under the GPL and cannot be compiled with the rest of the, now
> MIT licensed, SWI stack for commercial purposes.

SWI-Prolog is moving to BSD, not MIT (the difference is neglectable).
The when depends on how we will work around Ulrich Neumerkel who refuses
to give his consent for relicencing his contributions. I'm working with
a couple of people behind the scenes to resolve this. If you are
knowledgeable in this field, please contact me.

After this is done we will look at a replacement for GMP, probably with
a compiletime switch as GMP definitely the most robust, feature rich and
fastest big number library around. I also plan to get rid of readline.
Here, it seems that the BSD replacement `libedit' has a totally different
API but also interesting features such as the ability to support multiple
editing contexts.

Cheers --- Jan

[Markus Triska]

Hi Jan,

On Sunday, June 19, 2016 at 10:27:24 AM UTC+2, Jan Wielemaker wrote:

you include functions that have values in $R$, rationals only give you
an expensive false feeling of correctness. In other words, pi/0, sin/1,
etc. require floats.

One much better alternative to floats in this case are unums. Please see John Gustafson's recent book, "The End of Error":

https://www.crcpress.com/The-End-of-Error-Unum-Computing/Gustafson/p/book/9781482239867

It explains how to compute with unums and shows the important properties they preserve. It would be great to have this feature in SWI-Prolog, as a built-in alternative for floats.

There are also other alternatives that are much better than the floats we currently have.

All the best!
Markus

[Markus Triska]

Hi Jan,

On Saturday, June 18, 2016 at 8:19:50 PM UTC+2, Jan Burse wrote:

Further a speciality of SWI-Prolog the (**)/2 operator returns
integer instead of float. But not supported by (#=)/2:

(**)/2 has the wrong associativity; please use (^)/2 for exponentiation.

All the best!
Markus

[Jan Wielemaker]

On 06/19/2016 11:00 AM, Markus Triska wrote:
> Hi Jan,
>
> On Sunday, June 19, 2016 at 10:27:24 AM UTC+2, Jan Wielemaker wrote:
>
>
> you include functions that have values in $R$, rationals only give you
> an expensive false feeling of correctness. In other words, pi/0, sin/1,
> etc. require floats.
>
>
> One much better alternative to floats in this case are unums. Please see

> John Gustafson's recent book, "*The End of Error*":

>
> https://www.crcpress.com/The-End-of-Error-Unum-Computing/Gustafson/p/book/9781482239867
>
> It explains how to compute with unums and shows the important properties
> they preserve. It would be great to have this feature in SWI-Prolog, as
> a built-in alternative for floats.
>
> There are also other alternatives that are much better than the floats
> we currently have.

Sure. I'm happy if someone wants to generalise the internal arithmetic
APIs to easily support additional formats. That could also facilitate
alternative bignum libraries and possibly make this pluggable through
the C API, so you can load GMP, an alternative MP library, unum, etc. as
a library.

Not really an easy job as you both want to generalise and preserve
performance. Roughly, I think we'd need:

- (de)serialization to place numbers on the stacks
- conversion (casting) operations
- Define new arithmetic functions
- Hook into an arithmetic function to make it support
new formats or algorithms.
- Rules to deal with casting.

Cheers --- Jan

[Jan Wielemaker]

On 06/19/2016 10:27 AM, Jan Wielemaker wrote:
> I notice that GMP, which is currently used for rational support, is
> licensed under the GPL and cannot be compiled with the rest of the, now
> MIT licensed, SWI stack for commercial purposes.

Oh, before people start to feel uncomfortable, GMP is licensed by
LGPLv3. You can also use GMP version 3, which is licensed by the
LGPLv2. The LGPL is not imposed on other parts of the application,
so Prolog and your application can use any license. The LGPL does
pose some restrictions that you need to respect. Some of these
are hard to fulfil in some deployment scenarios and some scare
away commercial users, sometimes for a good reason and sometimes
not.

Cheers --- Jan

[Jan Burse]

Hi,

I am on purpose never writing "Hi Markus, please add this and that feature" here. Since
this is a discussion forum. I also don't know whether it makes sense to add bitwise
operations to CLP(FD), can you reason about them?

Interval consistency for bitwise operations is not extremely good. For example from
X #= Y /\ C you cannot bound Y, if X is bound. Not sure whether providing a CLP(FD)
wrapper is nothing more than rushing into writing such wrappers.

Here are some more investigations into (^)/2. There seems to be a lot of divergence
among CLP(FD) systems. I tried against DOSExclips:

a) Here is my (mathematical) expectation:

    X #= Y^(-1)*Z, Y=100, Z=25
    --> gives X = 4.

    (Could be generalize to X #= X1^A1*..*Xn^An, where we would
    allow Ai to be positive and negative)

b) Eclips reaction:
 
     Refuses negative exponent by exception.

     ?- X #= Y^(-1)*Z.
     out of range in ria_binop(5, -1.0Inf, 1.0Inf, -1.0, -1.0, _707, _708)
     Abort

     Although it could do the computation, with (/)/2 instead of (//)/2:

     ?- X #= Z / Y, Z=100, Y=25.
     X = 4
     Z = 100
     Y = 25

     ?- X #= Z // Y, Z=100, Y=25.
     instantiation fault in //(Z, Y, _500)
     Abort

c) SWI-Prolog reaction:

     First accepts the negative exponent:

     ?- X #= Y^(-1)*Z.
     _G1714*Z#=X,
     Y^ -1#=_G1714.

     But then gives a wrong result:

     ?- X #= Y^(-1)*Z, Z=100, Y=25.
     false.
    
     It could do the computation with (//)/2 but not with (/)/2:

     ?- X #= Z/Y, Z=100, Y=25.
     ERROR: Domain error: `clpfd_expression' expected, found `_G1151/_G1152'

     ?- X #= Z//Y, Z=100, Y=25.
     X = 4,
     Z = 100,
     Y = 25.

[Markus Triska]

Hi Jan,

On Sunday, June 19, 2016 at 2:01:40 PM UTC+2, Jan Burse wrote:

I am on purpose never writing "Hi Markus, please add this and that feature" here. Since
this is a discussion forum.

I welcome feature requests as part of the discussion.
 

Interval consistency for bitwise operations is not extremely good. For example from
X #= Y /\ C you cannot bound Y, if X is bound. Not sure whether providing a CLP(FD)
wrapper is nothing more than rushing into writing such wrappers.

I rushed into supporting them after 10 years of not supporting them. This is the way CLP(FD) development used to happen also in the past: Users let me know about a feature they need, and I do my best to make it available. Only in the more recent past, this has changed to users sometimes tacitly assuming that CLP(FD) cannot be be extended. At least I get the strong impression from the way the discussions are now happening: It seems that users have become less interested in actually contributing to development, and spend more time opposing it. In part, this is probably because the most vocal users were not even around during the initial phases of CLP(FD) development and now only rarely see completely new functionality being added because many very useful predicates are already available.

In the case of the bitwise operators, we take the same approach that was used for other more complex constraints: First, a rudimentary implementation is provided, so that we can finally move to using (#=)/2 in more places. This has now happened. Next, this is generalized to implement proper delays for cases that cannot yet be propagated. This has also happened already. For example, in the case you cite:

?- X #= Y /\ C.
X#=Y/\C.

?- 1 #= Y /\ C.
1#=Y/\C.

This only means that nothing more is derived in such cases. Next, we wait for user input. I mean not in the form of "CLP(FD) is teh suck", but in the form of "Could you please add propagation for the following situation: I have a CLP(FD) expression of the form ... etc.". Let's see if that happens. Next, I will add it, and you will have a more useful system.

Regarding (/)/2: This was previously used to denote what is now denoted by (//)/2. I will, in due time, re-introduce (/)/2 with a different meaning, so that the example you show will also work with (/)/2. However, I want to give users sufficient time to adapt their existing programs to this change.

All the best!
Markus

[Jan Burse]

BTW: The only difficult operators are really bitwise \/ and bitwise /\.
The other operators you can map to arithmetic:

     \ X               == -X-1               (sic!, who would know that?)
     X>>N           == X//2^N
     X<<N           == X*2^N

Now if your CLP(FD) system can also deal with negative exponents,
inside arguments of (//)/2 and (*)/2, you could also implement
>> and << such that you would also have:

     X<<N          == X>>(-N)

And both >> and << would not only work for positive arguments. This
would give you reasoning with \, << and >>. The propagation is already
there in your system, I find:

    ?- Y #= X*2^N, N in 5..7, X in 3..10.
    Y in 96..1280,

This could be the propagation of:

    ?- Y #= X<<N, N in 5..7, X in 3..10.
    /* doesn't work yet */

Bye

[Jan Burse]

Hi,

> BTW: The only difficult operators are really bitwise \/ and bitwise /\.

In CLP(B) one could do the following trick. Take a BDD, binary
decision diagram. Normally leaf nodes are 0 and 1. So this is
a bus of width 1.

You could also allow leaf nodes in the full integer ranges. These
are then busses of width 1 or greater. For convenience you could
add an array notation:

    X[N]           == (X /\ 1<<N)
    X[N] := E    == (X /\ \ (1<<N) \/ E)

Bye

[Jan Burse]

Am Sonntag, 19. Juni 2016 19:12:36 UTC+2 schrieb Markus Triska:

This only means that nothing more is derived in such cases. Next, we wait for user input. I mean not in the form of "CLP(FD) is teh suck", but in the form of "Could you please add propagation for the following situation: I have a CLP(FD) expression of the form ... etc.". Let's see if that happens. Next, I will add it, and you will have a more useful system.

You wouldn't need CLP(FD) for that. Thats only freeze/2 or when/2. You can
even combine freeze/2 and when/2 with CLP(FD).

So nobody has to wait for an integration of bitwise operations in any of the CLP(FD)
system, since freeze/2 and when/2 are usually already there:

    Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 7.3.22)
    Copyright (c) 1990-2015 University of Amsterdam, VU Amsterdam

    ?- X in 0..10, freeze(X, (0 =:= X /\ 1)), label([X]).
    X = 0 ;
    X = 2 ;
    X = 4 ;
    X = 6 ;
    X = 8 ;
    X = 10.

Works already for 10 years, or maybe less, dunno, depends on the CLP(FD)
system, and whether the same Prolog also supports freeze/2 and when/2.

I would expect from a CLP(FD) integration that it gives more business value
than only freeze/2 and when/2. But except for \, << and >> I guess its harder
to integrate /\ and \/ with some propagation, and not a 5 minutes quicky.

Bye

[Jan Burse]

 Better:

      X[N]           == (X>>N) /\ 1.
      X[N] := B    == (X /\ \ (1<<N) \/ (B<<N))

But I dunno how a >> or << would work on a BDD. Maybe
just shift the leafs. Hm. Or directly attack [], it would be
kind of a projection, similar to (^)/2.

Bye

[Markus Triska]

Hi Jan,

You wouldn't need CLP(FD) for that. Thats only freeze/2 or when/2.

I gave you more than that. For example, you can use bitwise operations in constraint reification:

?- X #= (Y >> (Z mod D)) #<==> T, D = 0.
D = T, T = 0,
X in inf..sup,
Z in inf..sup,
Y in inf..sup.

This is tedious and error-prone to express with freeze/2 or when/2. You are welcome to try it.

All the best,
Markus

[Jan Burse]

A mind might wander towards this direction:
http://stackoverflow.com/questions/13664870/reification-of-term-equality-inequality

But SICStus states the minimal requirement for reified constraints as follows:
https://sicstus.sics.se/sicstus/docs/4.0.8/html/sicstus/Reified-Constraints.html

Which I guess gives for equality when entailment is extremly weak:

    reified_eq(E1, E2, B) :- when((ground(E1),ground(E2);nonvar(B)), reified_eq2(E1, E2, B)).

    reified_eq2(E1, E2, B) :- var(B), !, (E1 =:= E2 -> B=1; B=0).
    reified_eq2(E1, E2, 0) :- E1 =:= E2.
    reified_eq2(E1, E2, 1) :- \+ (E1 =:= E2).

The above assumes E1 and E2 as total functions and not with some CLP(FD)
functions intervowen that can have inference of domain ranges etc..

I see some slight business value here, in the ease of combining an even weak
operation with the rest of CLP(FD).

For non-weak operations we can say something about E1 =:= E2, i.e. its
entailment, even when E1 and E2 are non-ground and in dependance of the other
constraints over the variables occuring in E1 and E2.

Bye

[Jan Burse]

Corr.:

    reified_eq(E1, E2, B) :- when((ground(E1),ground(E2);
                                                nonvar(B)),  reified_eq2(E1, E2, B)).

    reified_eq2(E1, E2, B) :- var(B), !, (E1 =:= E2 -> B=1; B=0).

    reified_eq2(E1, E2, 0) :- when((ground(E1), ground(E2)), E1 =:= E2).
    reified_eq2(E1, E2, 1) :- when((ground(E1), ground(E2)), \+ (E1 =:= E2)).

[Jan Burse]

Question is, why not allow (weak) reification of anything?
For example:

   X @< Y #<==> B.

In Jekejeke Prolog I already allow (weak) expression of anything.
For example:

     X #= foo(bar).

Which will be the same has:

    foo(bar, H), X #= H.

Could do the same for boolean expression aka reification. With
a when/2 helper:

   reify_anything(C, B) :- when((ground(C); nonvar(B)), reify_anything2(C, B)).

   reify_anything2(C, B) :- var(B), (C -> B=1; B=0).
   reify_anything2(C, 0) :- when(ground(C), \+ C).
   reify_anything2(C, 1) :- when(ground(C), C).

(P.S.: Got the (\+)/1 wrong in my previous posts).

Bye

[Jan Burse]

 But ultimately what will block you from implementing non-weak
/\ and \/ is, that these require different bound handling. Lets compare
(/\)/2 with min/2.

From a min/2 constraint:

    X #= min(Y, Z).

One can derive range constraints:

    X #= min(Y, Z), X #=< Y, X #=< Z.

For a (/\)/2 constraint something similar is possible, except that
the comparator is not yet part of CLP(FD) and even not found in the
ISO standard directly. So if we have:

    X #= Y /\ Z.

We could derive:

    X #= Y /\ Z, X subset_eq Y, X subset_eq Z

But neither subset_eq exists currently in CLP(FD), nor a set representation
that could deal with such a comparator. For example bitwise.

     3 subset_eq X, X subset_eq 6.

Has no solution and should fail. Its the same as:

      {0,1} subset_eq X, X subset_eq {1,2}

On the other hand:

     3 #=< X, X #=< 6

Has of course the solutions X in 3..6. So for the bitwise operations
a whole new domain range concept would be needed, if at all this
would make some sense. Still how would you label the stuff?

Bye

[Jan Burse]

Just noticed that the following already works in Jekejeke
Prolog before the current release 1.1.4:

    Works already since release 1.1.2:

     ?- X #= 1<<4.
     X = 16
   
But it slipped my attention that I could also delay if some
of the arguments are non-ground, and also sub-evaluate
via CLP(FD).

It worked already for ground arguments in Jekejeke Prolog
since each evaluable function (ISO terminology) is tunneld
by a predicate, so the above is basically:

     ?- <<(1,4,Y), X #= Y.
     Y = 16,
     X = 16

Further the following is also possible, before the current
release 1.1.4, since Jekejeke Prolog has further an automatic
bridging feature:

    Works already since release 1.1.2:

    factorial(0, 1).
    factorial(N, X) :- N>0, M is N-1, factorial(M, Y), X is N*Y.

    ?- X #= factorial(3).
    X = 6 ;
    No

But I am still not sure what the "attempt to delay everything
everywhere" would bring. Could possibly introduce any expression
and any reification delay quite simply based on this tunneling
and bridiging, just changes this line:

/**
 * C (finite):
 * A callable C is also a value expression.
 */
sys_value_expr(C, L, A) :-
   sys_callable(C), !,
   call(C, X),
   sys_value_expr(X, L, A).

http://www.jekejeke.ch/idatab/doclet/blog/en/docs/15_min/02_reference/finite/linform.html?hash=o483

Bye

If you also allow X #= factorial(3), (#=)/2 can handle much more
expressions than (is)/2 can do, and you could not be able to convert
back from (#=)/2 to (is)/2.

In Jekejeke Prolog this wouldn't be a problem if (#=)/2 is extended this
way since (is)/2 can handle arbitrary expressions because of
the aforementioned tunneling and bridging:

    ?- H is 1+2, factorial(H, X).
    X = 6 ;
    No
   
  - same as -

    ?- X is factorial(1+2).
    X = 6

See also:
Tunnels: Unifying evaluable functions and predicates. (Jekejeke)
https://plus.google.com/wm/1/+JekejekeCh/posts/6wWyUPi2MD3

[Jan Burse]

An important experiment could be whether its possible
to bootstrap CLP(FD) capable functions by such a mechanism.

For example do we need abs/1 hardwired inside the CLP(FD).
Wouldn't it be possible to supply an abs/1 function via a
predicate definition:

    abs(X, Y) :- ... /* what should go here */

The following would create a choice point:

    abs(X, Y) :- X #< 0, Y #= -X.
    abs(X, Y) :- X #>= 0, Y #= X.

But the following via reification wouldn't create a choice point,
but has possibly a weaker interval consistency as a CLP(FD)
builtin function abs/1:

    abs(X, Y) :- (X #< 0 #/\ Y #= -X)
          #\/ (X #>= 0 #/\ Y #= X).

Didn't try yet, since my reification is not yet completely realized,
cannot test interval consistency, this is exactly what is currently
missing as of release 1.1.4.

Bye

[Markus Triska]

Hi Jan,

On Tuesday, June 21, 2016 at 10:24:08 AM UTC+2, Jan Burse wrote:

An important experiment could be whether its possible
to bootstrap CLP(FD) capable functions by such a mechanism.

There is one important thing left to do in this respect, which is taking this idea even further: My goal is to use a declarative description of the actual arithmetic relations to generate the code for arithmetic propagators. Currently, we still need to implement propagators manually. Whether entirely or only partially makes little difference conceptually. I consider the development of arithmetic propagators truly finished if they can be automatically derived from arithmetic axioms. This is completely out of reach currently, but I think it is doable, and I will work on these ideas in CLP(Z).

All the best,

Markus