CLP(FD): what is necessary?

CLP(FD): what is necessary?

Post by Wit Jakucz » Fri, 14 Mar 2008 20:46:49


i,
I am transferring a private discussion with Markus Triska
about clpfd library that is a part of SWI Prolog.
Markus asked me (after tracking my discussion on
polish newsgroup with AL) what is wrong with his clp library.
I will be talking only about ECLiPSe and SWI because
this two prologs are only that could be considered
as free.

From my point of view, clp(fd) library must be
extensible. By extensible I mean not only technical
possibilities to write their own global constraints
but also good manual (SWI lacks such manual). ECLiPSe
provides its users with quite good manual on creating
global constraints. Moreover good clp library should
have a wide range of global constraints. Good reference
is SICStus. Both ECLiPSe and SWI seems poor comparing to
SICStus.

In our discussion Markus suggested that
incorporating propia or CHR could be an answer for
the need of customized global contraints.
Propia is really interesting but for now it
is completely useless for me as my software should
run quickly. To achieve this I have to write special
global constraints from scratch. Any black-box approach
is not acceptable. This differs CLP from MIP by the way.

Regarding CHR I cannot say much as I have never
used this methodology. Nevertheless it looks quite
interesting.

Good environment for developing software that
is based on clp should provide its users with clean
and robust interface. By clean I mean mainly
clear syntax. Delay clauses
(http://eclipse.crosscoreop.com/doc/userman/umsroot111.html)
are good approach. In ECLiPSe there is also another
mechanism based on suspensions (Internally both
approaches are equivalent). The problem with
ECLiPSe is that it each suspension can have a
priority. This makes implementing constraints
really painful and makes ECLiPSe not robust.
I had not enough time to track in depth Markus' library.
My impression is that it is less cleaner that ECLiPSe's
suspension mechanism but it seems to be more robust
(no priorities!).

Very nice mechanism has B-Prolog. Also SICStus is
a good solution.

So going back to Markus' basic question: "How can
I improve clpfd library?". My answer is to:
1) write a documentation with examples :)
2) Create more clean syntax for defining constraints.
It is really important to have a clear syntax
from which a user could easily deduce conditions
that wakes the constraint. The conditions are:
- a variable has been instantiated
- a variable has been bounded (min or max)
- a variable's domain has been changed

In ECLiPSe you can use the following syntax
(such syntax is clean to me):

suspend(
propagator(X),
Priority,
[
X->inst, %instantiated variable
X->ic:min, %lower bound has been changed
X->constrained %a domain has been altered
]
)

In SICStus you would use:
fd_global(
propagator(X),
state(Y),
[
val(X),
min(X),
dom(X)
]
)

Developer having such code can very quickly
deduce the logic behind global constraint.
In this example propagator(X) is woken
if one of the following conditions occur:
- X has been instantiated
- lower bound of X has been changed
- X's domain has been changed

Mark, could
 
 
 

CLP(FD): what is necessary?

Post by Jan Wielem » Fri, 14 Mar 2008 22:23:32


<snip>

Thanks for your input. I'd like to concentrate on this:


