Another attempt at pattern matching

In my previous post I'm talking about feature-tests without really explaining what I mean. So here's an attempt to re-phrase, expand on and give some background to my thoughts.

I spent yesterday re-reading parts of Forgy's thesis (using OPS2) and the AI Journal article (using OPS5) describing the Rete Algorithm.

The implementation described in the thesis uses a whole lot of nodes to test for features of the fact-structure as well as the values contained in a fact. This approach of classifying things is known as Structural Typing.

Compiling the MB11 production in OPS2 (see 2.2.1 Productions with one Condition Element in the thesis):

MB11 ( (Want (Monkey Near =P))
       -->
      (Want (Monkey On Floor)) )

produces no less than five nodes in the Rete Network:

1. Is the element a list of two subelements?
2. Is the first subelement Want?
3. Is the second subelement a list of three subelements?
4. Is the first subelement of the second subelement Monkey?
5. Is the second subelement of the second subelement Near?

The article, however, describes a different approach, based on Static Typing, which requires you to declare the structure of a fact before using it. This way, we can remove all feature-tests and replace them with only one test, an expression node (also known as an object type node).

The MB11 production for OPS5 looks like this:

(p mb11
 (goal ^status active ^type walk-to ^object [p])
  -->
 (make goal ^status active ^type on ^object floor))

They're not the same, I know.

But still, from the description in the article this would be compiled into three nodes:

1. Is the element's class goal?
2. Is the value of the status attribute active?
3. Is the value of the type attribute walk-to?

It doesn't take too large a rulebase before the benefits of this approach start to show. But at the same time, it seems that we have also lost the possibility to match nested structures.

In OPS5, according to the OPS5 Reference Manual, there's a possibility to create a vector attribute which can hold several values. Here's part of an OPS5 dialog that shows what happens when you match a vector attribute:

OPS> (vector-attribute bar)
(BAR)
OPS> (literalize foo bar)
NIL
OPS> (p rule
       (foo ^bar [bar])
        -->
       (write " [bar] = " [bar] (crlf)))
*
NIL
OPS> (make foo ^bar 1 2 3)
NIL
OPS> (run)
1. RULE 1 [bar] =  1

I haven't yet been able to match several values with one variable (as $? allows you to in CLIPS). I'm not sure if this is even possible in OPS5. Actually, in chapter 2.6 The Range of Applicability of the Algorithm of Forgy's thesis he describes some of the constraints that we have to work around. In short, they are: 1) facts must only contain constants and 2) it must be possible to determine (at compile-time) which subelement each condition matches. This last constraint applies to Multifield variables and is probably one explanation to why they're so much slower than regular variables.

My question in the previous post was: why aren't nested data structures supported? Don't get me wrong. I'm not out to convince anyone to change anything or question whatever decisions has been made. I don't know if the issue is related to Multifield variables or not and I'm not sure I really care. The situation is as it is and CLIPS works just fine for my needs.

But. I'd really, *really* love to learn more about the design decisions made in different production systems regarding this, and other, areas. If you know of papers, articles, books or magazines that contain information about OPS, CLIPS and/or ART history please let me know.

[Update 2008-04-05]: The article The OPS Languages - An Historical Overview in this issue of PC AI magazine looks interesting enough to order.

Evolvable Rules

I stumbled on Evolvable Rules and REAT (Rete Evolution of Augmenting Topologies) yesterday whilst searching for interesting stuff to read. I'm not yet sure about what I think of the project but Greg sure got my attention.

The idea behind evolvable rules seem to be using Artificial Neural Network (ANN) techniques to generate a Rete network and some additional stuff like conflict resolution and the code needed for executing the RHS of a rule.

There's not that much info yet but Greg shares a few references that explain the technology he intends to use. Apart from Charles Forgy's Rete papers (the thesis and the article) and the Wikipedia description of the Rete algorithm (which we have another Charles to thank for) he also refers to Evolving Neural Networks through Augmenting Topologies by Kenneth O. Stanley and Risto Miikkulainen.

I haven't read the last paper that thoroughly (skimmed it once) and I'm only just learning about ANN technology but it seems to me that this requires a lot of work. And, if I understand correctly, it might not be very good at producing a Rete network at all and since there are "simple" rules that can be used to construct a Rete network based on, for example, an Abstract Syntax Tree I don't really see the point. Apart from being really cool of course ;-)

Anyway, I'm real interested to see how all this works out. I've had similar lines of thought myself after having read An Optimization Algorithm for Production Systems by Toru Ishida last summer. It would be really neat to find a way to automatically optimize (restructure) a Rete network based on the contents of the working memory without having to pass through all Facts and re-evaulate the goal of the optimization continuously.

The problem is that I have no idea of how, or even if, it can be accomplished. But I bet that if someone does it, it's probably going to have something to do with using ANN GA techniques. I'm not holding my breath though.

Yet another starting-over post

This is the fifth time I've decided to start over (more or less from scratch) in my attempt to produce a Rete rule engine in Python. It' irritating that it's so hard to get the pyRete code into a shape I'm pleased with and I've been feeling kind of low these past few weeks since my last attempt to beat the RuleCompiler into submission failed miserably.

I know that developing a rule engine is no easy task and that others have devoted large portions of their lives doing it so 2 years isn't that much, really. I'd feel a whole lot better though if I was sure that I won't write this post again in a year or so.

Even more profiling...

Ok, this will be my last post about (this round of) profiling. Honest!

