Negated conjunctions and binding visibility

[mrrodriguez]

I'd expect the following to work:

(let [q (dsl/parse-query []
                         [[:not [:and
                                 [?t <- Temperature]
                                 [Cold (= temperature (:temperature ?t))]]]])
      s (mk-session [q])]
  (-> s
      fire-rules
      (query q)))

However, I get:

ExceptionInfo Using variable that is not previously bound. This can happen when an expression uses a previously unbound variable, or if a variable is referenced in a nested part of a parent expression, such as (or (= ?my-expression my-field) ...). 
Unbound variables: #{?t}  clojure.core/ex-info (core.clj:4593)

I understand why this is though. The Rete network is normalized in disjunctive normal form (DNF).
So this comes out to be something like:

(clara.rules.compiler/to-dnf '[:not [:and
                                     {:type Temperature
                                      :constraints []
                                      :fact-binding :?t}
                                     {:type Cold
                                      :constraints ['(= temperature (:temperature ?t))]}]])
;= [:or
;=   [:not {:type Temperature, :constraints [], :fact-binding :?t}]
;=   [:not {:type Cold, :constraints [(quote (= temperature (:temperature ?t)))]}]]

Since the two conditions get split across an :or the second condition no longer has visibility to the binding ?t.

I think this one is going to be a little tricky to solve.

I know that I can manually extract the conjunction into another rule and get the behavior I'm looking for like:

(let [r (dsl/parse-rule [[?t <- Temperature]
                         [Cold (= temperature (:temperature ?t))]]
                        (insert! (with-meta {:marker true}
                                   {:type :__stub})))
      q (dsl/parse-query []
                         [[:not [:__stub]]])
      s (mk-session [r q])]
  (-> s
      fire-rules
      (query q)))

;= ({})

Given that, I was beginning to think that perhaps the simplest way to handle these sorts of scenarios would be for the Clara compiler to automatically extract out a rule like this before the network is put into DNF. This would allow consumers to not have to get confused about why it doesn't work when it looks like it should.

This is just my first inclination though. I haven't really wrapped my head around what else could be done in terms of doing something more sophisticated with the DNF or perhaps some sort of subnetwork.
I know the (great) Doorenbos paper linked in the Clara wiki @ https://github.com/rbrush/clara-rules/wiki/Introduction#the-rules-engine goes into quite a bit of detail about handling of negated conjunctions in 2.7.
I'm not sure if that is the appropriate place to get inspiration into this problem, but that was something that popped into my head that I remember reading about.

I may be completely missing a simpler way to solve this though, so I'd appreciate your feedback on the matter!

[rbrush]

Ah, I thought I had worked around the complexity of sub-networks from that paper but didn't think of this flow. I like the idea of generating a rule more than adding sub-networks to the algorithm at first glance. I'll explore some more options in the next day or so and post back here.

[rbrush]

I think generating a rule that handles this as @mrrodriguez suggested in the original report. This keeps the engine itself simpler which I think will pay dividends. I'm going to be traveling a bit and might not be able to jump into this right away but plan to do so as soon as I'm able to.

[mrrodriguez]

If the approach you think sounds reasonable is to extract a rule, I may already have already thought through that one a bit in and I may be able to get a branch up in a few days to show you what I was thinking there. I sort of already implemented this sort of idea in a more specific context. There was one little caveat I thought about as far as extracting out a rule, but I'll discuss that more when I have a working example up.

Just letting you know in case it could save you some effort.

[rbrush]

@mrrodriguez I spent some time on this today before seeing your latest comment. I've shared a rough draft of that attempt here. I also ran into a caveat when extracting a rule in that (fire-rules) must be invoked for this to work. (Although in almost all use cases consumers should be using fire-rules, anyway.)

I can think of a couple things lacking in this initial pass: 1.) I don't attempt to handle further nested complex expressions that share bindings and 2.) I'm adding rules in all compound negations, not just those that need it because of bindings.

Anyway, hopefully I'm not stepping on your toes too much with this one. I'm certainly open to better approaches if you had one in mind or in progress, so this is just a reference.

(It looks like the Jenkins build failed but it didn't offer an explanation and it works locally, so I suspect Jenkins might be flakey here.)

[mrrodriguez]

Thanks for the heads up! I hadn't actually started on a Clara-specific fix for this and was instead handling it at the consuming application level. I'm glad to see what you have here is mostly aligned with the same thing that I did though. Here is my (lengthy, sorry!) thoughts on this topic now.

---

I can think of a couple things lacking in this initial pass: 1.) I don't attempt to handle further nested complex expressions that share bindings

In my initial pass, I extracted recursively for all nested negation conditions. However, I think this would likely just be an edge case and we could leave it out on first pass if you want to keep it simpler.

and 2.) I'm adding rules in all compound negations, not just those that need it because of bindings.

I also kept it it simple like you said above and extracted complex negation conditions regardless of if they really had the binding scenario that requires it. I just thought it wasn't worth the complexity since the transformation would (a) not likely be too common and (b) shouldn't be a performance issue.

---

I also ran into a caveat when extracting a rule in that (fire-rules) must be invoked for this to work. (Although in almost all use cases consumers should be using fire-rules, anyway.)

I'd be curious to know what sort of use-case you have in mind that would justify the consumer not calling fire-rules. My thoughts on this is that the rules engine makes no guarantees at all about the state of the network prior to fire-rules being called.

Not having guarantees around the pre-fire-rules state of the network has a few benefits to me:
(a) It allows for things like rules to be extracted by the compiler automatically

• this can be good for scenarios like this,
• or for actual automatically detectable optimization scenarios in the future.

(b) It allows for the rules engine to possibly be more lazy in when it performs propagation across the beta network.

• I'm roughly thinking along the lines of how Drools v6+ made the engine perform beta node propagations in a lazier "goal driven" style. It is my understanding that beta nodes are not "linked" into their rules until certain criteria are met. One of these criteria may be concerned with the salience and other heuristic chosen (rule load order). I am not sure if it is reliable for the consumer to have expectations about the working memory state prior to fire-rules when using Drools v6+ . I am not positive on this though.

I think my point (a) is the stronger of the two, but I do like to do comparison against another mainstream engine.

---

There are two red flags that still stands out to me with this change still:

a) Now (and anytime in the future) if we want the compiler to be able to extract out rules this sort of change is fairly simple to make unless the consumer has changed the :fact-type-fn that the engine uses to dispatch to the alpha network. This point is a little scary to me and was my biggest hesitation for how to do this in a way that always works.
The only robust solution I came up with was to special case a type, like clara.rules.engine.NegationResult, so that the Clara engine always respected dispatch on that class, despite what the :fact-type-fn's behavior has been set to do.
I think this could be accomplished just be a slight alteration to
clara.rules.compiler/create-get-alphas-fn to have a "special" type (or types in the future) that it always looked for first.