I think the discussion is about `free'. As you can learn from the FSF
website, free isn't about free as in free beer, but in free as in
freedom of speech. That is the case here as well. I'm more inclined to
use `Open'. Not in the way you us it, although that form of openness is
important to reach my `Open': community carried software. If you want to
do commercial development with a free Prolog, you should become member
of its community and guide it in the direction you want, either by
investing time in development, testing, documenting, etc. or by
investing money to get someone else (sometimes the main developers,
sometimes another expert) do the work. Using that principle it works for
both sides. The developers get financial resources and code from the
community, the users gets direct access to developers and the rest of
the community and profits from the testing and extensions from other
parts of the community.

Done properly, this is highly effective for everybody because it greatly
reduces overhead costs. Just think or marketing, legal costs, trying to
establish and protect license schemas, financial and organizational
hassle buying and selling software, etc.

Note that it works for small and big communities and even comparable to
commercial software. Specialized commercial software is very expensive,
while in small open communities each member needs to invest majorly. Big
mainstream commercial software is cheap and in big mainstream open
projects you don't have to do much.

I think Markus is doing a great job establishing a clp(fd) library with
some nice features. I'm sure he is interested in enhancing the design
and make it easy to extend.

Some things are almost inherently associated with community software.
Not that many developers like documenting and where documenting a single
piece of the cake is still doable, keeping the dependencies in the
overall documentation up to date is asking too much. Only big
communities can fix the documentation problem by regularly publishing
nice integrated documentation as a book. Small communities have to work
with nice, largely automated, tools to get some minimal documentation.

Cheers --- Jan

 
 
 

CLP(FD): what is necessary?

Post by ulric » Fri, 14 Mar 2008 22:50:47

Wit Jakuczun < XXXX@XXXXX.COM > writes:

The current interfaces in SICStus and ECLiPSe are for
experts only ; being very close to the engine. Not a
single property can be guaranteed by those interfaces.
The desire to provide better abstractions has not
yet produced the ultimate language for such extensions.
At some point in the past indexicals looked very promising.

So that is still an open area and your input is welcome!

The achievements of Markus Triska's clpfd implementation in SWI
so far have been to provide the basic constraints in a clean
and robust fashion with highlights as:

* Correctness: Similar to SICStus Prolog open domains are possible
thus extending CLP(FD) towards CLP(Z). While SICStus reports
overflows above 2^56 as representation errors, SWI has

* No limits (except resource limits, indeed):

?- 7^7^7 #>= X.

Note that other systems implicitly constrain all variables to
a small finite range. Failure in such systems means: No solution
within those limits. If a solution exists outside, you will not
find it.

* Favourable termination properties: All predicates and
constraints in SWI's library(clpfd) terminate.

With this library and SWI's ability to prevent infinite
terms you get a clean language for introductory courses!

Just defer is/2 and its archaic company to a more advanced level.
 
 
 

CLP(FD): what is necessary?

Post by A.L. » Fri, 14 Mar 2008 22:55:30

On 13 Mar 2008 13:23:32 GMT, Jan Wielemaker < XXXX@XXXXX.COM >




I see this discussion (at least, as it started on pl.comp.lang.c) a
bit differently: what is needed to have complete CLP(FD) system that
could be useb not only for solving MONEY and Sudoku problems, but
problems of industrial complexity ans scale.

One requirement, posted on that discssion was that there must be
framework for creating new global constraints. And this is what I
don't see in SWI CLP(FD) library. Or it is there, but I don't see
this?...

A.L.
 
 
 

CLP(FD): what is necessary?

Post by Wit Jakucz » Sat, 15 Mar 2008 00:10:40

Dnia 13 Mar 2008 13:23:32 GMT
Jan Wielemaker < XXXX@XXXXX.COM > napisa(a):

No. The discussion is about improving clp(fd) library
in SWI (and other free prologs). I have presented my point
of view, that's all.

I would prefer not talking about FSF and their understanding
of freedom. I understand you point of view though.

My post is a such guidance.

Of course! I happily expressed my opinions to Markus.
I did not want to criticize Markus.

Best regards
--
[ Wit Jakuczun <W.Jakuczun [at] wlogsolutions.com> ]
[ WLOG Solutions http://www.yqcomputer.com/ ]
 
 
 

CLP(FD): what is necessary?

Post by A.L. » Sat, 15 Mar 2008 01:18:40

On Thu, 13 Mar 2008 13:50:47 GMT, XXXX@XXXXX.COM




That what?... What "property"?...

I don't think that SICStus and ECLIPSE interface is "for experts
only'. Actually, both are pretty simple.


Agree. But actually, very little more.

The whole thread was NOT about criticizing anybody. Thw whole thread
was pretty technical: what is required to have commercial grade
CLP(FD) system in Prolog. Nobody was criticizing SWI and Marcus.

I would suggest to concentrate on technical issyes ratther than "who
did what and who did't what"

A.L.
 
 
 

CLP(FD): what is necessary?

Post by ulric » Sat, 15 Mar 2008 01:23:17

A.L. < XXXX@XXXXX.COM > writes:



Monotonicity and similar properties to guarantee that your
extention is a constraint at all. It is a night mare to
locate such bugs. I cannot imagine that you never ran into
those. Just think of unifications that instantanously assign
values to several variables, like (A-B=1-2).

Guaranteed termination would be a bonus.
 
 
 

CLP(FD): what is necessary?

Post by tomenannem » Sat, 15 Mar 2008 01:47:30


Users can also help writing and improving documentation.
Whoever likes to use the clpfd library should contribute
a little text for the documentation! If you couldn't
understand something and the developer told you how to
do it on comp.lang.prolog or another mailing list,
write a little bit of documentation. It's only fair that you
give something back for what you get.

If users would contribute just a little, they would benefit
a lot more.
 
 
 

CLP(FD): what is necessary?

Post by Wit Jakucz » Sat, 15 Mar 2008 01:58:25

Dnia Thu, 13 Mar 2008 11:18:40 -0500
A.L. < XXXX@XXXXX.COM > napisa(a):

Agree.

I support this suggestion! I wanted to talk about technical
issues. Nothing more...

Best regards
--
[ Wit Jakuczun <W.Jakuczun [at] wlogsolutions.com> ]
[ WLOG Solutions http://www.yqcomputer.com/ ]
 
 
 

CLP(FD): what is necessary?

Post by Joachim Sc » Sat, 15 Mar 2008 02:50:54


Yes, delay-clauses were invented first, but are now just
declarative syntactic sugar for the suspend/3 primitive:

delay p(X) if var(X).
p(X) :- writeln(just_instantiated(X)).

is implemented (via clause expansion) as

p(X) :- var(X), !, suspend(p(X), 0, X->inst).
p(X) :- writeln(just_instantiated(X)).

Delay clauses are nice for some simple cases, but not
general enough for most constraint applications.


> The problem with

Hmm, priorities were introduced to _address_ problems with
constraint implementation, not to create them :-)

Having propagators wake up with different priority can be
quite important, so i think it is an important feature for
a constraint system. Probably it is more relevant for a
system like ECLiPSe that aims at combining different solution
methods, than for a system that just wants to do FD.

I am not sure what you mean by "not robust" - do you refer to
the fact that higher priority propagators can interrupt lower
priority ones? I guess this can be confusing when implementing
a low priority propagator, but you can always create "atomic regions"
by wrapping them in call_priority/2.

A real problem of priorities is however that they are hard to
implement without slowing down the whole waking mechanism.


-- Joachim
 
 
 

CLP(FD): what is necessary?

Post by bart demoe » Sat, 15 Mar 2008 04:38:21


While I appreciate what you meant to write, I disagree with naming
this "correctness" - didn't I send a bug report to Markus recently
that pointed out something not quite correct in the SWI clpfd package,
and that was not caught by any of your testing ? It was unrelated to
the FD versus Z issue.
Please do not name something correct if it isn't [no blame is intended
towards Markus].



That's fine as long as the user is aware of it, and as long as the system
makes an effort making her aware of it. Nobody expects 1 << 34 to give the
correct answer in C, and everybody knows that to get the correct answer,
there is price to pay, and a particular library to use.



I would only name this favourable, if you have a proof that some
predicates or constraints in X's library(clpfd) don't - for any other X.



is/2 is certainly archaic, but also very useful. For me, the only archaic
thing about is/2 that really should be dumped, is the evaluation of source
level variables. Having eager arithmetic in a language is excellent.

Cheers

Bart Demoen
 
 
 

CLP(FD): what is necessary?

Post by A.L. » Sat, 15 Mar 2008 04:41:28

On Thu, 13 Mar 2008 17:50:54 +0000, Joachim Schimpf



OK, I am bot familiar with current version of ECLIPSE... Are
priorities defined for each constraint separately, or across teh
system? And what happens if I am using 2 custom constraints, each with
its own priorities numbered from 1 to 5?...

A.L.
 
 
 

CLP(FD): what is necessary?

Post by A.L. » Sat, 15 Mar 2008 05:15:54

On Thu, 13 Mar 2008 20:38:21 +0100, bart demoen < XXXX@XXXXX.COM >



Don't quite understand. Could you be more specific?...

A.L.