I have now decided on which implementation to use so I thought I should take some time to describe it.

It *is* a bit of a hack, but it allows me to remove the eval calls in the OO implementation. It's not as fast as the flattened, procedural Rete implementation. But it's quite close and, more importantly, I believe it's easier to implement and add optimizations to it.

Here's the profiling output:

using 4000 facts
plain OO impl. Assert took 6.0490000248 s and produced 79735 facts
hack OO impl. Assert took 3.16399979591 s and produced 79735 facts
inline impl. Assert took 2.68400001526 s and produced 79735 facts

As you can see, the difference is about half a second between the hack and the inline version.

using 10000 facts
plain OO impl. Assert took 15.2119998932 s and produced 199735 facts
hack OO impl. Assert took 7.88100004196 s and produced 199735 facts
inline impl. Assert took 7.49099993706 s and produced 199735 facts

Luckily, that difference remains "constant" for any size of the data set and the difference between the plain OO and the hack remain at about 50%.

Now, to talk about how it's done. In the plain OO version, the Rete Compiler makes an instance of AlphaTestNode like this:

>>> a1 = rete.AlphaTestNode('a.n > 10')

The AlphaTestNode is defined as:

>>> class AlphaTestNode(object):
...     def __init__(self, expr):
...         self.expr = expr
...         self.nexts = []
...     
...         self.right_activate = self.activate
...     
...     def activate(self, tag, token):
...         if eval(self.expr, token):
...             for next in self.nexts:
...                 next.right_activate(tag, token)

whenever activate is called on the a1 instance it will evaluate the expression 'a.n > 10' using the token, and all bindings (variable name and value) found in it, as execution scope. In order to remove the expensive eval call we have to "inline" the expression to be tested. A macro would have been very handy here (the Lisp type) but I don't expect them to show up in Python any time soon so instead we'll have to have a work-around. If we remove the class definition and replace it with a function:

>>> def make_AlphaTestNode(expr, var):
...     class_definition = \
... """class GeneratedAlphaTestNode(object):
...     def __init__(self):
...         self.nexts = []
...         self.right_activate = self.activate
...     
...     def activate(self, tag, token):
...         %s = token['%s']
...         if %s:
...             for next in self.nexts:
...                 next.right_activate(tag, token)""" % (var, var, expr)
...             
...     exec(compiler.compile(class_definition, '__generated__', 'exec'))
...     return GeneratedAlphaTestNode()

we can make an instance of AlphaTestNode equivalent to the one above (a1) using:

>>> a1 = rete.make_AlphaTestNode('a.n > 10', 'a')

The "extra" parameter ('a') is used to generate a statement to bind the variable (a), found in the token, locally before execution. This is necessary because we cannot specify token as the execution context (as we can when using eval or exec).

The parameter class_definition will look like this when it's sent to the compile method:

>>> class GeneratedAlphaTestNode(object):
...     def __init__(self):
...         self.nexts = []
...         self.right_activate = self.activate
...
...     def activate(self, tag, token):
...         a = token['a']
...         if a.n > 10:
...             for next in self.nexts:
...                 next.right_activate(tag, token)

executing the code object that is returned by compile causes the class GeneratedAlphaTestNode to become available in local scope so all that is left to do is to make an instance and return it.

Ugly!? Incomprehensible!? Yes, sir! But it shaves a lot of time off of fact evaluation in the Rete Network so I don't care!

Next up is to implement a second pass in the compilation step to remove "un-necessary" nodes. This is actually the main reason I chose this design over the inlined, flattened, procedural implementation. Optimizing travseral of the Rete Network in an OO implementation means traversing it and moving "next pointers" from one node to another whilst in procedural code I would have to handle it on the level of source code (text) which feels a lot harder (I can't think of an easy way to do it so if you've got suggestions please let me know).

Corrected profiling results

It's official: I'm a dimwit!

The inline versions of the profiling tests I presented last week are wrong. The correct time for the plain inline version is in fact somewhere between a third to half of the OO implementation.

The inlined version was incorrectly using eval calls to test the conditions. The whole speed-up stems from replacing, for example,

>>> eval('a.n > 10', token)

with

>>> a = token['a']
>>> a.n > 10

The reason that I can lose the eval in the inline version is because it works by translating source code from the rule definition to regular Python code, which is then compiled into a function object which is invoked at run-time.

In the OO-version, the test to be performed is bound to the instance of the node and since the activate method is "pre-defined" we need eval in order to execute whatever test is stored in the instance. Most activate methods besically looks like this:

>>> def activate(self, tag, token):
...   if eval(self.test, token):
...     # store in mem and propagate

There might be a way of doing the same sort of "trick" to get rid of the eval in the OO-implementation as well. I'll have to think about that though.

More profiling

Turns out I was right about the error in the current pyRete version. I hand made a Rete network by connecting nodes from the refactored Rete implementation and it turned out to be as fast as (and sometimes faster than) the one based on dictionaries/functions.

Whilst the one based on dicts and functions is in some was easier to handle and deal with it also has some serious drawbacks. First and foremost it saves state at *each* node. This can probably be dealt with but then I'd have to write some boiler-plate code to handle when and when not to store tokens and that was the whole point of the implementation, to reduce the boiler-plate code. Secondly, it can be harder to wrap your head around since you'd have to look at both where the function is defined and where it is called in order to find out the exact behaviour of a node. It's not magic or anything but it may be confusing at first.

