Home > Archive > Prolog > March 2008 > CLP(FD): what is necessary?
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
CLP(FD): what is necessary?
|
|
| Wit Jakuczun 2008-03-13, 8:14 am |
| Hi,
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/...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 you show us how you can do this in
SWI now?
2) develop global constraints that users could
use out-of-the-box.
3) do not try to pursuit ECLiPSe's propia or CHR.
Try to make as much as possible functionality
that SICStus' clp(fd) library offers.
It would have been MUCH better for ECLiPSe if developers
had implemented more global constraints
and not add new functionality (like propia).
4) Speed of execution is not always a matter. It is nice
to have fast prolog implementation but from my experience
the biggest speedup comes from specialised propagators
and not from specific implementation.
My opinion is that free prologs could be used for
proprietary software but their creators should
pay more attention to what is important to business
and business needs "just-enough" solutions and
not "do-everything" solutions.
Markus, I hope I have answered your questions.
I suppose that AL would drop his views on the
issue ;).
Best regards
--
[ Wit Jakuczun <W.Jakuczun [at] wlogsolutions.com> ]
[ WLOG Solutions http://www.wlogsolutions.com ]
| |
| Jan Wielemaker 2008-03-13, 7:49 pm |
| On 2008-03-13, Wit Jakuczun <wit@mefisto.hades> wrote:
> Hi,
> 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.
<snip>
Thanks for your input. I'd like to concentrate on this:
> My opinion is that free prologs could be used for
> proprietary software but their creators should
> pay more attention to what is important to business
> and business needs "just-enough" solutions and
> not "do-everything" solutions.
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
| |
|
| On 13 Mar 2008 13:23:32 GMT, Jan Wielemaker <jan@nospam.ct.xs4all.nl>
wrote:
>On 2008-03-13, Wit Jakuczun <wit@mefisto.hades> wrote:
>
><snip>
>
>Thanks for your input. I'd like to concentrate on this:
>
>
>I think the discussion is about `free'.
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.
| |
| Wit Jakuczun 2008-03-13, 7:49 pm |
| Dnia 13 Mar 2008 13:23:32 GMT
Jan Wielemaker <jan@nospam.ct.xs4all.nl> napisa=C5=82(a):
> <snip>
>=20
> Thanks for your input. I'd like to concentrate on this:
>=20
>=20
> I think the discussion is about `free'.
No. The discussion is about improving clp(fd) library
in SWI (and other free prologs). I have presented my point=20
of view, that's all.
I would prefer not talking about FSF and their understanding
of freedom. I understand you point of view though.
> If you want to do commercial development with a free Prolog, you should=20
> become member of its community and guide it in the direction you want
My post is a such guidance.=20
> 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.
>=20
Of course! I happily expressed my opinions to Markus.=20
I did not want to criticize Markus.
Best regards
--=20
[ Wit Jakuczun <W.Jakuczun [at] wlogsolutions.com> ]
[ WLOG Solutions http://www.wlogsolutions.com ]
| |
| Ulrich Neumerkel 2008-03-13, 7:49 pm |
| Wit Jakuczun <wit@mefisto.hades> writes:
> 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.
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.
| |
|
| On Thu, 13 Mar 2008 13:50:47 GMT, ulrich@mips.complang.tuwien.ac.at
(Ulrich Neumerkel) wrote:
>
>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.
That what?... What "property"?...
I don't think that SICStus and ECLIPSE interface is "for experts
only'. Actually, both are pretty simple.
>
>With this library and SWI's ability to prevent infinite
>terms you get a clean language for introductory courses!
>
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.
| |
| Ulrich Neumerkel 2008-03-13, 7:49 pm |
| A.L. <alewando@zanoza.com> writes:
>On Thu, 13 Mar 2008 13:50:47 GMT, ulrich@mips.complang.tuwien.ac.at
>(Ulrich Neumerkel) wrote:
>
>That what?... What "property"?...
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.
| |
| tomenannemie@gmail.com 2008-03-13, 7:49 pm |
|
> 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.
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.
| |
| Wit Jakuczun 2008-03-13, 7:49 pm |
| Dnia Thu, 13 Mar 2008 11:18:40 -0500
A.L. <alewando@zanoza.com> napisa=C5=82(a):
> I don't think that SICStus and ECLIPSE interface is "for experts
> only'. Actually, both are pretty simple.
>=20
Agree.
> I would suggest to concentrate on technical issyes ratther than "who
> did what and who did't what"
>=20
I support this suggestion! I wanted to talk about technical
issues. Nothing more...
Best regards
--=20
[ Wit Jakuczun <W.Jakuczun [at] wlogsolutions.com> ]
[ WLOG Solutions http://www.wlogsolutions.com ]
| |
| Joachim Schimpf 2008-03-13, 7:49 pm |
| Wit Jakuczun wrote:
> 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/...umsroot111.html)
> are good approach. In ECLiPSe there is also another
> mechanism based on suspensions (Internally both
> approaches are equivalent).
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
> ECLiPSe is that it each suspension can have a
> priority. This makes implementing constraints
> really painful and makes ECLiPSe not robust.
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
| |
| Jan Wielemaker 2008-03-13, 7:49 pm |
| On 2008-03-13, Wit Jakuczun <wit@mefisto.hades> wrote:
> Dnia Thu, 13 Mar 2008 11:18:40 -0500
> I support this suggestion! I wanted to talk about technical
> issues. Nothing more...
Ok. Wit raised both a technical and an organizational issue. I'm not
skilled enough in the details of CLP ... The only remark I have is that,
especially in open projects, it is vital to define robust interfaces if
you want community contributions.
Cheers --- Jan
| |
| bart demoen 2008-03-13, 7:49 pm |
| On Thu, 13 Mar 2008 13:50:47 +0000, Ulrich Neumerkel wrote:
> 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 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].
> 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.
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.
> * Favourable termination properties: All predicates and
> constraints in SWI's library(clpfd) terminate.
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.
> Just defer is/2 and its archaic company to a more advanced level.
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
| |
|
| On Thu, 13 Mar 2008 16:23:17 GMT, ulrich@mips.complang.tuwien.ac.at
(Ulrich Neumerkel) wrote:
>A.L. <alewando@zanoza.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).
>
Actually, no... I believe that it is enough to read manual carefully.
I have about 20 custom constraints... Of course, usual bugs happen...
>Guaranteed termination would be a bonus.
Agree, but can live without this...
A.L.
| |
|
| On Thu, 13 Mar 2008 20:38:21 +0100, bart demoen <bmd@cs.kuleuven.be>
wrote:
>On
>
>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.
>
Don't quite understand. Could you be more specific?...
A.L.
| |
| bart demoen 2008-03-13, 7:49 pm |
| On Thu, 13 Mar 2008 15:15:54 -0500, A.L wrote:
> On Thu, 13 Mar 2008 20:38:21 +0100, bart demoen <bmd@cs.kuleuven.be>
> wrote:
>
>
> Don't quite understand. Could you be more specific?...
Sorry to be so dense.
I meant:
?- X = 1+2, Y is X*3.
should give an error
instead of 9.
Source level variables to the right of is/2 (or in < =:= ...)
should be numbers, and not be evaluated.
Prolog could also have the ability to evaluate source level variables,
but it should be a separate built-in - and if Prolog would have only one
predicate, it should be the one that does not evaluate source level vars.
Hope I was more clear this time.
Cheers
Bart Demoen
| |
|
| On Thu, 13 Mar 2008 21:38:35 +0100, bart demoen <bmd@cs.kuleuven.be>
wrote:
>O
>Sorry to be so dense.
>I meant:
>
> ?- X = 1+2, Y is X*3.
>should give an error
>instead of 9.
>
>Source level variables to the right of is/2 (or in < =:= ...)
>should be numbers, and not be evaluated.
>
>Prolog could also have the ability to evaluate source level variables,
>but it should be a separate built-in - and if Prolog would have only one
>predicate, it should be the one that does not evaluate source level vars.
>
>Hope I was more clear this time.
Thanks!
A.L.
| |
| Joachim Schimpf 2008-03-13, 10:15 pm |
| bart demoen wrote:
>
> Sorry to be so dense.
> I meant:
>
> ?- X = 1+2, Y is X*3.
> should give an error
> instead of 9.
>
> Source level variables to the right of is/2 (or in < =:= ...)
> should be numbers, and not be evaluated.
That's what ECLiPSe does, though it hasn't been popular and I
had to defend that decision many times...
>
> Prolog could also have the ability to evaluate source level variables,
> but it should be a separate built-in - and if Prolog would have only one
> predicate, it should be the one that does not evaluate source level vars.
You can do it simply with a function, in ECLiPSe called eval/1
(implemented by predicate eval/2):
?- X = 1+2, Y is eval(X)*3.
This is type-clean and makes the intention clear.
-- Joachim
| |
| Joachim Schimpf 2008-03-13, 10:15 pm |
| A.L. wrote:
> On Thu, 13 Mar 2008 17:50:54 +0000, Joachim Schimpf
> <jschimpf@cisco.com> wrote:
>
>
> OK, I am bot familiar with current version of ECLIPSE... Are
> priorities defined for each constraint separately, or across teh
> system?
It's a simple scheme of a small number (12) of priorities
across the system.
> And what happens if I am using 2 custom constraints, each with
> its own priorities numbered from 1 to 5?...
We've had endless discussions about an improved priority scheme
within the ECLiPSe team and with users, but never arrived at a
satisfactory proposal. We considered float-priorities, partially
ordered ones, priority vectors, you name it...
There is some risk of trying to do things via priorities that are
better done via data-driven dependencies or localised computations.
The current, simple system allows you to assign priorities roughly
according to propagator complexity or effectiveness, to give debugging
and visualisation goals high priority, and a few other tricks.
A principle is that priority choice should not affect correctness,
only efficiency.
-- Joachim
| |
| Bart Demoen 2008-03-14, 8:13 am |
| Joachim Schimpf wrote:
> You can do it simply with a function, in ECLiPSe called eval/1
> (implemented by predicate eval/2):
>
> ?- X = 1+2, Y is eval(X)*3.
>
> This is type-clean and makes the intention clear.
I like that.
Cheers
Bart Demoen
| |
| Jan Wielemaker 2008-03-14, 8:13 am |
| On 2008-03-14, Bart Demoen <bmd@cs.kuleuven.ac.be> wrote:
> Joachim Schimpf wrote:
>
>
> I like that.
Nice indeed. If there is sufficient support, I'm happy to add eval(X) as
a function. Of course without dropping the normal evaluation.
--- Jan
| |
| Wit Jakuczun 2008-03-14, 8:13 am |
| Dnia Thu, 13 Mar 2008 17:50:54 +0000
Joachim Schimpf <jschimpf@cisco.com> napisa=C5=82(a):
> Yes, delay-clauses were invented first, but are now just
> declarative syntactic sugar for the suspend/3 primitive:
>=20
> delay p(X) if var(X).
> p(X) :- writeln(just_instantiated(X)).
>=20
> is implemented (via clause expansion) as
>=20
> p(X) :- var(X), !, suspend(p(X), 0, X->inst).
> p(X) :- writeln(just_instantiated(X)).
>=20
> Delay clauses are nice for some simple cases, but not
> general enough for most constraint applications.
>=20
Exactly. Moreover they are really clean.
>=20
>=20
> Hmm, priorities were introduced to _address_ problems with
> constraint implementation, not to create them :-)
>=20
The problems I had:
- priorities break atomicity of propagator. This means
that propagators with higher priority can change=20
situation INSIDE low-level propagator.
I was forced to use:
ic_kernel:exclude(X, Val) =20
instead of clean
X #\=3D Val =20
- It is not clear if there is any policy for=20
priorities. It would be much better to have
priorities defined like this:
Debugging:
suspend( =20
Goal,
debug,
Conditions
)
CLP(FD):
suspend(
Goal,
fd,
Conditions
)
and so on
Of course internally this could be solved
using priority system you have. But such
interface could help users to create
constraints with consistent priorities.
For example, I do not understand why=20
priorities for global constraints
form (ic_global) are different then=20
for other constraints (ic)?
> 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? =20
For example. Moreover priorities is another degree of
freedom. Robust system would be such that would eliminate=20
as much as possible degrees of freedom.
I had to check source code to check at what priority=20
runs different constraints (global use different priorities
then simple constraints).
> 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.
>=20
I know ;) (I used it). But still it is not something that
makes is easier. Much better would be to create
a standard for priorities.
> A real problem of priorities is however that they are hard to
> implement without slowing down the whole waking mechanism.
>=20
What was the main reason for introducing priorities?
Neither SWI, nor SICStus or B-Prolog have=20
priorities. You just declare constraint and off you go ;).=20
Best regards
--=20
[ Wit Jakuczun <W.Jakuczun [at] wlogsolutions.com> ]
[ WLOG Solutions http://www.wlogsolutions.com ]
| |
| Wit Jakuczun 2008-03-14, 8:13 am |
| Dnia Thu, 13 Mar 2008 14:41:28 -0500
A.L. <alewando@zanoza.com> napisa=C5=82(a):
> On Thu, 13 Mar 2008 17:50:54 +0000, Joachim Schimpf
> <jschimpf@cisco.com> wrote:
> =20
>=20
> 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?...
>=20
Constraints will be applied according to their priorities.
That would not be a problem. The problem (for me) was
that constraint with higher priority can be activated
inside constraint with lower priority unless you
take special care to prevent this.
Best regards
--=20
[ Wit Jakuczun <W.Jakuczun [at] wlogsolutions.com> ]
[ WLOG Solutions http://www.wlogsolutions.com ]
| |
| vscosta@gmail.com 2008-03-14, 8:13 am |
|
Hi!
Well, you have my support :). I'd actually suggest adding a prolog
flag to disable evaluation of generic terms outside eval.
Best
Vitor
On Mar 14, 8:31 am, Jan Wielemaker <j...@nospam.ct.xs4all.nl> wrote:
> On 2008-03-14, Bart Demoen <b...@cs.kuleuven.ac.be> wrote:
>
>
>
>
>
>
> Nice indeed. If there is sufficient support, I'm happy to add eval(X) as
> a function. Of course without dropping the normal evaluation.
>
> --- Jan
| |
| Joachim Schimpf 2008-03-14, 8:13 am |
| Wit Jakuczun wrote:
....
> - It is not clear if there is any policy for
> priorities. It would be much better to have
> priorities defined like this:
>
> Debugging:
>
> suspend(
> Goal,
> debug,
> Conditions
> )
>
> CLP(FD):
> suspend(
> Goal,
> fd,
> Conditions
> )
>
> and so on
>
> Of course internally this could be solved
> using priority system you have. But such
> interface could help users to create
> constraints with consistent priorities.
That's a good suggestion, thanks.
>
> For example, I do not understand why
> priorities for global constraints
> form (ic_global) are different then
> for other constraints (ic)?
The main point is that you want to execute "cheaper" propagators
before more expensive ones, e.g. constant time ones like X #= Y+3,
before linear ones like LongLinearExpression #> 0, before quadratic
or cubic time ones like some of the global constraints. Some of
your propagators may run a whole simplex algorithm for example.
Of course this is only a heuristic, the system of propagators
still needs to compute a fixpoint, and that should be the same
regardless of priorities.
....
> I know ;) (I used it). But still it is not something that
> makes is easier.
One idea I had to make this simpler was to separate waking-priority
from run-priority. Run-priority would by default be very high, so
that propagators are atomic by default, independent of the priority
with which they are woken.
>
> What was the main reason for introducing priorities?
> Neither SWI, nor SICStus or B-Prolog have
> priorities. You just declare constraint and off you go ;).
Hopefully answered above. You will also see that the new G12
constraint platform being developed in Melbourne has opted for
having priorities.
-- Joachim
| |
| Wit Jakuczun 2008-03-14, 8:13 am |
| Dnia Fri, 14 Mar 2008 11:33:59 +0000
Joachim Schimpf <jschimpf@cisco.com> napisa=C5=82(a):
>=20
> The main point is that you want to execute "cheaper" propagators
> before more expensive ones, e.g. constant time ones like X #=3D Y+3,
> before linear ones like LongLinearExpression #> 0, before quadratic
> or cubic time ones like some of the global constraints. Some of
> your propagators may run a whole simplex algorithm for example.
I understand.
> Of course this is only a heuristic, the system of propagators
> still needs to compute a fixpoint, and that should be the same
> regardless of priorities.
>=20
Correct but with atomic propagators it would be much easier
to maintain.
>=20
> ...
>=20
> One idea I had to make this simpler was to separate waking-priority
> from run-priority. Run-priority would by default be very high, so
> that propagators are atomic by default, independent of the priority
> with which they are woken.
>=20
I think that would be a VERY good idea. That would make priorities
more useful. One could use call_priority for this but it would
be much better to do it by default.
>=20
> Hopefully answered above. You will also see that the new G12
> constraint platform being developed in Melbourne has opted for
> having priorities.
>=20
Goals seems impressive.=20
Best regards
--=20
[ Wit Jakuczun <W.Jakuczun [at] wlogsolutions.com> ]
[ WLOG Solutions http://www.wlogsolutions.com ]
| |
| Jan Wielemaker 2008-03-14, 7:29 pm |
| On 2008-03-14, vscosta@gmail.com <vscosta@gmail.com> wrote:
>
> Hi!
>
> Well, you have my support :). I'd actually suggest adding a prolog
> flag to disable evaluation of generic terms outside eval.
Added. No flag. I just agree this is better style. When Bart&Tom
finish their type checker we can flag the is/2 type errors and people
can wrap the victim variables in eval(Var).
Flags changing runtime behaviour are far more evil than evaluating
terms under is/2 :-)
Cheers --- Jan
| |
|
| On 14 Mar 2008 13:31:56 GMT, Jan Wielemaker <jan@nospam.ct.xs4all.nl>
wrote:
>On 2008-03-14, vscosta@gmail.com <vscosta@gmail.com> wrote:
>
>Added. No flag. I just agree this is better style. When Bart&Tom
>finish their type checker we can flag the is/2 type errors and people
>can wrap the victim variables in eval(Var).
>
>Flags changing runtime behaviour are far more evil than evaluating
>terms under is/2 :-)
>
OK, but what standard says about this? Does it say at all?...
A.L.
| |
| Kish Shen 2008-03-14, 7:29 pm |
| Joachim Schimpf wrote:
> Wit Jakuczun wrote:
>
> Hopefully answered above. You will also see that the new G12
> constraint platform being developed in Melbourne has opted for
> having priorities.
>
The other main reason is for debugging, especially if your debugging
code (e.g. the debugger itself) is written in the source language, like
ECLiPSe. You want this code to run at a very high priority, so that the
state of the code you are debugging does not change as you are running
the debugger code.
Cheers,
Kish Shen
| |
| Neng-Fa Zhou 2008-03-14, 7:29 pm |
| "Wit Jakuczun" <wit@mefisto.hades> wrote in message
news:20080313124649.580be484@mefisto.hades...
> 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/...umsroot111.html)
> are good approach. In ECLiPSe there is also another
> mechanism based on suspensions (Internally both
> approaches are equivalent). The problem with
A successor of Delay Clauses, called Action Rules, have been developed for
implementing constraint propagators. Take a look at my TPLP paper to see how
nicely and efficiently various kinds of propagators can be implemented in
the language. Bart Demoen has added a package for action rules to SWI, but I
don't know how efficient his implementation is.
Cheers,
Neng-Fa
| |
| Joachim Schimpf 2008-03-14, 7:29 pm |
| Neng-Fa Zhou wrote:
....
> A successor of Delay Clauses, called Action Rules, ...
I don't think you should say that, because they are conceptually
very different. Delay clauses are meta level annotations that
don't affect the declarative meaning of the program (you can remove
them without changing the meaning of your prgram). If I am not mistaken,
Action rules do affect the meaning (because they contain "actions"), right?
-- Joachim
| |
| Wit Jakuczun 2008-03-14, 7:29 pm |
| Dnia Fri, 14 Mar 2008 13:56:56 +0000
Kish Shen <kishshen@yahoo.com> napisa=C5=82(a):
> Joachim Schimpf wrote:
=20[color=darkred]
>=20
> The other main reason is for debugging, especially if your debugging=20
> code (e.g. the debugger itself) is written in the source language, like=20
> ECLiPSe. You want this code to run at a very high priority, so that the=20
> state of the code you are debugging does not change as you are running=20
> the debugger code.
>=20
I do understand a need for debugging. But it would be MUCH
simpler and cleaner if debugging goals were not mixed with constraints.
User should declare that this goal is for debugging. System should
first evaluate debugging goals before evaluating other goals.
It is not good to use the same priority system for debugging and
constraints.
Best regards
--=20
[ Wit Jakuczun <W.Jakuczun [at] wlogsolutions.com> ]
[ WLOG Solutions http://www.wlogsolutions.com ]
| |
| Wit Jakuczun 2008-03-14, 7:29 pm |
| Dnia Fri, 14 Mar 2008 10:06:28 -0500
"Neng-Fa Zhou" <nzhou@acm.org> napisa=C5=82(a):
> "Wit Jakuczun" <wit@mefisto.hades> wrote in message=20
> news:20080313124649.580be484@mefisto.hades...
>=20
> A successor of Delay Clauses, called Action Rules, have been developed fo=
r=20
I have noticed Action Rules but I have not tried them.
What is the main difference between Action Rules and Delay Clauses?
Action Rules looks similar to CHR. What are the main
differences?
Best regards
--=20
[ Wit Jakuczun <W.Jakuczun [at] wlogsolutions.com> ]
[ WLOG Solutions http://www.wlogsolutions.com ]
| |
| Jan Wielemaker 2008-03-14, 7:29 pm |
| On 2008-03-14, A.L <alewando@zanoza.com> wrote:
> On 14 Mar 2008 13:31:56 GMT, Jan Wielemaker <jan@nospam.ct.xs4all.nl>
> wrote:
>
>
> OK, but what standard says about this? Does it say at all?...
Nothing. Many Prolog systems take the freedom to add more evaluable
functions. This is just one example. If you use it, it will work on
ECLiPSe, SWI-Prolog >= 5.6.53 and if I understand Vitor on the next
YAP release. On most other systems you get an exception. If there is
a good and portable type system for which having eval(_) is useful, it
will eventually get more popular and ISO standard. Dream dream ...
Cheers --- Jan
| |
|
| On Fri, 14 Mar 2008 10:06:28 -0500, "Neng-Fa Zhou" <nzhou@acm.org>
wrote:
>"Wit Jakuczun" <wit@mefisto.hades> wrote in message
>news:20080313124649.580be484@mefisto.hades...
>
>A successor of Delay Clauses, called Action Rules, have been developed for
>implementing constraint propagators. Take a look at my TPLP paper
Cannot find this paper.... Could you provide a link?...
A.L.
| |
| Neng-Fa Zhou 2008-03-14, 7:29 pm |
|
"Joachim Schimpf" <jschimpf@cisco.com> wrote in message
news:1205504359.212176@sj-nntpcache-3.cisco.com...
> Neng-Fa Zhou wrote:
> ...
>
> I don't think you should say that, because they are conceptually
> very different. Delay clauses are meta level annotations that
> don't affect the declarative meaning of the program (you can remove
> them without changing the meaning of your prgram). If I am not mistaken,
> Action rules do affect the meaning (because they contain "actions"),
> right?
I call (AR) Action Rules a successor of (DC) Delay Clauses because AR is
inspired by DC and AR subsumes DC (A delay clause is a special action rule
where the events watched are only ins events and the action is just true).
Cheers,
Neng-Fa
| |
| Neng-Fa Zhou 2008-03-14, 7:29 pm |
|
"A.L." <alewando@zanoza.com> wrote in message
news:vu9lt3haj2e3monvomvksptsm9j1qomkot@
4ax.com...
> On Fri, 14 Mar 2008 10:06:28 -0500, "Neng-Fa Zhou" <nzhou@acm.org>
> Cannot find this paper.... Could you provide a link?...
"Programming Constraint Propagation in Action Rules"
http://www.sci.brooklyn.cuny.edu/~zhou/papers/arule.pdf
arxiv.org/pdf/cs.PL/0506005
Here is another paper you might be interested in, which has been rejected
four times and yet to find a place to get published.
"The dom event and its use in implementing constraint propagators",
http://www.cs.gc.cuny.edu/tr/techreport.php?id=208
I have a plan to write a tutorial on the use of Action Rules to implement
constraint propagators for a wide range of constraints including linear,
non-linear, extensional, and global constraints. I'll keep you posted.
Cheers,
Neng-Fa
| |
| Annemie Janssens 2008-03-14, 7:29 pm |
| > I have noticed Action Rules but I have not tried them.
> What is the main difference between Action Rules and Delay Clauses?
> Action Rules looks similar to CHR. What are the main
> differences?
CHR tends to be higher-level than either Action Rules or Delay
Clauses.
While the other features are only available in one (or two?) system,
CHR is be availabe in Eclipse, SWI-Prolog, Yap, Ciao, SICStus, XSB
and hProlog.
You can find lots of material on the CHR website:
http://www.cs.kuleuven.be/~dtai/projects/CHR/
There is also a paper by the Action Rules and CHR implementors on
implementing CHR with Action Rules, which may be useful to see some
of the differences:
* CHR workshop version:
http://www.cs.kuleuven.ac.be/cgi-bi...nfo.pl?id=42254
* technical report:
http://www.cs.kuleuven.be/publicati.../CW449.abs.html
Cheers,
Tom
| |
|
| On Fri, 14 Mar 2008 13:15:12 -0500, "Neng-Fa Zhou" <nzhou@acm.org>
wrote:
>
>"A.L." <alewando@zanoza.com> wrote in message
> news:vu9lt3haj2e3monvomvksptsm9j1qomkot@
4ax.com...
>
>
>"Programming Constraint Propagation in Action Rules"
>http://www.sci.brooklyn.cuny.edu/~zhou/papers/arule.pdf
>arxiv.org/pdf/cs.PL/0506005
>
>Here is another paper you might be interested in, which has been rejected
>four times and yet to find a place to get published.
>
>"The dom event and its use in implementing constraint propagators",
>http://www.cs.gc.cuny.edu/tr/techreport.php?id=208
>
>I have a plan to write a tutorial on the use of Action Rules to implement
>constraint propagators for a wide range of constraints including linear,
>non-linear, extensional, and global constraints. I'll keep you posted.
>
Thanks!
A.L.
| |
|
| On Fri, 14 Mar 2008 11:33:34 -0700 (PDT), Annemie Janssens
<janssens.annemie@gmail.com> wrote:
>
>CHR tends to be higher-level than either Action Rules or Delay
>Clauses.
>While the other features are only available in one (or two?) system,
>CHR is be availabe in Eclipse, SWI-Prolog, Yap, Ciao, SICStus, XSB
>and hProlog.
>
>You can find lots of material on the CHR website:
>http://www.cs.kuleuven.be/~dtai/projects/CHR/
>
>There is also a paper by the Action Rules and CHR implementors on
>implementing CHR with Action Rules, which may be useful to see some
>of the differences:
>* CHR workshop version:
>http://www.cs.kuleuven.ac.be/cgi-bi...nfo.pl?id=42254
>* technical report:
>http://www.cs.kuleuven.be/publicati.../CW449.abs.html
>
Thanks for pointers; finally I know how CHR works :)
A.L.
| |
|
|
| bart demoen 2008-03-14, 7:29 pm |
| On Fri, 14 Mar 2008 10:06:28 -0500, Neng-Fa Zhou wrote:
> Bart Demoen has added a package for action rules to SWI, but I
> don't know how efficient his implementation is.
I am not so powerful as to be able to add a package to SWI :-)
What we did: write a translator from action rules to SWI-Prolog
that respects (hopefully) the semantics as we understood them. Not easy,
because there is no formal description of the semantics of ARs and the
informal description in the manual hides surprises, the actual
implementation in B-Prolog shows surprises (even to Neng-Fa, if I remember
correctly; no offence meant, just showing it is difficult) and the
B-Prolog sources (that could be taken as the ultimate specification) are
invisible.
The translation does not result in efficient code, unless there is
decent support from the underlying Prolog system (and AFAWK no major
system has such decent support).
All in all, I consider Action Rules as a very expressive tool,
but unfortunately underspecified and with some implementation driven
decisions in it. Maybe that is fine, but it needs more scrunity if it
would have to become a widely accepted feature. Also, the concept is still
evolving because problems (bugs) and new features creep up from time to
time.
I am not against ARs at all, I just wish we (Neng-Fa, Joachim, me and
others) had more time to investigate the issues, clarify the relation with
ECLiPSe delay clauses, the HAL delay construct etc. And maybe come up with
a semantics of all these things - the semantics could be given by a
translator (ala term-expansion of something similar - no formal semantics
with evolving algebras, denotational semantics, whatever is needed I hope).
One thing I would like to understand: how can priorities be
integrated/reconciled with Action Rules ? Perhaps a dual question: why
does B-Prolog with its ARs not have priorities ?
Cheers
Bart Demoen
| |
| bart demoen 2008-03-14, 7:29 pm |
| On Fri, 14 Mar 2008 14:19:18 +0000, Joachim Schimpf wrote:
> Delay clauses are meta level annotations that
> don't affect the declarative meaning of the program (you can remove
> them without changing the meaning of your prgram).
You earlier gave the example:
> delay p(X) if var(X).
> p(X) :- writeln(just_instantiated(X)).
I can certainly not remove the delay declaration without changing the
procedural meaning of the program.
Now for ARs, it is probably true one can't just change the => into :-
in every Action Rule and get a program that is declaratively the same.
But that seems more a feature of the choice of syntax than of the
principle, no ?
Cheers
Bart Demoen
| |
| bart demoen 2008-03-14, 7:29 pm |
| On Fri, 14 Mar 2008 11:33:34 -0700, Annemie Janssens wrote:
> CHR tends to be higher-level than either Action Rules or Delay
> Clauses.
> While the other features are only available in one (or two?) system,
> CHR is be availabe in Eclipse, SWI-Prolog, Yap, Ciao, SICStus, XSB
> and hProlog.
Note that these two statements are about orthogonal issues: availability
and level.
But both seem to be true - for the second statement, just look at the
manuals and count.
For the first statement: the CHR language proper does never refer to the
degree of instantiation of a source level variable, and it has no explicit
language construct to postpone something. All this is implicit in the
semantics of the guards, and the matching in the heads (something
partially true in action rules). The other big difference is that in CHR,
one can express in the head a conjunction of truths, while action rules
(and delay clauses) only allow for inference based on (search for) single
truths.
Cheers
Bart Demoen
| |
| Wit Jakuczun 2008-03-14, 7:29 pm |
| Dnia Fri, 14 Mar 2008 12:57:03 -0500
"Neng-Fa Zhou" <nzhou@acm.org> napisa=C5=82(a):
>=20
> "Joachim Schimpf" <jschimpf@cisco.com> wrote in message=20
> news:1205504359.212176@sj-nntpcache-3.cisco.com...
>=20
> I call (AR) Action Rules a successor of (DC) Delay Clauses because AR is=
=20
> inspired by DC and AR subsumes DC (A delay clause is a special action rul=
e=20
> where the events watched are only ins events and the action is just true).
>=20
And what about :
suspend( agent(X),=20
Priority,
[
inst(X)
]
)
where
agent(X) :-
Condition(X),
Action(X).
It look like:
agent(X), Condition(X), { ins(X) } =3D> Action(X).
What is the difference between suspension mechanism that
is available in ECLiPSe and AR?
Best regards
--=20
[ Wit Jakuczun <W.Jakuczun [at] wlogsolutions.com> ]
[ WLOG Solutions http://www.wlogsolutions.com ]
| |
| Neng-Fa Zhou 2008-03-14, 7:29 pm |
|
"bart demoen" wrote in message
news:pan.2008.03.14.20.09.43.577477@cs.kuleuven.be...
> On Fri, 14 Mar 2008 10:06:28 -0500, Neng-Fa Zhou wrote:
> informal description in the manual hides surprises, the actual
> implementation in B-Prolog shows surprises (even to Neng-Fa, if I remember
> correctly; no offence meant, just showing it is difficult) and the
> B-Prolog sources (that could be taken as the ultimate specification) are
> invisible.
The AR that originally designed for programming constraint propagation has a
very simple semantics. Thanks to Kazunori Ueda san who helped clarify the
description of the semantics in the TPLP paper. Later on, extensions such as
disjunctive channels were added to make AR a target language for compiling
CHR. I agree that these extensions complicates the semantics, but most users
may not be interested in them.
Regarding the implementation, I have complete confidence in the quality in
the next version (7.1) to be released soon. The CLP(FD) system was tested
using a suite of over 5000 programs under different settings for GC and no
problem was found.
I wish I could make B-Prolog open source. Can you find a sponsor for it:-)
> All in all, I consider Action Rules as a very expressive tool,
> but unfortunately underspecified and with some implementation driven
> decisions in it. Maybe that is fine, but it needs more scrunity if it
> would have to become a widely accepted feature. Also, the concept is still
> evolving because problems (bugs) and new features creep up from time to
> time.
That's why I feel the need for a comprehensive tutorial. You are welcome to
join the effort if you are interested.
> One thing I would like to understand: how can priorities be
> integrated/reconciled with Action Rules ? Perhaps a dual question: why
> does B-Prolog with its ARs not have priorities ?
The quick answer is that I didn't feel such a need for a priority construct.
For certain constraint problems, changing the order of propagators can lead
to better performance, but in general you pay more than you gain as far as
programming constraint propagators is concerned. Since in B-Prolog
propagators are activated in the order they are created, you could use this
fact to program some simple strategies.
Cheers,
Neng-Fa
| |
|
| On Fri, 14 Mar 2008 19:58:36 -0500, "Neng-Fa Zhou" <nzhou@acm.org>
wrote:
>
>I wish I could make B-Prolog open source. Can you find a sponsor for it:-)
What it means "sponsor for open source"?..
A.L.
| |
| Joachim Schimpf 2008-03-15, 8:10 am |
| bart demoen wrote:
> On Fri, 14 Mar 2008 14:19:18 +0000, Joachim Schimpf wrote:
>
>
>
> You earlier gave the example:
>
>
> I can certainly not remove the delay declaration without changing the
> procedural meaning of the program.
Touche :-)
I should have said the declarative, logical reading.
It does not hold for side effects or metalogical constructs.
-- Joachim
| |
| Markus Triska 2008-03-18, 7:19 pm |
| A.L. <alewando@zanoza.com> writes:
>
> Agree. But actually, very little more.
As most current users of SWI's library(clpfd) seem to use it in the
context of teaching, this area is currently most important. However, I
will also help users from other areas: If you or anybody else needs a
specialisied constraint, I can give a few hints how to add it to the
library (which is easy), and help with the implementation - just e-mail
me. Such requirements will also help to find a good extension language.
| |
|
| On Tue, 18 Mar 2008 20:00:55 +0100, Markus Triska <triska@logic.at>
wrote:
>A.L. <alewando@zanoza.com> writes:
>
>
>As most current users of SWI's library(clpfd) seem to use it in the
>context of teaching, this area is currently most important. However, I
>will also help users from other areas: If you or anybody else needs a
>specialisied constraint, I can give a few hints how to add it to the
>library (which is easy), and help with the implementation - just e-mail
>me. Such requirements will also help to find a good extension language.
Sorry, I am using SICStus. However, it would be interesting for
everybody how to define custom constraints. Is this too hard to be
published in the manual?...
A.L.
| |
| Ulrich Neumerkel 2008-03-18, 7:19 pm |
| bart demoen <bmd@cs.kuleuven.be> writes:
>On Thu, 13 Mar 2008 13:50:47 +0000, Ulrich Neumerkel wrote:
>
>
>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].
What is correct in SICStus and SWI is the interface that permits
open domains - certainly not the implementation itself. If the
interface as such is incorrect, no implementation, no matter how
good, will ever be able to overcome these shortcomings.
Concerning the correctness of the implementation, I am certainly
dissatisfied with the current state offering inherently incomplete
testing as the only choice. Still I am very happy about the
feedback of attentive observers!
For similar reasons I am interested in a global constraint
interface that guarantees as many constraint-properties as possible.
>
>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.
Try X #> Y, Y #> X, X #> 0 in your favorite system. Termination
can only be observed as an overflow of the domain. In some sense
any propagation mechanism over integers terminates as it will continue
only if some bound has been reduced thus resulting eventually
in a resource overflow. I hope we agree that such cases should
not be considered terminating.
|
|
|
|
|