LISA bug alert!

Dean Allemang has submitted an excellent bug report regarding the manner in
which LISA manages its join node memories. The relevant portion of the
report is included below; the permanent fix will probably be some time
coming.

--------- report here ------------
I think this is a great project - I wish I had known about
it earlier (I selected OPS5 for a project earlier this year,
because I wanted to work in LISP, but I wanted a rule-
based system.  OPS5 just isn't a modern programming
system; I had to hack it a lot).

When I translated the project to LISA, I found a problem
with the way tokens are associated with activations.
In the case of a derived token, its sort-code is computed
from the sort-code of the parent and the fact it is derived
from, using the following formula:

           (setf (slot-value self 'sort-code)
             (+ (ash (get-sort-code parent) 3)
                (get-fact-id fact)))

(this from token.lisp).

It seems to me that if you have more than 8 facts, there
is a chance for two tokens created this way to have
the same sort-code.  Since this sort-code is used as
a hash-table index elsewhere (e.g., when looking up
activations to disable in the case of not-tokens), this
collision could result in the wrong activation being
disabled.

This happened in my application when the sort code of
one parent was 5, and it was combined with fact 9
(+ (ash 5 3) 9) is 49, and another parent had id 6,
and was combined with fact 1 (+ (ash 6 3) 1) is 49.
The resulting hash entry for the second token clobbered
the entry for the first one, making the first activation
immune to disabling.  The symptom is that after several
rules have fired, the old activation is still enabled, and
it fires, even though its preconditions are no longer
satisfied.  Needless to say, this plays havoc with the
solution.

I have made a quick fix to this by replacing the above
code with

           (setf (slot-value self 'sort-code)
             (+ (ash (get-sort-code parent) 10)
                (get-fact-id fact)))

I honestly don't know why this works; other similar
solutions (like using (gensym) to generate unique
numeric ids) fail terribly, presumably because my
"unique" ids are not really unique.  The solution
above doesn't seem correct either, since now the
collision can happen as soon as there are over 1000
facts, which doesn't seem out of the question (though
my application doesn't reach that number of facts).

I hope this explanation is enough for you to track down
the bug and make a more comprehensive fix; if you
need files that tickle the bug (my best one has a
single rule, but several dozen facts), I would be happy
to provide one.
----------- end report -----------

I'll be concentrating on this folks, but I need to refresh myself with
LISA's Rete implementation; it's been 18 months since I've been in this area
of the code.

Cheers,

--
------------------------------------------
David E. Young
[email protected]
http://www.bloodhoundinc.com

"Those who expect to reap the blessings of liberty
 must undergo the fatigues of supporting it."
  -- Thomas Paine

"But all the world understands my language."
  -- Franz Joseph Haydn (1732-1809)



-------------------------------------------------------
This sf.net email is sponsored by: OSDN - Tired of that same old
cell phone?  Get a new here for FREE!
https://www.inphonic.com/r.asp?r=sourceforge1&refcode1=vs3390