Given these two drawbacks of the dicts and functions implementation I decided that I wasn't going to use it. At all... unless I could find a way to perform function inlining and that the inlined version was faster than an optimized OO-Rete network.

So, now I've got no less than six implementations of a small Rete network[1]:
1) the current pyRete implementation (which is quite obviously just plain wrong).
2) the experimental dicts and functions implementation
3) the refactored OO-implementation
4) an optimized version of 3[2]
5) an implementation using function inlining based on 2
6) an optimized version of 5[2]

Here are the results (I've run these about ten times and the numbers below are typical) for 2 to 6 using 4000 facts:

2) took 6.58899998665 s => 79735 facts
3) took 5.98900008202 s => 79735 facts
4) took 5.70799994469 s => 79735 facts
5) took 5.63800001144 s => 79735 facts
6) took 5.52800011635 s => 79735 facts

Inlining apparently speeds up the matching but not with much and I'm not sure it's worth the effort. It would be cool though to generate a large blurb of code and see if it can be optimized by some other program like psyco or possibly one of the bytecodehacks or some such thing. I haven't looked for optimizers but I believe I will have to if I am going to get something out of the inlining implementation.

All in all. This week's been good fun looking at different implementations but it's time to get back to work and make sure that the pyRete code in the subversion repository works as expected.

[1] Here is the Rete network I'm using. Memory nodes are not shown.

#                       TYPE
#                       
#   TOP         ALPHA {--+     TYPE
#                            
#    +--} JOIN {--+    ALPHA {--+
#                      
#           +--} JOIN {--+
#                 
#                  +--} BETA
#                        
#                         +--} PROD

[2] I have removed a few "unneccessary" memory nodes. But since I believe that that sentence can easily be misunderstood I'll try to explain a bit more.
I have, for example removed storage of tokens at nodes which are never "read" in other parts of the network. For example the Beta Node places Tokens directly into the Production Node instead of going via a Beta Memory Node. It is "last" in the network and the Beta Memory would have fed the Production Node. Also, the first AlphaMemory has been converted into a LeftInputAdapter and sends Tokens directly to the second Join instead of going thru a DummyJoin with a DummyTopNode.

Some profiling results

I've made a small test to see how my experimental Rete implementation is performing. I'm using a very simple rule that generates a lot of tokens:

>>> @pyRete.Rule
... def rule(a = Foo, b = Foo):
...   if a.n > 10 and b.n < 20 and a.n > b.n:
...     print a.n, b.n

where Foo is a value object.

I'm comparing against the pyRete version currently in Subversion and the results are not looking good. In fact, they're looking *so* bad, I believe it is because of an error in the pyRete implementation rather than a difference in time for object+ method lookups (which is what I hoped to test).

I'm only timing the assert_fact method calls (and the index loop):

... start = time.time()
... for i in range(size):
...   pyRete.assert_fact(Foo(n=i))
... stop = time.time()

so Rete compilation, parsing and such is not included. Here are the results:

using 50 facts [Foo(0), Foo(1), ..., Foo(49)]
rule: +O+O+A+A+B+P
pyRete implementation took 0.210000038147 s => 735 facts
expRete implementation took 0.0599999427795 s => 735 facts

using 100 facts [Foo(0), Foo(1), ..., Foo(99)]
rule: +O+O+A+A+B+P
pyRete implementation took 0.871000051498 s => 1735 facts
expRete implementation took 0.149999856949 s => 1735 facts

using 200 facts [Foo(0), Foo(1), ..., Foo(199)]
rule: +O+O+A+A+B+P
pyRete implementation took 3.51600003242 s => 3735 facts
expRete implementation took 0.319999933243 s => 3735 facts

using 300 facts [Foo(0), Foo(1), ..., Foo(299)]
rule: +O+O+A+A+B+P
pyRete implementation took 7.84099984169 s => 5735 facts
expRete implementation took 0.481000185013 s => 5735 facts

using 400 facts [Foo(0), Foo(1), ..., Foo(399)]
rule: +O+O+A+A+B+P
pyRete implementation took 14.0199999809 s => 7735 facts
expRete implementation took 0.671000003815 s => 7735 facts

Clearly, something's not right. Going from 300 to 400 fact objects shouldn't take nearly twice as long.

