I managed to get drools to work the same way no matter what the insertion order. (See
attached eclipse project.)
Basically I created a custom conflict resolver that preempts the use of recency: it orders
matched tuples according to their objects' hash codes first. (That technically
won't work to completely ignore recency in all cases because of the way most java VMs
create default hash codes, but it's good enough for this example.) It's possible
that Jess uses a conflict resolution rule like this by default and that's why it has
this result out of the box.
--- On Fri, 4/17/09, Paul Fodor <paul.i.fodor(a)gmail.com> wrote:
From: Paul Fodor <paul.i.fodor(a)gmail.com>
Subject: Re: [rules-users] Negation semantics in Drools
To: "Rules Users List" <rules-users(a)lists.jboss.org>
Date: Friday, April 17, 2009, 11:28 PM
Hi Edson,
2009/4/17 Edson Tirelli <tirelli(a)post.com>
>
>
> Paul,
>
> I am not an expert on logic programming, but in
this case, your example
> is negating a goal (not a fact) in the backward
chaining:
>
> win(X):- move(X,Y), not(win(Y)).
>
> Pure forward chaining systems don't have goals,
since they are data
> driven.
>
> I don't think this would be a good or fair
comparison because it is
> comparing a native concept in one side and an emulated
concept in the other
> side. If you were negating an actual fact, the
comparison would be more an
> apples-to-apples comparison.
>From the logic point of view, win/2 and move/2 are both
literals (atoms, if
no explicit negation is used) and we define clauses (which
can be
facts or rules). The logical semantics (well-founded model
theory or stable
model semantics) makes no distinction between the negation
of a literal
move/2 (defined through a set of facts) and the negation of
a literal win/2
(which is defined through a recursive rule).
These are declarative semantics and have nothing to do with
the operational
semantics (how to actually compute them).
There are forward chaining systems (such as: DLV,
OntoBroker from Ontoprise,
IRIS) that compute them as well as some top-down systems
(tabled XSB, Yap).
We are interested in measuring the performance for a set of
features
that are considered important for the Semantic Web
(computing logical
models, dynamic updates, joins or relations, recursion
rules, persistent
data, etc.). For all these features we wanted to test the
technology for
rule systems (production rule systems were one of the
technologies we
studied). I agree that production rule systems are more fit
for other
tasks (for instance, reactive rules), but we wanted to see
if they can be
easily used for the Semantic Web tasks. For each feature
that we tested, we
tried our best to represent it in the best way for every
given system. We
are always open to sugestions of other banchmarks to test.
Regards,
Paul
>
> Just my .02c
>
>
> Edson
>
> 2009/4/17 Paul Fodor <paul.i.fodor(a)gmail.com>
>
>> Now, I am curious. What is the background on
this exercise? There are
>>> some problems that are better suited for
backward and others better suited
>>> for forward chaining. Most problems would be
modeled in very different ways
>>> in each technology.
>>
>>
>> It is just a set of tests we made in a suite of
benchmarks. We wanted
>> compare and benchmark both the different the
technologies and various rule
>> systems.
>>
>>
>>> If we were just searching for the solution,
it would just be the case
>>> of writing (in forward chaining) one or two
rules that would provide the
>>> correct answer. But since this seems to be an
academic exercise, I am
>>> curious to understand the goals of it so that
we can properly model it.
>>
>>
>> The goal of this particular test (and our other
stratified or
>> non-stratified tests) was to see how efficient are
implementations of
>> default negation in rule systems. Programs using
negation can be very
>> various, but we tried to come up with a bunch of
standard classic problems
>> and implemented them in the best way possible in
each rule system.
>>
>> You are right that each technology has its own
strong and weak points
>> depending on the tasks intended to solve. Even the
way of implementing each
>> particular task differs a lot on various rule
systems.
>>
>> Regards,
>> Paul.
>>
>>
>>> Cheers,
>>
>>
>>> Edson
>>>
>>> 2009/4/17 Paul Fodor
<paul.i.fodor(a)gmail.com>
>>>
>>>> Hi Edson,
>>>>
>>>> The "insertLogical" doesn't
work for non-stratified programs.
>>>> For instance, in the win-nowin example, if
there is a move(1,2) and
>>>> a move(2,1), the order in which the two
facts are inserted determines the
>>>> final model (please see hte tests below).
>>>>
>>>> In logic programming, this example has two
stable models: {win(1)} and
>>>> {win(2)}, or a well-founded model {}
(win(1) and win(2) are both undefined).
>>>>
>>>> Regards,
>>>> Paul.
>>>> *
>>>>
>>>> package
>>>> *tests;
>>>>
>>>> *
>>>>
>>>> import
>>>> *tests.Test.Win;*
>>>>
>>>> import
>>>> *tests.Test.Move;
>>>>
>>>> *
>>>>
>>>> rule
>>>> *"direct"
>>>>
>>>> *when*
>>>>
>>>> m : Move(x : first, y : second)
>>>>
>>>> *not* Win(first == y)
>>>>
>>>> *then*
>>>>
>>>> *insertLogical*(*new* Win(m.getFirst()));*
>>>>
>>>> end
>>>> *
>>>>
>>>> move
>>>>
>>>> 1
>>>>
>>>> 2
>>>>
>>>> move
>>>>
>>>> 2
>>>>
>>>> 1
>>>>
>>>> Test:
>>>>
>>>> reading rulefile: win.drl ...
>>>>
>>>> reading datafile: win_upper3_drools.drools
...
>>>>
>>>> loading cputime: 0.016
>>>>
>>>> loading walltime: 0.016
>>>>
>>>> calculating ...
>>>>
>>>> computing cputime: 0.0
>>>>
>>>> computing walltime: 0.0040
>>>>
>>>> Derived facts in memory:move(1, 2).
>>>>
>>>> win(2).
>>>>
>>>> move(2, 1).
>>>>
>>>> 3
>>>>
>>>> move
>>>>
>>>> 2
>>>>
>>>> 1
>>>>
>>>> move
>>>>
>>>> 1
>>>>
>>>> 2
>>>>
>>>> Test:
>>>>
>>>> reading rulefile: win.drl ...
>>>>
>>>> reading datafile: win_upper4_drools.drools
...
>>>>
>>>> loading cputime: 0.016
>>>>
>>>> loading walltime: 0.016
>>>>
>>>> calculating ...
>>>>
>>>> computing cputime: 0.0
>>>>
>>>> computing walltime: 0.0040
>>>>
>>>> Derived facts in memory:move(2, 1).
>>>>
>>>> win(1).
>>>>
>>>> move(1, 2).
>>>>
>>>> 3
>>>>
>>>> 2009/4/17 Edson Tirelli
<tirelli(a)post.com>
>>>> >
>>>> >
>>>> > I did not had time to analyze what
jess is doing, but note that
>>>> what is important is the final answer. In
your example, with Move(1,2) and
>>>> Move(2,3), the final answer must be
Win(2), right? And that is what Drools
>>>> will answer, does not matter the order in
which the data is entered into the
>>>> engine.
>>>> >
>>>> > BUT, *very important*: the
following construct in backward
>>>> chaining:
>>>> >
>>>> > win(X):- move(X,Y), not(win(Y)).
>>>> >
>>>> > Is better represented in forward
chaining using *logicalInsert*
>>>> instead of a regular *insert*:
>>>> >
>>>> > rule "direct" % Drools
>>>> >
>>>> > when
>>>> > m : Move(x : first, y :
second)
>>>> > not Win(first == y)
>>>> > then
>>>> > logicalInsert(new
Win(m.getFirst()));
>>>> > end
>>>> >
>>>> > Since in your backward chaining
rule, only one win() predicate
>>>> instantiation will remain true.
>>>> >
>>>> > So, even with differences in the
reasoning algorithm, the answer
>>>> is correct.
>>>> >
>>>> > Please explain further if I am
missing anything.
>>>> >
>>>> > Edson
>>>> >
>>>> >
>>>> > 2009/4/17 Paul Fodor
<paul.i.fodor(a)gmail.com>
>>>> >>
>>>> >> Hi Edson, Greg,
>>>> >> I don't think the rule is
written wrong. This is how the win-nowin
>>>> program is written in logic programming: X
wins if there is a move from X to
>>>> some Y and Y doesn't win:
>>>> >>
>>>> >> win(X):- move(X,Y), not(win(Y)).
>>>> >>
>>>> >> rule "direct" % Drools
>>>> >>
>>>> >> when
>>>> >> m : Move(x : first, y :
second)
>>>> >> not Win(first == y)
>>>> >> then
>>>> >> insert(new Win(m.getFirst()));
>>>> >> end
>>>> >>
>>>> >> I think that it's interesting
that, in Jess (another production rule
>>>> system), the stratified model is always
computed right, no matter what was
>>>> the order of the facts in the database. If
you want to take a look, please
>>>> see the equivalent program in Jess for
win-nowin that I attached. Just run
>>>> it with:
>>>> >> jess test.clp
>>>> >>
>>>> >> win_upper1_jess.jess
>>>> >>
>>>> >> (move (cur 1) (next 2))
>>>> >> (move (cur 1) (next 3))
>>>> >> (move (cur 2) (next 4))
>>>> >> (move (cur 2) (next 5))
>>>> >> ...
>>>> >>
>>>> >> win_upper2_jess.jess
>>>> >>
>>>> >> (move (cur 2) (next 4))
>>>> >> (move (cur 2) (next 5))
>>>> >> (move (cur 1) (next 2))
>>>> >> (move (cur 1) (next 3))
>>>> >> ...
>>>> >>
>>>> >> test.clp:
>>>> >>
>>>> >> (deftemplate move (slot cur)
(slot next))
>>>> >> (deftemplate win (slot val))
>>>> >>
>>>> >> (defrule find_win
>>>> >> (move (cur ?cur) (next
?next))
>>>> >> (not (win (val ?next)))
>>>> >> =>
>>>> >> (assert (win (val ?cur)))
>>>> >> )
>>>> >>
>>>> >> (defquery query-win
>>>> >> (win (val ?val))
>>>> >> )
>>>> >> (open "win_result.txt"
output a)
>>>> >> (printout output
./win_upper1_jess.jess crlf)
>>>> >> (reset)
>>>> >> (load-facts
"./win_upper1_jess.jess")
>>>> >> (bind ?tmx (call
java.lang.management.ManagementFactory
>>>> getThreadMXBean))
>>>> >> (deffunction cputime () (return
(* (?tmx getCurrentThreadCpuTime)
>>>> 1E-9)))
>>>> >> (bind ?starttime_wall (time))
>>>> >> (bind ?starttime_cpu (cputime))
>>>> >> (run)
>>>> >> (bind ?query_result (run-query*
query-win))
>>>> >> (bind ?count 0)
>>>> >> (while (?query_result next)
>>>> >> (++ ?count)
>>>> >> )
>>>> >> (printout output "solutions:
" ?count crlf)
>>>> >> (bind ?endtime_cpu (cputime))
>>>> >> (bind ?endtime_wall (time))
>>>> >> (bind ?walltime (- ?endtime_wall
?starttime_wall))
>>>> >> (bind ?cputime (- ?endtime_cpu
?starttime_cpu))
>>>> >> (printout output "computing
cputime: " ?cputime crlf)
>>>> >> (printout output "computing
walltime: " ?walltime crlf)
>>>> >> (close output)
>>>> >>
>>>> >> Regards,
>>>> >> Paul Fodor.
>>>> >>
>>>> >> 2009/4/16 Edson Tirelli
<tirelli(a)post.com>
>>>> >>>
>>>> >>> Ha, thanks a lot Greg. I
need new glasses... he is actually
>>>> comparing with the parameter
"second", but when creating the win fact, using
>>>> the parameter "first".
>>>> >>>
>>>> >>> not Win(first == m.second)
>>>> >>> insert(new Win(m.first));
>>>> >>>
>>>> >>> Yes, in this case the
engine is working exactly as it should.
>>>> >>>
>>>> >>> Anyway, I added the
(fixed) test case to the codebase, just in
>>>> case. :)
>>>> >>>
>>>> >>> Thanks,
>>>> >>> Edson
>>>> >>>
>>>> >>> 2009/4/16 Greg Barton
<greg_barton(a)yahoo.com>
>>>> >>>>
>>>> >>>> You don't have to
worry. The engine is acting as it should.
>>>> >>>>
>>>> >>>> The rule Paul had was
this, a bit simplified for clarity:
>>>> >>>>
>>>> >>>> rule "direct"
>>>> >>>> when
>>>> >>>> m : Move()
>>>> >>>> not Win(first ==
m.second)
>>>> >>>> then
>>>> >>>> insert(new
Win(m.first));
>>>> >>>> end
>>>> >>>>
>>>> >>>> If the insertion order is
[Move(1,2), Move(2,3)] then the rule
>>>> matches first on Move(2,3) and Win(2) is
inserted. No other rule fires
>>>> because now Move(1,2) and Win(2) match up,
removing the instantiation with
>>>> Move(1,2) from the agenda.
>>>> >>>>
>>>> >>>> If the insertion order is
[Move(2,3), Move(1,2)] then the order is
>>>> this:
>>>> >>>>
>>>> >>>> matched Move(1,2) insert
Win(1)
>>>> >>>> matched Move(2,3) insert
Win(2)
>>>> >>>>
>>>> >>>> The insertion of Win(1)
in the first firing does NOT prevent the
>>>> instantiation with Move(2,3) from then
firing.
>>>> >>>>
>>>> >>>> So it's all good. :)
Sample code and output attached.
>>>> >>>>
>>>> >>>> --- On Thu, 4/16/09, Greg
Barton <greg_barton(a)yahoo.com> wrote:
>>>> >>>>
>>>> >>>> > From: Greg Barton
<greg_barton(a)yahoo.com>
>>>> >>>> > Subject: Re:
[rules-users] Negation semantics in Drools
>>>> >>>> > To: "Rules
Users List" <rules-users(a)lists.jboss.org>
>>>> >>>> > Date: Thursday,
April 16, 2009, 8:50 PM
>>>> >>>> > It is on the latest
snapshot release,
>>>> >>>> >
5.0.0.20090417.005612-483
>>>> >>>> >
>>>> >>>> > --- On Thu, 4/16/09,
Edson Tirelli <tirelli(a)post.com>
>>>> >>>> > wrote:
>>>> >>>> >
>>>> >>>> > > We need to
investigate if that is still happening
>>>> >>>> > in
>>>> >>>> > > latest trunk.
>>>> >>>> >
>>>> >>>> >
>>>> >>>> >
>>>> >>>> >
_______________________________________________
>>>> >>>> > rules-users mailing
list
>>>> >>>> >
rules-users(a)lists.jboss.org
>>>> >>>> >
https://lists.jboss.org/mailman/listinfo/rules-users
>>>> >>>>
>>>> >>>>
>>>> >>>>
>>>> >>>>
_______________________________________________
>>>> >>>> rules-users mailing list
>>>> >>>>
rules-users(a)lists.jboss.org
>>>> >>>>
https://lists.jboss.org/mailman/listinfo/rules-users
>>>> >>>>
>>>> >>>
>>>> >>>
>>>> >>>
>>>> >>> --
>>>> >>> Edson Tirelli
>>>> >>> JBoss Drools Core
Development
>>>> >>> JBoss, a division of Red Hat
@
www.jboss.com
>>>> >>>
>>>> >>>
_______________________________________________
>>>> >>> rules-users mailing list
>>>> >>> rules-users(a)lists.jboss.org
>>>> >>>
https://lists.jboss.org/mailman/listinfo/rules-users
>>>> >>>
>>>> >>
>>>> >>
>>>> >>
_______________________________________________
>>>> >> rules-users mailing list
>>>> >> rules-users(a)lists.jboss.org
>>>> >>
https://lists.jboss.org/mailman/listinfo/rules-users
>>>> >>
>>>> >
>>>> >
>>>> >
>>>> > --
>>>> > Edson Tirelli
>>>> > JBoss Drools Core Development
>>>> > JBoss, a division of Red Hat @
www.jboss.com
>>>> >
>>>> >
_______________________________________________
>>>> > rules-users mailing list
>>>> > rules-users(a)lists.jboss.org
>>>> >
https://lists.jboss.org/mailman/listinfo/rules-users
>>>> >
>>>>
>>>>
>>>>
>>>>
_______________________________________________
>>>> rules-users mailing list
>>>> rules-users(a)lists.jboss.org
>>>>
https://lists.jboss.org/mailman/listinfo/rules-users
>>>>
>>>>
>>>
>>>
>>> --
>>> Edson Tirelli
>>> JBoss Drools Core Development
>>> JBoss, a division of Red Hat @
www.jboss.com
>>>
>>>
_______________________________________________
>>> rules-users mailing list
>>> rules-users(a)lists.jboss.org
>>>
https://lists.jboss.org/mailman/listinfo/rules-users
>>>
>>>
>>
>> _______________________________________________
>> rules-users mailing list
>> rules-users(a)lists.jboss.org
>>
https://lists.jboss.org/mailman/listinfo/rules-users
>>
>>
>
>
> --
> Edson Tirelli
> JBoss Drools Core Development
> JBoss, a division of Red Hat @
www.jboss.com
>
> _______________________________________________
> rules-users mailing list
> rules-users(a)lists.jboss.org
>
https://lists.jboss.org/mailman/listinfo/rules-users
>
>
_______________________________________________
rules-users mailing list
rules-users(a)lists.jboss.org
https://lists.jboss.org/mailman/listinfo/rules-users