Truth maintenance inconsistency when removing facts that are logically equals, yet duplicated in working memory

[mrrodriguez]

I appear to have stumbled on an issue that can occur when there are logically equals facts inserted via a logical insert, but later must be retracted.

I'll demonstrate this with the simplest case that comes to mind:

(defrecord A [])
(defrecord B [])
(defrecord C [])

(defrule inserts-b
  [A]
  =>
  (insert! (->B)))

(defrule inserts-c
  [:not [B]]
  [A]
  =>
  (insert! (->C)))

(defquery find-c
  [] [?c <- C])


(-> (mk-session [inserts-b inserts-c find-c])
    (insert (->A))
    (insert (->A))
    fire-rules
    (query find-c))

;; Returns
({:?c #my.test.C{}})

The reason this happens is that 2 inserts of the A type fact results in inserts-c rule to insert 2 equals instances of C objects.

I looked at tracing and I the clara.rules.engine logic all does what I expect. The issue is in clara.rule.memory.

Eventually the flow of events ends up in the remove-elements! protocol fn impl in TransientLocalMemory. remove-elements! uses a set-based approach to removing
the elements queued up to be removed from memory.

2 logically equals instances of C objects will result in a set of only 1 object queued up to remove.
We get something like:

(remove-first-of-each element-set previous-elements)

where element-set to remove is the truncated-to-1 set of C objects. However, the previous-elements are allowed to have logical duplicates because Clara logical insert allows
for duplicates to be inserted into working memory. So we have 2 C objects in previous-elements and we need to remove both C objects, but the set causes this cardinality piece
of the operation to be lost.

I believe the fix for this is relatively simple - don't use sets here for these operations. This would likely require a little refactoring to remove-first-of-each as well
as any clara.rules.memory function affected by this set-based behavior.

For example, in the same remove-element! fn impl, I see

;; return the removed elements.
(s/intersection element-set (set previous-elements))

I'm not sure this will be a desirable return value either, since duplicates removed will not be made clear to the caller.

---

I know there has been some performance tuning recently to the remove-first-of-each logic (and possible some other related stuff). I haven't analyzed this enough at this point
to have a full picture of any performance costs or changes that would need to be made to remove memory elements in a non-set-based fashion.

My immediate thoughts on remove-first-of-each is that right now you have a constant-time set lookup cost, with a worst case linear time "sweep" of the previous-elements. This
makes it a O(n), where n is the size of previous-elements.
So at a glance I could see this changing to a O(m x n) operation where m is the size of the element-set that is no longer actually a set - so probably renamed to just elements or
something. This is due to a needing to do a linear sweep through the removal elements if they are no longer in a set. The size of m is probably small so this probably doesn't matter.

If it did we could probably just use a map where the keys were the elements to remove the value was the count of how many to remove.

There may be further reaching consequences than in memory though that I haven't gotten to look at yet.

[rbrush]

Good catch. I think we're okay with the O(m x n) linear sweep you mention since m is small. If nothing else, we could check the size of the incoming changes and swap to a map-with-counts when retracting more than 10 or so items, which should be an unusual case.

I was actually thinking that a lot of Clara's memory implementation would be significantly cleaner if we built on efficient multiset collections that support intersection and subtract operations. But that's probably more than we'd want to carve off to solve this particular problem.

[mrrodriguez]

Ok. Thanks for the feedback. I like the memory improvement thought. I'm thinking you're right that' it is worthy of its own issue though.

I think I'll try to get a PR in tomorrow for the quicker fix for this.

Let me know if you've already worked on it or plan to do it yourself so I don't duplicate effort. Although it's always worth the learning experience right? :P

[rbrush]

I haven't worked on in yet, so a PR is welcome. (I can probably get to it on Sunday).

[mrrodriguez]

I have a PR up for this @ #85.

[rbrush]

Closing this one, since the pull request has been merged.