Now, in order to be fair I should also mention that the experimental Rete implementation is hand-made (but it's topology is identical to that pyRete generates) and doesn't include things like callbacks for debugging, compilation, activations and statistics. However, that cannot account for *all* of the extra time, maybe some of it. I don't know.

I will try to make a hand-made, slimmed OO Rete Network tomorrow to see if I can get a fair comparison.

Experimental Rete implementation

Last week I tried a "new" approach for pyRete's Rete implementation. At the moment I'm using a number of objects linked together such that they make up a Directed Acyclic Graph. Which also happens to be the way most other implementations handle it (I think).

Take for example object type tests. In pyRete they are implemented such that the Rule Compiler instantiates an ObjectTypeNode and initializes it with the type to test against. Later on it connects the instance to the "next" nodes in the Rete Network (usually Alpha Nodes). The ObjectTypeNode basically looks like this:

>>> class ObjectTypeNode(Node):
...   def __init__(self, type):
...     self.type = type
...     self.successors = []
...   def activate(self, tag, timestamp, obj):
...     if obj.__class__.__name__ == self.type:
...       for node in self.successors:
...         node.activate(tag, timestamp, obj)

The above is of course grossly simplified, for starters it doesn't have any error checking, but it's enough to convey the general idea.

There are several other types of nodes as well. They all have a list of successors and at least one activation method (Join Nodes have two). When a fact is asserted, it is propagated through the Rete Network via the activation methods of each node.

There are several problems with my current approach and it's no secret that I've been trying to clean up and simplify both the Rete Implementation, the Rule Parser and the Rule Compiler. However, a simple, efficient implementation using an object-based DAG have so far eluded me. So last week I tried to use functions (instead of objects) together with a hash table to provide, among other things, storage (it replaces the memory node objects).

So far, I've only got some very simple tests working but the code is smaller, cleaner and faster. The ObjectTypeNode above is replaced by:

>>> class Rete(dict):
...   def __init__(self):
...     self["OBJ"] = {}
...   def make_object_type_node(self, var, value):
...     key = (var, '__class__.__name__', value)
...     def activate(tag, o):
...       if getattr(getattr(o, '__class__'), '__name__') == value:
...         token = Token()
...         token[var] = o
...         if tag == '+':
...           self["MEM"][key].append(token)
...         elif tag == '-':
...           self["MEM"][key].remove(token)
...         self.propagate(tag, token, key)
...     self["OBJ"][key] = activate
...     self["MEM"][key] = []
...     self["NEXT"][key] = []
...     return key

What happens here is that the Rule Compiler calls the make_object_type_node instead of instantiating an object. The method calculates a unique key, defines the activate function and registers it in the common hash table. It also registers two empty lists which are used as output memory ("MEM") and as a list of succesor nodes ("NEXT").

The object type test is performed within the activate method and uses a common propagate method, which looks like this:

>>> def propagate(self, tag, obj, key):
...   [self[dictionary][_key](tag, obj) for _key, dictionary in self["NEXT"][key]]

One of the *really* good things with it is that those two lines can be used for all types of nodes. The Rule Compiler only needs to register which dictionary the next node is found in (usually "ALPHA" for Object type tests) and which key it has.

One of the bad things with this approach is that all of the function calls are nested so it might not work too great for large Rete Networks.

The idea was actually to generate one function that would have *all* tests (for one rule) laid out as a procedural function which would update a common (to all rules) storage of some sort. I'm not 100% sure of what it would look like and since Python doesn't have macros I can't really do it either so this will do for now.

Once I get the more complicated things working (Not Nodes) I'll let you know if it's better or worse than my current implementation.

Node sharing in the Rete network

Joe asked about beta node sharing on the Ruleby mailing list a couple of days ago. Whilst I answered Joe's question, Peter managed to tell him what he wanted to know. He described, with a short example, how node sharing is done in the beta network. When I read his description I couldn't help but to think about how I've read a paper about different strategies for sharing nodes in a Rete network. However, I can't remember which paper it is.

It is quite possible that I dreamed the whole thing or that I've misinterpreted a paper describing something related (or possibly even something completely different ;-). I've re-read the relevant sections of all Rete papers I've got and I've checked the source codes of a number of Rete implementations and I've found nothing. They all do (more or less) the same thing.

[2007-07-05] Update: Turns out I'm not very crazy, the paper I was thinking about is An Optimization Algorithm for Production Systems by Toru Ishida. However, I think I may have misinterpreted it since I've only had time to skim through it and it appears that he mostly concentrates on topology transformation which I guess is more or less equivalent to re-ordering the conditional elements of a rule. It has little or nothing to do with manipulating the actual sharing of nodes from a rule compiler's perspective.

The following CLIPS rules and their compilation messages should come as no surprise to those familiar with Rete.

(defrule A
  (foo ?foo ?bar)
  (bar ?bar ?baz)
  (baz ?baz ?qux)
  (qux BLAH)
 => )

Compilation output is, as expected:

+j+j+j+j

If we define another rule

(defrule B
  (foo ?foo ?bar)
  (bar ?bar ?baz)
  (baz ?baz ?qux)
  (qux BLECH)
 => )

most of the nodes are shared:

=j=j=j+j

If we define a third rule, with the exact same conditional elements but put the last element first instead

(defrule C
  (qux BLABLAH)
  (foo ?foo ?bar)
  (bar ?bar ?baz)
  (baz ?baz ?qux)
 => )

NO nodes are shared

+j+j+j+j

This is one of the gotchas with Rete-based engines. The rule author needs to know how the engine compiles the Rete network so that he/she won't write rules that create an unneccessary large network. But considering that database vendors seems to have come quite far with techniques for optimizing SQL query statements (regardless of how clumsily the author has written them) I'm guessing "something" could be done for Rete implementations as well.

I can think of ways to compile the network to maximize sharing but that would require storing additional information in tokens which won't be very good because it will probably eat more memory than those extra nodes shared anyway.

Does anyone know if someone has tried to experiment with different techniques for sharing nodes? Or is this issue "solved" already in the sense that it cannot be fixed and current sharing techniques are as good as it gets?

Rete or Not?

This is probably old stuff to most people but I only found InRule yesterday when I was checking to see if my del.icio.us subscriptions had anything interesting for me to read about. Anyway, on InRule's web site they have a paper titled Rete or Not?

The paper is an attempt to convince us that InRule's engine is better than Rete-based engines. AFAICT the reason is because InRule's engine can handle multiple modes for rule execution. But the paper is mostly about why Rete's no good anyway. Among other things, it says, "...users must understand how a Rete engine works before effectively writing rules" and, my favourite statement, "Roughly 20% of business applications have a need for Rete".

There are quite a few things in the paper that conflicts with my view of how the Rete Algorithm works and in general how a Rete-based rule engine works and what can and cannot be done with one. For example, the description of partial "left" and "right" matches doesn't make any sense.

To me, the Rete Algorithm is a solution to the many patterns/many facts matching problem. It's not the only solution and it might not even be the best solution but the claims they make in the paper are just too much.

I find it hard to take it seriously since they don't say which engine they're comparing against, come to think of it, they don't even say how the InRule engine works. Apart from saying that they have an execution mode that is similar to Rete and some other modes which work sequentially there's NO information about what's going on.

If they really want to convince people they have a better engine; why not run some benchmarks?

[2007-06-25] Update: Well, apparently: "InRule will benchmark using your performance needs, with real-life application and capacity scenarios. We recognize that every client environment is unique, and do not believe in making idle claims based on questionable proprietary benchmarks. We will demonstrate and substantiate actual performance metrics."

What about questionable (all benchmarks are) non-proprietary ones? It seems they don't do those either. What the **** does benchmark using your performance needs mean anyway? And, just so you know. I'm not kidding or making this up or anything! That's what they say on their web site. Right here (under Performance).

I'm adding the label humour to these posts. This is too much. It's gotta be a joke.

Another paper to read

Last week, I found Jeremy Wertheimer's master thesis from MIT; Derivation of an efficient rule system pattern matcher. It seems very interesting. He derives a Rete implementation using program transformations (in the programming language Refine which seems to be some Lisp dialect or other). Apparently he starts out with a small formal specification of Rete and applies transformations to it step by step in order to derive an efficient pattern matcher. Very cool.

Ruleby's matching algorithm

I've been looking at Ruleby these last few days and especially how the Miss Manners benchmark executes.

I find Ruleby particularly interesting because Ruby and Python are somewhat similar and I'm hoping to get some good ideas for my pyRete implementation. I haven't got pyRete into the state where it's ready to run Miss Manners yet and I'm trying to figure out how much more I need to do. I'm really hoping that this little detour into Ruby-land will prove fruitful.

Anyway, the matching in Ruleby seems to e working a bit differently than I expected. I'm hoping that Joe or Matt can explain what's happening. Below is part of a call trace of Miss Manners with 4 guests:

--#RootNode:01.assert_fact [Fact |8|[Guest name=n4, sex=m, hobbies=h1]]
--#ObjectNode:02.assert [Fact |8|[Guest name=n4, sex=m, hobbies=h1]]
--#ObjectNode:02.build_results
--#ObjectNode:02.resolve #MatchResult(f)(24308940)()#MatchResult(24308870)(guest=[Guest name=n4, sex=m, hobbies=h1]/24355540, )
--#ObjectNode:02.propagate_assert #MatchResult(24308610)(guest=[Guest name=n4, sex=m, hobbies=h1]/24355540, )[Fact |8|[Guest name=n4, sex=m, hobbies=h1]]
--#JoinNode:02.assert #ObjectNode:02#MatchResult(24308610)(guest=[Guest name=n4, sex=m, hobbies=h1]/24355540, )[Fact |8|[Guest name=n4, sex=m, hobbies=h1]]
--#JoinNode:02.filter_match_results #MatchResult(24308610)(guest=[Guest name=n4, sex=m, hobbies=h1]/24355540, )
--#RootNode:01.check_references #ObjectNode:02
--#ObjectNode:07.assert [Fact |8|[Guest name=n4, sex=m, hobbies=h1]]
--#ObjectNode:07.build_results
--#ObjectNode:07.resolve #MatchResult(f)(24306540)()#MatchResult(24306470)(rg=[Guest name=n4, sex=m, hobbies=h1]/24355540, )
--#ObjectNode:08.assert [Fact |8|[Guest name=n4, sex=m, hobbies=h1]]
--#ObjectNode:08.build_results
--#ObjectNode:08.resolve #MatchResult(f)(24305450)()#MatchResult(24305380)(lg=[Guest name=n4, sex=m, hobbies=h1]/24355540, )
--#ObjectNode:08.build_results
--#ObjectNode:08.resolve #MatchResult(24305120)(lg=[Guest name=n4, sex=m, hobbies=h1]/24355540, )#MatchResult(24305190)(leftGuestName=n4/24355540, )

--#RootNode:01.assert_fact [Fact |9|[LastSeat seat=4]]
--#ObjectNode:15.assert [Fact |9|[LastSeat seat=4]]
--#ObjectNode:15.build_results
--#ObjectNode:15.resolve #MatchResult(f)(24303590)()#MatchResult(24303520)(ls=[LastSeat seat=4]/24355530, )
--#ObjectNode:15.build_results
--#ObjectNode:15.resolve #MatchResult(24303260)(ls=[LastSeat seat=4]/24355530, )#MatchResult(24303330)(lastSeat=4/24355530, )
--#ObjectNode:15.propagate_assert #MatchResult(24302480)(ls=[LastSeat seat=4]/24355530, lastSeat=4/24355530, )[Fact |9|[LastSeat seat=4]]
--#JoinNode:14.assert #ObjectNode:15#MatchResult(24302480)(ls=[LastSeat seat=4]/24355530, lastSeat=4/24355530, )[Fact |9|[LastSeat seat=4]]
--#JoinNode:14.filter_match_results #MatchResult(24302480)(ls=[LastSeat seat=4]/24355530, lastSeat=4/24355530, )
--#RootNode:01.check_references #ObjectNode:15
--#RootNode:01.compare_node_to_wm #ObjectNode:16
--#ObjectNode:16.assert [Fact |0|[Guest name=n1, sex=f, hobbies=h3]]
--#ObjectNode:16.assert [Fact |1|[Guest name=n1, sex=f, hobbies=h1]]
--#ObjectNode:16.assert [Fact |2|[Guest name=n1, sex=f, hobbies=h2]]
--#ObjectNode:16.assert [Fact |3|[Guest name=n2, sex=f, hobbies=h3]]
--#ObjectNode:16.assert [Fact |4|[Guest name=n2, sex=f, hobbies=h2]]
--#ObjectNode:16.assert [Fact |5|[Guest name=n3, sex=m, hobbies=h1]]
--#ObjectNode:16.assert [Fact |6|[Guest name=n3, sex=m, hobbies=h3]]
--#ObjectNode:16.assert [Fact |7|[Guest name=n4, sex=m, hobbies=h2]]
--#ObjectNode:16.assert [Fact |8|[Guest name=n4, sex=m, hobbies=h1]]
--#ObjectNode:16.assert [Fact |9|[LastSeat seat=4]]

I've rewritten the Object References from the trace in order to distinguish them easier.

The blue line is where the last guest data is asserted. It propagates into three different ObjectNodes so there's probably no sharing between rules. But why is the same fact asserted again (into ObjectNode:16) when the LastSeat fact is asserted?

It seems Peter was right about the matching and this might well be the reason Ruleby gets such weird performance on Miss Manners. Unfortunately I don't know enough Ruby to re-write the implementation but I really hope that Joe and/or Matt will be able to.

I'll stop this dissecting of their engine now and start working on pyRete again.

Another look at Ruleby and Ms Manners

I ran Miss Manners with 4, 8, 16 and 32 guests through ruby-prof earlier today. I also merged the output line-wise for each of the runs and added two metrics I thought might help track down the weird behaviour of Miss Manners.

Ruby-prof tracks the number of calls (as calls) and I added the number of calls / the number of calls in the "previous" (rel/prv) run and in the "first" (rel/frst) run. Where the "previous" means 16 for 32, 8 for 16 and 4 for 8 guests. 4 is also the "first", it's factor is always 1.

Here's a selection of the output[1], woolfel style:

|Guests  time (sec)
|    4:   0.942000150680542
|    8:   5.41799998283386
|   16:   102.727999925613
|   32:   3797.01999998093
|
|Guests rel/prv rel/frst    calls  name
|    4:  01.00  00001.00     2880  Ruleby::Core::Node#resolve
|    8:  15.85  00015.85    45650  Ruleby::Core::Node#resolve
|   16:  35.76  00566.79  1632363  Ruleby::Core::Node#resolve
|   32:  42.99  24365.68 70173154  Ruleby::Core::Node#resolve
|
|    4:  01.00  00001.00    16371  Ruleby::Core::MatchResult#==
|    8:  17.15  00017.15   280747  Ruleby::Core::MatchResult#==
|   16:  29.28  00502.21  8221607  Ruleby::Core::MatchResult#==
|   32:  46.92  23563.22 385753525  Ruleby::Core::MatchResult#==
|
|    4:  01.00  00001.00      324  Ruleby::Core::Activation#==
|    8:  23.05  00023.05     7468  Ruleby::Core::Activation#==
|   16:  43.85  01010.79   327496  Ruleby::Core::Activation#==
|   32:  35.75  36139.05 11709052  Ruleby::Core::Activation#==
|
|    4:  01.00  00001.00       44  Ruleby::Core::Activation#<=>
|    8:  11.86  00011.86      522  Ruleby::Core::Activation#<=>
|   16:  17.04  00202.18     8896  Ruleby::Core::Activation#<=>
|   32:  12.36  02499.43   109975  Ruleby::Core::Activation#<=>
|
|    4:  01.00  00001.00      162  Ruleby::Core::Action#==
|    8:  23.05  00023.05     3734  Ruleby::Core::Action#==
|   16:  43.85  01010.79   163748  Ruleby::Core::Action#==
|   32:  35.75  36139.05  5854526  Ruleby::Core::Action#==

There are a few other places worth mentioning as well but they're all effects rather than causes (Hash#==, Array#empty? etc).

I haven't studied these "spots" of the source code in detail yet. I still think that fixing the engine.match method is the way to go, it seems to be doing a lot of extra work. Peter left a comment saying it might be because of how matching is performed in the Rete network. I agree with him that it looks suspicious but I really can't tell. At least not yet, I'll look at it during the weekend though.

[1] I wrote a python script to calculate the extra metrics and to merge the four output files. If you want it, send me an e-mail.

[2007-05-13] Update: I'm starting to believe that Peter's right about the matching. From what I've seen and read in the comments I'd say that Ruleby is performing a lot more work during matching than they need to. I get the feeling that they're not storing as many partial matches as they can and therefore they need to recalculate a lot of things (compare_to_wm and check_references) when a fact filters through the network.

A closer look at Ruleby and Ms Manners

I've spent some time trying to understand the inner workings of Ruleby and in particular what happens when Ms Manners is run. On the Benchmarks page, they've written:

For Ruleby, this benchmark ran well for 16 guests. However, as the number of guests increases to 32 and 64, the relative performance of the benchmark drops off. This is due to a hack/bug in the implementation of the Rete algorithm. This problem is described on the Open Issues page under the heading ‘Iterating over Working Memory.’

But, I can't really understand the issue described on the Open Issues page. And I'm not sure that it's related to why Ms Manners' performance degrades when adding more guests. I have skimmed the code previously and I noticed that the match method is recursive and I'm guessing that's most likely where the problem is.

If we open up engine.rb and look at the Engine class' match method it looks like this. The comments are mine.

| def match(agenda=@root.match, used_agenda=[], activation_counter=0)
|   agenda = @conflict_resolver.resolve agenda
|   if(agenda && agenda.length > 0)          
|     activation = agenda.pop
|     used_agenda.push activation
|     activation.fire self
|
|     new_agenda = @root.match # <-- Conflict Set?!
|
|     # HACK the following is a workaround.  This problem would best be
|     # solved by working this into the nodes themselves.    
|     new_agenda.each do |a|
|       used = false
|       used_agenda.each do |used_activation|
|         used = true if used_activation.object_id == a.object_id
|       end
|  
|       # BUG we are comparing against the current agenda, but we may need to
|       # compare against all activations that have existed...
|       if (agenda.index(a) == nil) && (!used)
|         a.counter = activation_counter+1
|         agenda.push a
|       end
|     end   
|     agenda.delete_if {|a| new_agenda.index(a) == nil}
|
|     match(agenda, used_agenda, activation_counter+1) # <-- This is what
|                                                      #     slows it down!
|   end
| end

Also, if you look at the memory usage during execution you'll notice that it climbs steadily until the program exits. All those Activations are kept in memory until the method exits, even though they'll never be used and most of them are duplicates anyway.

Unfortunately I have no patch to submit for this issue but I'm sure Joe and Matt won't find it too hard to fix. But it will probably require some re-thinking of the current engine.match design.

[2007-05-10] Update: It turns out I was as wrong as I could be. Joe rewrote the engine.match method in a non-recursive way and it made NO difference at all. Bummer! But, only slightly annoyed I'm going to continue looking for why Manners behaves as it does. Even though I'm probably not the best man for the job I doubt I'll ever get a better opportunity to finally learn some Ruby.

Ruleby - a Ruby Rule Engine

I just found the Ruleby project and I think it looks real promising.

Ruleby is a rule engine written in the Ruby language. It is a system for executing a set of IF-THEN statements known as production rules. These rules are matched to objects using the forward chaining Rete algorithm.

The code isn't available as I'm writing this but that appears to be a configuration problem rather than a strategy. I don't quite understand what they're saying on their benchmarks and open issues pages because I have a problem relating it to my understanding of how the Rete algorithm works. I'm sure it will all become clear once I can access the source code.

I really thought that Michael Neale's effort Ruby Rules would be the first pure-Ruby implementation of the Rete algorithm but unfortunately development seems to have slowed down.

Another Wikipedia update ...

Charles has, again, updated the entry on the Rete Algorithm over at wikipedia.

I haven't had the time read through it yet, but it looks impressive. I think it's tripled (at least) in length and has a lot more details in the description of various parts of the algorithm. It ought to last the whole commute home tonight ;-)

