[rules-users] Negation semantics in Drools
Edson Tirelli
tirelli at post.com
Fri Apr 17 21:45:26 EDT 2009
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.
Just my .02c
Edson
2009/4/17 Paul Fodor <paul.i.fodor at 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 at 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 at 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 at 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 at 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 at 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 at yahoo.com> wrote:
>>> >>>>
>>> >>>> > From: Greg Barton <greg_barton at yahoo.com>
>>> >>>> > Subject: Re: [rules-users] Negation semantics in Drools
>>> >>>> > To: "Rules Users List" <rules-users at 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 at post.com>
>>> >>>> > wrote:
>>> >>>> >
>>> >>>> > > We need to investigate if that is still happening
>>> >>>> > in
>>> >>>> > > latest trunk.
>>> >>>> >
>>> >>>> >
>>> >>>> >
>>> >>>> > _______________________________________________
>>> >>>> > rules-users mailing list
>>> >>>> > rules-users at lists.jboss.org
>>> >>>> > https://lists.jboss.org/mailman/listinfo/rules-users
>>> >>>>
>>> >>>>
>>> >>>>
>>> >>>> _______________________________________________
>>> >>>> rules-users mailing list
>>> >>>> rules-users at 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 at lists.jboss.org
>>> >>> https://lists.jboss.org/mailman/listinfo/rules-users
>>> >>>
>>> >>
>>> >>
>>> >> _______________________________________________
>>> >> rules-users mailing list
>>> >> rules-users at 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 at lists.jboss.org
>>> > https://lists.jboss.org/mailman/listinfo/rules-users
>>> >
>>>
>>>
>>>
>>> _______________________________________________
>>> rules-users mailing list
>>> rules-users at 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 at lists.jboss.org
>> https://lists.jboss.org/mailman/listinfo/rules-users
>>
>>
>
> _______________________________________________
> rules-users mailing list
> rules-users at 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.jboss.org/pipermail/rules-users/attachments/20090417/96d3f32a/attachment.html
More information about the rules-users
mailing list