Tuesday, May 11, 2010

Drools Language Enhancements (Drools 6) updates

Davide has been working on the new parser for Drools 6, he's updated the language guide with some more ideas. Don't worry, core developers are still focusing on 5.1. The full language guide, aimed to provide the Drools 6.0 drl syntax can be found here:
http://community.jboss.org/wiki/DroolsLanguageEnhancements

The parts Davide has updated are:
Pipes - Pass through Filters
Unit support
Rising / Falling edges


Pipes - Pass through Filters

While accumulate performs map and fold operations it returns a derived result. Pipes allow us to filter a set of Tuple chains, that represent the actual join partial match results. In 5.0.x we had "over" as a temporal pass through filter, Person() over win:time(30s). We feel this concept should be more generalised to allow any pluggable filters, and for those filters to work on single Patterns of a group of patterns:
Person() | win:time(30s)
These pipes can be combined, so we only allow the Persons for the last 10 minuts to propagate forward (retracting anyone who existed more than 10 mins ago) but we throttle the network updates to every 30s:
Person() | win:time(10m) | throttle(30s)
This is important for combination with say accumulates, where we don't want every single change to be aggregated and the result propagated:
acc( Bus( $t: takings) | win:time(1h) | throttle(5m),
$avgTakings : avg( $t ) )
So th above calculates the average takings for the last hour, continously, but it only updates the results every 5 minutes. Throttle is just currently a proposed filter name, we might come up with something different for that behaviour later.

Pipes don't just work on single Patterns, they can work on multiple patterns. So for instance we could provide a "unique" filter that remove ambiguous cross product joins; which Charles Forgy mentioned at ORF09. In the following example if we instead insert 3 As we would get 1 resulting match, not 9.
(A() A() A()) | unique
Unit support

Groovy added unit support, based around leveraging JScience and JSR275. http://groovy.dzone.com/news/domain-specific-language-unit-. The dot notation is a bit too ambigous for Drools, but we already use # to cast patterns, so we can do the same for units.
3#km + 5#m
We can cast existing units to other units. So we can declare something as 3km, but have it returned as feet.
3#km#feet
If a unit is combined with a normal literal, then it's just a operator on that literal value, for instance the following is 6k, it is not executed in the same way as 3km * 2km would do.
3#km * 2
# can be used with methods and functions. If the method returns a literal, then it's the same as saying 3km. If the method returns a unit, then it's like a caste:
returnInt()#km
returnKm()#feet
This works for strings too, and can be used to provide date/time formatting:
"2012 12 04"#myDateFormat
Rising / Falling edges

Grindworks supports the idea of executing actions on the rising or falling edges of a rule. While we could do this on the actions too, we think initially this would be better on the LHS, as a special conditinal element.
when
rising Person( age == 30 )

when
falling Person( age == 30 )
Clealry rising is the default behaviour for a pattern. Whether we allow it's inclusion, for readability intent, or only support falling, is to be decided.