b) The rules that are extracted from the conditions should be sure to get the same properties - via :props as the production from which they were extracted from. An obvious to think about here is the :salience property should be the same as the production the new rule was extracted from. In the case of explicit higher priority/salience I think this change would make it work in a very non-intuitive way since the higher priority rule would now rely on a lower priority rule. However, I think it is likely important that all :props are copied since we do not know if the consumer has changed the :activation-group-fn.

[rbrush]

I'm not too worried about making guarantees for sessions prior to fire-rules being run. It's just a behavior change that could potentially break consumers if they happened to be (accidentally) relying on the current behavior. A couple existing tests did this and broke when I made this change, but I don't think this is a big problem, and we can also mitigate it by narrowing the scenarios where we apply this.

Good point on the issues with an alternate :fact-type-fn in this scenario. I agree that we can probably address this with a change to create-alphas-fn to identify some sort of "special" type. Some simple way of identifying such special system types seems best to me. Perhaps a parent type of :clara.rules.engine/system-type, and we can check if a given type extends that and use the Clojure type function for that rather than a user-provided :fact-type-fn?

So we would execute this when the clara.rules.engine namespace is loaded:

(derive clara.rules.engine.NegationResult :clara.rules.engine/system-type)

And then the create-alphas-fn would check for system types with:

(isa? fact-type :clara.rules.engine/system-type)

And just use Clojure's type hierarchy in that case.

Also agreed we should merge the :props over.

If you're interested and able to take this any further please feel free to do so (but please don't feel obligated if you have other demands!). In any case I'll be back from my trip next week and will pick it up from there.

[mrrodriguez]

Sorry for the delayed response. I thought I responded to this, but apparently that is not the case.
I think your proposed idea makes sense to me and sounds like the general idea I was thinking that would work here.

If you plan to work through this within the next few days, that sounds good to me. If I were to work on it, it'd probably be delayed until next week.

[rbrush]

No problem. I just got back into town and am happy to pick it up again.

[rbrush]

I believe this is fixed in the above commit, using the rule generation strategy discussed earlier in the thread.

[mrrodriguez]

I think the changes looked good here. Thanks for working through this one so quickly!

[rbrush]

Targeting for 0.10.0. (I don't think we will do a 0.9.3 since changes in issue #153 are large enough to bump the version).