CLP(FD): what is necessary?

Dnia Fri, 14 Mar 2008 11:33:34 -0700 (PDT)
Annemie Janssens <janssens.annemie@gmail.com> napisa=C5=82(a):

> You can find lots of material on the CHR website:
> http://www.cs.kuleuven.be/~dtai/projects/CHR/
>=20
> 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...o.pl?id=3D42254
> * technical report:
> http://www.cs.kuleuven.be/publicati.../CW449.abs.html
>=20
Thank you.

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

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

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

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 ]

"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.

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

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.

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.