We could combine this with a branch
when
...
branch( rising Person(....),
[b1] falling Person(....)
This also has some ramifications for Logical Closures, as it solves some of the same problems.

11 comments:

  1. Before going down the measures rabbit hole too far, you may want to visit javax.measures from JScience.
    http://jscience.org/api/javax/measure/unit/package-summary.html

    ReplyDelete
  2. D'Oh. Apply all available text before engaging response. :-)

    ReplyDelete
  3. As per the Groovy impl, it will be based around javax.measures from JScience, we are just adding syntax sugar.

    ReplyDelete
  4. Mark, can you explain the rising and falling stuff a little more (for mere mortal understading ;)

    Keep up the good work!

    ReplyDelete
  5. Rising edge is when something becomes true, falling edge is when something moves from true to false. So it allows you to do something when a pattern which was true, becomes false.

    ReplyDelete
  6. Grindwork's rising/falling edge "appears" to be the result of misunderstanding temporal logic. A fact may be true at some point and later become "not true". Other people have written about this like modification logic, and other papers. The material is there for those who take time to study.

    Grindworks also has some odd misconception of truth maintenance. It's not logical truth maintenance and doesn't look like well established TMS approaches.
    http://www.cis.temple.edu/~ingargio/cis587/readings/tms.html
    http://www.cs.umd.edu/Honors/reports/Schwartz/doyle.html
    http://www.cs.cf.ac.uk/Dave/AI2/node81.html

    Look at grindworks definition and see if it makes any sense for yourself.

    http://www.grindwork.com/site/node/9
    http://www.grindwork.com/site/node/8

    ReplyDelete
  7. @Anonymous:

    As far as rising/falling goes, it does not represent temporal logic; that would be implemented in user rules if desired. What GTS does is actually act as a server, as its name implies. It does not simply infer over a set of input facts until it reaches a conclusion; it allows the asynchronous assertion and retraction of facts and rules as the system is running, and effectively never quiesces or is explicitly asked to run. Thus, facts become true and no longer true due to true external consequences and sensors acting over real physical time, and forward-chained rules rise and fall as those effects (and its own internal effects) take place.

    The server continually "thinks" about and reacts to what it currently knows. Its knowledge is modified by its own rules, and by the external world.



    Truth maintenance tracks the justification of an inference, and is typically applied to a feedback loop which keeps the inference asserted only while its backing support remains true. This notion can be applied to many different type of inference engines, which result in different implications and uses. The links you provide only regard theorem provers (aka automated reasoners, problem solvers, etc) which are in a completely different space than expert systems such as Drools and the Grindwork Thinking Server.

    "Logical assertions" in expert systems do track the justification of an inference, retracting the fact when it is no longer supported. GTS's TMS follows and expands on this same mechanism. This has been classified as truth maintenance by other expert system authors at least since the early 90s (from available CLIPS 5.x documentation), and possibly well back into the 80s.

    In fact, Googling for "truth maintenance" "logical assertion" yields a first page full of Drools documentation links. ;-)

    Theorem provers allow asserting negations and inferring negated consequents, which can lead to logical conflicts with positive assertions & consequents. Truth maintenance is critical in resolving these conflicts, providing an explanation to the user about the conflict, or introspecting the justification of each of the conflicting inferences in order to automatically choose a preference.

    Expert systems (and Prolog) only hold true or conditionally true facts. While they can check for negated matches and queries, they cannot assert falsehood, only retract a fact. Thus, many of the uses and options for TMS from theorem provers simply have no respective mechanism in expert systems.

    ReplyDelete
  8. I would argue rising/falling edge is a subset of temporal logic. To me, it has nothing to do with async/sync assertions. Temporal logic deals with the fact that data (aka facts) maybe be true at some point and no longer true at another point in time. Within temporal logic is the concept of corrective actions, which can be in the context of checking the derived conclusions are still "true" (TMS)or performing a new action.

    Thanks for taking time to explain what Grindworks is attempting to achieve with rising/falling edge feature.

    I disagree those links only apply to solvers or provers. The theory of truth maintenance goes back at least 30 years and there's has been a lot of papers written on the topic. Logical truth maintenance being just one form. Wikipedia page on truth maintenance (http://en.wikipedia.org/wiki/Truth_maintenance_system) is pretty light. There's a lot more papers on the topic on ACMQueue (http://portal.acm.org/citation.cfm?id=5974).

    I agree that solvers use TMS differently than expert systems. What remains to be proven is how well thought out grindworks TMS compared to logical truth maintenance. There is a subtle difference, which grindworks needs to explain to the users. The burden is on grindworks to prove and explain their approach is sound, considering there's 20+ yrs behind logical truth maintenance.

    ReplyDelete
  9. The falling feature was added into production use two years ago. Performing falling-edge behaviors with only standard production rule firings requires 2 separate rules, and an intermediate "continuation fact" to capture rising state for the falling rule to act on the same data. The continuation fact needs to be cleaned up after use or error, rule ordering dependencies need to be managed, and a number of pragmatics arise.

    Since this is a common pattern, we raised the level of abstraction of the system to properly capture the intent of what we're doing by incorporating this feature. A smarter environment and a more informed compiler yield less developer work and fewer man/machine communication errors. However, the nature of this feature is still fundamentally equivalent to the existing notions of rule firings and TMS that other expert systems have already employed.

    I'm not sure if I quite understand the nature of your challenges. Are you claiming that all production rule system style TMS is inherently flawed? While our full documentation for our productized version is unfortunately still pending, our TMS is currently exactly equivalent to such systems:

    Drools: http://blog.athico.com/2010/01/drools-inference-and-truth-maintenance.html
    CLIPS: http://iweb.tntech.edu/bhuguenard/ds6530/ClipsTutorial/CLIPS%20tutorial%205.htm

    I fully appreciate that theorem provers and other systems/notations which allow negative assertions must perform far more inference in their TMS since, for example, a positive assertion somewhere might lead to a negative inference elsewhere which conflicts with a positive fact which supports a currently-held truth.

    Fact bases made up of purely positive assertions and positive inferences have a much simpler time dealing with TMS since there is a simple, direct chain of positive truth to maintain, and logical conflicts cannot arise. Such systems only need to monitor retraction of known supporting facts, and assertion of LHS-negated clauses, in order to maintain truth.

    ReplyDelete
  10. If you look at how CLIPS, ART and JESS implement Logical truth maintenance, you'll see the LHS defines "logical" patterns. Grindwork does not and deviates from that design. Clearly there's many ways to implement TMS, but claiming Grindwork is the same as logical truth maintenance is clearly not true. Please study CLIPS and JESS logical TMS thoroughly before claiming Grindworks is the same. It clearly isn't the same, since it does not support the concept of a logical CE. There are times when a change in the LHS should not affect any assertions in the RHS.

    It's pretty clear grindwork hasn't taken time to study existing state of art thoroughly and get a deep understanding before re-inventing things that have already been done.

    Logical truth maintenance is the dominant form of TMS in expert systems because it proved to be better than other forms. Many other systems have been tried in earlier expert systems. There's a wealth of literature out there waiting for people to read. Those who don't learn from history are doomed to repeat it.

    ReplyDelete
  11. Correct, we do not intersperse "logical" within a single continuous LHS clause. We have the logical "when" clause, and the separate non-logical "calculate" clause (which inherits successful bindings from the "when" clause). The "calculate" clause defaults to (true) if not given. Both of these clauses together define the LHS.

    We found it clearer to keep these two separate, rather than shoving a special embedded scope into the LHS that carries additional syntactic constraints. Both rising and falling edges are user-accessible for *all* in-cycle rules, not just ones with opt-in behavior, so our global semantics demand focus on the logical truth lifecycle.

    We also allow the RHS to specify whether or not individual assertions use the logical TMS. This allows a single rule to perform both ground assertions ("rising +") and logical assertions ("maintain"), which CLIPS-style systems cannot do, but Drools for instance can (insert vs insertLogical). However, Drools does not distinguish logical vs non-logical LHS sections yet, while CLIPS and GTS do.

    All of this adds up to providing the exact same TMS mechanisms as the systems you mentioned, but also exposing more complete and finer-grained access for use beyond merely copying legacy features. We simply separated it into its constituent parts in both the LHS and RHS for clarity and orthogonality.


    I've expanded on this, and described our decisions of the use of the non-logical clause that you've hinted at in a separate blog post:

    http://www.grindwork.com/site/node/44

    While much discussion has already passed here, this is still a Drools blog. ;-) You're very welcome to hop over to our site and we can continue discussing details there.

    I do appreciate your questions and misunderstandings. Since we are still creating our documentation, they help out tremendously in showing us where we need to be particularly clear in our summaries, and what new people with prior expertise take as first impressions.

    ReplyDelete