Duplicate rule sources cause duplicate activations

Question

Duplicate rule sources cause duplicate activations

Closed this issue 9 years ago · 12 comments

I'd expect the below to pass:

(let [r (dsl/parse-rule [[Temperature (= ?t temperature)]]
                        (insert! (->Cold ?t)))
      q (dsl/parse-query []
                         [[?c <- Cold]])

      q-res (fn [s]
              (-> s
                  (insert (->Temperature 10 "MCI"))
                  fire-rules
                  (query q)))

      s1 (mk-session [r q])
      s2 (mk-session [r r q])] ; Notice the duplicate `r`

  (is (= (q-res s1)
         (q-res s2))
      (str "s1 res: " (vec (q-res s1)) \newline
           "s2 res: " (vec (q-res s2)) \newline)))

However, it fails and prints:

FAIL in clojure.lang.PersistentList$EmptyList@1 (form-init2547955108651183275.clj:15)
s1 res: [{:?c #clara.rules.testfacts.Cold{:temperature 10}}]
s2 res: [{:?c #clara.rules.testfacts.Cold{:temperature 10}} {:?c #clara.rules.testfacts.Cold{:temperature 10}}]

expected: (= (q-res s1) (q-res s2))
  actual: (not (= ({:?c #clara.rules.testfacts.Cold{:temperature 10}}) ({:?c #clara.rules.testfacts.Cold{:temperature 10}} {:?c #clara.rules.testfacts.Cold{:temperature 10}})))
false

The simplest fix for this is to just remove duplicate rule sources at the clara.rules.compiler/mk-session level (used by clara.rules/mk-session). In my case, we have a somewhat "automated" process of generating the rule sources given to mk-session. When doing this, it is fairly easy to mistakenly give dupicate rule sources. We could fix this by ensuring we do something like a distinct call on our rule sources prior to mk-session, however, I'm wondering if it would be more appopriate for Clara to do this itself.

However, this used to not be an issue prior to the change at this line in this commit
@ 1ecf31d#diff-de7dcf2c204d43bcc40c5739f69cc6c0R516.
It looks to me though that this change to clara.rules.compiler/add-to-beta-tree was actually a "fix" because nodes represented empty environment as {}, while the binding for env in this scope would always be nil for empty environment, and nil isn't equal to {}. Prior to this, I'm assuming that sibling node merging in this function often didn't merge as desired.
My diagnosis of the change to add-to-beta-tree could be wrong, because I am still pretty confused when trying to fully understand what that function is doing in a few places.

I did narrow it down to these lines that are concerning finding the matching-node (aka mergable sibling node I think):

(or (= env (:env beta-node))
    (and (empty? env)
         (empty? (:env beta-node))))

which when I switch back to:

(= env (:env beta-node))

my test passes as I expected.

However, I don't think this is a good fix, since I think there is likely something else going wrong in
add-to-beta-tree as mentioned above.

When the sibling nodes get "correctly" merged in the current master branch version of add-to-beta-tree we ultimately get a beta node like:

{:node-type :join, :condition {:type clara.rules.testfacts.Temperature, :constraints [(= ?t temperature)]},
 :children [{:node-type :production, :production {:lhs [{:type clara.rules.testfacts.Temperature, :constraints [(= ?t temperature)]}], :rhs (clara.rules/insert! (clara.rules.testfacts/->Cold ?t))}}
            {:node-type :production, :production {:lhs [{:type clara.rules.testfacts.Temperature, :constraints [(= ?t temperature)]}], :rhs (clara.rules/insert! (clara.rules.testfacts/->Cold ?t))}}], :env {}, :join-bindings #{}}

Here, the :production node duplicates from both sibling nodes have probably been both added to the new merged node.

It is possible this problem is only about duplicate beta nodes that have a :production node child, however, I haven't determined this.

Overall, I do think it may also be a good idea to just avoid wasted work by ensuring all rule sources are distinct at the mk-session level.
However, I still think there is probably something to track down in add-to-beta-tree here.

Answer 1 · 2016-01-13T15:47:28.000Z

Regarding duplicate removal, removal of duplicate rule sources would solve some cases, but a more general approach would be to call distinct on the rule structures at [1].
That would handle cases like

(mk-session [rule-in-ns-1] 'ns-1)

which doing distinct on the rule-sources wouldn't. Since distinct uses a hash-based set internally and rule structures are Clojure maps that cache their hashcodes I don't see any likely performance problems with this approach (although even if they were records and thus ran into [2] I doubt it would be a big deal.)

Regarding node-sharing in the beta tree, I discussed this with @mrrodriguez and it looks like there isn't as much sharing as we initially expected. It looks like [3] just looks for top-level matching nodes; I don't see any attempt to match against children of the beta-nodes there. I suspect trying to do this would be an involved effort, but I haven't given a ton of thought to it.

Answer 2 · 2016-01-13T16:06:25.000Z

I like the distinct idea @WilliamParker suggests. We could go a step further and simply place rules in a set as an early step in mk-session, and use that set from there. That would also solve a request that popped up on the Clojurian/Clara slack channel last week to make session caching independent of rule order. I'd be tempted to go that route.

As for node sharing: I'm working on a significant improvement to node sharing as part of some refactoring for issue #153. It's true that we don't do a ton of sharing, basically just commonality from the top. I'm hopeful to get a draft of the refactoring for #153 up in the next few days that will significantly improve sharing, and better support that case of complex disjunctions.

Answer 3 · 2016-01-13T16:14:03.000Z

Yeah, I like the idea of doing a "distinct" at the level of rule structures, not rule sources for the reason Will mentioned. I like the idea of a set as well, but my only hesitation for things like sets is that the order the rules are given can change from one JVM instance to another. I'm just wondering if that would lead to different performance behavior from one run to the next or the Rete network coming out differently each time it is compiled for the same rule set or anything else like that.

My concern there may not be well-founded though. There may be enough determinism in the compiler already to deal with this issue. I haven't thought through that completely.

In general I do like to see consistent, deterministic behavior from one JVM instance to the next where possible, just because it avoids subtle changes. However, I think Clara does have freedom to not provide many order guarantees in general beyond something like :salience at this point.

Answer 4 · 2016-01-13T16:21:59.000Z

@mrrodriguez Yeah, Clara won't make ordering guarantees between runs unless the user explicitly sets salience or provides a specialized function to sort rules. So distinct shouldn't affect any guarantees.

If we do want to provide better ordering (e.g., rules fire in order in which the are loaded from a source) then we could attach additional data to the rule itself...like a sort of automatic, secondary salience. That can be done independently of duplicate removal (and would merit a separate issue, of course.)

Answer 5 · 2016-01-14T21:18:26.000Z

The idea of having set-based caching and set-based productions at the mk-session - i.e. prior to building the Rete network - level sounds good to me.

Will this just be merged into the work being done with #153 then or should we do it separately?

Answer 6 · 2016-01-15T20:29:13.000Z

I think this is separate from #153. We can just use this issue to track it.

Answer 7 · 2016-01-30T14:37:35.000Z

FYI - Mike and I discussed this offline and I'm planning to do this one (unless you've started/are done/otherwise would prefer to work on it yourself of course).

Answer 8 · 2016-01-30T15:13:47.000Z

It's all yours! And thank you.

On Saturday, January 30, 2016, WilliamParker notifications@github.com
wrote:

FYI - Mike and I discussed this offline and I'm planning to do this one
(unless you've started/are done/otherwise would prefer to work on it
yourself of course).

—
Reply to this email directly or view it on GitHub
#157 (comment).

Answer 9 · 2016-02-01T19:02:45.000Z

I submitted a pull request at #167

Two notes on it:

I considered caching on the raw sources, and not even loading the productions into a set if there is an exact match, but some quick profiling suggests to me that this isn't much of a performance hotspot. Calling load-rules on a decently large namespace took about a millisecond on my computer.
It would be probably be valid to put the alpha nodes into sets as well, but that seemed out of scope for this issue. I haven't given much thought (yet, anyway) to whether that would have perf consequences, although my guess would be no.

Answer 10 · 2016-02-01T19:53:56.000Z

Looks good, and #167 has been merged. I was going to ask about your first point, but agree with your reasoning above.

Anything else we wanted to do on this one, or shall we close the issue?

Answer 11 · 2016-02-02T16:39:01.000Z

I don't see anything else to do here.

Answer 12 · 2016-02-02T19:27:38.000Z

Looks good to me!