2007-01-21

The RuleCompiler and Network Topology

Working on the RuleCompiler has raised a lot of questions. Trying to implement the Rete Algorithm has taught me a lot of things and it is very interesting indeed. Reading Doorenbos' or Forgy's thesis gives a rather broad and general overview of the algorithm but there are several things that are not discussed, at least not extensively. One of those things are network topology.

Consider the following (as always, rather silly rule):

>>> @pyRete.Rule
... def foo(a=int, b=int, c=int, d=int):
... if a==b and c==d:
... pass
In the above mentioned papers all BetaNodes (tests involving 2 variables) are chained together. If the BetaNodes' variables overlap, there's no problem (these are the only types of examples given). They'll more or less automatically be connected because one of the input's for the second BetaNode will have to be taken from the first node's BetaMemory.

But, in the rule above, tokens taken from the first node's BetaMemory won't contain either of the variables c or d. I can think of (at least) two ways to compile the Rete Network for the above Rule. I can't say if one is "better" than the other, they contain roughly the same amount of nodes and will probably perform similarly (I haven't tested), but I've chosen topology #2 for pyRete.

This screen dump shows Topology #1:



There are 4 ObjectTypeNodes (red) and 4 AlphaMemories (yellow/greenish) because there's no sharing at all, remember? However, there are 2 LeftInputAdapters (gray) that each feed into a BetaNode (blue). The BetaMemories (darkblue) are joined in a "dummy join" (blue) that feeds into the last BetaMemory that feeds the ProductionNode (white).

The dummy join's job is to extend the incoming left token with the variables and bindings from the incoming right token. There's no test being performed, it basically just performs "token" addition:

{ 'a': n, 'b': n, } + { 'c': n, 'd': n, } = { 'a': n, 'b': n, 'c': n, 'd': n, }

and passes it on to the next Node.

Here's Topology #2



Here, as well, are 4 ObjectTypeNodes and 4 AlphaMemories. There's only 1 LeftInputAdapter though. It feeds into a BetaNode, which, via a BetaMemory, feeds a "dummy join" that feeds into the last BetaNode. The last BetaNode's Memory feeds the ProductionNode.

The dummy join's task here is the same as in #1. It's just a way to make sure that the last BetaNode is fed tokens containing the left input's variables and bindings.

The reason I chose Topology #2 is based on gut-feeling and "looks" and not because I can point you to a page and paragraph in Forgy's thesis saying "that's why!", so if you know it's wrong (or right) please leave a comment.

[Update 2007-01-23]
It turns out that the run-time properties of the two Topologies were not the same, as I previously thought. My implementation of the JoinNode has turned out to be wrong. What happens is that the JoinNode propagates Tokens even though the left input is empty which means that Tokens with only 2 variables/bindings end up in the ProductionNode. Very irritating, but fixed now.

7 kommentarer:

woolfel sa...

Most of the papers on RETE don't explain this too well. If I'm reading the rule correctly:

a == b is the first join
c == d is the second join

There should be 2 join nodes. The first joins a == b. It propogates to the second join node with tests c == d. Generally speaking, it's better to have fewer join nodes. more join nodes leads to more memory consumption and impacts performance.

hope that helps

Johan Lindberg sa...

Thanks for the comment Peter and, yes, your reading of the rule is correct.

But the question is how to join the two joins?

a==b and c==d are both implemented as BetaNodes with BetaMemories. One of the BetaMemories will hold Tokens with variables "a" and "b" and the other with "c" and "d" but the ProductionNode will have to have Tokens with all four variables. Therefore, I'll have to join them somehow...

It's very similar to what I described in a previous post about DummyJoins [http://commentsarelies.blogspot.com/2006/10/constructing-rete-network.html]

woolfel sa...

It sounds like you create tokens for the bindings and propogate those down the RETE network. Is that a correct interpretation?

are a, b, c, d objects? or are they just bound variables? It's been a long time since I've played with python and aren't familiar with the syntax.

Johan Lindberg sa...

Yes, that is a correct interpretation.

A Token includes variable names AND values. They are actually Python dictionaries (similar to Java's HashTable).

The Token that ends up in the ProductionNode when I assert the number 1 is:

{ 'a': 1, 'b': 1, 'c': 1, 'd': 1, }

Here, a, b, c and d (keys) are actually string representations of the Rule's variables pointing to their bound objects (values).

The reason I do it this way is because all tests in pyRete are executed in a separate and "closed" context (using eval). I "inject" the Token into the context and automatically all key/value pairs in it become variables bound to objects/values which are available to the expression evaluated.

It's a simple model and it requires very little code to setup and execute. There are some problems of course but I want to work out the other parts of the implementation before I start optimizing this.

woolfel sa...

Now that I think I understand how it works, I would do it this way.

there's 4 bound variables.

the left-input-adapter passes the first variable a down the left side of the first join. the input node for B would pass the bound variable directly to the first join. I would skip the alphaNode, since I don't see a literal constraint in the rule.

the first join pass the bound variable for a and b to the next join. This next joinNode doesn't perform a join. In jamocha i call it ZJBetaNode. So the second join just propogates a, b and c to the third join node, which joins c and d.

the final node is the terminal node. Hope that helps. My first comment was wrong, since I misread the rule :( Silly me, I should have read it more carefully.

peter

Johan Lindberg sa...

Great! That's actually, more or less, exactly what happens. Before you told me about the ZJBetaNode in Sumatra I couldn't figure out what to do in these situations. As you know, the Rete-papers are a bit fuzzy in some areas. Now I'm just worried I might be over-using it.

woolfel sa...

that's how most engines handle it. it's what happens when the joins are compiled to produce sequential joins. I actually optimized the joins with zero evaluation to just propogate.