Dissecting Rete - Intra-element condition tests in Rete/UL

The last few days have seen some debate about Rete and Rete/UL in particular. It's all Charles fault, he started it when he updated Wikipedias entry on the Rete Algorithm ;-)

You'll find the meat of it over at Peter's blog, in particular here. Peter goes on to analyse the Rete/UL approach in his entry on Limitations of EAV WME and then later on in the entry Exhaustive lookup.

I've already commented about the need for extra Joins in Rete/UL so I won't say anything about that here. However, the question of intra-element conditions remains.

Unfortunately Doorenbos is very vague in his description of intra-element conditions. In fact, he says next to nothing about them. Which has led me to believe that they aren't performed at all. The same end-result can be produced anyway, only, it requires a lot more join operations and more space (to store unneccessary tokens).

Let's look at one of the examples, this one is used in several places:

(find-stack-of-two-blocks-to-the-left-of-a-red-block
  ([x] ^on [y])      /* C1 */
  ([y] ^left-of [z]) /* C2 */
  ([z] ^color red)   /* C3 */
 -->
  ... RHS ... )

the Rete Network shown in Figure 2.2(b) on page 10 corresponds to this production. In the same illustration he shows how the 9 WMEs can be combined into a set of 3 WMEs that satisfy the LHS. What would happen if we change the production to:

