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.