(find-stack-of-two-blocks-to-the-left-of-a-red-block
  ([x] ^on [y])      /* C1 */
  ([y] ^left-of [z]) /* C2 */
  ([z] ^color red)   /* C3 */
  ([z] ^size medium) /* C4 */
 -->
  ... RHS ... )

let's also add 3 other WMEs:

w10 (B1 ^size large)
w11 (B2 ^size medium)
w12 (B3 ^size medium)

This would create another Beta Memory (matches for C1^C2^C3), a Join Node (join on values of [Z]) and an Alpha Memory (AM for C4).

In Forgy's description of Rete, C3 and C4 also represent an intra-element condition. To test it you would normally hook the constant tests together and only let WMEs proceed to the Alpha Memory if both tests evaluate to True.

In Rete/UL, things work a little differently. Alpha Nodes and Memories map one-to-one with conditions. This means, among other things, that the Alpha Memory for C4 will contain w11 and w12 even though w6 never made it to the Alpha Memory for C3 (since both w6 and w11 have id = B2 we "know" that w11 can never be used to construct a matching token but the Rete Network won't be able to "know" that until the join).

The Production Node will still have one token that matches all of the tests in the network (w1^w5^w9^w12). But what if we modify w12 to

w12 (B3 ^size large)

The Alpha Memory C4 will now only contain w11 and the last join (with w1^w5^w9) will fail. No token will be sent to the Production Node but most of the Alpha and Beta Memories remain unchanged (this is where the extra space requirement shows up).

In the example above there's only one intra-element condition. If we would have had five of them instead, and WMEs that passed four of the constant tests, we would have to perform four joins before we can conclude that none of the WMEs can be used to trigger the RHS.

Using intra-element conditions as Forgy describes reduces the number of tokens to store and therefore the number of joins to try. We would still have to test four times (in Alpha Nodes) before we can throw away the WMEs but constant tests are cheaper than joins so this will most probably have an effect on performance. How much of an effect? I have no idea. It would be interesting to test though.

All of this leads me to believe that Rete/UL is not meant to be used as a general purpose "object" based production system but that it rather works with little bits and pieces (as described in the paper) of facts. Trying to use it as if it was JBoss Rules or Jess will of course not give the best effect but if that's not what it was built for...

It's a pity that Doorenbos doesn't compare and contrast the Rete/UL implementation with the one that Forgy describes in his 1979 thesis, and in particular the effect it has on performance (in both space and time).

About the Rule Compiler

I've managed to get the pyRete Rule Compiler to generate a directed (acyclic) graph which, at least, resembles a Rete Network. There are still some situations it can't handle, but it works quite well in most situations.

>>> import pyRete
>>> class Foo(pyRete.Fact):
...   def __init__(self, n):
...     self.n = n

>>> @pyRete.Rule
... def rule1(foo = Foo):
...   if foo.n == 1:
...     pass

>>> @pyRete.Rule
... def rule2(foo1 = Foo, foo2 = Foo):
...   if foo1.n > 0 and foo2.n > 1 and foo1.n > foo2.n:
...     pass

>>> ruleengine = pyRete.RuleEngine(None)
>>> ruleengine.addRules([rule1, rule2])
+O+A+P
=O=O+A+A+B+P

>>> ruleengine.showReteNetwork()

The last line pops up the wxWidgets Rete Network Viewer which looks like this:



Rule2 is the left branch, rule1 is the right branch in this graph. The red node is an ObjectTypeNode, the yellow ones are Alpha Nodes, the green/yellow ones are Alpha Memories, the grey ones are LeftInputAdapters, the blue one is a Beta Node, the darker blue is a Beta Memory and the white ones are Production Nodes.

There are a few things that doesn't look good. For example, the Beta Memory shouldn't be there in rule2 and the LeftInputAdapter shouldn't be there in rule1 but I'm getting closer and closer...

More stuff to read.

For some time now, I've been looking for a place to buy the article Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match, Artificial Intelligence, 19, pp 17-37, 1982.

So far, I haven't found one. I can find the article citation over at ACM but there's no way for me to purchase it (I'm not a member). Today it dawned on me that I might find Forgy's PhD thesis instead and ... I did.

Why, why, why didn't I think of that before!?

Anyway. If you know of a place where I can buy a printed or electronic copy of the 1982 AI article, please let me know.

[2006-10-13] Ok, finally I got my hands on both papers (thanks Charles and Peter). I haven't read the article more than once and the thesis (chapter 2) only twice. But so far, IMHO, the article is nowhere near as good as the thesis.

Constructing a Rete Network.

I've got my ObjectTypeNodes, my AlphaNodes, my BetaNodes, my AlphaMemories, my BetaMemories and my ProductionNodes. Everything is set, I'm all ready to start constructing the Rete Network.

Most of my test-rules provide little or no problem at all. I hook up a chain of AlphaNodes after an ObjectTypeNode and end it all with an AlphaMemory. If it's the "first" AlphaMemory for this Rule I also make a LeftInputAdapterNode. Then I hook up the "first" BetaNode's leftInput to the LeftInputAdapter and the rightInput to the AlphaMemory that holds the second variable's type and so on and so on until there's no more BetaNodes left and I add on the ProductionNode.

In cases like that there's no problem. This is also the "classic" portrait of what a Rete Network looks like. Almost every example I've seen has had this "look", but what if there's no condition in the rule that requires joining? Say that we'd write a rule like this:

>>> import pyRete
>>> @pyRete.Rule
... def foo(a = Type1, b = Type2):
...   if a.n == 1 and b.n == 2:
...     print "Score!"

sure, it's stupid. But never mind that.

At the moment, pyRete makes two ObjectTypeNodes, two AlphaNodes and a ProductionNode. But there's no way to trigger the Action because the Rete Network "stops" at the AlphaMemories. So now I have to decide, do I perform a dummy join in the ProductionNode or do I set up a dummy BetaNode that feeds the ProductionNode? Also, are there more situations like this? Looks like I'm spending this week going through some source code to check out how Drools and Sumatra handles this situation.

BTW. Charles Young updated Wikipedia this week with more details on the Rete Algorithm. I likes.